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

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

（蘭州交通大學(xué) 交通運輸學(xué)院，甘肅 蘭州 730000）

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

0　引言

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

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

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

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

1　模型描述及假設(shè)

1.1　模型假設(shè)

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

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

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

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

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

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

模型的約束如下：

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

2　例證

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

表1　網(wǎng)絡(luò)圖參數(shù)表

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

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

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

圖1　無向網(wǎng)絡(luò)圖

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

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

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

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

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

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

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

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

第四周期派出的是車輛h2，該車輛行駛的路線和第一周期第三輛車的行駛路線相同，如圖3所示，車輛服務(wù)的總時間為142min，消耗的車輛總?cè)莘e為7m3。

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

表2　各周期的車輛分派表

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

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

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

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

3　總結(jié)與展望

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

參考文獻：

[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].天津：天津大學(xué)（碩士學(xué)位論文），2012.

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

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

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

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

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