帶油耗的單車場開放式車輛路徑問題研究

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

車輛路徑問題 （Vehicle Routing Problem,VRP）最早由Dantzing和Ramser[1]于1959年提出,之后產生了這一問題的許多變種，例如：多車型車輛路徑問題 （Heterogeneous-vehicle Vehicle Routing Problem，HVRP）[2-4]；多車場車輛路徑問題[5-6]；開放式車輛路徑問題[7-11]等等。

針對各種車輛路徑問題，大部分文獻的目標函數大致由兩部分組成： （1）車輛的啟動費用； （2）車輛的行駛費用。首先，車行駛費用與行駛距離有關，而現實生活中，隨著油價的不斷上漲，在考慮車行駛費用的時候除了考慮行駛距離對于行駛費用的影響，耗油量對于行駛費用的影響也是很大的，所以熊浩[12]、唐加福[13]等人在目標函數中考慮了油耗成本對線路的影響，但是他們考慮的都是封閉式車輛路徑問題。而由于各廠商現在大部分都采用物流外包，所以有必要考慮路徑為開放形式的，這樣更符合實際生活，故此本文考慮帶油耗的開放式車輛路徑問題，即：車輛在對其負責的路徑上的客戶進行服務時，不必回到原車場，而是終止于它所服務的最后一個客戶點。另外，由于一個物流公司所服務的客戶其需求不同，因此可能需要該物流公司派出不同類型的車輛對其進行服務，即使所服務的客戶沒有特殊要求，物流公司本身也可能具有不同型號的車輛，而不同車型的車輛其啟動費和最大容量是不同的，由此會對物流公司的車輛分配方案產生影響，所以本文研究的車輛路徑問題還要考慮車輛的啟動費用及容量。

1 問題描述

本文研究一種帶油耗的單車場多車型開發式車輛路徑問題。它可以描述為：有一個車場，車場中共有L種類型的車輛。設第l 1≤l≤（）L 種類型車共有Kl輛 （Kl足夠大，即各種類型的車足夠用），每輛的容量為Ql，啟動費用為Cl。設車場共有K輛車，那么該車場共為N個客戶點服務，其中第i（ 1≤i≤N ）個客戶點所需貨物

重為gi。配送車輛從車場裝上貨物出發，為N個客戶送貨，要求每個客戶只由一輛車為其完成送貨任務，車輛將貨物運送完畢后結束于其最后服務的客戶點。被派出完成配送任務的每輛車的費用都為它所產生的油耗與它的啟動費用，目標為使所有被派出的車輛的費用之和最小。

2 數學建模

用0表示車場，cl表示第l（ 1≤l≤L ）種類型車輛單位距離單位重量的燃油費用，表示第l（ 1≤l≤L ）種類型的第k（ 1≤ k≤Kl）輛車從節點i（ i∈ ｛0,1,…,N ｝）駛向節點j（ j∈ ｛1,…,N ｝）時其上的載重量，dij（i,j=0,1,…,N ）表示節點i與節點j之間的距離， 其中dii=0（ i=0,1,…,N ）。與都是0-1決策變量，當第l（ 1≤l≤L ）種類型的第k（1≤ k≤Kl）輛車從節點 i（ i∈ ｛0,1,…,N ｝）駛向節點j（ j∈｛1,…,N ｝）（i≠j）時xlikj=1， 否則當節點 （客戶）i（i∈ ｛1,…,N｝）由第l（ 1≤l≤L ）種類型的第k（ 1≤ k≤Kl）輛車服務時否則于是上述問題可用下列0-1整數規劃模型進行描述：

其中： （1）的第一項與第二項分別表示所有配送車輛總的油耗和總的啟動費用； （2）表示所用的每類型車車數不超過此類型車數； （3）表示每個客戶點恰好被訪問一次； （4）表示離開每個客戶點的車輛數小于或等于進入該客戶點的車輛數； （5）表示被派遣的每一輛車的載重量都不超過其容量。

3 模型求解

因為開放式車輛路徑問題 （OVRP）是NP難的[8]，而本文討論的問題是對OVRP的擴展，所以本文的問題也是NP難的，因此下面采用禁忌搜索算法對其進行求解。

3.1 禁忌算法中的初始解的求法

由于禁忌搜索算法求解的好壞在一定程度上依賴于其初始解，所以下面用改進的最近鄰算法求初始解，以得到更優的結果。

改進的最近鄰算法：M：表示未安排路線的客戶集合；s：用以累加一條路徑上客戶點的需求量；r：存儲一條未完成路徑其車輛的容量與其當前最后一個節點處需求量的累加值（）s之差；M'：存儲本文討論問題中一個解的全部路徑；lujing：存儲當前要生成的路徑，如果生成完畢，將其加入到M'中；j：存儲當前未完成路徑中的最后一個節點；i：存儲當前M中被選中要為其安排路線的那個點。

第一步：初始化。令M←1,…,｛｝N ， s←0， M'←?， lujing←?。第二步：當M≠?時，重復以下步驟，否則，算法結束，輸出M'。步驟1：如果lujing=?。隨機選一車型，記為k，將其添加到lujing中，即在M中選擇其需求量與它和車場距離之比最大者， 將其序號賦給i， 令r-gi，如果lujing≠?，在M中選取其需求量與它到lujing中最后一個節點j的距離比值最大者，將其序號賦給i，

本文的問題要求油耗盡量小，為了實現這一目標，在改進的最近鄰算法中生成一條新的路徑時，在未安排路線的節點中選取其需求量與它到當前未完成路徑的最后一個節點 （如果當前未完成路徑為空時，其最后一個節點為車場）的距離之比最大或次大者進行添加，這樣很明顯可以降低油耗。

3.2 禁忌算法中解的表示

由于上述問題為多車型單車場問題，本文用MATLAB實現該禁忌搜索算法，為了便于進行鄰域操作，所以采用車型代替車場，用一維元胞數組來表示問題的一個解，例如，設一車場共有3種類型的車輛，該車場為10個客戶完成送貨任務，則可以用1，2，3表示三種車型，1～10表示10個客戶，則一維元胞數組：

表示問題的一個解其含義如下，此解共有5條路徑：第一條路徑：第2種類型的一輛車從車場出發到達客戶2，再由客戶2出發到達客戶5結束；第二條路徑：第3種類型的一輛車從車場出發到達客戶1，再由客戶1出發到達客戶4，再由客戶4出發到達客戶10結束；第三條路徑：第1種類型的一輛車從車場出發到達客戶3結束；第四條路徑：第2種類型的一輛車從車場出發到達客戶7，再由客戶7出發到達客戶9結束；第五條路徑：第1種類型的一輛車從車場出發到達客戶6，再由客戶6出發到達客戶8結束。

3.3 禁忌算法中鄰域操作

由于本文問題中車輛具有不同的類型，加上要減少車輛的啟動費用，所以下面采用一些特殊的鄰域操作來減少所使用車輛的剩余容量以及減少所使用的車輛的數目。

隨機從M'（其含義同改進的最近鄰算法中的M'）中取兩條路徑，再分別從兩條路徑中取出兩個節點：

（1）如果兩節點均為車型，則分別將取出的兩路徑的車型更換成容量與其路徑裝載量 （該路徑上所有客戶點需求量之和，以下同）最近的車型。

（2）如果兩節點一點為車型，一點為客戶點，將客戶點插在另一路徑的車型之后，并在原路徑中將其清除，如果清除客戶點之后此路徑中還有客戶，就將此兩條路徑的車型更換成容量與其裝載量最近的車型。如果清除客戶點之后這條路徑已經沒有客戶，則將其在M'中刪除，只將另一條路徑的車型更換成容量與其裝載量最近的車型。

（3）兩節點均為客戶點，將第二個客戶點插在第一個客戶點之后，并在原路徑中將其清除，如果清除客戶點之后此路徑中還有客戶，就將此兩條路徑的車型更換成容量與其裝載量最近的車型。如果清除客戶點之后這條路徑已經沒有客戶，則將其在M'中刪除，只將另一條路徑的車型更換成容量與其裝載量最近的車型。

3.4 禁忌算法中評價值的計算

為了擴大搜索范圍，本禁忌搜索算法允許各次迭代中由不可行解產生鄰居，但為了在算法結束后能夠得到問題的可行解，因此對不可行解進行懲罰，設p為懲罰因子，且令若解x中共有ux條路不可行，而設x對應的目標函數值為fx，那么解x的評價值為

3.5 禁忌搜索算法中禁忌對象、禁忌長度

本文所選的禁忌對象及禁忌長度參照文獻[14]。

4 例 子

假設某一車場為30個客戶配送貨物，該車場共有3種類型配送車輛，每種類型車輛足夠用，第1，2，3種車型每輛車的容量分別為10，20，50，啟動費用依次為100，150，300，車場坐標為 （11,11），各個客戶的需求量及坐標如下列表1～2所示。要求車場合理為各客戶配送貨物并使配送費用 （總油耗加上總啟動費用）最少。

調用算法1后得到的初始可行解為：

表1 各個客戶的需求量

x0對應的目標函數值 （總的費用）為2.6553e+004；

運行完禁忌搜索算法后產生的可行解為：

x1對應的目標函數值 （總的費用）為：2.1686e+004。

對此例而言，禁忌搜索算法對初始解的改善是很明顯的。

5 結 論

本文針對帶油耗的單車場多車型車輛路徑問題采用禁忌搜索算法進行求解，提出了改進的最近鄰法求初始解，此算法可以降低油耗，在禁忌搜索算法中為了減少所派遣車輛的剩余容量和所派遣的車輛數而采用了一些特殊的鄰域操作，算例表明該算法易于實現，且效果較好。本文為單車場問題，而對于多車場問題我們將進行下一步研究。

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

[2] 楊文霞，郭海湘，楊娟,等.改進的掃描法求解單車場多車型車輛路徑問題[J].物流技術，2010,4(215):50-53.

[3] 賈立雙，李靜.基于一種改進算法的單車場多車型車輛調度研究[J].中國制造業信息化，2008,37(19):8-10.

[4] 洪波，郎茂樣.多車型配送車輛調度問題的模型及其禁忌搜索算法研究[J].長沙交通學院學報，2005(3):73-77.

[5] 鐘石泉，賀國光.多車場車輛調度智能優化研究[J].華東交通大學學報，2004(6):25-29.

[6] Oberlin P.,Rathinam S.,Darbha S.A Transformation for a Multiple Depot,Multiple Traveling Salesman Problem[C].American Control Conference,2009:2636-2641.

[7] Sariklis D,Powell S.A heuristic method for the open vehicle routing problem[J].Journal of the Operational Research Society,2000,51:564-573.

[8] 符卓.開放式車輛路徑問題及其應用研究[D].長沙：中南大學 （博士學位論文），2003.

[9] 段風華，符卓.有軟時窗多車場開放式車輛路徑及其禁忌搜索[J].計算機工程與應用，2008,44(36):42-44.

[10] 鐘石泉，杜綱，賀國光.有時間窗的開放式車輛路徑問題及其遺傳算法[J].計算機工程與應用，2006,34:201-204.

[11] 孫國華.帶軟時間窗的開放式滿載車輛路徑問題研究[J].船計算機工程與應用，2011,47(17):13-17.

[12] 熊浩.多車型車輛共享的MDVRP問題及其遺傳算法[J].華中師范大學學報，2010,44(1):29-32.

[13] Tang J.F.,Zhang J.,Pang Z.D.A scatter search algorithm for solving vehicle routing problem with loading cost[J].Expert Systems with Applications,2010,37(6):4073-4083.

[14] 馮芳媛，張麗華，李阿慧.B2C電子商務中帶退貨的多配送站點車輛路徑優化問題研究[J].物流科技，2011(7):15-19.