協同物流網絡中帶有時間窗的車輛路徑問題研究

□ 劉 璽

(中國石油大學(華東)，山東 青島 266580)

1 引言

協同物流網絡(Collaborative Logistics Network)是近年來基于協同理論發展起來的現代物流網絡，它能夠實現物流企業之間的協同，共同完成配送任務。因此，如何規劃多供應商協同配送下路徑，最大限度地降低成本的就顯得尤為重要。

車輛路徑問題(VRP，Vehicle Routing Problem)由Dantzig和Ramser于1959年提出[1]，并引起了廣泛關注，屬于典型的NP-hard問題。隨后，不同學者使用各類算法對單對多、多對多車輛路徑問題進行了求解[2-5]。本文從物流集成服務商的角度出發，研究協同物流網絡中多供應商協作下，帶軟有時間窗的車輛路徑問題(VRPTW，Vehicle Routing Problem with Time Window)。通過對實際問題的分析，構建數學模型，設計智能優化算法和算例，證明本文設計模型的合理性和算法的有效性。

2 問題描述與假設條件

2.1 問題描述

在協同物流網絡中，多個供應商與多個客戶點信息共享，物流集成服務商選擇供應商為客戶進行貨物配送，安排車輛為客戶進行要求運輸車輛在客戶的時間窗內完成配送任務。但配送過程存在如下問題：①配送車輛與客戶時間窗不匹配，產生時間窗等待或者延遲成本；②車輛行駛路徑決策不科學，導致配送成本增加。

具體問題描述如下：多供應商多客戶組成的協同物流網絡由G=(O∪I，A)表示，路線集合A={(i,j)|i，j∈N∪O,i≠j}，區域內多供應商集合為O{o|o=1,2,…,|O|}，共同為客戶集合N{n|n=1,2,…,|N|}提供貨物配送服務，各個供應商和各個客戶之間道路互通，容量為H的配送車輛集合為K{k|k=1,2,…,|K|}。客戶i的配送時間窗為[tei,tli]，λi表示客戶i時間窗的緊急程度，tki為車輛k到達客戶i的時間，ω1為車輛的等待成本，ω2為延遲成本。ck為車輛k的單位配送成本，Fk為車輛k的固定調用成本。協同運作的供應商與客戶之間為N-N匹配關系，決策變量選擇如下：

2.2 條件假設

①每個客戶的一類貨物只由一輛車供給，需求不可拆分；

②每輛車必須從供應商出發，完成配送任務后返回該供應商；

③配送成本只與車輛啟用次數和配送距離有關。

3 模型構建

模型目標選擇為總成本最小，成本包含配送車輛的固定調用成本、變動成本和時間窗成本。其中配送成本由車輛的固定調用成本和變動成本構成，第i個加客戶的配送成本可以表示為：

(1)

時間窗成本：

(2)

模型構建如下：

(3)

s.t.:

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

其中，目標函數(3)表示的是整個配送過程中總成本最小；約束條件(4)表示某類貨物的配送量不能配送車輛的裝載容量；約束條件(5)表示一個客戶的某類貨物需求任務只由一輛配送車輛完成；約束條件(6)表示一個客戶的某類貨物需求任務只由一個供應商提供；約束條件(7)為車輛使用數量限制；約束條件(8)表示配送車量從供應商出發，完成任務后返回該供應商；約束條件(9)表示消除子回路；約束條件(10)表示車輛到達客戶的時間；約束條件(11)和(12)表示兩個決策變量均為0-1變量。

4 算例分析

4.1 算法設計

遺傳算法由于其全局優化性能良好、適應性強，在復雜的線性、非線性問題上表現出優秀的空間搜索能力，所以本文選用遺傳算法進行求解。

①編碼。

當遇到各種多決策變量情況，如組合服務、循環路徑、多任務等時，一維編碼方案表現能力大打折扣。因此Gottlieb等提出了矩陣編碼[6]，矩陣編碼是指采用矩陣的形式來對個體進行編碼。根據問題描述，對模型進行編碼設計，供應商數目為n，客戶數目為m，行表示出發點，列表示到達點，車輛旅行路徑可用一個矩陣表達。

②初始種群及適應度函數。

設置種群規模為θ，按照編碼規則隨機生成θ個滿足路徑約束、時間窗約束和配送量要求的染色體，適應度函數選擇F=minC。

③選擇、交叉與變異操作。

選擇操作部分，本文采用輪盤賭法，適應度值越大的個體，被選擇幾率越高。交叉操作部分，本算法采用多點交叉的方式，隨機選擇矩陣中多列進行交叉，交叉的概率取值范圍通常為[0.4，0.99]。變異操作部分隨機選擇矩陣，對其列進行變異操作。

④本文設置了遺傳算法的迭代次數，當遺傳操作達到該次數時，即終止操作。

4.2 實例分析

本文選取青島市某副食配送網絡，物流網絡內共有3個供應商和20個客戶，每個客戶訂貨量已知，車輛行駛速度為40km/h，固定調用成本為30元。供應商坐標分別為Ⅰ(120.335，36.134)、Ⅱ(120.217，36.072)、Ⅲ(120.135，36.066)，按照優先級，將客戶坐標分為λ1：(120.414，36.430)、(120.243，36.193)、(120.403，36.151)、(120.304，36.361)、(120.473，36.405)、(120.189，36.921)、(120.456，36.130)；λ2：(120.425，36.151)、(120.339，36.176)、(120.512，36.395)、(120.495，36.334)、(120.181，36.430)、(119.853，36.258)、(120.880，36.320)；λ3：(120.362，36.233)、(120.511，36.371)、(120.282，35.770)、(120.251，36.528)、(120.102，35.801)、(120.108，36.235)。

參數設置完畢后，在Matlab R2017b上進行算法的求解。遺傳算法中的參數設置如下：種群初始規模為50，迭代次數為300，交叉概率為0.6，變異概率為0.08。多次求解得到最終結果為配送方案A，啟用5輛配送車，總路程630.5km，總成本970.75元，其中時間窗成本為0。另外改變約束條件，求解原單供應商固定分區配送下方案B，啟用6輛配送車，總路程776km，總成本1110.9元，其中時間窗成本為70元。對比如表1所示。

表1 配送方案對比表

通過對比可以看出，三個供應商協同配送方案A相比傳統配送方案B的旅行距離節約18.75%，配送成本節約12.62%，時間窗匹配度增加10%。從整體角度看，共同配送的方式能夠最大化配送效益，減少車輛配送距離。

5 總結

本文構建了帶有軟時間窗的協同物流網絡中的車輛路徑問題模型，采用矩陣編碼的遺傳算法對問題進行了求解，并與傳統配送方式進行了對比。由于傳統配送方式下，供應商往往只能送達某一分區的客戶，多個分區獨立運行，導致成本較高。多供應商協同配送并考慮客戶時間窗的要求更符合實際情況，且能夠最大化協同物流網絡的整體效益。