多車場(chǎng)多配送中心半開(kāi)放式滿載車輛路徑問(wèn)題研究

孫蕊　張麗華　趙麗娜　竇冰潔

摘 要：文章研究一個(gè)多車場(chǎng)多配送中心的半開(kāi)放式滿載車輛路徑問(wèn)題。在任務(wù)配送過(guò)程中需要考慮車輛的啟動(dòng)費(fèi)用、里程限制等約束條件，在不超過(guò)車輛里程限制的基礎(chǔ)上車輛可返回配送中心進(jìn)行二次配送。建立了此類問(wèn)題的數(shù)學(xué)模型，設(shè)計(jì)了解決該問(wèn)題的遺傳算法，并通過(guò)例子對(duì)遺傳算法進(jìn)行了說(shuō)明。結(jié)果表明文章給出的遺傳算法對(duì)解決帶里程限制的多車場(chǎng)、多配送中心半開(kāi)放式滿載車輛路徑問(wèn)題是可行的。

關(guān)鍵詞：運(yùn)籌學(xué)；半開(kāi)放式車輛路徑問(wèn)題；滿載；里程限制；遺傳算法

中圖分類號(hào)：F252.14 文獻(xiàn)標(biāo)識(shí)碼：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 引 言

車輛路徑問(wèn)題（Vehicle Routing Problem， VRP）是交通運(yùn)輸和物流配送系統(tǒng)中非常重要的問(wèn)題，而對(duì)于大型的生產(chǎn)制造企業(yè)、煤炭運(yùn)輸業(yè)等，由于被運(yùn)輸?shù)呢浳镄枨罅糠浅４螅ǔ＿M(jìn)行的都是整車運(yùn)輸也就是滿載車輛路徑問(wèn)題。

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

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

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

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

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

1 問(wèn)題描述

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

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

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

2 數(shù)學(xué)建模

其中：（1）式右側(cè)第一項(xiàng)為所有被使用車輛從所在車場(chǎng)出發(fā)到相應(yīng)配送中心的總空車行駛費(fèi)用與總啟動(dòng)費(fèi)用之和；第二項(xiàng)為車輛從配送中心滿載貨物出發(fā)到客戶處所有車次的滿載行駛費(fèi)用；第三項(xiàng)為所有被使用車輛從客戶點(diǎn)出發(fā)返回車場(chǎng)的空車行駛費(fèi)用。（2）式表示從各配送中心發(fā)出的貨物數(shù)量不超過(guò)其存儲(chǔ)量。（3）式表示到達(dá)用戶的車輛次數(shù)等于其需求量。（4）式表示各被使用車輛行駛里程不超過(guò)里程限制。（5）式表示各車場(chǎng)發(fā)出與返回的車輛相同。

3 遺傳算法設(shè)計(jì)

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

3.1 生成初始種群

種群規(guī)模設(shè)為含100條染色體。

（1）節(jié)點(diǎn)間的最短距離

用Floyd算法求原始運(yùn)輸網(wǎng)絡(luò)中任意兩點(diǎn)i、j之間的最短距離，同時(shí)得到從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離路徑。

（2）可行解的類型

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

（3）染色體的編碼

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

設(shè)c=c +…+c 為所有客戶總的需求，本文用MATLAB實(shí)現(xiàn)遺傳算法，為此用一個(gè)c行6列的矩陣存儲(chǔ)一個(gè)可行解：該解中不帶返回車輛的路徑用該矩陣的一行來(lái)表示，該行的第1到第6個(gè)元素依次存儲(chǔ)0、該車輛出發(fā)車場(chǎng)序號(hào)、到達(dá)的配送中心序號(hào)、到達(dá)的客戶序號(hào)、返回的車場(chǎng)序號(hào)、該車經(jīng)過(guò)上述節(jié)點(diǎn)的總行駛里程，而該解中某一帶返回車輛的路徑用這個(gè)矩陣的兩行來(lái)表示：這兩行的第1行6個(gè)元素依次存儲(chǔ)1、該車輛出發(fā)車場(chǎng)的序號(hào)、到達(dá)的配送中心序號(hào)、到達(dá)的客戶序號(hào)、0、經(jīng)過(guò)上述節(jié)點(diǎn)的行駛里程；第2行6個(gè)元素依次存儲(chǔ)2、該車第一次到達(dá)的客戶序號(hào)、該車輛返回的配送中心序號(hào)、到達(dá)的客戶序號(hào)、返回的車場(chǎng)序號(hào)、經(jīng)過(guò)上述節(jié)點(diǎn)的行駛里程。例如：本文第4節(jié)給出的例子中有2個(gè)車場(chǎng)、3個(gè)配送中心、7個(gè)客戶，客戶總需求為10整車，下列兩個(gè)10行6列矩陣（表1、表2）分別表示該實(shí)例的一個(gè)不帶返回和帶返回的可行解。

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

用一個(gè)1行2列的元胞數(shù)組來(lái)存儲(chǔ)一條染色體：該元胞數(shù)組的第1個(gè)元素存儲(chǔ)一個(gè)可行解，第2個(gè)元素存儲(chǔ)該可行解的適應(yīng)值。

每條染色體適應(yīng)值的計(jì)算方法為：先求出該染色體對(duì)應(yīng)的可行解中所有車輛總的行駛費(fèi)用與總的啟動(dòng)費(fèi)用之和C，那么該染色體的適應(yīng)值為1/C。

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

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

在表3中，根據(jù)里程限制判斷第10行對(duì)應(yīng)車輛的配送任務(wù)能否交由第1行對(duì)應(yīng)的車輛來(lái)完成，即判別第1行的車輛能否在給客戶9送完貨之后再返回某一有能力并且離客戶點(diǎn)9和客戶點(diǎn)8路程之和最小的配送中心取貨，將貨物送至客戶點(diǎn)8處再返回某一車場(chǎng)（要保證所有車場(chǎng)收發(fā)車數(shù)目相同）而總的行程不超過(guò)16，如果能，就將第10行對(duì)應(yīng)的車輛刪除，而將其配送任務(wù)交給第1行對(duì)應(yīng)的車輛完成，此時(shí)第1行對(duì)應(yīng)的車輛送兩次貨：給客戶點(diǎn)9和客戶點(diǎn)8送貨，該輛車就由不帶返回的車輛變?yōu)閹Х祷氐能囕v，如果不能就對(duì)第9行對(duì)應(yīng)的車輛進(jìn)行判別，如此下去直到在第2行到第10行中找到第一個(gè)符合要求的行或第2行到第10行對(duì)應(yīng)的車輛都不符合要求為止，在表3中第10行對(duì)應(yīng)的車輛符合要求，于是它的配送任務(wù)就交由第1行對(duì)應(yīng)的車輛來(lái)完成，而表3被修改為表4。在將表3修改為表4的過(guò)程中，表3的第2至9行的內(nèi)容有可能被修改，這是因?yàn)樾枰ＷC各個(gè)車場(chǎng)收發(fā)車的數(shù)目相同所致，如果被修改了，就將表4中第3至10行按最后一個(gè)元素（行駛里程）從小到大進(jìn)行排列，之后對(duì)表4的第3行實(shí)施對(duì)表3的第1行同樣的操作，…，最后得到表2這個(gè)帶返回的可行解，將該可行解與其適應(yīng)值放在一個(gè)1行2列的元胞數(shù)組中作為一條染色體。

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

3.2 個(gè)體的選擇

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

3.3 交叉和變異

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

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

交叉后這兩行依次變?yōu)椋?/p>

變異：取變異概率為0.4，對(duì)滿足變異概率的染色體，將其對(duì)應(yīng)的可行解中第1個(gè)元素為0或1的行中第3個(gè)元素（配送中心）進(jìn)行修改：在有能力的配送中心中尋找一個(gè)使其到這些行對(duì)應(yīng)車輛出發(fā)的車場(chǎng)和送貨客戶總行程最近的配送中心，用它去替換該行的配送中心，例如在表5中，第1、第3、第4、第6行，第8到第10行的第3個(gè)元素（配送中心）都要做修改，比如第3行需要在有能力的配送中心：3、5中尋找一個(gè)到車場(chǎng)1和客戶點(diǎn)6總的行程最近的配送中心來(lái)替換配送中心3，表5經(jīng)變異操作后變?yōu)楸?。

4 例 子

本文采用文獻(xiàn)[16]的例子：某一有12個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)（如圖1所示），圖1給出了原始運(yùn)輸網(wǎng)絡(luò)的連接狀況和相鄰兩節(jié)點(diǎn)間的距離。

在圖1中，節(jié)點(diǎn)1、2為車場(chǎng)，3、4、5為配送中心，6～12為客戶，表7給出了每個(gè)車場(chǎng)擁有的車輛數(shù)、每個(gè)配送中心存放的貨物數(shù)（整車）和每個(gè)用戶點(diǎn)需要的貨物數(shù)（整車）。

設(shè)每輛車的啟動(dòng)費(fèi)為3，當(dāng)λ =λ =1時(shí)，運(yùn)行第3節(jié)給出的遺傳算法后得到該例子的一個(gè)次優(yōu)解，該次優(yōu)解一共使用了5輛車，即一共有5條路徑如表8所示。

這5條路徑的長(zhǎng)度依次為：14，12，12，16，13，因此5條路徑的長(zhǎng)度之和為67，該次優(yōu)解其目標(biāo)函數(shù)值為：3×5+67=82，其中3×5是5輛車總的啟動(dòng)費(fèi)用。

文獻(xiàn)[16]得到的本例的次優(yōu)解一共使用10輛車，即一共有10條路徑如表9所示，這10條路徑的長(zhǎng)度依次為：4，6，6，6，6，6，12，7，10，9，得10條路徑的長(zhǎng)度之和為72，該次優(yōu)解的目標(biāo)函數(shù)值為：3×10+72=102，其中3×10為10輛車的總啟動(dòng)費(fèi)用。

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

對(duì)上述兩個(gè)次優(yōu)解比較發(fā)現(xiàn)：本文得到的次優(yōu)解：（1）車輛使用數(shù)量少；（2）各條線路長(zhǎng)短比較均衡，因此各輛車的使用量以及司機(jī)工作量大致相同，更符合實(shí)際需求；（3）目標(biāo)函數(shù)值小，結(jié)果更優(yōu)。

5 結(jié) 論

本文利用遺傳算法解決了一個(gè)帶里程限制的多車場(chǎng)、多配送中心半開(kāi)放式的滿載車輛路徑問(wèn)題，并要求車輛在不超過(guò)其里程限制的基礎(chǔ)上允許返回配送中心進(jìn)行二次配送。通過(guò)例子對(duì)本文的問(wèn)題及給出的遺傳算法進(jìn)行了說(shuō)明，通過(guò)比較發(fā)現(xiàn)，本文的問(wèn)題更符合實(shí)際配送需求，給出的算法得到的結(jié)果更優(yōu)。

參考文獻(xiàn)：

[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] 郭海湘，楊娟，等. 帶服務(wù)優(yōu)先級(jí)的煤礦資源配送車輛路徑問(wèn)題[J]. 系統(tǒng)管理學(xué)報(bào)，2012，21（1）：133-144.

[3] 郭耀煌，李軍. 滿載問(wèn)題的車輛路線安排[J]. 系統(tǒng)工程學(xué)報(bào)，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] 劉冉，江志斌，陳峰，等. 多車場(chǎng)滿載協(xié)同運(yùn)輸問(wèn)題模型與算法[J]. 上海交通大學(xué)學(xué)報(bào)，2009，43（3）：455-459.

[7] 霍佳震，張磊. 用節(jié)約法解決帶有時(shí)間窗的滿載車輛調(diào)度問(wèn)題[J]. 工業(yè)工程與管理，2006，11（4）：39-42.

[8] 孫國(guó)華. 帶軟時(shí)間窗的開(kāi)放式滿載車輛路徑問(wèn)題研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2011，47（17）：13-17.

[9] 孫國(guó)華. 帶時(shí)間窗的開(kāi)放式滿載車輛路徑問(wèn)題建模及其求解算法[J]. 系統(tǒng)工程理論與實(shí)踐，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] 陳新莊，郭強(qiáng)，范昌勝. 多車場(chǎng)滿載車輛路徑優(yōu)化算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（22）：5866-5868.

[16] 范昌勝，郭強(qiáng)，岳愛(ài)峰. 多車場(chǎng)滿載車輛路徑問(wèn)題遺傳算法[J]. 陜西科技大學(xué)學(xué)報(bào)，2011，29（2）：69-74.endprint