高增亮 劉皓若 王霞
摘 要:針對工業(yè)?;肺锪髋渌统杀靖甙?、風(fēng)險性大的特點,本研究基于物聯(lián)網(wǎng),提出一套?;冯娮游锪髋渌吐窂揭?guī)劃與監(jiān)控系統(tǒng),以提高?;返倪\輸效率,進(jìn)而減小?;愤\輸?shù)某杀竞惋L(fēng)險。首先,本研究根據(jù)系統(tǒng)的主要工作和目的,對系統(tǒng)整體架構(gòu)進(jìn)行了設(shè)計。然后結(jié)合工業(yè)?;返呐渌吞攸c,提出MODVRP模型和預(yù)優(yōu)化、實時優(yōu)化兩階段求解策略。最后,通過實驗驗證了研究提出的模型和算法。實驗結(jié)果表明,本研究提出的模型和算法可有效解決多目標(biāo)動態(tài)路徑優(yōu)化問題,大大降低了運輸成本和風(fēng)險。
關(guān)鍵詞:物聯(lián)網(wǎng);電子物流配送;路徑規(guī)劃;MODVRP
中圖分類號:TN929.5 文獻(xiàn)標(biāo)識碼:A 文章編號: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
隨著我國化工業(yè)的發(fā)展,危化品的種類和運輸量在不斷上升。由于危化品具有易燃、易爆、腐蝕等特性,因此在運輸環(huán)節(jié)往往具有高成本和高風(fēng)險性。在此情況下,物流企業(yè)如何掌控危化品的配送全過程,降低配送的風(fēng)險和成本,是物流企業(yè)亟需解決的問題。目前,常見的工業(yè)危化品物流配送路徑規(guī)劃與監(jiān)控系統(tǒng)對動態(tài)信息的處理能力較弱,無法滿足?;愤\輸對實時性的要求。因此,本研究在采用物聯(lián)網(wǎng)對車輛數(shù)據(jù)進(jìn)行采集的前提下,提出提出?;冯娮游锪髋渌吐窂絻?yōu)化目標(biāo)函數(shù),并通過MODVRP對模型進(jìn)行求解,以此達(dá)到時間、成本和滿意度最優(yōu)。
1 目標(biāo)函數(shù)
在現(xiàn)代物流配送過程中,成本、旅行時間、客戶滿意度是影響企業(yè)利益的和對車輛路徑規(guī)劃的主要因素[3]。因此本研究在尋求?;奋囕v物流配送最優(yōu)路徑時,以這3個對象作為模型的目標(biāo)函數(shù)。
1.1 問題編碼
問題編碼包括車場編碼、客戶、道路編碼[4]。其中,車場包括配送中心和第三方機(jī)構(gòu)。設(shè)配送中心為m(m=N+1,N+2,…N+M),負(fù)責(zé)給N個不同地理位置的客戶送貨,每個配送中心有Rm輛車,每輛車的最大載量為Qkm(k=1,2,…Rm),發(fā)車成本為Fkm;第三方機(jī)構(gòu)為h(h=N+M+1,…N+M+H),每個機(jī)構(gòu)有Rh輛車,每輛車的最大載量為Qkh,租賃成本為Zhk??蛻鬷(i=1,2,...,N),客戶需求量為Qi,每個客戶的服務(wù)時間窗為[Ei,Li],開始服務(wù)時間為ti,客戶在ti時間的滿意度可表示為:
道路編碼即對用戶i到j(luò)的距離dij進(jìn)行編碼。設(shè)每段路上配送中心車k的初始車速為,道路影響車速的時間為,對車輛的影響系數(shù)為。
1.2 目標(biāo)函數(shù)構(gòu)建
定義決策變量為:
以成本、時間和客戶滿意度作為優(yōu)化目標(biāo),得到目標(biāo)函數(shù)為:
式中,f1,f2,f3分別表示成本目標(biāo)、旅行時間目標(biāo)、客戶滿意度目標(biāo)。
2 目標(biāo)函數(shù)求解
對目標(biāo)函數(shù)的求解分為預(yù)優(yōu)化和實時優(yōu)化兩個階段,整體求解流程如下圖1所示。在求解過程中,采用預(yù)優(yōu)化和實時優(yōu)化的方式進(jìn)行求解[5]。預(yù)優(yōu)化階段是根據(jù)用戶需求和相關(guān)參數(shù)建立MODVRP模型產(chǎn)生預(yù)優(yōu)化路徑。同時考慮到MODVRP具有動態(tài)性,采用局部優(yōu)化用于實時優(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ù)編碼的方式對問題編碼,并初始化粒子群設(shè)置每個粒子的初始位置、速度以及個體的最優(yōu)解和全局最優(yōu)解;②選取距離用戶最近的車場中載重量最大的車輛進(jìn)行配送,計算各個粒子的目標(biāo)向量值;③應(yīng)用遞歸法建立非劣解集Ndset,并從中選取個體最優(yōu)解bestPi和全局最優(yōu)解bestG;④更新粒子狀態(tài)得到新種群,應(yīng)用自適應(yīng)網(wǎng)格技術(shù)求得Ndset。⑤若滿足終止條件,則停止算法;若不滿足終止條件,則重復(fù)步驟③④⑤。
2.2 實時優(yōu)化階段
實時優(yōu)化階段主要目的是根據(jù)用戶需求的變動信息,實現(xiàn)對路徑的重新規(guī)劃,具體優(yōu)化過程分為兩步,第1步對預(yù)優(yōu)化得到的子路徑進(jìn)行過濾跟蹤,將服務(wù)過的用戶和待服務(wù)的用戶設(shè)置為不變點;第2步對剩余的用戶進(jìn)行局部優(yōu)化。當(dāng)用戶需求發(fā)生變化時,只需修改路徑中的配送量即可。本研究通過GI和VNS兩種方式結(jié)合進(jìn)行實時優(yōu)化。
(1)GI優(yōu)化路徑。GI即貪婪插入,主要操作原理是為新增加的用戶點尋找距離最近的點,然后插入在最近點的后面[6]。然后根據(jù)不同的車輛裝載量、最大路徑約束等約束條件對路徑進(jìn)行階段,形成新的路徑。這樣的操作方式可以滿足每個子路徑能插入最多的用戶需求點。雖然GI操作得到了車輛配送的新路徑,但這條路徑并不是最優(yōu)的,故需要再次對新路徑進(jìn)行VNS優(yōu)化。
(2)VNS優(yōu)化路徑。VNS即變鄰域搜索,主要通過改變鄰域結(jié)構(gòu)首先求得局部最優(yōu)解,然后再求得全局最優(yōu)解[7]。對于VNS搜索,本研究設(shè)計4種鄰域結(jié)構(gòu),即路徑內(nèi)2-opt、路徑間點插入、路徑間點交換、路徑間片段交換。則在上述鄰域結(jié)構(gòu)的基礎(chǔ)上,通過以下步驟進(jìn)行操作:①令t=0,w=0。任意選擇兩個用戶點,根據(jù)兩點路徑選擇鄰域結(jié)構(gòu)搜索;②判斷得到的新路徑相較于原路徑是否有所改進(jìn),若有改進(jìn),則保留最新路徑;若有改進(jìn),但得到的新解f '小于f+σ,則接受新解;若沒有改進(jìn),則令w=w+1。其中,σ表示偏差值,值為0.2f。③當(dāng)t=t+1時,若w>β(β表示最大迭代次數(shù)),則停止搜索;反之,重復(fù)以上步驟。
3 仿真驗證
本研究實驗中的算法均在MATLAB程序上進(jìn)行編寫,并在 Intel(R) Core(TM) i5-3470 CPU 3.2GHz,4.0GB上運行。由于MODVRP的特殊性,目前沒有一個統(tǒng)一的測試庫對本研究提出的算法進(jìn)行測試,故本研究采用設(shè)計的實例和標(biāo)準(zhǔn)的MDVRPTW實例庫對提出的算法進(jìn)行分析。
設(shè)計實例為4個配送中心,2個第三方機(jī)構(gòu),14個初始客戶服務(wù)。具體用戶信息和車場車輛信息如下表1和表2所示。
應(yīng)用本研究提出的MODVRP模型和兩階段求解算法對設(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 )、旅行時間最小的( 5561.4,35.2,0.41 )的3個目標(biāo)向量進(jìn)行路線優(yōu)化,如表3所示。
在實時優(yōu)化階段,增加10個新用戶,老用戶中有4個用戶需求增加。根據(jù)用戶需求變化,采用VNS算法再次進(jìn)行路徑優(yōu)化,并設(shè)置非改進(jìn)最大迭代次數(shù)為10次,由此可得Pareto最優(yōu)解集為具體見圖3所示。
根據(jù)圖8的結(jié)果,對成本最?。?6001.3,55.6,0.67 )、用戶不滿意度最小( 6872.9,53.8,0.32 )、旅行時間最?。?6792.2,48.4,0.45 )的3個目標(biāo)向量進(jìn)行優(yōu)化,得到最優(yōu)路徑見表4所示。
4 結(jié)語
由于工業(yè)?;返奶厥庑裕湮锪髋渌偷某杀竞惋L(fēng)險性較大。在保障安全運輸?shù)幕A(chǔ)上,減少運輸?shù)某杀卷槕?yīng)了物流企業(yè)的需求。本研究基于物聯(lián)網(wǎng),對工業(yè)?;返碾娮游锪髋渌吐窂竭M(jìn)行了規(guī)劃與監(jiān)控,實現(xiàn)了對?;返牡统杀?、低風(fēng)險的運輸。首先,本研究根據(jù)工業(yè)?;愤\輸調(diào)度與監(jiān)控的主要工作,對系統(tǒng)整體架構(gòu)進(jìn)行了設(shè)計。然后結(jié)合工業(yè)?;返呐渌吞攸c,提出MODVRP模型和預(yù)優(yōu)化、實時優(yōu)化兩階段求解策略。最后,完成了對提出的模型和算法的實驗。實驗結(jié)果表明,本研究提出的模型和算法可有效解決多目標(biāo)動態(tài)路徑優(yōu)化問題,降低了運輸成本和風(fēng)險。
參考文獻(xiàn)
[1]王蘭敬. 基于物聯(lián)網(wǎng)的我國區(qū)域智慧物流配送能力評價[J]. 商業(yè)經(jīng)濟(jì)研究,2020(16):122-124.
[2]趙晨聰,陶文瀚,凌雅文,等. 云計算技術(shù)對現(xiàn)代物流業(yè)的影響[J]. 計算機(jī)時代,2020(08):85-86+90.
[3]于江霞,杜紅亞,羅太波. 基于客戶分類的即時配送路徑優(yōu)化研究[J]. 交通運輸系統(tǒng)工程與信息,2020,20(04):202-208.
[4]先夢瑜. 基于人工魚群算法的民航運輸路徑智能規(guī)劃算法[J]. 電子設(shè)計工程,2020,28(17):20-24.
[5]謝龍光,王磊,楊芳,等. 基于模糊算法的帶電作業(yè)機(jī)器人路徑跟蹤方法研究[J]. 電子設(shè)計工程,2020,28(17):33-36+41.
[6]王紅艷. 基于粒子群算法的物流路徑優(yōu)化方法研究[J]. 電子設(shè)計工程,2020,28(17):61-65.
[7]黃富禹,劉春. 基于物聯(lián)網(wǎng)技術(shù)的隧道自動化變形監(jiān)測系統(tǒng)設(shè)計[J]. 科學(xué)技術(shù)創(chuàng)新,2020(26):118-119.
[8]吳志峰,吳子岳. 基于GPS/MATLAB的AUV路徑優(yōu)化分析[J]. 計量學(xué)報,2020,41(08):926-931.
[9]郭榮佐,鄧涵文,陳芳瑩,等. 物聯(lián)網(wǎng)邊緣計算資源分配模糊建模與優(yōu)化研究[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/OL]. 無線電通信技術(shù):1-7.