帶訂單選擇車輛路徑問(wèn)題的模型與算法

孫劉誠(chéng)，孫 焰

(同濟(jì)大學(xué)道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室，上海201804)

0 引言

物流是社會(huì)活動(dòng)的經(jīng)濟(jì)基礎(chǔ)，然而由于物流資源分散、信息封閉、重復(fù)配送等，導(dǎo)致物流成本一直居高不下.共同配送作為一種低成本、高效率的協(xié)作型配送模式，受到了學(xué)者和從業(yè)者等各界人士的廣泛關(guān)注.共同配送包括多種形式，其中很重要的一種形式是通過(guò)企業(yè)間的信息共享，從而實(shí)現(xiàn)運(yùn)輸訂單在合作企業(yè)間的相互交換和協(xié)調(diào)，企業(yè)車輛互相代為完成訂單，提高車輛裝載率，減少車輛的交叉重復(fù)行駛，不僅可以降低物流成本、提高企業(yè)經(jīng)濟(jì)效益，還具有營(yíng)造良好的交通環(huán)境、降低碳排放等社會(huì)效益.

這種協(xié)作型配送模式衍生出了一類新的車輛路徑問(wèn)題，稱為帶訂單選擇的車輛路徑問(wèn)題(Vehicle Routing Problem with Request Selection,VRPRS).在此類問(wèn)題中，運(yùn)輸企業(yè)不僅面對(duì)由托運(yùn)人托付的運(yùn)輸訂單，同時(shí)也可以通過(guò)信息平臺(tái)接收到由合作企業(yè)發(fā)布的運(yùn)輸訂單.運(yùn)輸企業(yè)既可以將自身訂單委托給合作企業(yè)，同時(shí)支付一定的委托費(fèi)；也可以接受其他企業(yè)發(fā)布的訂單，并獲得相應(yīng)的報(bào)酬.運(yùn)輸企業(yè)需要同時(shí)進(jìn)行訂單選擇及車輛路徑優(yōu)化使得自己利益最大化.

由于共同配送是近年才發(fā)展并興起的協(xié)同物流運(yùn)作模式中的重要內(nèi)容，故目前在此背景下的車輛路徑問(wèn)題研究較少.Chu[1]首先提出了在運(yùn)力不足的情況下可將運(yùn)輸訂單外包給其他合作企業(yè)的車輛路徑問(wèn)題，并設(shè)計(jì)了一種啟發(fā)式算法求解；Bolduc[2]之后加強(qiáng)了前者的求解能力；C?té[3]隨后完善了該問(wèn)題的定義，稱該類問(wèn)題為帶公共承運(yùn)人的車輛路徑問(wèn)題(Vehicle Routing Problem with Private Fleet and Common Carriers,VRPPC)，并開(kāi)發(fā)了更為有效的算法如擾動(dòng)型元啟發(fā)式算法和禁忌搜索算法，能求解更大規(guī)模的該問(wèn)題.Liu[4]研究了整車運(yùn)輸下的帶訂單選擇的取送貨問(wèn)題(Pickup and Delivery Problem,PDP)，并考慮了既可以將訂單委托給合作企業(yè)，也可以接受其他企業(yè)的委托.

共同配送環(huán)境下的車輛路徑問(wèn)題取得了一定的成果，但除了Liu[4]外，其他研究?jī)H考慮了可將訂單外包給合作企業(yè)，忽略了還可以選擇完成其他企業(yè)的發(fā)布的訂單，并且Liu[4]針對(duì)的是整車運(yùn)輸取送貨問(wèn)題，沒(méi)有考慮更一般意義下的車輛路徑問(wèn)題.因此本文從一家運(yùn)輸企業(yè)角度出發(fā)，在需要同時(shí)進(jìn)行訂單選擇及車輛路徑優(yōu)化的條件下，對(duì)此類車輛路徑問(wèn)題提出了新的模型和算法，為共同配送系統(tǒng)中的個(gè)體行為分析提供了理論基礎(chǔ).

1 基于訂單選擇的共同配送可行性分析

傳統(tǒng)的共同配送概念中，一般是將所有企業(yè)的訂單信息、車輛信息集中起來(lái)進(jìn)行資源優(yōu)化.但是實(shí)施存在困難，一是誰(shuí)將占據(jù)主導(dǎo)地位難以達(dá)成一致，二是企業(yè)往往不愿意共享所有商業(yè)信息.在此背景下，一種基于訂單選擇的共同配送模式應(yīng)運(yùn)而生，其主要步驟描述如下：

(1)各運(yùn)輸企業(yè)將邊際收益較低的若干訂單發(fā)布到共享“訂單池”中；

(2)各運(yùn)輸企業(yè)根據(jù)“訂單池”及各自其余訂單情況提出訂單取舍意向；

(3)聯(lián)盟決策中心根據(jù)各企業(yè)訂單取舍意向按某種機(jī)制重新分配訂單，并返回步驟(2)，直至所有訂單最終分配完畢；

(4)聯(lián)盟決策中心根據(jù)各企業(yè)的貢獻(xiàn)程度進(jìn)行利益分配.

與前面模式不同，該模式下各企業(yè)地位平等，不必暴露過(guò)多商業(yè)信息，具備很強(qiáng)的落地潛力.其中每個(gè)步驟都是有待解決的問(wèn)題，并且需要指出的是，步驟間還存在很強(qiáng)的聯(lián)系，其交互關(guān)系、機(jī)制、參數(shù)等需要合理制定以盡量滿足“激勵(lì)相容”原則，許多學(xué)者就此進(jìn)行了討論，如Lai[5]針對(duì)整車運(yùn)輸提出了一種基于迭代拍賣的方案達(dá)到該目的，Chen[6]則考慮了組合拍賣機(jī)制在零擔(dān)運(yùn)輸協(xié)作中的應(yīng)用.限于篇幅，本文將重點(diǎn)放在步驟(2)，即運(yùn)輸企業(yè)的訂單選擇行為上，剝離出來(lái)形成獨(dú)立的子問(wèn)題進(jìn)行研究.

2 模型構(gòu)建

2.1 問(wèn)題描述

在上述背景下，本文研究VRPRS的完整描述如下：運(yùn)輸企業(yè)面對(duì)1組由托運(yùn)人托付的訂單(內(nèi)部訂單，對(duì)應(yīng)的客戶稱為內(nèi)部客戶)，以及其他合作運(yùn)輸企業(yè)發(fā)布的訂單(外部訂單，對(duì)應(yīng)的客戶稱為外部客戶)，可以選擇將部分內(nèi)部訂單委托給合作企業(yè)，并支付一定的委托費(fèi)用，同時(shí)也可以選擇接受部分外部訂單獲取報(bào)酬，確定由本企業(yè)完成的1組訂單后，合理安排一定數(shù)量車輛攜帶各客戶所需的貨物從配送中心出發(fā)，依次訪問(wèn)客戶并最終回到配送中心.問(wèn)題求解目標(biāo)是選擇由本企業(yè)完成的訂單，并且優(yōu)化車輛路徑，使得收益最大化.

2.2 模型假設(shè)

為了便于研究，該問(wèn)題有如下前提假設(shè)：

(1)外部訂單是合作企業(yè)發(fā)布的邊際收益最低的訂單(如地理上的離群客戶點(diǎn)等)，本企業(yè)可自由選擇；

(2)委托給合作企業(yè)的訂單不會(huì)被拒絕；

(3)所有貨物初始均在一個(gè)公共配送中心，運(yùn)輸企業(yè)車輛由此裝貨出發(fā)；

(4)貨物互相兼容可以混裝；

(5)企業(yè)擁有的車輛數(shù)資源固定，避免運(yùn)輸企業(yè)無(wú)限接收訂單；

(6)考慮到公共客戶總需求量可能大于車輛最大容量，允許客戶需求可拆分，即1個(gè)客戶可由多輛車輛服務(wù).

2.3 符號(hào)說(shuō)明

根據(jù)圖論的理論，該問(wèn)題可以定義在一個(gè)有向圖G=(V,A)上，點(diǎn)集V={0}?C，點(diǎn){}0代表公共配送中心，C=CS?CA代表客戶點(diǎn)的集合，其中CS表示內(nèi)部客戶，CA表示外部客戶，弧集A=({0}?C)×({0}?C).

(1)模型使用參數(shù).

L——合作企業(yè)集合({}0代表本企業(yè))；

Q——車輛容量；

cij——從點(diǎn)i到點(diǎn)j的費(fèi)用，i,j∈V；

e——托運(yùn)人托付訂單的單位收益；

g——完成委托訂單的單位收益；

h——委托給外部企業(yè)的單位成本；

K——可用車輛數(shù).

(2)模型的決策變量.

xij——從i到j(luò)行駛的車輛數(shù)，i,j∈V；

qij——點(diǎn)i到點(diǎn)j的貨流量，i,j∈V；

2.4 VRPRS模型構(gòu)建

根據(jù)上述符號(hào)，可構(gòu)建VRPRS的混合整數(shù)規(guī)劃模型為

式(1)為目標(biāo)函數(shù)，表示企業(yè)獲得的總收益最大化，總收益計(jì)算公式為：托運(yùn)人托付的訂單的收益+完成外部委托訂單的收益—委托給外部企業(yè)的成本—車輛可變成本；式(2)保證客戶點(diǎn)滿足的流量約束；式(3)保證配送中心的流量約束；式(4)表示不會(huì)有貨物回流到配送中心；式(5)保證滿足車輛流約束；式(6)保證使用車輛數(shù)不超過(guò)最大可用車輛數(shù)；式(7)保證車輛容量滿足約束；式(8)保證貨流量非負(fù)；式(9)和式(10)保證部分參數(shù)為0-1變量.

2.5 普通CVRP模型構(gòu)建

為了與運(yùn)輸企業(yè)僅完成內(nèi)部訂單的經(jīng)濟(jì)效益進(jìn)行對(duì)比，這里另外提出了普通帶容量約束的車輛路徑問(wèn)題(Capacitated Vehicle Routing Problem，CVRP)模型.將VRPRS模型中的式(10)替換為

式(11)表示完成托運(yùn)人托付的所有訂單；式(12)表示不接受其他企業(yè)的任何委托訂單.由式(1)～式(9)，式(11)和式(12)組成的模型即為普通版CVRP模型.

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

由于VRP為NP-Hard問(wèn)題，所以其延伸問(wèn)題VRPRS同樣為NP-Hard問(wèn)題，精確算法會(huì)導(dǎo)致維度爆炸，無(wú)法在有效時(shí)間內(nèi)求解，故考慮啟發(fā)式算法.因遺傳算法具有較好的全局尋優(yōu)能力，在VRP問(wèn)題上有較好的應(yīng)用，決定針對(duì)本文問(wèn)題，設(shè)計(jì)該算法進(jìn)行求解.

3.1 染色體編碼

本文染色體采取十進(jìn)制編碼，將客戶序號(hào)按一定順序排列，從而形成一個(gè)染色體.這類染色體簡(jiǎn)潔直觀，在旅行商問(wèn)題(Traveling Salesman Problem,TSP)中應(yīng)用廣泛.但是由于在VRP問(wèn)題里客戶由多輛車輛服務(wù)，因此推廣到VRP問(wèn)題時(shí)還涉及到解碼問(wèn)題，即將一串十進(jìn)制染色體編碼進(jìn)行分割，每段編碼對(duì)應(yīng)一輛車的訪問(wèn)順序，從而轉(zhuǎn)化為可行解的結(jié)構(gòu)，可以進(jìn)一步求得染色體對(duì)應(yīng)的適應(yīng)度.為解決這一問(wèn)題，大多數(shù)研究里引入了貪婪算法或在染色體中添加編碼0代表切割點(diǎn)，但是前者作為一種啟發(fā)式算法導(dǎo)致難以覆蓋到某些解空間，損失了一定的精度；而后者則在染色體交叉時(shí)產(chǎn)生了大量不可行解，降低了算法的求解效率.Beasley[7]針對(duì)普通VRP問(wèn)題提出了一種分割算法，算法對(duì)客戶點(diǎn)的任意組合順序，巧妙的將分割問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，并利用現(xiàn)有的最短路算法在多項(xiàng)式時(shí)間內(nèi)求得其對(duì)應(yīng)的最優(yōu)分割結(jié)果.本文由于車輛數(shù)有限制，涉及到各客戶的取舍，因此需對(duì)這種分割算法進(jìn)行改進(jìn).

基于其思路，設(shè)計(jì)了一種針對(duì)本文問(wèn)題的染色體編碼規(guī)則和對(duì)應(yīng)的分割算法，描述如下：

設(shè)定染色體為P=(p1p2…pn)，n為客戶數(shù)，其中前m個(gè)基因(p1…pm)為由本企業(yè)服務(wù)的內(nèi)部客戶和接受委托的外部客戶，后n-m個(gè)基因(pm+1…pn)為委托給合作企業(yè)的內(nèi)部客戶或者不接受委托的外部客戶.

對(duì)由本企業(yè)服務(wù)的客戶，即前m個(gè)基因(p1…pm)，構(gòu)造一張輔助圖G′=(V′,E′)，其中，V′代表點(diǎn)集{0,1,…,m}，E′代表有向邊集.對(duì)于邊(i,j)，其中i,j∈V′，i＜j，若滿足容量約束式(13)和式(14)，則邊(i,j)的費(fèi)用如式(15)所示；否則，費(fèi)用設(shè)為無(wú)窮大inf.

對(duì)于基因段(p1…pm)，其對(duì)應(yīng)的最優(yōu)分割為在圖G′中尋求從0到m的最短路問(wèn)題，設(shè)最短路徑長(zhǎng)度為sm，那么在該m取值下對(duì)應(yīng)的染色體P=(p1p2…pn)的總收益，即適應(yīng)度為

對(duì)所有的1≤m≤n，求出U(m)的最大值max(U(m))，則該值為染色體P=(p1p2…pn)最終適應(yīng)度值.最短路算法采取Dijkstra算法，則本文的染色體分割算法時(shí)間復(fù)雜度為O(n3).

3.2 染色體的選擇交叉與變異

本文選擇輪盤賭為染色體選擇的方式，并每次選擇均保留歷史最優(yōu)解以免優(yōu)秀基因的消失，以概率α選擇次序交叉法(Order Crossover,OX)為染色體交叉方法.該方法從父代中隨機(jī)選取一段路徑，并保持另一個(gè)父代中城市的相對(duì)次序，示例如圖1所示.

圖1 染色體次序交叉示例Fig.1 Example of OX in the chromosome

對(duì)染色體以一定的概率β進(jìn)行變異操作，變異的方法為經(jīng)典的2-opt算子：將染色體中隨機(jī)一段基因取逆序放入原位置.

3.3 算法整體框架

本文遺傳算法的框架如圖2所示.

4 算例分析

本節(jié)將對(duì)算法進(jìn)行一系列數(shù)值實(shí)驗(yàn).首先在經(jīng)典的CVRP數(shù)據(jù)集上對(duì)算法的有效性進(jìn)行了分析，而針對(duì)本文提出的問(wèn)題，由于目前不存在該問(wèn)題的標(biāo)準(zhǔn)算例，因此構(gòu)造產(chǎn)生各種規(guī)模算例進(jìn)行測(cè)試，并進(jìn)行結(jié)果分析.算法由Matlab編程實(shí)現(xiàn)，并在Intel Core i5-4590 CPU@3.30GHz處理器，8GB內(nèi)存計(jì)算機(jī)上進(jìn)行計(jì)算.

4.1 算法有效性分析

為驗(yàn)證本文算法的有效性，與已知最優(yōu)解的CVRP部分算例[8]進(jìn)行了對(duì)比，解保留到個(gè)位數(shù)，結(jié)果如表1所示.其中，IGA表示本文算法的解，BN表示已知最優(yōu)解，Gap表示與已知最優(yōu)解的差距(%)，Time表示求解時(shí)間(s).

與已知最優(yōu)解的對(duì)比表明，本文算法能在可接受時(shí)間內(nèi)較好地逼近最優(yōu)解，并且在部分中小規(guī)模算例中能達(dá)到最優(yōu)解，說(shuō)明了本文算法的有效性.

4.2 算例構(gòu)造

公共配送中心的坐標(biāo)為(0,0)，客戶點(diǎn)均在[1 0 ,90]×[1 0 ,90]的平面內(nèi)隨機(jī)生成，客戶對(duì)各原指定運(yùn)輸企業(yè)的貨物配送需求為0或者[5,15]之間的隨機(jī)數(shù)，客戶中存在同時(shí)對(duì)多個(gè)運(yùn)輸企業(yè)均有貨物配送需求的，稱為共同客戶，共同客戶占比設(shè)為10%，內(nèi)部客戶占比設(shè)為60%，并有2個(gè)合作企業(yè).費(fèi)用cij設(shè)為點(diǎn)i到點(diǎn)j的歐氏距離.控制最大車輛數(shù)為，即剛好滿足原運(yùn)輸需求的最小車輛數(shù)，使得企業(yè)更傾向于進(jìn)行合理的訂單選擇而不是簡(jiǎn)單通過(guò)完成更多訂單增加經(jīng)濟(jì)效益.其他參數(shù)設(shè)定如表2所示.客戶數(shù)100以下的稱為小規(guī)模算例，100及以上的稱為大規(guī)模算例.算例命名由所有客戶數(shù)和本企業(yè)車輛數(shù)構(gòu)成，如“n100-k8”表示100個(gè)客戶，8輛自有車輛的算例.

圖2 算法框架Fig.2 Algorithm framework

表1 本文解對(duì)比已知最優(yōu)解Table 1 IGA vs.Best known

表2 算例參數(shù)設(shè)置Table 2 Instance parameter settings

4.3 結(jié)果分析

本文遺傳算法中設(shè)定交叉概率為0.75，變異概率為0.05，種群規(guī)模為60，初始種群隨機(jī)生成，終止條件為經(jīng)過(guò)100次迭代歷史最優(yōu)解仍沒(méi)有更新.數(shù)值實(shí)驗(yàn)結(jié)果如表3所示.其中 B-CVRP，B-VRPRS，B-Gap分別表示普通配送的收益，帶訂單選擇的配送收益，以及收益提升的百分比(%)；C-CVRP，C-VRPRS，C-Gap分別表示普通配送的車輛行駛距離，帶訂單選擇配送的車輛行駛距離，以及行駛距離增加的百分比(%).結(jié)果表明，企業(yè)的收益平均有8.22%的提升，并且車輛的行駛路徑反而有所減少，平均減幅達(dá)到18.41%.可以看出，在共同配送模式下，通過(guò)訂單的雙向委托，運(yùn)輸企業(yè)的個(gè)體選擇行為不僅有利于企業(yè)經(jīng)濟(jì)效益的提高，并且對(duì)于減少汽車配送行駛距離，從而幫助提升交通環(huán)境，降低碳排放等有著積極的作用.

表3 數(shù)值實(shí)驗(yàn)結(jié)果Table 3 Results of the numerical experiments

將n20-k2算例的優(yōu)化結(jié)果展示如圖3所示(訂單選擇前后的車輛路徑).可以觀察到，為了盡可能獲得更大利益，運(yùn)輸企業(yè)將若干個(gè)離群內(nèi)部客戶點(diǎn)委托給了合作企業(yè)，選擇了其他企業(yè)發(fā)布的更加順路的外部客戶點(diǎn)，使得其服務(wù)客戶在地理上更加集中，從而使得車輛行駛距離減少，降低了運(yùn)輸成本.

圖3 訂單選擇前后車輛路徑Fig.3 Vehicle routing before and after request selection

5 結(jié)論

本文在共同配送環(huán)境下，基于企業(yè)間可以雙向委托訂單的策略，提出了一種新的帶訂單選擇的車輛路徑問(wèn)題，以最大化企業(yè)經(jīng)濟(jì)效益為目標(biāo)建立了混合整數(shù)規(guī)劃模型.針對(duì)此NP-Hard問(wèn)題，設(shè)計(jì)了遺傳算法，并提出了針對(duì)該問(wèn)題染色體編碼的解碼的一種多項(xiàng)式時(shí)間最優(yōu)分割算法.通過(guò)數(shù)值實(shí)驗(yàn)，發(fā)現(xiàn)通過(guò)訂單交換和協(xié)調(diào)，一家運(yùn)輸企業(yè)的個(gè)體選擇行為，不僅能夠提高企業(yè)的利潤(rùn)，并能夠一定程度上減少車輛的行駛距離，實(shí)現(xiàn)企業(yè)經(jīng)濟(jì)效益和社會(huì)效益的雙贏.本文的研究是以一家運(yùn)輸企業(yè)為主體進(jìn)行的，重點(diǎn)在于分析聯(lián)盟中的個(gè)體訂單選擇行為.未來(lái)的研究主體將轉(zhuǎn)移到多家運(yùn)輸企業(yè)的共同配送聯(lián)盟，考慮合作企業(yè)間委托任務(wù)價(jià)格的敏感性等，充分分析委托代理雙方的互動(dòng)關(guān)系，通過(guò)制定合理的委托策略結(jié)合個(gè)體行為反應(yīng)，以達(dá)到共同配送聯(lián)盟各方合作博弈的目的.

參考文獻(xiàn)：

[1]CHU C W.A heuristic algorithm for the truckload and less-than-truckload problem[J].European Journal of Operational Research,2005,165(3):657-667.

[2]BOLDUC M C,RENAUD J,BOCTOR F,et al.A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers[J].Journal of the Operational Research Society,2008,59(6):776-787.

[3]C?Té J F,POTVIN J Y.A tabu search heuristic for the vehicle routing problem with private fleet and common carrier[J].European Journal of Operational Research,2009,198(2):464-469.

[4]LIU R,JIANG Z,LIU X,et al.Task selection and routing problems in collaborative truckload transportation[J].Transportation Research Part E Logistics&Transportation Review,2010,46(6):1071-1085.

[5]LAI M,CAI X,HU Q.An iterative auction for carrier collaboration in truckload pickup and delivery[J].Transportation Research Part E Logistics &Transportation Review,2017(107):60-80.

[6]CHEN H.Combinatorial clock-proxy exchange for carrier collaboration in less than truck load transportation[J].Transportation Research Part E Logistics&Transportation Review,2016(91):152-172.

[7]BEASLEY J E.Route first—Cluster second methods for vehicle routing[J].Omega,1983,11(4):403-408.

[8]AUGERAT P,BELENGUER J,BENAVENT E,et al.Computational results with a branch and cut code for the capacitated vehicle routing problem[J].Rapport De Recherche-IMAG,1995:495.