多次需求的特殊路段限容量弧路徑問題研究

李坤陽

摘 要：限容量弧路徑問題在城市生活當(dāng)中具有一定的普遍性，引起廣泛的關(guān)注。本文所關(guān)注的焦點(diǎn)是針對(duì)CARP問題的一種拓展問題：考慮了特殊路段的多次需求情況下的路徑優(yōu)化問題。首先提出了此類問題的背景和意義，然后針對(duì)該問題中的容量約束和需求次數(shù)兩個(gè)方面進(jìn)行了分析，最后建立模型，并用模擬退火算法進(jìn)行求解，然后對(duì)結(jié)果進(jìn)行分析。

關(guān)鍵詞：多次需求;弧路徑問題;路徑優(yōu)化

DOI：10.16640/j.cnki.37-1222/t.2019.02.199

0 引言

限容量弧路徑問題（Capacitated Arc Routing Problem， CARP），是一種把研究對(duì)象設(shè)置為道路或路段的問題，主要的應(yīng)用方面是城市的服務(wù)車輛，例如城市道路的灑水車、垃圾收集車、冬季除雪車等，均是服務(wù)道路或路段的車輛。我國的城市建設(shè)一直在發(fā)展，以南京為例，2012年的城市道路長度為6615公里，而在2016年時(shí)城市道路長度為8012公里。城市建設(shè)的同時(shí)，會(huì)使得城市道路網(wǎng)發(fā)生變化，而這也對(duì)服務(wù)車輛的運(yùn)營提出的新的要求。關(guān)于CARP問題，國內(nèi)外學(xué)者進(jìn)行了一些研究，Li J Q等[1]根據(jù)澳大利亞的礦場(chǎng)中道路信息，結(jié)合運(yùn)煤車的運(yùn)行模式，考慮了動(dòng)態(tài)的灑水車根據(jù)需求改變服務(wù)方案，并解決了該礦場(chǎng)灑水車場(chǎng)的選址問題。Lacomme P等人[2]則考慮了周期性的問題，考慮多目標(biāo)的情況下，并設(shè)計(jì)了一種改進(jìn)的遺傳算法進(jìn)行求解，并且得到了較好質(zhì)量的解。劉潔等人[3]考慮了垃圾收集車的問題，并結(jié)合了城市中的轉(zhuǎn)向限制和單行道的情況，將弧路徑問題轉(zhuǎn)換成了節(jié)點(diǎn)路徑問題。朱征宇等人[4]對(duì)灑水車的問題設(shè)計(jì)了一種改進(jìn)后的雙層遺傳算法，并且在單個(gè)車場(chǎng)的基礎(chǔ)上考慮了多個(gè)補(bǔ)水場(chǎng)的問題。很多學(xué)者對(duì)CARP問題進(jìn)行了研究，但多數(shù)研究只考慮了一次服務(wù)需求，而對(duì)于一些特殊路段，在實(shí)際的應(yīng)用中可能會(huì)需要不止一次的服務(wù)。因此，研究這些特殊路段的多次需求對(duì)于改善城市道路環(huán)境、提高服務(wù)車輛的運(yùn)營和管理水平、減少成本的耗費(fèi)是有幫助的。

1 問題分析

考慮需求次數(shù)的特殊路段弧路徑問題可以這樣來對(duì)問題進(jìn)行描述：在城市道路網(wǎng)絡(luò)中，有一組具有不同服務(wù)需求次數(shù)的路段（可稱作“任務(wù)”）需要服務(wù)車輛進(jìn)行服務(wù)，而在某一節(jié)點(diǎn)處，存在一個(gè)車場(chǎng)，車場(chǎng)內(nèi)有一個(gè)由多輛相同的服務(wù)車輛所組成的車隊(duì)。現(xiàn)需要將任務(wù)分配給車隊(duì)中所有的服務(wù)車輛，并且確定服務(wù)車輛的路徑，保證所有的任務(wù)都能夠完成，也即所有有服務(wù)需求的路段均需要被服務(wù)車輛服務(wù)到，并且滿足路段的服務(wù)需求次數(shù)的要求。如何安排車隊(duì)中服務(wù)車輛的路徑問題，使得總的成本耗費(fèi)或行駛距離耗費(fèi)最小，是本問題需要重點(diǎn)考慮的內(nèi)容。

考慮特殊路段的多次需求問題，實(shí)際上是在CARP問題的基礎(chǔ)上加以多次需求因素，它與CARP問題的不同點(diǎn)在于，將某些特殊路段考慮了多次需求。而在該問題中，除了服務(wù)車輛的服務(wù)對(duì)象是城市道路的邊以外，還有兩點(diǎn)重要因素：容量限制和服務(wù)需求次數(shù)，是本問題著重考慮的部分，也是構(gòu)建模型和算例求解時(shí)，主要圍繞的部分。

1.1 容量限制

城市的服務(wù)車輛在對(duì)城市的路段進(jìn)行服務(wù)時(shí)，是需要考慮容量的影響。灑水車的水箱是有容量的，除雪車能承載的除雪劑也是一定的，垃圾收集車的容量同樣有限制，服務(wù)車輛的容量限制了服務(wù)車輛不能無限制的服務(wù)下去，當(dāng)服務(wù)了一定的時(shí)間或者一定長度的路段后，會(huì)因?yàn)槿萘肯拗频脑驘o法繼續(xù)作業(yè)。而本問題所研究的需求是不可拆分的，也即服務(wù)車輛對(duì)路段進(jìn)行服務(wù)時(shí)，只能選擇將路段的需求完全滿足，或者完全不服務(wù)，不能出現(xiàn)服務(wù)車輛服務(wù)路段的部分需求的情況。

因此，從容量限制的角度來看，本問題中，城市道路網(wǎng)絡(luò)中路段的平均長度越短，則服務(wù)車輛出行一次所能夠提供服務(wù)的路段數(shù)量也越多，并且返回車場(chǎng)時(shí)所剩余的容量也越少，利用率相對(duì)較高;而若路段的平均長度越長，則服務(wù)車輛出行一次所能夠提供服務(wù)的路段數(shù)量也越少，并且返回車場(chǎng)時(shí)所剩余的容量也越多，利用率相對(duì)較小。

1.2 服務(wù)需求次數(shù)

一般的城市路段只需要一次服務(wù)即可，如灑水車一天時(shí)間內(nèi)對(duì)一個(gè)路段灑水一次，垃圾收集車輛早上對(duì)路段上的垃圾箱進(jìn)行清理。但是有一些情況需要多次對(duì)路段進(jìn)行服務(wù)，如施工現(xiàn)場(chǎng)附近被渣土車經(jīng)常駛過的路段等情況，可能會(huì)需要多次服務(wù)才能滿足要求，而不僅僅是一次。

服務(wù)需求次數(shù)的要求，使得服務(wù)車輛的運(yùn)營模式對(duì)比僅僅服務(wù)一次情況時(shí)，要復(fù)雜一些。因?yàn)檫@將會(huì)對(duì)服務(wù)車輛的連續(xù)性造成影響，在考慮一次服務(wù)需求次數(shù)的情況下，服務(wù)車輛可以考慮連續(xù)的服務(wù)若干條相互接續(xù)的邊，以減少空駛距離;如果考慮了多次需求的情況下，當(dāng)?shù)谝淮畏?wù)時(shí)，連續(xù)的服務(wù)若干條相互接續(xù)的邊后，第二次的需求則會(huì)使之前服務(wù)過的、只有一次需求的邊成為空駛而不服務(wù)，這樣會(huì)增加空駛距離。而實(shí)際運(yùn)營中，應(yīng)當(dāng)盡可能減少空駛距離，以降低成本。

2 模型建立

在模型建立前，對(duì)該問題進(jìn)行假設(shè)條件的設(shè)置：（1）所有的服務(wù)車輛是相同的，并無任何區(qū)別;（2）服務(wù)車輛需要從車場(chǎng)出發(fā)，完成任務(wù)后最終返回車場(chǎng);（3）服務(wù)車輛進(jìn)行服務(wù)時(shí)，任務(wù)的需求不能拆分;（4）不考慮服務(wù)車輛在交叉口經(jīng)過時(shí)的行駛距離和服務(wù)容量的消耗。

在圖中，為頂點(diǎn)集，節(jié)點(diǎn)0為車場(chǎng)所在，為弧集，弧的長度為、需求量為、服務(wù)次數(shù)，有個(gè)容量為的服務(wù)車輛對(duì)圖中的路段進(jìn)行服務(wù)，確定每個(gè)服務(wù)車輛的路徑，使得總的行駛距離最小。

在模型中，需要兩個(gè)0—1變量對(duì)服務(wù)車輛的路徑問題進(jìn)行描述：

——當(dāng)服務(wù)車輛的對(duì)弧只途徑不服務(wù)則為1，否則為0;

——當(dāng)服務(wù)車輛的對(duì)弧服務(wù)則為1，否則為0。

模型建立如下：

?目標(biāo)函數(shù)（2.1）是要求總的行駛距離最短;約束式（2.2）表示車輛服務(wù)的所有任務(wù)的需求量之和不超過容量;約束式（2.3）表示滿足弧的服務(wù)次數(shù)要求;約束式（2.4）表示車輛對(duì)弧的選擇只有服務(wù)、途徑不服務(wù)和不途徑三種情況;約束式（2.5）表示服務(wù)車輛的車場(chǎng)約束，從車場(chǎng)出發(fā)最終必須返回車場(chǎng);約束式（2.6）表示道路網(wǎng)絡(luò)中的節(jié)點(diǎn)流量平衡約束;約束式（2.7）和（2.8）表示0—1變量的取值約束。

3 算例求解

現(xiàn)有一個(gè)局部城市道路網(wǎng)絡(luò)如圖3.1所示，為了便于計(jì)算，將該網(wǎng)絡(luò)轉(zhuǎn)換為表格形式，將路段的服務(wù)需求和車輛容量轉(zhuǎn)換成若干個(gè)單位長度表示，如表3.1所示，其中節(jié)點(diǎn)1為車場(chǎng)，編號(hào)3、8、11、12的路段需求次數(shù)為2次，其余路段的需求次數(shù)均為1次。另有服務(wù)車輛4輛，容量均為12，需要計(jì)算出服務(wù)車輛的總行駛耗費(fèi)的最小值。由于長度和需求正相關(guān)，因此考慮設(shè)置為相同的值。

需要說明的是，0—1變量是確定服務(wù)車輛路徑的主要參數(shù)，但是在對(duì)算例進(jìn)行求解的時(shí)候，為了方便求解，將問題轉(zhuǎn)化成直接安排任務(wù)分配給服務(wù)車輛的計(jì)算。

選擇模擬退火算法對(duì)上述問題進(jìn)行求解，相關(guān)參數(shù)為：初始溫度100，溫度下限1，降溫系數(shù)為0.95，迭代次數(shù)為100次。通過隨機(jī)方法確定初始解：1號(hào)車為（1，3，8，13），2號(hào)車為（5，2，7，8，12），3號(hào)車為（4，6，11，3，9），4號(hào)車為（10，12，11，14）。該初始解總耗費(fèi)為79，耗費(fèi)的計(jì)算除了任務(wù)本身的需求，還要加上相鄰任務(wù)之間的最短路徑的長度耗費(fèi)以及從車場(chǎng)出發(fā)和返回車場(chǎng)的長度耗費(fèi)。新解的產(chǎn)生方法為隨機(jī)互換任務(wù)弧，并同時(shí)檢驗(yàn)約束條件是否符合。

經(jīng)過計(jì)算后得到新的優(yōu)化方案：1號(hào)車為（1，8，3，7），2號(hào)車為（2，8，14，13，12），3號(hào)車為（6，12，11，10，9），4號(hào)車為（5，11，4，3），總的耗費(fèi)為49。

由算例的結(jié)算結(jié)果可知，在多次服務(wù)的考慮下，對(duì)于灑水車的運(yùn)營是有所影響，同時(shí)所建立的模型在模擬退火算法的計(jì)算下，能得到滿意解，說明該方法對(duì)于此類問題的求解比較有效。

4 總結(jié)

考慮了多次需求的服務(wù)車輛路徑問題，會(huì)使得服務(wù)車輛的路徑任務(wù)安排變得更加復(fù)雜。本文在解決問題時(shí)，引用了圖論中的建模基礎(chǔ)，建立模型并且運(yùn)用啟發(fā)式算法進(jìn)行求解，從而得到滿意解。

參考文獻(xiàn)：

[1]Li J Q，Mirchandani P，Knights P.Water truck routing and location of refilling stations in open pit mines[C]. Proceedings of 2008 Australian Mining Technology Conference. The Australian Institute of Mining and Metallurgy，2008：141-156.

[2]Lacomme P，Prins C，Ramdane-Chérif W.Evolutionary algorithms for multiperiod arc routing problems[C].Proc.9th Int.Conf.Inf.Process.Manage.Uncertainty Knowl.-Based Syst，2002：845-852.

[3]劉潔，何彥鋒.城市垃圾收集車輛弧路徑問題研究[J].成都大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，32（04）：423-426.

[4]朱征宇，劉建輝，楊永，謝志華.多車場(chǎng)灑水車路徑問題的雙層遺傳算法[J].微型電腦應(yīng)用，2008（06）：1-4.