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

李坤陽

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

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

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

0 引言

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

1 問題分析

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

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

1.1 容量限制

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

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

1.2 服務需求次數(shù)

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

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

2 模型建立

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

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

在模型中，需要兩個0—1變量對服務車輛的路徑問題進行描述：

——當服務車輛的對弧只途徑不服務則為1，否則為0;

——當服務車輛的對弧服務則為1，否則為0。

模型建立如下：

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

3 算例求解

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

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

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

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

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

4 總結

考慮了多次需求的服務車輛路徑問題，會使得服務車輛的路徑任務安排變得更加復雜。本文在解決問題時，引用了圖論中的建?；A，建立模型并且運用啟發(fā)式算法進行求解，從而得到滿意解。

參考文獻：

[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].成都大學學報（自然科學版），2013，32（04）：423-426.

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