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

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

車(chē)輛路徑問(wèn)題 （Vehicle Routing Problem，VRP）最早是于1959年由Dantzig和Ramser[1]提出的，由于VRP的實(shí)用性與復(fù)雜性，VRP一經(jīng)提出就引起了學(xué)術(shù)界廣泛的討論與研究。集送貨一體化車(chē)輛路徑問(wèn)題 （Pickup and Delivery Vehicle Routing Problem，PDVRP）是對(duì)傳統(tǒng)的VRP一個(gè)擴(kuò)展，目前越來(lái)越受到關(guān)注。1983年和1988年Bodin等人[2]以及Desrosiers等人[3]就已經(jīng)對(duì)滿(mǎn)載集送貨一體化車(chē)輛路徑問(wèn)題進(jìn)行了研究。Savelsbergh M.W.P.等人[4]在1995年對(duì)集送貨一體化車(chē)輛路徑問(wèn)題建立了數(shù)學(xué)模型，并對(duì)其特點(diǎn)、解決方案等進(jìn)行了綜述。對(duì)于非滿(mǎn)載集送貨一體化車(chē)輛路徑問(wèn)題，由于需要考慮到集貨點(diǎn)先于送貨點(diǎn)訪問(wèn)的問(wèn)題，難度較大。2008年Sophie N.P.等人[5-6]對(duì)于集送貨一體化問(wèn)題進(jìn)行了具體的分類(lèi)。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]對(duì)該問(wèn)題進(jìn)行了研究，并取得一定進(jìn)展。

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

1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

2.3.1 將染色體修改成問(wèn)題的解

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

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

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

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

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

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

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

2.4 遺傳操作

（1）選擇復(fù)制

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

（2）交叉操作

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

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

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

（3）變異操作

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

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

2.5 遺傳算法步驟

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

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

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

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

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

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

3 例 子

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

表1 任務(wù)信息

用4,5,6,7,8,9依次表示任務(wù)1～6的集貨點(diǎn)；用自然數(shù)10表示任務(wù)1的送貨點(diǎn)，自然數(shù)11表示任務(wù)2的送貨點(diǎn)，自然數(shù)12,13分別表示任務(wù)3的第1,2個(gè)送貨點(diǎn)（20,65）（30,45），自然數(shù)14表示任務(wù)4的送貨點(diǎn)，自然數(shù)15表示任務(wù)5的送貨點(diǎn)，自然數(shù)16,17,18分別表示任務(wù)6的第1,2,3個(gè)送貨點(diǎn)（75,29）（66.15）（85,18）。根據(jù)本文所提供算法，取交叉概率pc=0.6，變異概率pm=0.1，經(jīng)過(guò)400次迭代后，得到問(wèn)題的次優(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é) 論

本文對(duì)多車(chē)場(chǎng)開(kāi)放式帶有里程約束的軟時(shí)間窗集送貨一體化車(chē)輛路徑問(wèn)題采用遺傳算法進(jìn)行求解，算例表明該算法易于實(shí)現(xiàn)，且效果較好。本文為單車(chē)型問(wèn)題，而對(duì)于多車(chē)型問(wè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]李軍，郭輝煌.物流配送車(chē)輛調(diào)度理論與方法[M].北京：中國(guó)物資出版社，2001.

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

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

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

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

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

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

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

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