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

李坤陽

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

關鍵詞：多次需求;弧路徑問題;路徑優化

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

0 引言

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

1 問題分析

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

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

1.1 容量限制

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

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

1.2 服務需求次數

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

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

2 模型建立

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

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

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

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

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

模型建立如下：

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

3 算例求解

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

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

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

經過計算后得到新的優化方案：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，建立模型并且運用啟發式算法進行求解，從而得到滿意解。

參考文獻：

[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.