基于兩階段算法的時變電動車輛路徑問題

文/鄧詩言

1.引言

隨著城市化的加快和人口密度的提高，城市擁堵狀況日益嚴重。在此背景下，城市配送問題受到極大的影響。在使用電動車進行配送時，如果不考慮道路擁堵的情況，將會大大增加配送時間。因此，在考慮時變路網的情況下，合理規劃電動車的運輸路線，制定高效的配送方案至關重要。從2000年開始，就有國內外學者對時變網絡下的車輛配送路徑問題進行了研究，與傳統的靜態路網不同，時變路網會隨時間而發生改變。王衛國[1]等學者建立了雙目標的車輛配送路徑模型，通過考慮車輛時變行駛速度的方式來描述時變路網，并改進了傳統求解靜態路網下車輛路徑問題的算法。馬華偉[2]針對時變車輛路徑問題，以先進先出為原則，提出了一種兩階段啟發式算法，有效解決了時變車輛路徑問題中的“先出發，后到達”的問題。吳瑤[3]提出了一種食品損耗函數，車輛在配送部分易腐爛貨物時，貨物會隨時間增加而帶來更大的損耗，需考慮時變路網的影響，在最短的時間內將貨物送達以減少貨物損失。王楊[4]在時變路網下拓展了單一配送中心的情況，考慮了多個配送中心進行聯合配送。王寧[5]將貨物進行分類，針對不同價值的客戶進行分級配送，并在時變網絡下考慮客戶的滿意度。因此，在復雜多變的城市路網環境下，采用時變速度的方式描述時變路網，合理規劃電動車配送路徑，可以減少總配送路徑，降低配送成本，防止電動車因電量不足而中途擱置情況的發生。

2.問題描述

在城市的某一物流中心，承擔著為周圍一定半徑內的客戶提供配送服務的任務。需要配送的貨物，在當晚由城際貨運車輛送達物流中心。根據信息系統和GPS系統，顧客的配送坐標和貨物需求量以及時間窗是已知的。物流中心擁有同質的電動車隊，假設物流中心擁有足夠的場地和充電設施，以保證電動車在白天進行配送任務時為滿電狀態。在每天早上9點，電動車輛裝載貨物出發，為顧客提供配送需求。在城市中分布著地理信息已知的充電樁，電動車在配送途中若電量不足，可以訪問充電站以補充電量。其中，城市路網的狀態隨時間發生改變，具體表現為車輛的行駛速度在不同的時間擁有不同的行駛速度。根據已知的顧客信息、充電樁信息和車輛信息合理規劃配送路線。

3.模型建立

3.1 模型假設

為簡化研究內容和確定主要研究目標，在建立模型前做出以下假設：假設1：電動車訪問充電站時的充電時間相同，為1個小時；假設2：每個客戶都需要被訪問一次，且只能由一輛電動車訪問；假設3：電動車的型號相同，即載重量和電池容量相同；假設4：電動車離開物流中心和充電樁為滿電狀態；假設5：每個客戶都需要一定的時間收納貨物，因此車輛在到達顧客點后需停留10分鐘交接貨物；假設6：本文研究的車輛路徑問題為封閉式，電動車完成配送任務后需要返回物流中心；假設7：電動車能耗為線性能耗。

3.2 時變路網下車輛行駛速度

本文以車輛在不同時間下擁有不同的行駛速度以描述時變網絡，目前研究時變網絡中車輛實際行駛速度的方法主要分為Malandraki[6]模型和Ichoua[7]模型兩類，由于Malandrak模型沒有滿足先入先出原則，并且使用該模型可能出現先出發后到達的情況，因此本文使用Ichoua模型，將一天以5分鐘為間隔劃分為多個時間段，假設每個間隔內的平均速度不變，通過計算車輛在每個時段的行駛時間以獲得車輛在道路的總行駛時間。具體情況如圖1和圖2所示：

圖1 Malandraki模型行程時間圖

圖2 Ichoua模型行程時間圖

3.3 時變網絡電動車輛配送路徑模型

以車輛使用成本、距離成本和時間窗懲罰成本最小化為目標，建立以下模型：

?

目標函數（1）表示車輛固定成本、行駛成本和時間窗懲罰成本最小化，約束（2）表示車輛的在完成配送任務后需返回物流中心，約束（3）為進出流量平衡，到達該節點的車輛數等于離開該節點的車輛數，約束（4）和（5）表示一個客戶只能由一輛車服務一次，約束（6）和（7）為車輛載重約束，（8）-（10）為時間約束，約束（11）表示時間懲罰成本的計算，約束（12）表示電池電量不能為負且不超過最大滿電量，（13）和（14）定義變量取值。

4.兩階段算法設計

時變電動車輛路徑問題屬于NP-hard問題，精確式算法難以求解大規模問題，因此本文設計了兩階段算法進行求解。第一階段采用節約里程算法求得包含所有客戶和配送中心的TSP解（Traveling Salesman Problem），并采用分車算子，通過載重約束將TSP解轉化為包含多條子路徑的VRP解(Vehicle Routing Problem)，第二階段使用禁忌搜索算法對第一階段得到的VRP解進行搜索優化，得到最終的的VRP解。在第二階段使用一下四種算子進行解空間的搜索：（1）逆序鄰域搜索算子：即隨機截取一段路徑并將其逆序；（2）1-opt交換搜索算子：隨機截取一個點插入到路徑中的另一個位置；（3）2-opt交換搜索算子：隨機選擇2個點交換位置；（4）3-opt交換搜索算子：隨機選擇3個點調換它們的位置。

5.實例分析

本文選取了重慶市九龍坡區某企業的一個物流中心，并選擇了物流中心附近的30個點作為顧客點，顧客點的經緯度坐標和貨物需求量已知，并存在8個公用充電樁可供電動車充電，假設充電樁數量足夠，不考慮充電排隊等候的因素。其中電動車的電池容量62KWh，載重量為718.4kg，單次充電時間為70分鐘，單次充電成本為40元，每個客戶的固定服務時間為10分鐘，時間懲罰成本系數和分別為0.2和0.5元/分鐘，車輛固定成本為180元/輛。DC表示物流中心，點1-30為客戶點，點31-38為充電樁。在Intel core i5，內存為16GB的計算機上，使用MATLAB R2016b軟件編寫兩階段啟發式算法對模型進行求解。將算法運行10次后，將得到的成本最小的解作為本文的最優解，最后車輛的路徑規劃如圖4所示。一共使用了4輛電動車以完成配送任務，車輛的固定成本為720元，時間窗懲罰成本為189元，能量消耗成本為283元，充電成本為240元，總配送成本為1432元。具體配送路徑如下所示：路線1：0->10->14->4->26->24->25->37->3->7->0；路 線2：0->12->19->21->16->38->1->20->2->6->37->0；路線3：0->15->27->37->23->22->5->17->32->8->0；路 線4：0->11->18->13->9->28->35->30->29->0

圖3 算法迭代搜索圖

圖4 時變路網車輛路徑圖

6.總結

本文以Ichoua模型描述時變速度，運用兩階段求解算法對時變網絡下的電動車輛路徑問題進行求解，所提出的算法能夠有效求解該問題。在未來研究時，可以從時變速度對電動車能耗的影響進行考慮。

引用出處

[1]王正國,王紅衛,劉會新.雙目標時變速度車輛路徑問題的模型及算法[J].華中科技大學學報：自然科學版,2005,33(12):4.

[2]馬華偉,靳鵬,楊善林.時變車輛路徑問題的啟發式算法[J].系統工程學報,2012,27(2):7.

[3]吳瑤,馬祖軍.時變路網下帶時間窗的易腐食品生產-配送問題[J].系統工程理論與實踐,2017,37(1):10.

[4]王楊,魯曉春.時變路網下多配送中心多車型聯合配送[J].科學技術與工程,2018,18(36):9.

[5]王寧,胡大偉,徐杰,等.基于客戶價值和滿意度的城市冷鏈物流時變路徑問題[J].中國公路學報,2021,34(9):12.

[6]Malandraki C,Daskin M S.Time Dependent Vehicle Routing Problems:Formulations,Properties and Heuristic Algorithms[J].Transportation Science,1992,26(3):185-200.

[7]Ichoua S,Gendreau M,Potvin J Y.Vehicle dispatching with time-dependent travel times[J].European Journal of Operational Research,2003,144(2):379-396.