高增亮 劉皓若 王霞

摘 要：針對(duì)工業(yè)危化品物流配送成本高昂、風(fēng)險(xiǎn)性大的特點(diǎn)，本研究基于物聯(lián)網(wǎng)，提出一套?；冯娮游锪髋渌吐窂揭?guī)劃與監(jiān)控系統(tǒng)，以提高危化品的運(yùn)輸效率，進(jìn)而減小?；愤\(yùn)輸?shù)某杀竞惋L(fēng)險(xiǎn)。首先，本研究根據(jù)系統(tǒng)的主要工作和目的，對(duì)系統(tǒng)整體架構(gòu)進(jìn)行了設(shè)計(jì)。然后結(jié)合工業(yè)?；返呐渌吞攸c(diǎn)，提出MODVRP模型和預(yù)優(yōu)化、實(shí)時(shí)優(yōu)化兩階段求解策略。最后，通過實(shí)驗(yàn)驗(yàn)證了研究提出的模型和算法。實(shí)驗(yàn)結(jié)果表明，本研究提出的模型和算法可有效解決多目標(biāo)動(dòng)態(tài)路徑優(yōu)化問題，大大降低了運(yùn)輸成本和風(fēng)險(xiǎn)。

關(guān)鍵詞：物聯(lián)網(wǎng);電子物流配送;路徑規(guī)劃;MODVRP

中圖分類號(hào)：TN929.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1001-5922（2021）08-0166-04

Path Planning of Electronic Logistics Distribution of Industrial Hazardous Chemicals under the Background of Internet of Things

Gao Zengliang， Liu Haoruo， Wang Xia

（Industrial Internet Innovation Center （Shanghai） Co.， Ltd.， Shanghai 201306， China）

Abstract：In view of the characteristics of high cost and high risk of industrial hazardous chemicals logistics distribution， based on the Internet of things， this study proposes a set of hazardous chemicals electronic logistics distribution path planning and monitoring system， in order to improve the transportation efficiency of hazardous chemicals， and then reduce the cost and risk of hazardous chemicals transportation. First of all， according to the main work and purpose of the system， the overall architecture of the system is designed. Then， combined with the distribution characteristics of industrial hazardous chemicals， the MODVRP model and a two-stage solution strategy of pre-optimization and real-time optimization were proposed. Finally， the proposed model and algorithm are verified by experiments. The experimental results show that the model and algorithm proposed in this study can effectively solve the multi-objective dynamic path optimization problem， and greatly reduce the transportation costs and risks.

Key words：Internet of things; electronic logistics distribution; path planning; MODVRP

隨著我國(guó)化工業(yè)的發(fā)展，?；返姆N類和運(yùn)輸量在不斷上升。由于危化品具有易燃、易爆、腐蝕等特性，因此在運(yùn)輸環(huán)節(jié)往往具有高成本和高風(fēng)險(xiǎn)性。在此情況下，物流企業(yè)如何掌控?；返呐渌腿^程，降低配送的風(fēng)險(xiǎn)和成本，是物流企業(yè)亟需解決的問題。目前，常見的工業(yè)危化品物流配送路徑規(guī)劃與監(jiān)控系統(tǒng)對(duì)動(dòng)態(tài)信息的處理能力較弱，無法滿足?；愤\(yùn)輸對(duì)實(shí)時(shí)性的要求。因此，本研究在采用物聯(lián)網(wǎng)對(duì)車輛數(shù)據(jù)進(jìn)行采集的前提下，提出提出?；冯娮游锪髋渌吐窂絻?yōu)化目標(biāo)函數(shù)，并通過MODVRP對(duì)模型進(jìn)行求解，以此達(dá)到時(shí)間、成本和滿意度最優(yōu)。

1 目標(biāo)函數(shù)

在現(xiàn)代物流配送過程中，成本、旅行時(shí)間、客戶滿意度是影響企業(yè)利益的和對(duì)車輛路徑規(guī)劃的主要因素[3]。因此本研究在尋求危化品車輛物流配送最優(yōu)路徑時(shí)，以這3個(gè)對(duì)象作為模型的目標(biāo)函數(shù)。

1.1 問題編碼

問題編碼包括車場(chǎng)編碼、客戶、道路編碼[4]。其中，車場(chǎng)包括配送中心和第三方機(jī)構(gòu)。設(shè)配送中心為m（m=N+1，N+2，…N+M），負(fù)責(zé)給N個(gè)不同地理位置的客戶送貨，每個(gè)配送中心有Rm輛車，每輛車的最大載量為Qkm（k=1，2，…Rm），發(fā)車成本為Fkm;第三方機(jī)構(gòu)為h（h=N+M+1，…N+M+H），每個(gè)機(jī)構(gòu)有Rh輛車，每輛車的最大載量為Qkh，租賃成本為Zhk?？蛻鬷（i=1，2，...，N），客戶需求量為Qi，每個(gè)客戶的服務(wù)時(shí)間窗為[Ei，Li]，開始服務(wù)時(shí)間為ti，客戶在ti時(shí)間的滿意度可表示為：

道路編碼即對(duì)用戶i到j(luò)的距離dij進(jìn)行編碼。設(shè)每段路上配送中心車k的初始車速為，道路影響車速的時(shí)間為，對(duì)車輛的影響系數(shù)為。

1.2 目標(biāo)函數(shù)構(gòu)建

定義決策變量為：

以成本、時(shí)間和客戶滿意度作為優(yōu)化目標(biāo)，得到目標(biāo)函數(shù)為：

式中，f1，f2，f3分別表示成本目標(biāo)、旅行時(shí)間目標(biāo)、客戶滿意度目標(biāo)。

2 目標(biāo)函數(shù)求解

對(duì)目標(biāo)函數(shù)的求解分為預(yù)優(yōu)化和實(shí)時(shí)優(yōu)化兩個(gè)階段，整體求解流程如下圖1所示。在求解過程中，采用預(yù)優(yōu)化和實(shí)時(shí)優(yōu)化的方式進(jìn)行求解[5]。預(yù)優(yōu)化階段是根據(jù)用戶需求和相關(guān)參數(shù)建立MODVRP模型產(chǎn)生預(yù)優(yōu)化路徑。同時(shí)考慮到MODVRP具有動(dòng)態(tài)性，采用局部?jī)?yōu)化用于實(shí)時(shí)優(yōu)化階段的路線調(diào)整。

2.1 預(yù)優(yōu)化階段

引入Pareto最優(yōu)解求解預(yù)優(yōu)化階段的最優(yōu)解，然后應(yīng)用自適應(yīng)網(wǎng)格技術(shù)進(jìn)一步求得pareto最優(yōu)解。算法具體流程如下：①采用整數(shù)編碼的方式對(duì)問題編碼，并初始化粒子群設(shè)置每個(gè)粒子的初始位置、速度以及個(gè)體的最優(yōu)解和全局最優(yōu)解;②選取距離用戶最近的車場(chǎng)中載重量最大的車輛進(jìn)行配送，計(jì)算各個(gè)粒子的目標(biāo)向量值;③應(yīng)用遞歸法建立非劣解集Ndset，并從中選取個(gè)體最優(yōu)解bestPi和全局最優(yōu)解bestG;④更新粒子狀態(tài)得到新種群，應(yīng)用自適應(yīng)網(wǎng)格技術(shù)求得Ndset。⑤若滿足終止條件，則停止算法;若不滿足終止條件，則重復(fù)步驟③④⑤。

2.2 實(shí)時(shí)優(yōu)化階段

實(shí)時(shí)優(yōu)化階段主要目的是根據(jù)用戶需求的變動(dòng)信息，實(shí)現(xiàn)對(duì)路徑的重新規(guī)劃，具體優(yōu)化過程分為兩步，第1步對(duì)預(yù)優(yōu)化得到的子路徑進(jìn)行過濾跟蹤，將服務(wù)過的用戶和待服務(wù)的用戶設(shè)置為不變點(diǎn);第2步對(duì)剩余的用戶進(jìn)行局部?jī)?yōu)化。當(dāng)用戶需求發(fā)生變化時(shí)，只需修改路徑中的配送量即可。本研究通過GI和VNS兩種方式結(jié)合進(jìn)行實(shí)時(shí)優(yōu)化。

（1）GI優(yōu)化路徑。GI即貪婪插入，主要操作原理是為新增加的用戶點(diǎn)尋找距離最近的點(diǎn)，然后插入在最近點(diǎn)的后面[6]。然后根據(jù)不同的車輛裝載量、最大路徑約束等約束條件對(duì)路徑進(jìn)行階段，形成新的路徑。這樣的操作方式可以滿足每個(gè)子路徑能插入最多的用戶需求點(diǎn)。雖然GI操作得到了車輛配送的新路徑，但這條路徑并不是最優(yōu)的，故需要再次對(duì)新路徑進(jìn)行VNS優(yōu)化。

（2）VNS優(yōu)化路徑。VNS即變鄰域搜索，主要通過改變鄰域結(jié)構(gòu)首先求得局部最優(yōu)解，然后再求得全局最優(yōu)解[7]。對(duì)于VNS搜索，本研究設(shè)計(jì)4種鄰域結(jié)構(gòu)，即路徑內(nèi)2-opt、路徑間點(diǎn)插入、路徑間點(diǎn)交換、路徑間片段交換。則在上述鄰域結(jié)構(gòu)的基礎(chǔ)上，通過以下步驟進(jìn)行操作：①令t=0，w=0。任意選擇兩個(gè)用戶點(diǎn)，根據(jù)兩點(diǎn)路徑選擇鄰域結(jié)構(gòu)搜索;②判斷得到的新路徑相較于原路徑是否有所改進(jìn)，若有改進(jìn)，則保留最新路徑;若有改進(jìn)，但得到的新解f '小于f+σ，則接受新解;若沒有改進(jìn)，則令w=w+1。其中，σ表示偏差值，值為0.2f。③當(dāng)t=t+1時(shí)，若w>β（β表示最大迭代次數(shù)），則停止搜索;反之，重復(fù)以上步驟。

3 仿真驗(yàn)證

本研究實(shí)驗(yàn)中的算法均在MATLAB程序上進(jìn)行編寫，并在 Intel（R） Core（TM） i5-3470 CPU 3.2GHz，4.0GB上運(yùn)行。由于MODVRP的特殊性，目前沒有一個(gè)統(tǒng)一的測(cè)試庫(kù)對(duì)本研究提出的算法進(jìn)行測(cè)試，故本研究采用設(shè)計(jì)的實(shí)例和標(biāo)準(zhǔn)的MDVRPTW實(shí)例庫(kù)對(duì)提出的算法進(jìn)行分析。

設(shè)計(jì)實(shí)例為4個(gè)配送中心，2個(gè)第三方機(jī)構(gòu)，14個(gè)初始客戶服務(wù)。具體用戶信息和車場(chǎng)車輛信息如下表1和表2所示。

應(yīng)用本研究提出的MODVRP模型和兩階段求解算法對(duì)設(shè)計(jì)的實(shí)例進(jìn)行求解。首先，設(shè)置預(yù)優(yōu)化階段種群大小為50，迭代次數(shù)為120次，得到Pareto最優(yōu)解集，具體見圖2所示。

從中選取成本最小的（ 5523.8，35.4，0.52 ）、用戶不滿意度最小的（5764.9，43.6，0.33 ）、旅行時(shí)間最小的（ 5561.4，35.2，0.41 ）的3個(gè)目標(biāo)向量進(jìn)行路線優(yōu)化，如表3所示。

在實(shí)時(shí)優(yōu)化階段，增加10個(gè)新用戶，老用戶中有4個(gè)用戶需求增加。根據(jù)用戶需求變化，采用VNS算法再次進(jìn)行路徑優(yōu)化，并設(shè)置非改進(jìn)最大迭代次數(shù)為10次，由此可得Pareto最優(yōu)解集為具體見圖3所示。

根據(jù)圖8的結(jié)果，對(duì)成本最?。?6001.3，55.6，0.67 ）、用戶不滿意度最?。?6872.9，53.8，0.32 ）、旅行時(shí)間最?。?6792.2，48.4，0.45 ）的3個(gè)目標(biāo)向量進(jìn)行優(yōu)化，得到最優(yōu)路徑見表4所示。

4 結(jié)語(yǔ)

由于工業(yè)?；返奶厥庑?，其物流配送的成本和風(fēng)險(xiǎn)性較大。在保障安全運(yùn)輸?shù)幕A(chǔ)上，減少運(yùn)輸?shù)某杀卷槕?yīng)了物流企業(yè)的需求。本研究基于物聯(lián)網(wǎng)，對(duì)工業(yè)?；返碾娮游锪髋渌吐窂竭M(jìn)行了規(guī)劃與監(jiān)控，實(shí)現(xiàn)了對(duì)?；返牡统杀?、低風(fēng)險(xiǎn)的運(yùn)輸。首先，本研究根據(jù)工業(yè)危化品運(yùn)輸調(diào)度與監(jiān)控的主要工作，對(duì)系統(tǒng)整體架構(gòu)進(jìn)行了設(shè)計(jì)。然后結(jié)合工業(yè)?；返呐渌吞攸c(diǎn)，提出MODVRP模型和預(yù)優(yōu)化、實(shí)時(shí)優(yōu)化兩階段求解策略。最后，完成了對(duì)提出的模型和算法的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本研究提出的模型和算法可有效解決多目標(biāo)動(dòng)態(tài)路徑優(yōu)化問題，降低了運(yùn)輸成本和風(fēng)險(xiǎn)。

參考文獻(xiàn)

[1]王蘭敬. 基于物聯(lián)網(wǎng)的我國(guó)區(qū)域智慧物流配送能力評(píng)價(jià)[J]. 商業(yè)經(jīng)濟(jì)研究，2020（16）：122-124.

[2]趙晨聰，陶文瀚，凌雅文，等. 云計(jì)算技術(shù)對(duì)現(xiàn)代物流業(yè)的影響[J]. 計(jì)算機(jī)時(shí)代，2020（08）：85-86+90.

[3]于江霞，杜紅亞，羅太波. 基于客戶分類的即時(shí)配送路徑優(yōu)化研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2020，20（04）：202-208.

[4]先夢(mèng)瑜. 基于人工魚群算法的民航運(yùn)輸路徑智能規(guī)劃算法[J]. 電子設(shè)計(jì)工程，2020，28（17）：20-24.

[5]謝龍光，王磊，楊芳，等. 基于模糊算法的帶電作業(yè)機(jī)器人路徑跟蹤方法研究[J]. 電子設(shè)計(jì)工程，2020，28（17）：33-36+41.

[6]王紅艷. 基于粒子群算法的物流路徑優(yōu)化方法研究[J]. 電子設(shè)計(jì)工程，2020，28（17）：61-65.

[7]黃富禹，劉春. 基于物聯(lián)網(wǎng)技術(shù)的隧道自動(dòng)化變形監(jiān)測(cè)系統(tǒng)設(shè)計(jì)[J]. 科學(xué)技術(shù)創(chuàng)新，2020（26）：118-119.

[8]吳志峰，吳子岳. 基于GPS/MATLAB的AUV路徑優(yōu)化分析[J]. 計(jì)量學(xué)報(bào)，2020，41（08）：926-931.

[9]郭榮佐，鄧涵文，陳芳瑩，等. 物聯(lián)網(wǎng)邊緣計(jì)算資源分配模糊建模與優(yōu)化研究[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2020，41（09）：1878-1886.

[10]張志麗，王力權(quán)，王艷君，等. 衛(wèi)星物聯(lián)網(wǎng)系統(tǒng)隨機(jī)接入前導(dǎo)序列設(shè)計(jì)[J/OL]. 無線電通信技術(shù)：1-7.