多車場多配送中心半開放式滿載車輛路徑問題研究

孫蕊　張麗華　趙麗娜　竇冰潔

摘 要：文章研究一個多車場多配送中心的半開放式滿載車輛路徑問題。在任務配送過程中需要考慮車輛的啟動費用、里程限制等約束條件，在不超過車輛里程限制的基礎上車輛可返回配送中心進行二次配送。建立了此類問題的數學模型，設計了解決該問題的遺傳算法，并通過例子對遺傳算法進行了說明。結果表明文章給出的遺傳算法對解決帶里程限制的多車場、多配送中心半開放式滿載車輛路徑問題是可行的。

關鍵詞：運籌學；半開放式車輛路徑問題；滿載；里程限制；遺傳算法

中圖分類號：F252.14 文獻標識碼：A

Abstract： In this paper， a multi-depot， multi-distribution centers semi-open vehicle routing problem with full-truckload is discussed. In the process of delivery， the start-up cost， driving distance restriction and other constraints need to be considered， and the vehicles can return to the distribution center for the secondary distribution if their driving distances are less or equal to the driving distance restriction. An integer programming model for this problem is established， a genetic algorithm is given to solve it， and the genetic algorithm is illustrated. The results show that the genetic algorithm given in this paper to solve the multi-depot， multi-distribution centers semi-open vehicle routing problem with full-truckload and driving distance restriction is feasible.

Key words： operational research； semi-open vehicle routing problem； full-truckload； driving distance restriction； genetic algorithm

0 引 言

車輛路徑問題（Vehicle Routing Problem， VRP）是交通運輸和物流配送系統中非常重要的問題，而對于大型的生產制造企業、煤炭運輸業等，由于被運輸的貨物需求量非常大，通常進行的都是整車運輸也就是滿載車輛路徑問題。

滿載車輛路徑問題是NP難問題，由Ball等人[1]首次提出，到目前為止國內外對此類問題已進行了一定的研究，根據現有的文獻，滿載車輛路徑問題按配送層數大致可歸為三類：

（1）兩層配送型：車輛從車場（或配送中心）直接裝貨出發，去往需求客戶點送貨之后返回原車場，郭海湘等[2]就研究了此類問題。

（2）帶有重載點的兩層配送型：車輛從車場空車出發，去往每個客戶指定的裝貨點取貨，再給相應的客戶（卸貨點）送貨。將每對裝貨點和卸貨點稱為一個重載點，如文獻[3-14]討論的都是兩層重載點問題或者是該問題的變種。此類問題現今研究的較多。

（3）三層配送型：車輛從車場空車開往配送中心，在配送中心裝貨去往需求的客戶點送貨。如：陳新莊等人[15]研究的多車場多配送中心滿載車輛路徑問題：車輛從車場出發可以去任一有能力的配送中心取貨送往需求客戶，完成配送任務后要求車輛返回原車場，范昌盛等人[16]將該問題擴展為車輛完成配送任務后不必返回原車場，但要保證各個車場派出和返回的車輛數相同的半開放式問題。三層配送問題研究相對較少，但隨著信息技術的發展和經濟全球化趨勢，越來越多的產品在世界范圍內生產、流通、銷售和消費，使得物流活動日益龐大和復雜，兩層配送方式已不能完全滿足社會需要，應運而生的第三方物流、電子商務等，使得三層物流配送問題變得越來越重要了。

本文在范昌盛等人[16]研究的三層配送車輛路徑問題的基礎上考慮了車輛的啟動費用以及各車輛配送線路長度相差不要過于懸殊等因素，將問題擴展為帶車輛啟動費用和車輛里程限制的半開放式滿載車輛路徑問題，即要求車輛在不超過其里程限制的基礎上可以從客戶處再返回配送中心進行二次取貨，之后給有需求的客戶進行配送，這樣不僅減少了車輛的使用數量，降低了費用，還使得司機的工作時間及車輛的使用比較均衡，從而使配送方案更符合實際需要。

1 問題描述

在一個連通的運輸網絡上有n個節點，其中節點1，2，…，m為車場，m+1，…，m+p為配送中心，m+p+1，…，m+p+qn=m+p+q為客戶。設各車場車型都相同，且第ii=1，…，m個車場停有a 輛車，而第jj=m+1，…，m+p個配送中心存儲的貨物量可以供給b 輛車整車運送，客戶點kk=m+p+1，…，m+p+q需要c 輛整車的貨物滿足其需求。

車輛從其所在車場空車出發到某一配送中心取貨送至某客戶處，之后它可以直接返回某車場（這種車輛被稱為不帶返回的車輛），也可再返回到某一有能力的配送中心取貨送給某個需求未滿足的客戶然后返回某車場（這種車輛被稱為帶返回的車輛），要求各車場派出與返回的車輛數相同。

本文將不帶返回車輛所行駛的最大里程設為車輛的里程限制，各個被使用車輛在不超過里程限制的基礎上，可返回有能力的配送中心進行二次配送，并且它們都有相同的啟動費用。求一個滿足上述要求的配送方案，使得所有被使用車輛總的行駛費用和總的啟動費用之和最小。endprint

2 數學建模

其中：（1）式右側第一項為所有被使用車輛從所在車場出發到相應配送中心的總空車行駛費用與總啟動費用之和；第二項為車輛從配送中心滿載貨物出發到客戶處所有車次的滿載行駛費用；第三項為所有被使用車輛從客戶點出發返回車場的空車行駛費用。（2）式表示從各配送中心發出的貨物數量不超過其存儲量。（3）式表示到達用戶的車輛次數等于其需求量。（4）式表示各被使用車輛行駛里程不超過里程限制。（5）式表示各車場發出與返回的車輛相同。

3 遺傳算法設計

因本文的問題允許車輛進行二次配送，而且還考慮了車輛的啟動費用和里程限制，所以范昌盛等人[16]論文中的算法不能解決此問題，本文給出下面的遺傳算法來求解它。

3.1 生成初始種群

種群規模設為含100條染色體。

（1）節點間的最短距離

用Floyd算法求原始運輸網絡中任意兩點i、j之間的最短距離，同時得到從節點i到節點j的最短距離路徑。

（2）可行解的類型

將本文所討論問題的一個可行配送方案稱為其一個可行解。在一個可行解中，如果所有使用車輛都是不帶返回的，就稱該解為不帶返回的可行解，若至少有一輛是帶返回的，就稱該解為帶返回的可行解。

（3）染色體的編碼

每一條染色體由兩部分組成，第一部分為問題的一個可行解（可能是帶返回的，也可能是不帶返回的），第二部分為該可行解的適應值。

設c=c +…+c 為所有客戶總的需求，本文用MATLAB實現遺傳算法，為此用一個c行6列的矩陣存儲一個可行解：該解中不帶返回車輛的路徑用該矩陣的一行來表示，該行的第1到第6個元素依次存儲0、該車輛出發車場序號、到達的配送中心序號、到達的客戶序號、返回的車場序號、該車經過上述節點的總行駛里程，而該解中某一帶返回車輛的路徑用這個矩陣的兩行來表示：這兩行的第1行6個元素依次存儲1、該車輛出發車場的序號、到達的配送中心序號、到達的客戶序號、0、經過上述節點的行駛里程；第2行6個元素依次存儲2、該車第一次到達的客戶序號、該車輛返回的配送中心序號、到達的客戶序號、返回的車場序號、經過上述節點的行駛里程。例如：本文第4節給出的例子中有2個車場、3個配送中心、7個客戶，客戶總需求為10整車，下列兩個10行6列矩陣（表1、表2）分別表示該實例的一個不帶返回和帶返回的可行解。

表1與表2中第1個元素為0的各行分別對應一不帶返回的車輛及其路徑，例如表1的第一行對應一車輛，該車從車場1出發到配送中心3取貨，將貨物送到客戶點9之后返回車場1，這之間總行駛里程為6；表2中第一個元素為1、2的兩行對應一帶返回的車輛，即表2的第1、2行，第3、4行，第6、7行分別對應一帶返回的車輛及其路徑，比如表2的第1、2行對應一帶返回的車輛其路徑為：該車從車場1出發到配送中心3取貨，將貨物送到客戶點9處，這之間該車行駛的總里程為5，之后該車返回到配送中心3取貨，將貨物送至給客戶點8處，最后返回車場1，這之間行駛的總里程為5，于是該車行駛的總里程為10，因此表1共使用10輛不帶返回車輛，表2共使用7輛車，其中4輛是不帶返回的，3輛是帶返回的。

用一個1行2列的元胞數組來存儲一條染色體：該元胞數組的第1個元素存儲一個可行解，第2個元素存儲該可行解的適應值。

每條染色體適應值的計算方法為：先求出該染色體對應的可行解中所有車輛總的行駛費用與總的啟動費用之和C，那么該染色體的適應值為1/C。

（4）帶返回可行解的生成方法

先根據問題的條件諸如車場、配送中心的個數及它們的能力，客戶的個數及其需求，隨機生成一個不帶返回的可行解，如表1所示，將該可行解中所有車輛的最大行程作為里程限制，在表1中第4、第7、第10行對應的車輛的行駛里程最長都是16，將16作為里程限制，將該可行解的各行按最后一個元素（各行對應車輛的行駛里程）從小到大順序排列，例如對表1實施該操作后得表3：

在表3中，根據里程限制判斷第10行對應車輛的配送任務能否交由第1行對應的車輛來完成，即判別第1行的車輛能否在給客戶9送完貨之后再返回某一有能力并且離客戶點9和客戶點8路程之和最小的配送中心取貨，將貨物送至客戶點8處再返回某一車場（要保證所有車場收發車數目相同）而總的行程不超過16，如果能，就將第10行對應的車輛刪除，而將其配送任務交給第1行對應的車輛完成，此時第1行對應的車輛送兩次貨：給客戶點9和客戶點8送貨，該輛車就由不帶返回的車輛變為帶返回的車輛，如果不能就對第9行對應的車輛進行判別，如此下去直到在第2行到第10行中找到第一個符合要求的行或第2行到第10行對應的車輛都不符合要求為止，在表3中第10行對應的車輛符合要求，于是它的配送任務就交由第1行對應的車輛來完成，而表3被修改為表4。在將表3修改為表4的過程中，表3的第2至9行的內容有可能被修改，這是因為需要保證各個車場收發車的數目相同所致，如果被修改了，就將表4中第3至10行按最后一個元素（行駛里程）從小到大進行排列，之后對表4的第3行實施對表3的第1行同樣的操作，…，最后得到表2這個帶返回的可行解，將該可行解與其適應值放在一個1行2列的元胞數組中作為一條染色體。

用上述方法生成100條染色體，將它們存儲到一個100行2列的元胞數組中作為初始種群。

3.2 個體的選擇

用輪盤賭在父代中隨機選擇子代的個體，并使用精英保留策略， 即用父代的最好解代替選擇操作后得到的最差解。

3.3 交叉和變異

交叉：取交叉概率為0.6，對滿足交叉概率的兩條染色體還需滿足下列條件才進行交叉：它們對應的兩個可行解中：（1）都有不帶返回的車輛，（2）在不帶返回的車輛中都有出發車場與返回車場相同的車輛，（3）在滿足（1）和（2）的車輛里能各選出一輛，使得這兩輛車對應的車場和配送中心都有能力，那么這兩條染色體就可以交叉：交換兩輛車的車場和配送中心，客戶保持不變，并重新計算總里程。endprint

例如：表5也表示本文第4節例子的一個可行解（帶返回的），該解與表2表示的可行解滿足上述條件（1）～（3），這是因為表2的第9行與表5的第10行分別為：

交叉后這兩行依次變為：

變異：取變異概率為0.4，對滿足變異概率的染色體，將其對應的可行解中第1個元素為0或1的行中第3個元素（配送中心）進行修改：在有能力的配送中心中尋找一個使其到這些行對應車輛出發的車場和送貨客戶總行程最近的配送中心，用它去替換該行的配送中心，例如在表5中，第1、第3、第4、第6行，第8到第10行的第3個元素（配送中心）都要做修改，比如第3行需要在有能力的配送中心：3、5中尋找一個到車場1和客戶點6總的行程最近的配送中心來替換配送中心3，表5經變異操作后變為表6。

4 例 子

本文采用文獻[16]的例子：某一有12個節點的網絡（如圖1所示），圖1給出了原始運輸網絡的連接狀況和相鄰兩節點間的距離。

在圖1中，節點1、2為車場，3、4、5為配送中心，6～12為客戶，表7給出了每個車場擁有的車輛數、每個配送中心存放的貨物數（整車）和每個用戶點需要的貨物數（整車）。

設每輛車的啟動費為3，當λ =λ =1時，運行第3節給出的遺傳算法后得到該例子的一個次優解，該次優解一共使用了5輛車，即一共有5條路徑如表8所示。

這5條路徑的長度依次為：14，12，12，16，13，因此5條路徑的長度之和為67，該次優解其目標函數值為：3×5+67=82，其中3×5是5輛車總的啟動費用。

文獻[16]得到的本例的次優解一共使用10輛車，即一共有10條路徑如表9所示，這10條路徑的長度依次為：4，6，6，6，6，6，12，7，10，9，得10條路徑的長度之和為72，該次優解的目標函數值為：3×10+72=102，其中3×10為10輛車的總啟動費用。

表8中第1條路徑的含義是：車輛從車場1出發，經車場1到配送中心4的最短路徑1→4到配送中心4取貨，再經配送中心4到客戶點7的最短路徑4→7給客戶點7送貨，之后經客戶點7到配送中心5的最短路徑7→12→5返回到配送中心5取貨，再經配送中心5到客戶點12的最短路徑5→12給客戶點12送貨，最后經客戶點12到車場1的最短路徑12→7→1返回車場1， 同理可得表8中其它路徑以及表9中各條路徑的含義。

對上述兩個次優解比較發現：本文得到的次優解：（1）車輛使用數量少；（2）各條線路長短比較均衡，因此各輛車的使用量以及司機工作量大致相同，更符合實際需求；（3）目標函數值小，結果更優。

5 結 論

本文利用遺傳算法解決了一個帶里程限制的多車場、多配送中心半開放式的滿載車輛路徑問題，并要求車輛在不超過其里程限制的基礎上允許返回配送中心進行二次配送。通過例子對本文的問題及給出的遺傳算法進行了說明，通過比較發現，本文的問題更符合實際配送需求，給出的算法得到的結果更優。

參考文獻：

[1] Ball M， Golden B L， Assad A A. Planning for truck fleet size in the presence of a common-carrier option[J]. Decision Science， 1993（14）：103-120.

[2] 郭海湘，楊娟，等. 帶服務優先級的煤礦資源配送車輛路徑問題[J]. 系統管理學報，2012，21（1）：133-144.

[3] 郭耀煌，李軍. 滿載問題的車輛路線安排[J]. 系統工程學報，1995，10（2）：106-118.

[4] Arunapuram S， Mathur K， Solow D. Vehicle routing and scheduling with full truckloads[J]. Transportation Science， 2003，37（2）：170-182.

[5] Gronalt M， Hartl R F， Reimann M. New savings bas-ed algorithms for time constrained pickup and delivery of full truckloads[J]. European Journal of Operational Research， 2003，151（3）：520-535.

[6] 劉冉，江志斌，陳峰，等. 多車場滿載協同運輸問題模型與算法[J]. 上海交通大學學報，2009，43（3）：455-459.

[7] 霍佳震，張磊. 用節約法解決帶有時間窗的滿載車輛調度問題[J]. 工業工程與管理，2006，11（4）：39-42.

[8] 孫國華. 帶軟時間窗的開放式滿載車輛路徑問題研究[J]. 計算機工程與應用，2011，47（17）：13-17.

[9] 孫國華. 帶時間窗的開放式滿載車輛路徑問題建模及其求解算法[J]. 系統工程理論與實踐，2012，32（8）：1801-1806.

[10] Liu R， Jiang Z， Liu X， et al. Task selection and routing problems in collaborative truckload transportation[J]. Transportation Research Part E： Logistics and Transportation Review， 2010，46（6）：1071-1085.

[11] Liu R， Jiang Z， Fung R Y K， et al. Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration[J]. Computers & Operations Research， 2010，37（5）：950-959.

[12] Wang X， Kopfer H. Rolling horizon planning for a dynamic collaborative routing problem with full-truckload pickup and delivery requests[J]. Flexible Services and Manufacturing Journal， 2015（5）：1-25.

[13] Chebbi O， Chaouachi J. Multi-objective iterated greedy variable neighborhood search algorithm for solving a full-load automated guided vehicle routing problem with battery constraints[J]. Electronic Notes in Discrete Mathematics， 2015，47：165-172.

[14] Bai R， Xue N， Chen J， et al. A set-covering model for a bidirectional multi-shift full truckload vehicle rout-ing problem[J]. Transportation Research Part B： Methodological， 2015，79：134-148.

[15] 陳新莊，郭強，范昌勝. 多車場滿載車輛路徑優化算法[J]. 計算機工程與設計，2008，29（22）：5866-5868.

[16] 范昌勝，郭強，岳愛峰. 多車場滿載車輛路徑問題遺傳算法[J]. 陜西科技大學學報，2011，29（2）：69-74.endprint