周期性帶容量限制的弧路徑問題模型研究

李金萍，楊信豐，趙平平，盧軍莉　LI Jinping,YANG Xinfeng,ZHAO Pingping,LU Junli

（蘭州交通大學 交通運輸學院，甘肅 蘭州 730000）

(School of Traffic&Transportation Engineering,Lanzhou Jiaotong University,Lanzhou 730000,China)

0　引言

周期性帶容量限制的弧路徑問題（Periodic Capacitated Arc Routing Problem,PCARP）是路徑優(yōu)化問題中比較常見的一種，有著很強的應用背景。特別是隨著城市的不斷發(fā)展，城鄉(xiāng)建設的節(jié)奏加快，其在現(xiàn)實生活中的具體應用也越來越多；如城市垃圾回收問題，以及灑水車、除冰車和除雪車任務分配問題等都是周期性帶容量限制弧路徑優(yōu)化問題的具體應用。如何合理有效地安排車輛行駛路線，使得在盡量節(jié)約車輛、時間、人力等資源并滿足服務需求的條件下，服務的總成本最小，是該問題追求的主要目標。多周期帶有容量限制的弧路徑優(yōu)化問題是帶容量限制的弧路徑優(yōu)化問題的擴展問題，可描述為在某一個需被某種服務進行服務的道路交通網絡中，根據(jù)每條道路的條件如交通流、車輛自身條件等的實際差異，需要以不同的組合方式和服務頻率對一系列需求道路進行服務，根據(jù)實際情況，規(guī)劃合理的服務周期，在考慮各條道路的組合方式、服務頻率以及所規(guī)劃周期的條件下，由帶容量限制的服務車輛從車場出發(fā)對需服務的道路進行服務。

目前，國際上對PCARP問題的研究相對較少，Damon[1]等人運用新啟發(fā)式算法解決基于多周期的車輛弧路徑問題，并且將其應用到實際的車輛路徑優(yōu)化問題的處理中，其目的是將路徑分配給不同的客戶或者司機，使其工作量更加平衡。Bin[2]等人研究了基于時間窗的多周期車輛路徑優(yōu)化問題，問題是設計一個時長若干天的服務周期，并且每個有服務需求的顧客必須在規(guī)定的時間窗內被服務，Angelelli[3]等研究了動態(tài)的多周期車輛路徑優(yōu)化問題，該問題以周期的總成本最小為目標。Min Wen[4]等人對動態(tài)的多周期的車輛弧路徑問題進行研究，動態(tài)主要體現(xiàn)在，在多個時間周期條件下，可行的服務時間和客戶訂單信息隨時間的變化而變化。在算法方面，大多數(shù)都采用啟發(fā)式算法或線性規(guī)劃法對該問題進行解決，如Lacomme[5]提出了BIH、PMA、DMA與IPMA四種算法；Feng Chu[6-8]提出了DFNIH、LBH、SS算法與整數(shù)線性規(guī)劃法。

國內研究CARP和CARP擴展問題的文獻還很少[9-12]，領域的研究還處于初步的認識階段，薄非凡[13]等人用基于多周期的車場車輛路徑問題來描述城市垃圾清掃問題，并用混合遺傳算法進行求解。朱征宇、夏夢霜[14]研究了周期性帶有容量限制的弧路徑問題，以一個周期內服務需求道路的總花費值最小為目標，提出了二次單親遺傳法和改進MA算法。在以往的研究中，大多數(shù)也是用線性規(guī)劃法對進行建模，但模型中考慮的約束條件都比較少，很少有文獻將車輛服務時間、車輛容量、車輛數(shù)量、周期時長、道路需求次數(shù)等多個約束一起考慮進行建模。

綜上所述，研究多周期帶容量限制的弧路徑優(yōu)化問題，具有很重要的理論意義和現(xiàn)實意義。本文將服務分為若干服務周期，在考慮車輛容量、服務時間、道路需求等情況下，建立了以服務總時間最小的優(yōu)化模型，并運用LINGO軟件對實例進行了計算，對結果進行了分析。

1　模型描述及假設

1.1　模型假設

設每條道路的長度、服務車輛的數(shù)目、道路需求服務的次數(shù)、每個周期時長及每輛車的容量為已知量，并對該問題進行如下假設：（1）假設只有一個車場，所有服務車輛都需要從車場出發(fā)，服務完后返回車場。即每輛車行駛的每條路徑都為閉合路徑。（2）假設道路交通、自然環(huán)境等條件對服務車輛的車速沒有影響，即車輛只有行駛速度和服務速度兩種，服務時的速度小于行駛速度。

（3）在同一周期內，某一車輛在閉合道路上服務時，每條邊只能被服務車輛經過一次，不能反向行駛。（4）在同一周期內，所有服務車輛都有服務能力（服務時間）限制。

1.2　相關定義式及參數(shù)說明

以下是模型中使用的x,y變量:

1.3　數(shù)學模型及解釋

該問題所追求的目標是所有周期內所有車輛服務完所有需求邊的總時間最短，如果邊是有服務需求的邊，則該時間由車輛的行駛時間以及服務時間兩部分組成；否則，只有行駛時間，則該模型的目標函數(shù)如式（1）所示。

模型的約束如下：

約束式（2）表示對于路徑網絡中任何一個頂點j，車輛到達j的次數(shù)等于車輛從j出發(fā)的次數(shù)；約束式（3）表示所有車輛必須從車場出發(fā)；約束式（4）表示，在一個周期內，同一條道路最多被服務車輛服務一次；約束式（5）表示所有周期內的車輛對某條道路服務的總次數(shù)不超過道路的需求服務次數(shù)；約束式（6）表示在某一周期內，被某車輛所服務的所有道路的需求量不超過該車輛的容量；約束式（7）表示，某車輛服務完所有周期內需服務的道路和經過道路的總時長不超過車輛的最長服務時間；約束式（8）表示在某一周期內，服務車輛服務完所有需求道路后的時間不超過周期時長；約束式（9）是為了避免在求解過程中，車輛在兩點之間來回行駛或多點之間行駛形成子圈設立的約束條件；約束式（10）中的三個式子分別表示，車輛服務某一條邊的次數(shù)不超過經過該邊的次數(shù)；在同一周期內，同一車輛一旦經過某條邊，則不能再在該邊上反向經過；x、y是0,1變量。

2　例證

由于城市人口越來越多，環(huán)境污染越來越嚴重，很多城市為了進化環(huán)境，采用灑水車對城市道路進行周期性的灑水服務，假設有一車場，周圍有若干需灑水服務的道路。圖1是一個由車場以及周圍有服務需求的邊組成的無向網絡，其中較細的邊表示非服務需求道路，較粗的邊表示服務需求道路，圖中有6條服務邊，4條非服務邊，各邊的各個參數(shù)如表1所示。另外，有3輛服務車輛，h1,h2,h3的容量分別是6,8,10，單位是m3；各輛車的最長服務時間分別為200,250,350，單位為min；將一天分為4個周期，每個周期時長為180,240,240,180，單位為min。

表1　網絡圖參數(shù)表

以下是LINGO中計算得出該例的最優(yōu)解，每個周期內被派出車輛的行駛路線以及服務弧如下：

第一周期派出的車輛是h1和h3，車輛h1在該周期內只對邊1和2進行服務，具體行駛路線是1-2-3-1，如圖2所示，根據(jù)表1的數(shù)據(jù)得，服務的總時間是17+16+10=43min，消耗的車輛容積是2+3=5m3。

車輛h3在該周期對邊3,5,10進行服務，服務路線為1-4-5-6-1，如圖3所示，總服務時間為17+35+45+45=142min，消耗的車輛總容積為2+3+2=7m3。

圖1　無向網絡圖

圖2　第一周期第一輛車路線圖

圖3　第一周期第三輛車和第四周期第二輛車路線圖

第二周期的服務車輛有車輛h1和h2，h1僅對邊2,3服務，如圖4所示，具體行駛路線為1-3-4-1，服務總時間為16+45+25=86min，消耗的車輛容積是3+3=6m3。

車輛h2在第二周期對行駛路線中的所有道路都進行了服務，即對邊1,5,6進行服務，車輛行駛路線為1-2-6-1，服務總時間為28+20=48min，消耗的車輛容積是2+2+3=7m3。見圖5。

在第三周期內，派出的服務車輛是車輛h3，該車輛的行駛路線在所有周期內所有車輛的服務路線中是最長的一條，行駛過程中對需求邊2,3,6,10進行了服務，車輛行駛方向是1-4-5-6-2-3-1，如圖6所示，車輛服務的總時間為16+45+48+45+17+10=181min，消耗的車總容量是3+2+3+2=10m3。

圖4　第二周期第一輛車路線圖

圖5　第二周期第二輛車路線圖

圖6　第三周期第三輛車路線圖

第四周期派出的是車輛h2，該車輛行駛的路線和第一周期第三輛車的行駛路線相同，如圖3所示，車輛服務的總時間為142min，消耗的車輛總容積為7m3。

從計算結果來看，第一周期車輛h2沒有被派出，第二周期車輛h3沒有被派出服務，第三周期車輛h1,h2沒有被派出，第四周期車輛h1,h3沒有被派出服務。在所有周期內，所有周期內車輛服務的總次數(shù)是6次，每周期車輛的具體分配，車輛服務時間，容積消耗量如表2，表3，表4所示。

表2　各周期的車輛分派表

表3　各周期各車輛的服務時間表　單位：分鐘

表4　各輛車在各周期的消耗量　單位：立方米

由表4可知，每輛車在每個周期的服務時間都小于該車的最長服務時間，每輛車在每個周期的服務時間都小于該周期時長，每個周期車輛消耗的容積都小于車輛額定容積。每輛車的容量利用率和時間利用率如下：

結合時間和容量從行駛路徑方面來分析，在第一周期車輛h1和車輛h3對行駛路徑中所有的有服務需求的邊都進行了服務，車輛h1的行駛路徑中共有a1,a2兩條有服務需求的邊，服務過程中對兩條邊都進行了服務，車輛h3的線路中共有a3,a5,a10三條有服務需求的邊，服務過程中對三條邊都進行了服務，在該周期，兩輛車完成服務后，車輛h1的容積剩余量為1m3，不滿足任何一條服務邊的需求，車輛h3的容積剩余量為3m3，因此，兩輛車的容量在本次服務中都得到了充分的利用。在第二周期，車輛h1服務完后時間剩余量157min，服務完了路徑中所有的有服務需求的線路，并且，車輛容積剛好被完全利用，所以，在容積方面達到了最優(yōu)，車輛h2的行駛路線中所有的路線都是服務需求，并且全部對其服務，容積剩余量為1m3，所以是最優(yōu)的服務方式。第三周期，車輛h3的行駛路線是在所有周期內所有服務車輛的行駛路線中最長的，并且服務完了所有的有需求的路線，容積剩余量為0，從整體上得到最優(yōu)，車輛h2在第二周期服務完后，服務時間還剩余150min，為了滿足各邊的服務次數(shù)，在第四周期再派出服務，該服務的總時間為142min，車輛的容積剩余量為1m3，車輛h3的時間利用率和容量利用率都達到最大，所以是最優(yōu)選擇。從整體線路來看，車輛h3的容積和服務時間是最長的，為了充分利用車輛的容積和服務時間，應使其服務較長的有服務需求的路線。

3　總結與展望

周期性的帶有容量限制的弧路徑優(yōu)化問題是實際生活中常見的路徑優(yōu)化問題，但目前國內外對該問題的研究還較少，本文在一些假設條件下建立了該問題的數(shù)學模型，用LINGO軟件對模型進行求解，并且對計算結果進行了分析，進一步驗證了模型的有效性和正確性。本文雖然建立了該問題的數(shù)學模型，但還存在一些不足，在算法求解，多目標和多車場方面還有待進一步的研究。

參考文獻：

[1]Damon G.,Bruce G.,Edward W..The period vehicle routing problem:New heuristics and real-world variants[J].Transportation Research part E:Logistics and Transportation Review,2011,47(5):648-668.

[2]Glover F..Future paths for integer programming and links to artificial intelligence[J].Computers and Operations Research,1986,13(5):533-549.

[3]Angelelli E.,Bianchessi N.,Mansini R..Short Term Strategies for a Dynamic Multi-period Routing Problem[J].Transportation Research part C,2009,17(2):106-119.

[4]Min Wen,Gilbert L..The dynamic multi-period vehicle routing problem[J].Computers and Operations Research,2010,37(9):1615-1623.

[5]Lacomme P.,Prins C..Evolutionary algorithm for periodic arc routing problems[J].European Journal of Operational Research,2005,165(2):535-553.

[6]Chu F.,Labadi N.,Prins C..Heuristics for the periodic capacitated arc routing problem[J].Journal of Intelligent Manufacturing,2005,16(2):243-251.

[7]Chu F.,Labadi N.,Prins C..A scatter search for the periodic capacitated arc routing problem[J].European Journal of Operational Research,2006,169(2):586-605.

[8]Chu F.,Labadi N.,Prins C.The Periodic Capacitated Arc Routing Problem linear programming model,metaheuristic and lower bounds[J].Journal of Systems Science and Systems Engineering,2004,13(4):423-435.

[9] 胡珊，林丹.有補給點及多裝載的容量約束弧路徑問題的算法研究[D].天津：天津大學（碩士學位論文），2012.

[10] 朱征宇，謝志華，楊永,等.灑水車作業(yè)路線規(guī)劃的復雜CARP問題求解[J].計算機應用，2008,28(3):768-772.

[11] 李小華，朱征宇.多車場帶容量限制弧路徑規(guī)劃問題研究[D].重慶：重慶大學（碩士學位論文），2009.

[12] 謝志華.灑水車作業(yè)路線規(guī)劃問題的研究與應用[D].重慶：重慶大學（碩士學位論文），2008.

[13]薄非凡，魏法杰.城市垃圾清運中的周期多車場車輛路徑問題[J].交通標準化，2009,2(6):104-107.

[14] 夏夢霜，朱征宇.周期性帶容量限制弧路徑問題研究[D].重慶：重慶大學（碩士學位論文），2008.