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

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

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

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

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

1 問題描述

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

2 遺傳算法設計

2.1 染色體結構

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

2.2 初始種群的產生

設種群規模為n（n為偶數）。

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

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

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

2.3 適應值函數的確定

要確定每條染色體的適應值，首先要將該染色體改變成問題的一個解 （即在任務之間選適當的位置插入車場），之后計算該解的目標函數值z，取1/z為該染色體的適應值即可。

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

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

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

2.3.2 目標函數值的確定

本文問題解的目標函數值是下列三部分之和：該解中所使用車輛的啟動費用之和，所使用車輛行駛費用之和，所使用車輛到達各個任務的取貨點和送貨點所產生的違法軟時間窗約束的懲罰費用之和。

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

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

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

2.4 遺傳操作

（1）選擇復制

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

（2）交叉操作

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

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

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

（3）變異操作

step1 生成n-2行l列的0-1隨機數矩陣，該矩陣各個位置的元素分別對應變異種群中各個染色體相應位置的任務；

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

2.5 遺傳算法步驟

step1 輸入各個車場、各個任務的集貨點及送貨點的坐標、時間窗；各個任務貨運量；單位車輛的啟動費用，單位車輛單位里程的行駛費用；交叉概率及變異概率；種群規模；迭代次數；并將次優值設為無窮大，次優解為空。

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

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

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

step5 將步驟3中適應值最大的染色體復制兩次到經過步驟4后得到的種群中，得到新的種群。

step6 判斷是否達到迭代次數，若達到迭代次數，則算法終止；否則，對步驟5的新種群轉step3。

3 例 子

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

表1 任務信息

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

表2 次優解的路徑信息

4 結 論

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

[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]李軍，郭輝煌.物流配送車輛調度理論與方法[M].北京：中國物資出版社，2001.

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

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

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

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

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

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

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

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