求解多集散點車輛路徑問題的順路捎帶法

摘要:為了更好的解決多集散點車輛路徑問題，文章突破了傳統MDVRP研究中一個客戶的訂單只能由一輛車承載的限制，提出了一種新的算法.闡述了算法的基本原理，結合有效運輸值，給出了算法具體的順路捎帶規則。通過實例證明該算法在求解多集散點車輛路徑問題時是有效的。

關鍵詞:多集散點;車輛路徑問題;順路捎帶法;有效運輸

一、 引言

車輛路徑問題(Vehicle Routing Problem VRP)是由Dantzig和Ramser于1959年首次提出來的，是運籌學、應用數學、網絡分析、圖論、計算機應用及交通運輸等學科研究的一個熱點問題，也是典型的NP難題.近年來，國內外學者對VRP的研究多集中在單車場的車輛路徑安排上，較少關注多車場情況下的車輛路徑問題。

多集散點車輛路徑問題(Multi-Depot Vehicle Routing Problem，MDVRP)的解決方法比單車場條件下更加復雜，特別是當節點規模較大時，將很難得到問題的精確解.探討如何經過少量計算，得到一個相對滿意的解成為現階段學者研究的重點.Polacek利用可變鄰域搜索法(Variable Neighborhood Search)求解帶時間窗的MDVRP;Laporte分別針對對稱和非對稱的多車場車輛路徑問題提出來分支定界法;張明善等通過建立網絡流模型，給出了網絡流算法;鐘石泉等對有容量、時間窗、多車型等約束條件的MDVRP給出了針對具體約束的禁忌算法(Tabu Search Algorithm);鄒彤等對染色體編碼進行改進，提出了能夠表示每個車場所出動的車輛及其行駛路徑的新的染色體編碼，利用遺傳算法(Genetic Algorithm，GA)解決了該問題;王素欣等建立以訂單為基準的貨運車輛路徑問題模型，利用蟻群算法(Ant Colony Optimization，ACO)解決了該問題。

但是，通過分析我們不難發現，傳統的多集散點車輛路徑問題研究中，都限定每個客戶的訂單都必須且僅能由一輛車運送，這種限制在具體運輸過程中是不現實的。為了突破這種限制，本文嘗試用一種新的算法來解決該問題。

二、 MDVRP的模型

對于本文所要解決的多集散點車輛路徑問題具體界定如下:某第三方物流公司在一段時間內有多項配送任務或訂單需要完成.每項配送任務由配送的起點、終點、配送量構成。如配送任務Rij(i，j，qij)，其中i表示配送的起點，j表示終點，qij表示配送量。要求合理安排行車路線，在完成配送任務的前提下使總的行駛距離最短。

根據以上描述，對MDVRP模型進行以下假設:①每項配送任務的配送量不超過車輛的最大載重量且車輛容量相同;②車輛行駛距離不能超過其最大行駛里程;③車輛完成所有配送任務后原地待命，不需要回到初始出發點;④每個集散點可由不同的車輛多次訪問。

由以上分析建立模型如下:

目標函數:

其中i，j∈V，V為節點的集合;l∈NV，NV為車輛集合; X1ij表示編號為l的車輛是否從節點i載向節點j，如果是，X1ij=1，否則，X1ij=0;dij表示節點i，j間的距離;Qv為車輛最大載重量;q1j表示編號為l的車輛開往集散點j時車上貨物的重量;Lmax為車輛行駛的最大里程數。

上述模型中，(1)將車輛總路徑最小為優化目標;(2)、(3)分別表示配送量、車上貨物重量不超過車輛的最大載重量;(4)車輛行駛距離不超過其最大里程數。

三、 順路捎帶法及有效運輸

在以往的研究中，每個客戶的訂單都由一輛車獨自完成。車輛在配送任務的起點載貨，終點卸貨。在運輸過程中，雖途經不同的節點，但是在到達配送任務的終點前，不允許中途卸貨。這種運輸方式將每輛車都看作彼此之間相互獨立的個體，個體之間獨自完成配送任務，忽略了個體在運輸過程中的合作關系。順路捎帶法就是建立在車輛合作運輸思想上的，通過一定方式的合作，車輛可以有效的提高滿載率，減少運輸距離，優化行駛路徑。

1. 順路捎帶法的基本原理。所謂順路捎帶法是指，以合作運輸為前提，不同的車輛在運輸過程中，依據有效運輸值的大小，將同一個訂單的貨物逐漸運送至離目標節點距離更近的節點上。如有配送任務R12(1，2，q12)、R13(1，2，q13)，同時在節點1有途經節點2的車輛k，若滿足條件:(1)k有富余的運載能力，(2)距離d23

2. 有效運輸及有效運輸值。在運輸過程中，若總的配送任務確定，則總的配送量也確定，因此，車輛在單位距離內載貨量越大，總的運輸距離就越短，運輸成本就越低，運輸也就越有效。則:(1)有訂單Rij(i，j，qij)，如車輛將Rij從節點i運送至節點j，則對Rij來說是有效運輸，有效運輸值為qij/dij;(2)有訂單Rik(i，k，qik)，如車輛將Rik從節點i運送至節點j，且滿足djk

3. 順路捎帶規則。

(1)初始節點選擇。依據假設:車輛在完成配送任務后，不用回到出發點，而是在原地等待下一個配送任務，因此在初始階段，車輛不是集中在某個節點處，而是分散在各個節點處。這些節點有可能是下一個配送任務的起點，也可能是下一個配送任務的終點，還有可能沒有任何任務。為縮短車輛運輸距離，減少無效運輸，設定處在配送任務起點處的車輛，直接從該節點開始進行配送，不在配送任務起點處的車輛，先轉移至起點后，再開始配送。為方便運算，作者利用所有配送任務起點的集合為每輛車生成二維禁忌表Tabu[I][NV]， 其中I是配送任務起點的集合，NV為車輛的集合，元素til∈Tabu[I][NV]，若til=1表示編號為I的車輛未訪問過起點i，否則til=0。因為集散點多且集散點多訂單，所以每個節點允許被不同的車輛多次訪問。

為了防止算法陷入過早收斂，采用確定性選擇和隨機性選擇相結合的策略來提高全局搜索能力，即在算法的第一步，車輛都是根據二維禁忌表Tabu[I][NV]隨機選擇配送任務的起點，那些本身就處在起點處的車輛除外。

(2)車輛轉移規則。車輛在轉移過程中，依據有效運輸值的大小動態的選擇下一個節點，而在選擇過程中，最可能的就是選擇所在節點處所有配送任務中、某一項配送任務的終點，或者根據二維禁忌表Tabu[I][NV]選擇某一未訪問的起點，因此，在計算有效運輸值時只針對這些節點進行計算，以減少計算量，縮短計算時間。

(3)貨物裝載規則.當車輛 到達節點 時，由于存在順路捎帶，車輛可能同時面對三種不同類型的訂單:以i為起點的訂單;以i為終點的訂單;以別的節點為起點還未完成的訂單。為方便運算，在計算有效運輸值時，所有訂單的起點均為i。在計算過程中，那些以i為終點的訂單會因為起點終點相同，距離為零而自動被保留在i點，即完成該項配送任務。另外兩類訂單，1在容量限制的前提下，盡可能的滿載，并選擇有效運輸值最大的訂單組合進行配送。

四、 仿真實驗

某第三方物流公司在某一時刻的配送任務如表1所示，各節點坐標如表2所示.在這些節點中有的節點只運入貨物，如節點1，11;有的節點只運出貨物，如節點9，14;有的節點既有運入也有運出的貨物，如節點6，7，10，并且節點7和10之間均有貨物運送到對方。

假設車輛初始點分別為4，2，9，最大載重量QV=10t，出行最大里程Lmax=100km ，要求在不超載的情況下，合理安排車輛行車路線，以最小的成本完成所有配送任務。

用Java語言設計并實現，共進行40次運算，得到最小總路徑長度為113.33km，所有配送任務由3輛車聯合完成，各條路徑的詳細信息見表3。在運輸過程中，車輛依據有效運輸值，動態的對訂單進行順路捎帶，將訂單的貨物逐漸運送至距離目標節點更近的節點上，如訂單R2，13(2，13，1.5)首先被車輛2捎帶至節點7，然后被車輛1捎帶至節點6，最后由車輛3運送至終點，完成該訂單的配送;訂單R10，5(10，5，3)先被車輛1捎帶至節點7，然后由車輛3完成該訂單的配送;訂單R2，13(2，13，1.5)先被車輛1捎帶至節點10，最后由車輛2運輸至配送任務的終點。

五、 結論

重新描述了多集散點車輛路徑問題的實際背景，用配送任務將貨運關系清晰化;提出順路捎帶法，突破了一個客戶的訂單只能由一輛車運送的限制，提高了車輛的滿載率，減少了車輛的行駛距離;量化了有效運輸，給出了有效運輸值的計算方法，為順路捎帶提供了依據。

參考文獻:

1. Ramser D. The truck dispatching problem. Mgt Sci，1959，(6):81-89.

2. Polacek M， Hartl R F， Doerner K， et al. A variable neighborhood search for the multi depot vehicle routing problem with time windows. Springer Netherlands. Journal of Heuristics，2004，10(6):613-627.

3. 張明善，唐小我.多車場滿載貨運車輛優化調度的網絡流算法.系統工程學報，2002，17(3):216-220.

4. 鐘石泉，賀國光.多車場有時間窗的多車型車輛調度及其禁忌算法研究.運籌學學報，2005，9(4):67-73.

基金項目:國家社會科學基金資助項目(07CTQ007)。

作者簡介:牟小俐，重慶大學經濟與工商管理學院副教授;唐純金，重慶大學經濟與工商管理學院碩士生。

收稿日期:2009-12-17。