□ 劉 璽

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

1 引言

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

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

2 問題描述與假設條件

2.1 問題描述

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

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

2.2 條件假設

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

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

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

3 模型構建

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

(1)

時間窗成本：

(2)

模型構建如下：

(3)

s.t.:

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

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

4 算例分析

4.1 算法設計

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

①編碼。

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

②初始種群及適應度函數(shù)。

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

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

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

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

4.2 實例分析

本文選取青島市某副食配送網(wǎng)絡，物流網(wǎng)絡內共有3個供應商和20個客戶，每個客戶訂貨量已知，車輛行駛速度為40km/h，固定調用成本為30元。供應商坐標分別為Ⅰ(120.335，36.134)、Ⅱ(120.217，36.072)、Ⅲ(120.135，36.066)，按照優(yōu)先級，將客戶坐標分為λ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)。

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

表1 配送方案對比表

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

5 總結

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