考慮訂單優先級帶時間窗的多車型開放式車輛路徑問題研究

高子健, 初良勇

(1.集美大學航海學院, 廈門 361021; 2.集美大學福建航運研究院, 廈門 361021)

物流運輸活動通常在遇到特殊情形時會優先考慮派送訂單優先級更高的貨物,在劃定配送路線的一系列客戶點中,存在有重要客戶點相比于其他客戶點要求更快時間配送且緊急程度更高。對具有優先級要求的客戶點,其潛在價值較高,通常存在于特情應急場景中,或是高價客戶單配送場景,物流運輸需要通過調整配送順序來滿足優先訂單在配送時間上的需求。其次,考慮城市綜合交通發展現狀,為實現“碳達峰、碳中和”目標,物流運輸公司多考慮引入新能源車輛(主要指電車)同燃油車輛進行物資配送。根據城市道路車型限行要求靈活調配運輸任務,確保滿足時間節點和空間限制的前提下達到運送成本最小、能源利用最優的目標規劃。除此之外,建立城市網絡式運營的多配送中心能夠進一步提升貨物流轉速率,滿足實時性的要求,減少貨物在途服務時間以及車輛終點空載折返次數,降低運輸成本。

多車型多配送中心的車輛路徑優化問題是基于車輛路徑問題(vehicle routing problem,VRP)所提出的變題,該問題是分別從單車場多車型路徑優化問題(heterogeneous fleet vehicle routing problem,HFVRP)和多車場車輛路徑問題(multiple depot vehicle routing problem,MDVRP)拓展結合得到的一類多項式復雜程度的非確定性問題(non-deterministic polynomial,NP)[1]。物流研究中將多車場考慮為多配送中心,建立混合整數規劃模型,求解此類問題通常可用精確式算法或啟發式算法求解。由于精確式算法難以承載此類問題的龐大數據體量和復雜模型,故目前所開展的研究一般都通過啟發式算法求解,鄧欣[2]求解MDVRP問題時對小規模算例設計單親遺傳算法求解,而對大規模算例設計虛擬車場的遺傳算法求解;Zhang等[3]設計圖形強化學習算法求解該問題。郭海湘等[4]提出3種混合算法(混合啟發式算法、混合遺傳算法、混合蟻群算法)求解HFVRP問題,并且在3種算法間實驗比較得出混合蟻群算法相較于其他算法表現更優。多車型多配送中心的車輛路徑優化問題相對于前兩者復雜程度更高,領域內的學者也嘗試利用各類啟發式算法來求解,韓孟宜等[5]結合遺傳算法、節約算法以及大規模領域搜索算法求解應急物資配送背景下的VRP問題;陳呈頻等[6]提出多染色體遺傳算法求解該問題,通過對遺傳算法變形改進求解本問題均可驗證遺傳算法群對于該問題的可行性。但遺傳算法群相較于其他啟發式算法而言,求解本問題時容易陷入局部最優解,并且隨多目標對象群體增大,收斂速度也同樣會降低[7]。隨著各種新型啟發式算法[8]在其他領域問題上取得顯著進展,也同樣被引入求解VRP問題,根據算法針對不同問題的適應性,也有諸多學者利用其求解多車型多配送中心的車輛路徑優化問題:郝群茹等[9]基于傳統VRP問題考慮軟時間窗、工作車輛額定工時對成本價值影響,設計領域變化規則下的禁忌搜索算法求解問題;蔣權威[10]設計并改進貓群算法求解該問題;羅鴻斌改進粒子群算法求解該問題;Cao等[11]設計基于雙檔案算法(Two-Arch2)的模因算法(Memetic)求解帶容量的多車型多配送中心的車輛路徑優化問題。針對不同背景下的VRP問題研究在交通運輸道路優化領域均考慮使用遺傳算法及其混合算法求解,遺傳算法在解的多樣性和隨機性上具有較大優勢,而其他啟發式算法則具有運算速度快,收斂性高的特點,可以進一步考慮在優化解的結構情況下引入其他啟發式算法求解問題。

除上述問題外,時間窗因素和路徑限制因素[12-14]也常被考慮在內,Liu等[15]對多車隊混合運行的開-閉環VRP問題建立混合整數規劃模型,建立有向圖分析并且優化遺傳算法適配求解開閉環混合問題;范厚明等[16]在開環多配送中心場景中考慮需求可拆分的情況下建立運輸成本、整理成本、建設成本等之和最小為目標函數的規劃模型,設計混沌遺傳模擬退火算法求解該問題,驗證了算法對該問題的有效性;Carman等[17]考慮訂單優先級、時間窗等多重因素在研究蟻群算法的基礎上嵌套局部優化最大、最小τ值更新信息素處理訂單分配和VRP問題,同時結合IOT(internet of things)解決實際的電商物流配送問題,也同時對現階段特殊情況下的優先級訂單問題提出了初步的解決方案。通常情況下,多車型多配送中心的車輛路徑優化問題根據成本、效率、能耗等方面規劃最優路徑,但對于考慮運送訂單序列中存在優先配送客戶,存在優先配送時間需求等特殊因素缺乏普適性,而優先級訂單所存在的潛在價值也同樣不容忽視。

考慮到現實背景對優先訂單重要性的要求,現根據商客戶、車隊、倉儲等綜合反映出的運送環境進行分析,建立適用于特殊且帶有優先級序列訂單配送情形的車輛路徑問題,將該問題描述為考慮城市道路限行要求的多配送中心場景,采用新能源車與傳統燃油車多車型混合配送的形式,其中新能源車輛需考慮足電配送,在確定客戶服務優先順序的前提下服從時間窗約束,且車輛服務結束后可停駛在任一配送中心的考慮訂單優先級帶時間窗的多車型開放式車輛路徑問題(the open multi-vehicle routing problem considering order priority and time window,OMVRPOPTW)。對該問題采用優先策略粒子群算法求解,優化算法運算效率的同時解決解結構單一化的缺點。

1 問題描述與模型建立

1.1 問題描述

在特定運輸網絡中,存在多個配送中心和需要進行服務的客戶點,并且這些客戶點中存在有優先配送訂單和非優先配送訂單兩種類型。優先配送訂單需排列到前置配送任務中,非優先級配送訂單按照路徑最優原則派送。配送中心有燃油車和新能源車兩種車輛類型,車輛載重量、車輛最大行駛里程以及城市車型限行位置信息已知,燃油車輛有區域限行條件要求,新能源車輛在運行過程中遇到電量告急時前往就近配送中心充電,充電完成后出發繼續完成配送。

如圖1所示,運輸網絡中有配送中心P1、P2、P3和P4且均帶有新能源車輛充電設施,非優先級要求訂單標識為“N”。燃油車輛、新能源車輛分別從配送中心出發P1,按照城市限行要求前往不同區域配送,首先根據優先級訂單序列配送優先級訂單客戶1、2,其他客戶點在優先級訂單配送完成后根據成本效益最優目標規劃路徑并派送。每個客戶點都需要被服務,且被服務一次,車輛完成客戶點服務后不需要返回原配送中心。本文目標函數考慮燃油車輛的碳排放成本,新能源車輛與燃油車輛能耗成本忽略不計。在符合設定情景下,以總運輸成本、碳排放成本以及時間窗懲罰成本之和最小,規劃燃油汽車以及新能源車輛的最優配送路徑。

圖1 優先級策略下帶時間窗的多車型開放式配送問題圖示Fig.1 The open distribution problem of multi-vehicle with time window under priority strategy

1.2 建模假設

根據本文研究背景和現實情況分析,模型建立考慮以下假設。

(1)優先級訂單有配送順序要求,需按照序列依次配送。

(2)客戶需求量不大于車輛載重量,客戶需求不可拆分且配送過程不補貨。

(3)新能源車輛考慮快速充電策略從配送中心滿電量出發(充電站充電時長與充電量呈線形關系),且配送中心充電站可被訪問大于1次。

(4)客戶服務時間窗考慮為硬時間窗。

1.3 決策變量

已知配送中心集合P、客戶點集合O和充電站集合C;N=P∪O∪C為配送中心、客戶點與充電站的集合;B表示燃油車限制行駛區域;R表示車型為傳統燃油車;E表示為車型為新能源車。

參考單位距離燃油消耗量ρ(h)取決于貨車載貨量h的線性函數,即

ρ(h)=a(F0+h)+b

(1)

式(1)中:a、b為線性相關系數;燃油運輸車總重量分為車輛自重F0與貨物載重量h。

考慮集卡最大載重量為H,滿載時單位距離燃油消耗為ρ*,空載時單位距離燃油消耗為ρ0,則單位距離集裝箱卡車滿載、空載油耗量分別為

ρ0=aF0+b

(2)

ρ*=a(F0+H)+b

(3)

通過計算得到,單位距離燃油運輸車燃油消耗量ρ(h)可以表示為

(4)

則已知從轉運點i到轉運點j的距離表示為dij,則車輛經由轉運點i到轉運點j的燃油消耗量表示為

(5)

1.4 混合整數模型建立

基于上述定義的參數和變量以及油耗量的計算,建立總配送成本(運輸成本、碳排放成本、時間窗懲罰成本)最小為目標的帶時間窗開放式場景并考慮燃油運輸車、新能源運輸車在限行區域規定下的混合整數模型。若無特殊說明,i∈N,j∈N,k∈K。

(1)目標函數為

(6)

式(6)中:wik為車輛k在節點i的等待時間,k∈K;決策變量xijk表示車輛k由節點i駛向節點j時,xijk=1;否則xijk=0。

(2)約束條件為

(7)

(8)

(9)

式(9)中:pi為在節點i時車輛中貨物的載重量;Tik為車輛k到達節點i的時間。

(10)

eik

(11)

式(11)中:eik為轉運點i期望的最早到達時間;lik為節點i期望的最晚到達時間。

(12)

(13)

ui-uj+Mxijk≤M-1, ?i∈N,j∈N,k∈K

(14)

(15)

(16)

q′ik=D≥0, ?i∈P∪C,k∈E

(17)

式(17)中:q′ik為車輛k離開節點i時,車輛的剩余電量,k∈K。

qik≥0, ?i∈N,k∈E

(18)

式(18)中:qik為車輛k到達節點i時,車輛的剩余電量,k∈K。

Bik=D-qik, ?i∈P∪C,k∈E

(19)

式(19)中:Bik為車輛k在節點i補充的電量,k∈E。

qjk≤q′ik+D(1-xjik)-edijxijk,?i∈N,j∈N,k∈E

(20)

qik=q′ik, ?i∈O,k∈E

(21)

(22)

式(22)中:sik為車輛k在節點i的充電時間。

xijk={0,1}, ?i,j∈N,i≠j,k∈K

(23)

式(6)為目標函數;式(7)和式(8)為車輛區域限制行駛約束。式(7)為燃油車輛不可進入限行區域行駛送貨,燃油車輛不經過充電樁;式(8)要求車輛k從節點i到節點j被車輛k全程服務;式(9)～式(12)為時間窗約束。式(9)為新能源車輛時間窗約束;式(10)為車輛在i節點的提前到達等待時間和延遲到達等待時間計算;式(11)為到達時間和提前到達、延遲到達時間的關系;式(12)為燃油車輛的時間窗約束;式(13)為流平衡約束,車輛從配送中心出發并回到其他配送中心,松弛掉配送中心的流平衡約束,保證配送中心以外的其他節點的流平衡;式(14)消除子回路約束;式(15)和式(16)為車輛載重約束。式(15)為客戶點j需要的重量之和不超過新能源車輛運輸的限重;式(16)客戶點j需要的重量之和不超過燃油車輛運輸的限重;式(17)～式(22)為新能源車電量約束。式(17)和式(18)表示新能源車到達各個位置i時電量都要達到運行需求且離開配送中心、充電樁時電量充足;式(19)為電量補充公式,到達i節點需要補充的電量為總電量減去到達i節點剩余的電量;式(20)表示到達某節點的電量需要滿足離開上一節點電量的剩余值和補充值(如需補充電量時);式(21)表示新能源車到達客戶點i和離開客戶點i時的電量保持不變:式(22)表示新能源車輛充電時間的計算公式;式(23)為決策變量取值約束。

2 優先級策略粒子群優化算法

粒子群算法(particle swarm optimization,PSO)將目標種群中的獨立對象賦予特征信息,在尋優過程中進行局部交換,同時會將獨立對象之間組成群體,以群體為單位進行全局尋優和信息交換。PSO算法能夠同時兼顧局部和全局的發展空間,具有良好的協同搜索能力,并且算法本身對于單目標、多目標問題有較大提升空間。PSO算法因其收斂速度快、求解效率高的特點也使得其處理大部分優化問題時更具普適性。優先級策略粒子群優化算法(priority particle swarm optimization,PPSO)相對于一般粒子群算法而言,優化粒子群算法對于多目標問題具有更高適應性的特性,其在帶時間窗的開放式車輛路徑問題同樣更具有快速收斂性,本文研究在標準粒子群的基礎上,增加優先訂單序列篩選算子,并且利用貪婪算法優先搜尋局部最優解,后采用粒子群算法比較求出全局最優解,使其更能夠適應優先級訂單問題,提升算法搜索適應度函數最優值的效率。

2.1 種群編碼方式

結合優化粒子群算法的應用特征,本文研究對種群采用自然數二維編碼的方式對不同車輛服務不同客戶點的訪問表示。其中,第一維編碼對車輛類型和車輛編號進行區分;第二維編碼表示配送中心和客戶服務點編號。例如,在OMVRPOPTW問題中,存在配送中心、客戶點、燃油車輛和新能源車輛幾類元素,且在限行區域中需要對車輛和配送中心、客戶點進行區分,單數車輛將代表燃油車、雙數車輛代表新能源車,配送中心和客戶點根據不同實例對應不同編碼。如圖2(a)所示,對種群粒子編碼得到客戶點以及對應服務車輛,初始編碼對客戶點和車輛對應情況進行標記;如圖2(b)所示車輛1(燃油型)將依次服務1-2-7客戶點、車輛2(新能源型)將依次服務4-5-8客戶點、車輛3(燃油型)將依次服務3-6-9客戶點(客戶點編號的大小不作為最優路徑順序的判定依據)。

圖2 種群粒子編碼與解碼圖Fig.2 Population particle coding and decoding diagram

2.2 種群生成方式

粒子群算法相較于其他類型算法在初始種群的生成上需要盡可能地遍歷所有可能解,但隨機生成種群的方式無疑增加了較多無效解集合,在后續進一步進行局部尋優和全局尋優的過程中增加迭代次數,降低運算效率。在構造初始種群的問題上采用佳點集理論生成更加均勻分布的初始種群,相較于隨機生成法構造初始種群而言已經更好接近于粒子群算法所更適應的遍歷性。本文研究將貪婪策略應用到初始種群的生成方式中,通過面向車輛分配初始點的方式,添加路徑到車輛數量無法滿足要求為止而獲得近似最優解,將其作為初始種群帶入后續算法迭代中去。

2.3 優化粒子群算法的迭代

粒子群算法每代均需要評估當前粒子的適應度,不斷記錄當前局部最優pbest和全局最優gbest相對于前代是否為最優解來實現迭代過程,直至尋找到符合要求的全局最優值。為保證粒子始終保持運動更新狀態,當gbest不符合要求時,將按照式(24)和式(25)對粒子進行自身速度和位置的更新。

vit(k+1)=vit(k)w(k)+c1r1[pbest,it-xit(k)]+c2r2[gbest,t-xit(k)]

(24)

xit(k+1)=xit(k)+vit(k+1)

(25)

式中:i=1,2,…,N表示粒子總數;t=1,2,…,N表示粒子所處維度;k為迭代次數;w(k)為第k次迭代時慣性權重;c1、c2為學習因子;r1、r2為隨機數通常取[0,1];pbest,it為i粒子當前維度t局部最優;gbest,t為當前維度全局最優;xit為粒子位置;vit為粒子速度。

2.4 優化粒子群算法求解步驟

利用優先級策略優化粒子群算法求解OMVRPOPTW問題的算法求解步驟如下。

步驟1初始化優化粒子群算法的各項相關參數,如種群規模N、最大迭代次數Tmax、學習因子C1、C2、C3等。

步驟2利用貪婪算法生成初始化種群,并且初始化粒子的位置和速度,得到燃油車和新能源車兩種車型的車輛代號,并且利用輪盤賭法篩選出優先級訂單的客戶得到初始客戶配送次序。

步驟3綜合建模要求,將總服務成本最小的目標函數設置為適應度函數,并計算初始種群的個體極值、全局極值、領域極值。計算適應度函數值,使其滿足約束條件在車輛類型以及限制行駛區域分配的要求。

步驟4算法迭代計算,根據PSO粒子群位置、速度公式更新粒子狀態。

步驟5對更新后粒子個體極值、全局極值、局部最優值分別與其歷史最優情況進行比較,取二者中更優值更新進pbest和gbest。

步驟6粒子解碼生成燃油車輛和新能源車輛在所屬行駛區域的客戶點配送順序,判斷是否為訂單優先級順序并在其符合要求是繼續下一步,否則剔除當前數據,并更新數據列表,跳轉步驟4繼續迭代。

步驟7判斷迭代次數是否已到達Tmax并在其到達最大迭代次數時終止算法運算,并且輸出粒子當前最優狀態信息,回歸原問題求解,否則跳轉至步驟4繼續迭代。

步驟8對到達Tmax時的粒子狀態位置進行分析得到OMVRPOPTW問題的車輛調度方案并且輸出最小成本。

算法步驟流程如圖3所示。

圖3 優化粒子群算法流程圖Fig.3 Flowchart of the P-PSO algorithm

3 實驗結果與算例分析

本文實驗數據集取自Solomon標準數據集,利用客觀數據驗證模型和算法有效性。本次實驗算法在Python平臺中實現編程,計算機運行環境為2.9 GHz CPU 6-core i5處理器、16 GB內存。本章內容主要分為試驗結果和實驗對比分析兩部分,3.1節將對Solomon數據集r101～r110進行數值試驗,驗證算法的有效性;3.2節設置對比實驗,分別檢驗:①建模在考慮時間窗、碳排放、開閉路徑等因素作為變量時的成本對比分析;②本文研究中優化粒子群算法與標準粒子群算法在迭代時間、運行結果的差別;③初始種群分布采用貪婪策略與隨機數法的實驗對比。OMVRPOPTW涉及的參數及取值如表1所示。

表1 數值試驗參數取值表Table 1 Numerical test parameters

3.1 實驗結果分析

針對OMVRPOPTW特性選擇10組適題修改的Solomon標準數據集R型算例分別需求量為25、50、100及其對應新能源車1輛、2輛、5輛和同等燃油車輛數的不同規模進行測試,本文研究將10組算例計算得到計算最優結果(計算最優時間)、平均最優結果(平均運算時間)以及歷史最優計算結果(歷史最優運行時間)進行對比記錄,分別計算其最優解差值GAP=(計算最優值/平均最優值)/平均最優值×100%反應算法在計算結果中與歷史計算結果的表現,數值分析結果如表2所示。

表2 不同規模算例數值結果Table 2 Numerical results of different scale examples

通過多組數據實驗中可以看出r109算例已達到已知最優解,并且其他算例的最終結果均在合理范圍之內且均小于0.50%,反映出本文所使用算法在計算結果上的有效性,以及算法運算能力對于模型的適配性。

3.2 模型對比分析

在算例r101～r103(規模為100)的基礎上,取消訂單優先級客戶序列,客戶的配送順序完全由算法搜索得到最優解。為了區別訂單優先級的重要性,增加大時間窗懲罰成本,優先級訂單在車輛配送起每單位時間內增加損失,直到配送完畢后停止損失,其中,損失值=固定時間窗懲罰成本×0.2%(每單位時間)。采用優化粒子群算法求解,求解算例,如表3所示,可以得到總成本、運輸成本、時間窗懲罰成本(含大時間窗懲罰成本)均存在差異。

表3 模型對比算例數值結果Table 3 The model compares the numerical results of the example

優先策略雖然運輸成本略高于一般策略,但是時間窗懲罰成本和總成本均有降低。本實驗中,增加大時間窗懲罰成本,相當于實際情況中提升優先級訂單成本價格,對于價值更高、重要性更強的訂單優先配送,同樣能夠降低成本,并且提升客戶服務等綜合水平。

3.3 算法對比分析

優化粒子群算法相對于標準粒子群算法不僅體現在對模型的適應性,算法迭代收斂的次數和速度上同樣能夠判斷對算法的優化是否有效。以算例r101為研究對象,分別對算法改進的部分進行試驗以及算法整體性能進行對比分析。

(1)隨機生成初始種群與貪婪策略生成初始種群實驗對比分析。將初始種群隨機生成法和貪婪策略生成法進行對比,主要從運算結果和運算時間兩部分進行對比和分析。如表4所示,從總成本看,兩種初始種群生成的結果上差異并不大,但是時間上采用貪婪策略確實有效地減少了運算時間,提升了算法的運算效率。

(2)優化PSO與標準PSO計算結果對比分析。以r101算例為對象進行算法比較,主要對標準PSO和優化PSO算法在總成本、運輸成本、時間窗懲罰成本以及碳排放成本的計算結果上進行分析和討論。如表5所示,成本結果計算上優化PSO算法取得更低的成本數值,其中在碳排放成本上顯著降低30.06%,證明優化PSO算法在對多車輛路徑優化問題上能夠更好地對新能源車輛進行合理調度。

表5 算法實驗結果對比Table 5 Comparison of algorithm experimental results

優化PSO與標準PSO算法在迭代次數存在較為明顯差異,采用貪婪算法生成初始種群優先縮小了算法搜尋最優解的路徑,并且優先在迭代次數為100時達到最優值,算法比較迭代情況如圖4所示,可見在算法收斂性能和計算速度上能夠有效求解OMVRPOPTW問題,并具有較好適應性。

圖4 優化粒子群算法與標準粒子群算法迭代對比圖Fig.4 Comparison diagram of the P-PSO and standard PSO iterations

4 結論

基于多配送中心多車輛路徑優化問題,衍生出帶有優先級訂單順序需求的帶時間窗的多車型開放式車輛路徑問題。建立碳排放成本、運輸成本、時間窗懲罰成本之和為最小值的目標函數,針對優先級問題的特殊性,在算法設計上優化PSO算法,模擬訂單優先順序篩選符合條件的最優路徑,利用貪婪算法生成初始種群降低后期運算成本,提升算法運算效率。最后通過對算例的實例實驗對比算法各部分的有效性,實驗對訂單優先級客戶點增加獎勵因子,非訂單優先級客戶點不變,驗證了在優先級順序需求下,建模和算法結果并不會增加綜合成本。同時,對比標準PSO算法和優化PSO算法實驗數據結果,優化PSO算法在處理多車型問題上具有更顯著的優勢。

對于優先級順序需要的情況,物流運輸問題中較為常見,本文研究在時間窗約束上采取硬時間窗,但如果擴大優先級訂單的時間窗范圍并且考慮軟時間窗約束的情況時,既可以滿足訂單在符合要求的時間內送達也同時能夠進一步優化路徑選擇,未來將進一步優化優先級概念,考慮符合訂單要求的軟時間窗約束,同時考慮配送裝載情況進行研究。