有里程和軟時間窗約束的開放式多車場集送貨一體化車輛路徑問題研究

陳 鑫，王明陽，張麗華（沈陽師范大學(xué)，遼寧 沈陽 110034）

CHEN Xin,WANG Ming-yang,ZHANG Li-hua (Shenyang Normal University,Shenyang 110034,China)

車輛路徑問題 （Vehicle Routing Problem，VRP）最早是于1959年由Dantzig和Ramser[1]提出的，由于VRP的實用性與復(fù)雜性，VRP一經(jīng)提出就引起了學(xué)術(shù)界廣泛的討論與研究。集送貨一體化車輛路徑問題 （Pickup and Delivery Vehicle Routing Problem，PDVRP）是對傳統(tǒng)的VRP一個擴(kuò)展，目前越來越受到關(guān)注。1983年和1988年Bodin等人[2]以及Desrosiers等人[3]就已經(jīng)對滿載集送貨一體化車輛路徑問題進(jìn)行了研究。Savelsbergh M.W.P.等人[4]在1995年對集送貨一體化車輛路徑問題建立了數(shù)學(xué)模型，并對其特點、解決方案等進(jìn)行了綜述。對于非滿載集送貨一體化車輛路徑問題，由于需要考慮到集貨點先于送貨點訪問的問題，難度較大。2008年Sophie N.P.等人[5-6]對于集送貨一體化問題進(jìn)行了具體的分類。Li H.B.,Lim A.[7]和Gutiérrez-Jarpa G.等 人[8],Gambardella L.M.,Dorigo M.[9],Lu Q.,Dessouky M.M.[10],Dumitrescu I.等 人[11],Renaud J.等 人[12-13]對該問題進(jìn)行了研究，并取得一定進(jìn)展。

相較于國外，在國內(nèi)，李軍、郭輝煌[14]在其書中提到該問題，并給出了數(shù)學(xué)模型，并運(yùn)用C-W節(jié)約算法對該問題進(jìn)行了求解?；粽袢A、王新華[15]，王兆庚、李建庚、程世東[16]，屈援、汪波、鐘石泉[17]，鐘石泉、賀國光[18]對帶有時間窗約束的集送貨一體化車輛路徑問題進(jìn)行了擴(kuò)展，并對其進(jìn)行了求解。霍佳震、張磊[19]對集送貨一體化問題進(jìn)行了進(jìn)一步擴(kuò)展，不再限制每項任務(wù)只有一個集貨點和一個送貨點，而是每項任務(wù)必須有一個集貨點和一個或多個送貨點，并對此問題運(yùn)用修正的C-W算法進(jìn)行了求解。相較于單車場集送貨一體化問題，李臻、雷定猷[20]，鐘石泉、王雪蓮[21]則將單車場擴(kuò)展為多車場，對此類集送貨一體化問題建立了數(shù)學(xué)模型，并通過表上作業(yè)法、遺傳算法給出了問題的解。本文將前面文獻(xiàn)中研究的集送貨一體化車輛路徑問題進(jìn)行了擴(kuò)展，即將單車場情形推廣到多車場，將每個任務(wù)只有一個送貨點推廣到任務(wù)可以有多個送貨點的情形，如此一來，前人文獻(xiàn)中的算法不適用于求解本文的問題，因此本文給出一個遺傳算法對其進(jìn)行求解。

1 問題描述

由多車場發(fā)車執(zhí)行貨運(yùn)任務(wù)的開放式帶有里程約束的軟時間窗集送貨一體化車輛路徑問題，可描述為：某物流公司有l(wèi)項貨運(yùn)任務(wù)，表示為1,…,l，第i（i= 1,…,l）項任務(wù)均由1個集貨點與hi（hi≥1）個送貨點組成，這些貨運(yùn)任務(wù)由m個車場出發(fā)的同一種車型的車輛完成，每個集貨點、送貨點均有各自的時間窗限制，且若以［ET,LT］表示每個集貨點、送貨點的時間窗限制，則ET表示車輛到達(dá)該點的最早時間，后文稱時間窗上限，LT表示車輛到達(dá)該點的最晚時間，后文稱時間窗下限。已知每項貨運(yùn)任務(wù)的貨運(yùn)量為gi，車輛容量為q，并且滿足q

2 遺傳算法設(shè)計

2.1 染色體結(jié)構(gòu)

本文中的每一條染色體都是所有任務(wù)的一個排序。

2.2 初始種群的產(chǎn)生

設(shè)種群規(guī)模為n（n為偶數(shù)）。

step1 將各個任務(wù)中的送貨點按照時間窗進(jìn)行排序，即將時間窗下限小的排在前面，如果時間窗下限相同，則比較時間窗上限，時間窗上限小的排在前面；

step2 保持step1中各個的任務(wù)送貨點的排序不變，將所有任務(wù)編號為1,2,…,l，按該編號得到所有任務(wù)的一個排序，即為一個染色體；

step3 仍然保持step1中各個的任務(wù)送貨點的排序不變，隨機(jī)生成1,2,…,l的n-1個互不相同的排列 （這n-1個排列都與1,2,…,l的自然排列不同），分別按這n-1個排列生成所有任務(wù)的n-1個不同的排序，即得n-1條互不相同的染色體。

2.3 適應(yīng)值函數(shù)的確定

要確定每條染色體的適應(yīng)值，首先要將該染色體改變成問題的一個解 （即在任務(wù)之間選適當(dāng)?shù)奈恢貌迦胲噲觯?，之后計算該解的目?biāo)函數(shù)值z，取1/z為該染色體的適應(yīng)值即可。

2.3.1 將染色體修改成問題的解

用 i（i= 1,…,l）表示第i個任務(wù)，那么如果i1i2…il是1,2,…,l的一個排列，則i1i2…il就表示一個染色體，用j（j= 1,…,m）表示第j個車場，下面將該染色體修改成問題的一個解。

計算各車場與第一個任務(wù)i1的集貨點間的最小距離，設(shè)di1,j1=min｛ di1,j｜j=1,…,m｝，在任務(wù)i1前插入車場j1，讓車輛從第j1個車場出發(fā)沿著i1i2…il的順序前進(jìn) （其中各個任務(wù)的集貨點及送貨點的順序已經(jīng)排好），若該車輛在剛好完成第ik項任務(wù)時，行駛距離達(dá)到最大里程 （即完成第ik項任務(wù)時該車總的行程小于或等于最大里程，但若再完成第ik+1項任務(wù)時，總的行程就會超出最大里程），將任務(wù)i1i2…ik交由該車輛完成，將任務(wù)ik+1作為第一個任務(wù)，對ik+1ik+2…il重復(fù)上述過程，直到所有任務(wù)都被分配車輛為止。

2.3.2 目標(biāo)函數(shù)值的確定

本文問題解的目標(biāo)函數(shù)值是下列三部分之和：該解中所使用車輛的啟動費(fèi)用之和，所使用車輛行駛費(fèi)用之和，所使用車輛到達(dá)各個任務(wù)的取貨點和送貨點所產(chǎn)生的違法軟時間窗約束的懲罰費(fèi)用之和。

設(shè)c0為單位車輛的啟動費(fèi)用，c1為單位車輛單位里程的行駛費(fèi)用，那么，若一個解中所有貨運(yùn)任務(wù)需要r輛車完成，則該解中總的啟動費(fèi)用為c0*r，設(shè)該解中所使用車輛總的行程為d，則該解中所使用車輛行駛費(fèi)用之和為c1*d。

由于本文的時間窗約束為軟時間窗約束，故采取的是加入懲罰的措施，即：對于一個解的每一個集貨點或送貨點i，若車輛在該點規(guī)定時間窗內(nèi)到達(dá)，則不懲罰；若車輛到達(dá)該點時間早于該點時間窗的上限或晚于該點時間窗的下限，則加入懲罰，并且早到的懲罰要小于遲到的懲罰。即：若設(shè)F表示一個解的違法軟時間窗約束的總的懲罰費(fèi)用，那么：

其中：si表示車輛到達(dá)第i個點的時刻，a與b分別表示車輛早到和晚到的單位時間懲罰費(fèi)用。

2.4 遺傳操作

（1）選擇復(fù)制

參考劉國華、包宏、李文超[22]有關(guān)文獻(xiàn)中的選擇復(fù)制方法，在種群中，首先計算各個染色體的適應(yīng)值，將適應(yīng)值最大和最小的兩條染色體挑選出來，讓適應(yīng)值最大者保留下來進(jìn)入下一代種群，之后將它們從種群中刪除，然后對種群采用輪盤賭的方法選擇能夠進(jìn)行交叉變異的染色體。

（2）交叉操作

首先將要進(jìn)入交叉操作的種群中的染色體隨機(jī)兩兩配對，得到（n-22對染色體，對這（n-22對染色體中的每一對都產(chǎn)生0-1間的隨機(jī)數(shù)，如果該隨機(jī)數(shù)小于或等于交叉概率pc，那么這對染色體將進(jìn)行交叉操作。

在要進(jìn)行交叉操作的兩條染色體中，分別任意選取兩項貨運(yùn)任務(wù)的基因段，進(jìn)行交叉，從而產(chǎn)生兩條新的染色體。如果新生成的子體中存在任務(wù)缺失，則將缺失的任務(wù)加入新生成的子體之后，如果新生成的子體中存在任務(wù)重復(fù)，則將重復(fù)的任務(wù)刪除。為說明交叉操作，示例如下：

將第一條父體的基因段任務(wù)2與第二條父體的基因段任務(wù)3，以及將第一條父體的基因段任務(wù)5與第二條父體的基因段任務(wù)2進(jìn)行交叉操作，得到下一代的兩條子體：

（3）變異操作

step1 生成n-2行l(wèi)列的0-1隨機(jī)數(shù)矩陣，該矩陣各個位置的元素分別對應(yīng)變異種群中各個染色體相應(yīng)位置的任務(wù)；

step2 對變異種群中每個染色體都進(jìn)行下列操作：考察該染色體中的各個任務(wù)是否滿足變異條件，即看該任務(wù)對應(yīng)的隨機(jī)矩陣中的元素是否小于等于變異概率pm，如果是，則接著考察該任務(wù)是否有多個送貨點，如果是，則任意選取2個送貨點，將其位置進(jìn)行交換即可。

2.5 遺傳算法步驟

step1 輸入各個車場、各個任務(wù)的集貨點及送貨點的坐標(biāo)、時間窗；各個任務(wù)貨運(yùn)量；單位車輛的啟動費(fèi)用，單位車輛單位里程的行駛費(fèi)用；交叉概率及變異概率；種群規(guī)模；迭代次數(shù)；并將次優(yōu)值設(shè)為無窮大，次優(yōu)解為空。

step2 產(chǎn)生初始種群，種群中包括n條染色體。

step3 計算種群中各個染色體的適應(yīng)值，將其中適應(yīng)值最大的和最小的都挑選出來，更新次優(yōu)解和次優(yōu)值，將適應(yīng)值最大者保留進(jìn)入下一代種群，之后將這兩個染色體從種群中刪除，轉(zhuǎn)步驟4。

step4 對步驟3最后得到的種群進(jìn)行遺傳操作：即進(jìn)行選擇復(fù)制，交叉和變異操作。

step5 將步驟3中適應(yīng)值最大的染色體復(fù)制兩次到經(jīng)過步驟4后得到的種群中，得到新的種群。

step6 判斷是否達(dá)到迭代次數(shù)，若達(dá)到迭代次數(shù)，則算法終止；否則，對步驟5的新種群轉(zhuǎn)step3。

3 例 子

現(xiàn)有三個車場將其編號為1、2、3，它們的坐標(biāo)依次為（40,60）,（55,30）,（80,51），車輛從這三個車場出發(fā)共需要完成6項貨運(yùn)任務(wù)，任務(wù)信息見表1。各個車場的車型都相同，已知每輛車的載重量為q=10，速度v=45，最大行駛距離為180，啟動費(fèi)用及單位里程行駛費(fèi)用分別設(shè)為c0=10,c1=1，另時間窗懲罰系數(shù)：早到單位時間的懲罰費(fèi)用a=4，遲到單位時間的懲罰費(fèi)用b=7，試安排車輛行駛路線，使總費(fèi)用最小。

表1 任務(wù)信息

用4,5,6,7,8,9依次表示任務(wù)1～6的集貨點；用自然數(shù)10表示任務(wù)1的送貨點，自然數(shù)11表示任務(wù)2的送貨點，自然數(shù)12,13分別表示任務(wù)3的第1,2個送貨點（20,65）（30,45），自然數(shù)14表示任務(wù)4的送貨點，自然數(shù)15表示任務(wù)5的送貨點，自然數(shù)16,17,18分別表示任務(wù)6的第1,2,3個送貨點（75,29）（66.15）（85,18）。根據(jù)本文所提供算法，取交叉概率pc=0.6，變異概率pm=0.1，經(jīng)過400次迭代后，得到問題的次優(yōu)解：1→6→12→13→5→11→9→17→18→16→7→14→3→4→10→8→15其次優(yōu)值為：z=286.77，該次優(yōu)解含兩條路徑如表2所示：

表2 次優(yōu)解的路徑信息

4 結(jié) 論

本文對多車場開放式帶有里程約束的軟時間窗集送貨一體化車輛路徑問題采用遺傳算法進(jìn)行求解，算例表明該算法易于實現(xiàn)，且效果較好。本文為單車型問題，而對于多車型問題我們將進(jìn)行下一步研究。

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

[2]Bodin L.,Golden B.,et al.Routing and scheduling of vehicle and grews-the state of the art[J].Computers and Operations Research,1983(10):63-251.

[3]Desroslers J.,Laporte G.et al.Vehicle routing with full loads[J].Computers and Operations Research,1988,15:219-226.

[4]Savelsbergh M.W.P.,Sol M.The general pickup and delivery problem[J].Transportation Science,1995,29:17-25.

[5]Sophie N.P.,Karl F.D.,Richard F.H.A survey on pickup and delivery problems Part I Transportation between customers and depot[J].Fur Betriebswirtschaft,2008,58(1):21-51.

[6]Sophie N.P.,Karl F.D.,Richard F.H.A survey on pickup and delivery problems Part II:Transportation between pickup and delivery locations[J].Fur Betriebswirtschaft,2008,58:81-117.

[7]Li H.B.,Lim A.A meta-heuristic for the pickup and delivery problem with time windows[C]//Tools with Artificial Intelligence,Proceedings of the 13th International Conference,2001:160-167.

[8]Gutiérrez J.G.,Desaulniers G.,et al.A branch and price algorithm for the vehicle routing problem with deliveries,selective pickups and time windows[J].European Journal of Operational Research,2010,206(2):341-349.

[9]Gambardella L.M.,Dorigo M.An ant colony system hybridized with a new local search for the sequential ordering problem[J].INFORMS Journal on Computing,2000,12(3):237-255.

[10]Lu Q.,Dessouky M.M.A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows[J].European Journal of Operational Research,2006,175(2):672-687.

[11]Dumitrescu I.,Ropke S.,et al.The traveling salesman problem with pickup and delivery:polyhedral results and a branch and cut algorithm[J].Mathematical Programming,2010,121(2):269-305.

[12]Renaud J.,Boctor F.F.,Ouenniche J.A heuristic for the pickup and delivery traveling salesman problem[J].Computers and Operations Research,2000,27:905-916.

[13]Renaud J.,Boctor F.F.,Laporte G.Perturbation heuristics for the pickup and delivery traveling salesman problem[J].Computers and Operations Research,2002,29:1129-1141.

[14]李軍，郭輝煌.物流配送車輛調(diào)度理論與方法[M].北京：中國物資出版社，2001.

[15]霍佳震，王新華.基于約束規(guī)劃求解車輛調(diào)度問題[J].物流技術(shù)，2005,9:110-112.

[16]王兆庚，李建更，程世東.基于遺傳算法的集送一體化的車輛路徑問題[J].計算機(jī)工程應(yīng)用，2006,42(1):208-211.

[17]屈援，汪波，鐘石泉.單車場集送一體化車輛路徑問題及其混合算法研究[J].武漢理工大學(xué)學(xué)報，2007,31(5):811-814.

[18]鐘石泉，賀國光.有里程和時間窗約束的一體化車輛調(diào)度智能優(yōu)化[J].系統(tǒng)工程與電子技術(shù)，2006,28(2):240-243.

[19]霍佳震，張磊.有時間窗的集貨送貨一體化車輛路徑規(guī)劃啟發(fā)式算法研究[J].物流技術(shù)，2004,5:64-66.

[20]李臻，雷定猷.多車場車輛優(yōu)化調(diào)度模型及算法[J].交通運(yùn)輸工程學(xué)報，2004,4(1):83-86.

[21]鐘石泉，王雪蓮.多車場集送一體化車輛調(diào)度問題及其遺傳算法研究[J].西安電子科技大學(xué)學(xué)報，2009,19(1):63-68.

[22]劉國華，包宏，李文超.用MATLAB實現(xiàn)遺傳算法程序[J].計算機(jī)應(yīng)用研究，2001,18(8):80-82.