陳妍，單汨源，王秋鳳

?

多車型集配貨一體化車輛路徑問題研究

陳妍1，單汨源1，王秋鳳2

(1. 湖南大學(xué)工商管理學(xué)院，湖南長沙，410082；2. 中南大學(xué)圖書館，湖南長沙，410083)

針對客戶存在收貨和發(fā)貨雙重需求的物流配送問題，討論具有多種車型的集配貨一體化車輛路徑問題。在綜合考慮各車型的固定成本和可變配送成本的前提下，以總成本最小為目標(biāo)，以盡可能提高車輛滿載率、減少出行次數(shù)為思路，構(gòu)建多車型集配貨一體化車輛路徑優(yōu)化模型?；谧钚〔迦胭M用法設(shè)計初始可行解生成算法，通過引入基于概率的多算子鄰域操作、最優(yōu)解記憶裝置、多準(zhǔn)則終止原則對模擬退火算法進(jìn)行改進(jìn)，給出求解思路。設(shè)計算例并對多車型單/雙向集配貨模型的求解結(jié)果進(jìn)行比較，以驗證模型的實用性和算法的有效性。研究結(jié)果表明：使用改進(jìn)后的模擬退火算法對構(gòu)建的多車型集配貨一體化車輛路徑問題模型求解更直接簡便，對多車型集配貨一體化車輛路徑優(yōu)化后能有效降低配送成本。

車輛路徑問題；多車型；集配貨一體化；模擬退火算法

車輛路徑問題(vehicle routing problem, VRP)是由Dantzig等[1]提出。國內(nèi)外對VRP研究較多，Solomn等[2?9]對VRP的研究主要集中在求解算法的改進(jìn)、約束條件的變換以及客戶信息的不確定性等討論上。隨著現(xiàn)代物流的不斷發(fā)展，一方面，越來越多的客戶同時擁有送貨與收貨需求；另一方面，隨著客戶量的增大，物流企業(yè)的配送和收貨業(yè)務(wù)都不斷增大，這2項業(yè)務(wù)的融合和有效完成成為降低物流成本的重要問題，這就形成了集配貨一體化車輛路徑問題(VRP with pick-up and delivering, VRPPD)，即需同時考慮配送和回收的車輛路徑問題。目前，人們對集配貨一體化路徑問題和多車型路徑問題均進(jìn)行了相關(guān)研究。對VRPPD問題研究均假設(shè)顧客點進(jìn)行集配貨服務(wù)的車輛是同質(zhì)的(homogeneous)，即車輛具有相同的裝載能力、相同的固定費用、相同的最大行駛距離約束等，并且通常假設(shè)車輛數(shù)無限[10?12]。而對多車型車輛路徑問題(heterogeneous)，主要研究多車場、動態(tài)需求、開放式等情況下的優(yōu)化方法[13?15]。事實上，多車型集配貨一體化是物流配送中更普遍的問題。在實際配送管理中，物流企業(yè)所擁有的車隊(fleet)一般由一組異型(heterogeneous)的車輛組成，這些車輛具有不同裝載能力、不同的單位旅行費用，使用車輛具有不同的固定成本，由于受資金約束，物流企業(yè)擁有的各種類型車輛數(shù)目也是有限的，同時，為了降低人力成本、車輛固定成本、車輛行駛成本、時間成本，物流企業(yè)更趨向于集配貨問題同時完成。本文作者研究車輛路徑問題即具有固定車輛數(shù)的多車型集配貨一體化車輛路徑問題(heterogeneous fixed fleet vehicle routing problem with pickups and deliveries, HFFVRPPD)。首先構(gòu)建多車型集配貨一體化車輛路徑問題的數(shù)學(xué)模型，其次給出模型求解算法，最后通過算例驗證該模型和算法的有效性。

1 問題描述與模型

1.1 問題描述

從圖論的角度，多車型集配貨一體化車輛路徑問題(HFFVRPPD)可定義如下：設(shè)為有向圖，={0, 1, 2, …,}表示節(jié)點集，，，表示邊集；節(jié)點0表示車場點，一組車輛從車場點出發(fā)對顧客點進(jìn)行配送服務(wù)；表示待服務(wù)的顧客點集合，顧客點的需求即配貨量為d，回收即集貨量為p；每條邊(,)賦有旅行距離D；車場點有1隊車輛，表示車輛類型集，，表示具體某種類型的車輛，類型車輛具有裝載能力Q，類型車輛具有最大行駛距離限制L；使用1輛類型車輛的固定費用為f；在節(jié)點對(,)間類型車輛的單位可變旅行費用為v；不同類型的車輛數(shù)固定且為n。HFFVRPPD的優(yōu)化目標(biāo)是：確定車輛路線集對個顧客點進(jìn)行集貨和配貨服務(wù)，使得總的運輸費用最小。運輸費用包括使用車輛的固定費用和車輛的旅行費用。這些車輛路線滿足以下要求：1) 車輛路線開始于車場點，并結(jié)束于車場點；2) 每個顧客點僅由1輛車服務(wù)，且其集配貨量需求必須得到滿足；3) 在整個集配貨過程中，所有車輛均不能超過其裝載能力；4) 每條車輛路線的行駛距離不能大于其最大允許行駛距離。

1.2 模型假設(shè)

為了方便建立數(shù)學(xué)模型描述HFFVRPPD問題，本文進(jìn)行如下假設(shè)：

1) 只有1個物流中心；

2) 物流中心與需求點的坐標(biāo)位置及集貨量和配貨量均已知；

3) 各種車型的車輛數(shù)已知，且各車型的固定費用、旅行費用、車容量均已知；

4) 不考慮配送時間限制；

5) 每輛車服務(wù)1條回路，由場站出發(fā)且最終回到場站；

6) 每輛車在行駛中的車載質(zhì)量不超過該車型的容量限制；

7) 每輛車每次的配送距離不超過該車型允許的最大行駛距離；

8) 每個需求點能且只能被服務(wù)1次，即服務(wù)1次并滿足需求點的集配貨要求；

9) 貨物在運輸途中不會變質(zhì)損壞；不考慮司機(jī)的工作時間；不考慮道路的通行情況；不考慮運輸時的規(guī)章制度等。

1.3 模型的建立

HFFVRPPD的數(shù)學(xué)模型可表示為

s.t.

，

其中：式(1)為目標(biāo)函數(shù)式，表示使總配送成本最小(總配送成本包括所有出行的各車型固定成本和旅行成本)；式(2)表示每個顧客都必須被某種車型的車服務(wù)1次，且僅被服務(wù)1次；式(3)為車流量守恒式；式(4)用于限制每輛貨車所有配貨量不得超過車容量；式(5)用于限制每輛貨車所有集貨量不得超過車容量；式(6)表示車輛在行駛過程中，任一顧客點的載質(zhì)量都不能超過車容量；式(7)表示每條配送路徑的長度不超過車輛1次配送的最大行駛距離。

2 算法設(shè)計

2.1 模擬退火算法

HFFVRPPD問題是一個NP難題，即使是對HFFVRP問題和VRPPD問題求解，規(guī)模稍大時精確算法幾乎不可行[14]，因此，多采用啟發(fā)式算法求解[15]。模擬退火算法的基本原理來自于固體加熱至一定的溫度后由固體結(jié)構(gòu)瓦解變?yōu)橐后w結(jié)構(gòu)，再對其降溫過程加以控制，使得分子在變回固體結(jié)構(gòu)時，能重新排列成所預(yù)期的穩(wěn)定狀態(tài)。模擬退火算法已在理論上被證明是一種以概率1收斂于全局最優(yōu)解的全局優(yōu)化算法，因此，研究新車輛路徑問題時常用此算法[16]。本文研究的HFFVRPPD問題用模擬退火算法可以描述為：該問題的1個解及其目標(biāo)函數(shù)()分別與固體的1個微觀狀態(tài)及其能量()等價。模擬退火算法步驟為(以目標(biāo)函數(shù)求最小為例)[17?19]：

步驟1：隨機(jī)得到1個初始可行解0。設(shè)定初始溫度0，令當(dāng)前解，當(dāng)前迭代步數(shù)，當(dāng)前溫度。

步驟2：若在該溫度達(dá)到內(nèi)循環(huán)停止條件，則轉(zhuǎn)步驟3；否則，從鄰域中隨機(jī)選擇1個鄰解，并計算。若，則；否則，若(表示1個0到1之間的均勻隨機(jī)數(shù))，則，重復(fù)步驟2)。

步驟4：輸出計算結(jié)果，算法停止。

內(nèi)循環(huán)為第2步，它表示在同一溫度下進(jìn)行隨機(jī)搜索。外循環(huán)主要包括步驟3中溫度下降、迭代步數(shù)增加和停止準(zhǔn)則。

2.2 算法流程及改進(jìn)

對算法進(jìn)行改進(jìn)往往可以獲得更優(yōu)的結(jié)果。結(jié)合多車型集配貨一體化車輛路徑問題的特點，對傳統(tǒng)的模擬退火算法加以改進(jìn)，構(gòu)造求解該問題的一種新的模擬退火算法。其改進(jìn)方法如下。

1) 初始可行解的產(chǎn)生。將解編碼為=(0—1— 2—3—4—0—5—6—7—8—0—…—0)的形式(其中0代表配送中心，表示其前1條線路的結(jié)束和后1條線路的開始)。對于車輛數(shù)既定的多車型集配貨一體化問題，尋找初始可行解有一定困難，本文按圖1所示流程產(chǎn)生初始解。其中，最小插入費用由下式計算：

2) 鄰域操作方法與可行解的判斷。傳統(tǒng)模擬退火算法采取的鄰域操作是2-Opt交換法。這種交換法簡單易行，每次只交換2個節(jié)點，但其搜索解空間的能力不強(qiáng)。因此，在每一溫度下，要保證得到該溫度下的1個優(yōu)解，就需要較長時間來搜索解空間。當(dāng)溫度緩慢降低時，外循環(huán)的次數(shù)增多，算法的時間呈倍數(shù)增加，從而導(dǎo)致整個算法搜索時間過長。

為增強(qiáng)搜索解空間的能力，鄰域操作采用4種交換算子基于概率隨機(jī)進(jìn)行，分別為SWAP算子、RELOCATE算子、2-Opt算子和2-Opt*算子，見圖2。

(a) SWAP算子；(b) RELOCATE算子；(c) 2-Opt算子；(d) 2-Opt*算子

采用組合算子的優(yōu)點是在相同的迭代步數(shù)下，雖然得到的解個數(shù)沒變，但搜索解空間范圍增大很多，再配合1個記憶數(shù)組就可以保證得到1個較滿意的優(yōu)解，因此，可以在較大程度上減小馬爾科夫鏈的長度，從而節(jié)省算法時間。采用以下方式判斷產(chǎn)生的新解是否為可行解。

步驟2：求出各線路總配貨量D和總集貨量P，若＞或＞，則轉(zhuǎn)步驟7，否則，轉(zhuǎn)步驟3。

步驟3：將各線路總配貨量D以及各車型Q降序排列，按車容量分配車型，若大于某車容量的線路條數(shù)超過了大于該車容量的車輛數(shù)，則轉(zhuǎn)步驟7，否則，轉(zhuǎn)步驟4。

步驟4：求出每條線路的總長L，若存在某線路的L大于其對應(yīng)車型的最大行駛距離L，則轉(zhuǎn)步驟7，否則，轉(zhuǎn)步驟5。

步驟5：計算各車型所在路線的每個顧客需求點上貨物量狀況，若貨物量大于該車型最大容量，則轉(zhuǎn)步驟7；否則轉(zhuǎn)步驟6。

步驟6：該解為可行解，計算該解的目標(biāo)函數(shù)值，評價該解。若符合終止條件，則算法終止，否則，轉(zhuǎn)步驟7。

步驟7：重新進(jìn)行鄰域操作，產(chǎn)生變換后的解，轉(zhuǎn)步驟1。

3) 記憶裝置的設(shè)計。傳統(tǒng)模擬退火算法輸出時不能保證是本次計算所搜尋到的最優(yōu)解，本文在算法中內(nèi)嵌1個記憶數(shù)組，用于傳導(dǎo)各優(yōu)解。算法開始時，將記憶數(shù)組初始化為初始解，即：，。若搜索到1個滿足各種約束的優(yōu)解，則對與進(jìn)行比較，若，則；通過與的比較，不斷更新，最后輸出，就可以得到本次搜尋的最優(yōu)解。

4) 終止準(zhǔn)則的確定。采用混合停止準(zhǔn)則，即當(dāng)溫度低于某值或者記憶數(shù)組連續(xù)次無變化時，算法終止。此策略簡單易行，與初始溫度0和降溫系數(shù)一起易于控制算法迭代的步數(shù)，易于得到全局最優(yōu)解，并由消除不必要的多余迭代，以減少迭代步數(shù)，提高算法效率。的取值根據(jù)節(jié)點規(guī)模而變化，節(jié)點規(guī)模大，則較大。

與傳統(tǒng)模擬退火算法相比，改進(jìn)的退火算法在尋優(yōu)能力、計算效率等方面都更加優(yōu)化。

3 算例

基于文獻(xiàn)[14]中的客戶需求數(shù)據(jù)和文獻(xiàn)[20]中的車輛信息，設(shè)計如下算例：1個配送中心擁有6種車型，要完成27個既有配貨又有集貨任務(wù)的顧客需求點的配送任務(wù)，要求確定選用哪些類型、每輛車的服務(wù)路線，使得完成整個配送過程的費用最低。各顧客點的相關(guān)信息見表1，車輛屬性相關(guān)參數(shù)見表2。

表1 顧客需求點集配貨量

表2 配送車輛屬性

采用本文給出的改進(jìn)模擬退火算法，初始溫度為100℃，馬爾科夫鏈長度即外循環(huán)迭代次數(shù)為100，降溫速度系數(shù)為0.98。當(dāng)溫度低于0.2℃或者記憶數(shù)組連續(xù)30次無變化時，算法終止。

利用本文所設(shè)計的算法對其求解，得到最小費用為1 465.98元。圖3所示為求解過程中溫度與目標(biāo)值變化曲線，其中橫軸為溫度，縱軸為目標(biāo)函數(shù)值。從圖3可以看出改進(jìn)后的模擬退火算法在跳出局部最優(yōu)解方面具有優(yōu)越性。最終的路徑安排如圖4所示，最優(yōu)結(jié)果的車型、數(shù)量及路線如表3所示。為比較單向配送與集配貨一體化配送成本，計算多車型單向配送的結(jié)果，見表4。同時，將單獨配送和集貨與集配貨一體化配送的結(jié)果進(jìn)行綜合比較，見表5。

圖3 退火尋優(yōu)過程圖

圖4 集配貨一體化最優(yōu)路線圖

表3 最優(yōu)計算結(jié)果

注：總配送量為7 060 kg；總貨量為6 270 kg；固定費用為555元；可變費用為910.98元；總運輸費用為1 465.98元。

表4 單一任務(wù)計算結(jié)果

表5 單向配送結(jié)果與集配貨一體化配送結(jié)果比較

從表4和表5可以看出：采用多車型單向配送模式時，為了分別達(dá)到最優(yōu)，配貨任務(wù)和集貨任務(wù)需要不同的車輛、不同的路線去完成任務(wù)，其中配貨任務(wù)用車6輛，集貨任務(wù)用車5輛。通過比較可以看出：相對多車型單向配送方式，多車型集配貨一體化配送方式降低了47.99%的成本，因此，對多車型集配貨一體化車輛路徑問題的探討有實際意義。同時，為檢驗對模擬退火算法改進(jìn)的效果，與傳統(tǒng)模擬退火算法求解結(jié)果進(jìn)行比較，結(jié)果如表6所示。

表6 改進(jìn)模擬退火算法與普通模擬退火算法求解結(jié)果比較

Table 6 Results comparison of improved simulated annealing algorithms and general simulated annealing algorithms

從表6可以看出改進(jìn)后的模擬退火優(yōu)越性較明顯：1) 由于改進(jìn)后的模擬退火算法通過4種交換算子實現(xiàn)多鄰域操作，使得搜索的空間更加大，更有利于跳出局部最優(yōu)，尋找全局最優(yōu)，因此，獲得的集配貨一體化配送方案的成本更低；2) 由于其采用了多準(zhǔn)則終止方法，省去了一些不必要的反復(fù)計算，因此，提高了計算效率，求解時間得到了有效降低。

4 結(jié)論

1) 根據(jù)實際配送中出現(xiàn)的多車型集配貨一體化問題，建立了HFFVRPPD模型。該模型考慮了不同車型有不同的車容量、不同的初始出行費用、不同的運價及其不同的最大行駛距離等，更加符合實際。

2) HFFVRPPD屬于NP-hard問題，因此，更適合采用啟發(fā)式算法進(jìn)行求解。求解時對傳統(tǒng)的模擬退火算法進(jìn)行改進(jìn)，包括設(shè)計HFFVRPPD初始可行解的產(chǎn)生算法、基于概率的多算子鄰域操作、記憶裝置的嵌入、多準(zhǔn)則終止方法等。

3) 本文提出的模型與算法對多車型集配貨車輛路徑優(yōu)化具有節(jié)省配送車輛、減少配送里程、降低配送成本、提高配送效益等優(yōu)點。

[1] Dantzig G, Ramser J. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80?91.

[2] Solomn M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254?265.

[3] Desrochers M, Desrosiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows[J]. Operations Research, 1992, 40(2): 342?354.

[4] George I, Manolis K, Gregory P. A problem generator-solver heuristic for vehicle routing with soft time windows[J]. Omega, 2003, 31(1): 41?53

[5] Ho S C, Hangland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers & Operations Research, 2004, 31: 1947?1961.

[6] 周科平, 翟建波. 改進(jìn)蟻群算法在地下礦山運輸路徑優(yōu)化的應(yīng)用[J]. 中南大學(xué)學(xué)報(自然科學(xué)版), 2014, 45(1): 256?261. ZHOU Keping, ZHAI Jianbo. Application of improved ant colony algorithm in route optimization of underground mine’s transportation[J]. Journal of Central South University (Science and Technology), 2014, 45(1): 256?261.

[7] 薛雪, 孫偉, 劉曉文. 露天煤礦車輛的不確定調(diào)度模型與優(yōu)化求解[J]. 中南大學(xué)學(xué)報(自然科學(xué)版), 2011, 42(5): 1354?1360. XUE Xue, SUN Wei, LIU Xiaowen. Uncertain scheduling model and optimization of vehicle in open mine[J]. Journal of Central South University (Science and Technology), 2011, 42(5): 1354?1360.

[8] 高顯龍, 許茂增, 王偉鑫. 多車型車輛路徑問題的量子遺傳算法研究[J]. 中國管理科學(xué), 2013, 21(1): 125?133. GAO Xianlong, XU Maozeng, WANG Weixin. Study on multi-types vehicle routing problem and its quantum genetic algorithm[J]. Chinese Journal of management Science, 2013, 21(1): 125?133.

[9] 李進(jìn), 傅培華. 具有固定車輛數(shù)的多車型低碳路徑問題及算法[J]. 計算機(jī)集成制造系統(tǒng), 2013, 19(6): 1351?1362. LI Jin, FU Peihua. Heterogeneous fixed fleet low-carbon routing problem and algorithm[J]. Computer Integrated Manufacturing Systems, 2013, 19(6): 1351?1362.

[10] 王曉博, 任春玉, 李海晨. 多車型開放式車輛路線問題的混合啟發(fā)式算法[J]. 計算機(jī)工程與應(yīng)用, 2013, 49(7): 243?247. WANG Xiaobo, REN Chunyu, LI Haichen. Hybrid heuristic algorithm for heterogeneous open vehicle routing problem[J]. Computer Engineering and Applications, 2013, 49(7): 243?247.

[11] 葛顯龍, 王旭, 邢樂斌. 動態(tài)需求的多車型車輛調(diào)度問題及云遺傳算法[J]. 系統(tǒng)工程學(xué)報, 2012, 27(6): 823?832. GE Xianlong, WANG Xu, XING Lebin. Multi-vehicle scheduling problems and cloud GA based on the dynamic needs[J]. Journal of Systems Engineering, 2012, 27(6): 823?832.

[12] 羅鴻斌. 多車場多車型車輛調(diào)度問題的改進(jìn)粒子群算法[J]. 計算機(jī)工程與應(yīng)用, 2014, 50(7): 251?253. LUO Hongbin. Study on multi-depots and multi-vehicles vehicle scheduling problem based on improved particle swarm optimization[J]. Computer Engineering and Applications, 2014, 50(7): 251?253.

[13] 劉云忠, 宣慧玉. 車輛路徑問題的模型及算法研究綜述[J]. 管理工程學(xué)報, 2005, 19(1): 124?130. LIU Yunzhong, XUAN Huiyu. Summarizing research on models and algorithms for vehicle routing problem[J]. Journal of Industrial Engineering and Engineering Management, 2005, 19(1): 124?130.

[14] Saez D, Cristian E, Nunez A. Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering[J]. Computers & Operations Research, 2008, 35(11): 3412?3438.

[15] Hoff A, Gribkovskaia I, Laporte G, et al. Lasso solution strategies for the vehicle routing problem with pickups and deliveries[J]. European Journal of Operational Research, 2009, 192(3): 755?799.

[16] Amico M D, Righini G, Salani M. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection[J]. Transportation Science, 2006, 40(12): 235?247.

[17] 陶胤強(qiáng), 牛惠民. 帶時間窗的多車型多費用車輛路徑問題的模型和算法[J]. 交通運輸系統(tǒng)工程與信息, 2008, 8(1): 113?117. TAO Yinqiang, NIU Huimin. Model and heuristic algorithm for the multi-type vehicles routing problem with multiple costs and time windows limits[J]. Journal of Transportation Systems Engineering and Information Technology, 2008, 8(1): 113?117.

[18] Lin S W, Yu V F, Chou S Y. Solving the truck and trailer routing problem based on a simulated annealing heuristic[J]. Computers & Operations Research, 2009, 36(5): 1683?1692.

[19] Toth P, Vigo D. The vehicle routing problem[M]. Siam, USA: Society for Industrial and Applied Mathematics, 2002: 10?40.

[20] 李相勇. 車輛路徑問題模型及算法研究[D]. 上海: 上海交通大學(xué)管理科學(xué)與工程, 2007: 56?78. LI Xiangyong. A study on models and algorithms for vehicle routing problems[D]. Shanghai: Shanghai Jiaotong University. Management Science and Engineering, 2007: 56?78.

Research on heterogeneous fixed fleet vehicle routing problem with pick-up and delivering

CHEN Yan1,SHAN Miyuan1, WANGQiufeng2

(1. School of Business Administration, Hunan University, Changsha 410082, China; 2. Library of Central South University, Changsha 410083, China)

Considering that heterogeneous fixed fleet vehicle routing problem with pickups and deliveries (HFFVRPPD) in logistics distribution is a widespread NP problem, which is more complex than single/multi vehicle with one way routing problem, HFFVRPPD optimization model was established to improve the load rate of vehicle, and reduce travel times. The algorithm of producing initial feasible solutions of the model was constructed, the improved simulated annealing algorithm was designed, which includes the operation of multi operators neighborhood based on the probability, embedding of memory devices, and the termination of many standard ways. The multi vehicle routing with one way problem and HFFVRPPD were compared to verify the effectiveness of the model and algorithm. The results show that the improved simulated annealing algorithm solving the HFFVRPPD is more convenient, and the HFFVRPPD optimization can effectively reduce the distribution costs.

vehicle routing problem; heterogeneous fixed fleet vehicle; pickups and deliveries; simulated annealing algorithm

10.11817/j.issn.1672-7207.2015.05.049

U492.2；TP301.6

A

1672?7207(2015)05?1938?08

2014?07?22；

2014?09?26

國家自然科學(xué)基金資助項目(70971036)；湖南省軟科學(xué)研究計劃項目(2013ZK3026) (Project(70971036) supported by the National Natural Science Foundation of China; Project(2013ZK3026) supported by Soft Science Research Plan of Hunan Province)

單汨源，教授，博士生導(dǎo)師，從事運營管理、項目管理與調(diào)度優(yōu)化研究；E-mail: yanchen@hnu.edu.cn

(編輯 陳燦華)