今天我們給大家?guī)淼氖荄ial a ride問題(DAR)的介紹，文中所用資料多參考于文獻。先上目錄

本期內容

1.問題介紹

2.發(fā)展歷史與應用

3.問題分類

4. 算法

1.問題介紹

如今我們對通過手機App等方式打車比較習以為常了，但在智能手機未普及之前，人們通常是通過打電話來訂車的，也就是Dial a ride。如果我們開了一家出租車公司，在接到這些顧客的服務請求之后，我們自然需要考慮一下怎么用我們手上的出租車來滿足顧客的需求，在這樣的背景下我們就需要考慮一下這個問題啦。

Cordeau and Laporte曾經給這個問題下過定義：DAR問題即在滿足顧客請求的前提下，在一個由所有節(jié)點和弧組成的完全圖中組織車輛的行駛路線，使得這些行駛路線達到例如成本最低的規(guī)劃目標。此外需要注意的是這種服務是共享的，即可能有多個不同的乘客同時在同一輛車上，跟我們說的順風車有相似之處。

那么為什么要研究這樣的問題呢？大家如果仔細地思考我們的公共交通系統(tǒng)就會發(fā)現，一種公共交通方式無法同時滿足有成本效益的運作要求和高質量服務的要求。這里高質量服務并不是說司機給你開的什么車或者司機素質如何，而是說能不能在顧客期望的時間將顧客從指定的出發(fā)地運輸到要求的目的地。而我們的公交車和火車、高鐵等能夠運輸大量的乘客，是有成本效益的。

待發(fā)高鐵(來源：鳳凰網)

雖然高鐵、公交這些工具能夠運輸大量的乘客，但是這些工具通常是固定路線和排班的。乘客需要根據這些路線和排班調整自己的行程。的士能夠提供點到點的接送服務，但是這種服務不論是在金錢還是環(huán)境上的花費都是相對比較大的。也就是說我們會面臨成本效益和服務質量的矛盾，但是還是會有人思考能不能全都要，在這兩者之間平衡一下呢？平衡了之后的成果就是一種請求式的公共交通服務，先接收大家的請求，再派車進行服務，相對平衡一下成本效益和服務質量。這幾種方式我們可以對比一下：

2.發(fā)展歷史與應用

請求式的公共交通服務(也就是Dial a ride)首次嘗試于1970年的美國俄亥俄州，1972年在英國的阿賓頓也有嘗試。后來其可行性被證明以后相似的服務模式就開始在各地出現。

在早期，這種服務模式對哪些人群最有好處呢？答案是年長者和由于殘疾行動不便的人，這一人群比較難正常地使用公共交通出行，因此這樣的服務非常受這一人群的歡迎。美國在1990年的殘疾人法案中，要求所有的公共交通代理公司為殘疾人提供區(qū)別于普通的公共巴士服務的輔助客運系統(tǒng)（一般無固定路線或時間表），結果促進了DAR被廣泛地引入、改進。

Dial a ride曾是一種為年長者和殘疾人提供的非盈利性質的服務，通常在進行規(guī)劃的時候以最小化花費為目標。在一些機場中，這種服務模式被用來運輸老人、殘疾人和傷者等，其服務時間窗非常短，規(guī)劃目標是使得移動的距離最小。

還有一種主要的應用在醫(yī)療衛(wèi)生領域，在這一領域的應用中，時間的緊迫性和設備或人員兼容性等特征非常重要以及如何完成工作人員和維修人員的日程安排也很復雜。例如對香港醫(yī)院管理局(醫(yī)管局)而言，需要派車輛進行病人的運輸，每輛運送病人的救護車的內部必須在連續(xù)的行程之間進行消毒，以避免疾病擴散（Lim et al.,2017）。

后來在公共交通領域也有了相關的應用，在需求量比較低的時間段（例如大晚上）或者地點（例如比較偏僻的地方）無法使用固定的公共交通時（例如過了末班車時間或者沒有對應的行駛線路），就可以使用這種服務模式。

而在近些年，隨著技術的發(fā)展（網絡和移動通信、云計算、數據分析等）使得DAR能夠以新的方式運行。如果大量的人單獨使用私家車通勤的話，不僅會導致中央商務區(qū)和城市道路的擁堵，還會增加很多碳排放，所以這種服務模式又開始有市場了。

但是這種服務系統(tǒng)的運營是非常復雜的，在不同的應用場景下會有不同的特征，例如在醫(yī)護領域會對時間窗約束的要求比較高，而對于殘疾人則需要盡可能減少移動距離，有的運營公司會使用多車型的車隊進行服務等等。這意味著需要有相應的算法進行實時性比較好的規(guī)劃和排班才能夠提供比較高質量的服務，這也是這一領域研究的意義。

3.問題分類

正如上述所說，在不同運營環(huán)境下的DAR會考慮不同的特征，一些比較常見的需要考慮的問題特征通常有以下幾點：

1. 對需求節(jié)點的訪問：如果不允許拒絕請求，則需要規(guī)劃各個請求節(jié)點的訪問；如果允許拒絕請求，則需要根據情況考慮接受哪些請求并作進一步規(guī)劃。

2. 時間窗：每個顧客都能指定從出發(fā)點出發(fā)的時間窗和到達目的地的時間窗。

3. 車輛場站：即車輛一趟服務中開始服務與結束服務的地點。

4. 旅程：當車輛回到場站的時候視為完成了一次旅程。

5. 車輛容量：即車輛核載人數。

6. 乘行時間：乘客乘車時花費的時間。

7. 路線持續(xù)時間：車輛在一次旅程中所花費的時間。

      通常在進行DAR的規(guī)劃時需要在考慮上述特征的同時分配車輛，并為車輛作路徑規(guī)劃。我們知道，規(guī)劃是需要一個規(guī)劃目標的，規(guī)劃目標可以從運營者視角出發(fā)（例如車輛行駛時間、總行駛距離、需要的車輛數量、司機的工作時間等）或者用戶視角出發(fā)（例如乘行時間、等待時間、時間窗的滿足情況等）。但是這兩種視角對應的目標常常是沖突的。作為乘客，當然是希望能夠盡可能地減少等待時間和乘行時間，但是這樣就會造成運營成本的增加，比如需要增派車輛以達到這樣的目標。

在很多情況下，規(guī)劃目標的制定是多目標的，需要綜合考慮多種情況。解決多目標DAR的研究大致可以分為三種：

1. 以多個目標的加權和為規(guī)劃目標：目標的加權和適用于對不同目標的權重有明確和直接的評估的問題。

2. 按照重要性的順序考慮：必須首先優(yōu)化較高優(yōu)先級的目標，然后在可能的情況下進一步優(yōu)化較低優(yōu)先級的目標。Garaix et al. (2010)首先考慮最小化運營成本然后才是最大化服務的質量。

3. 尋找問題的Pareto邊界：Pareto邊界由那些與其余的解相比不占劣勢的解組成，Pareto邊界為決策者提供了所有可能的最優(yōu)解的全貌，當決策者對每個標準的相對重要性不確定時，這是特別有利的。它還有助于在戰(zhàn)術層面上在不同的目標之間進行權衡。( Paquette et al., 2013 ).

而更加廣泛的針對所有DAR的研究的分類則可以從兩個方面來看：

1. 如果所有與決策制定相關的信息都在操作開始之前提供給決策制定者，則認為是規(guī)劃的運作是靜態(tài)的；如果在規(guī)劃的運作過程中出現了新的信息，并且允許決策者對這些新信息做出響應，那么這個過程就是動態(tài)的。

2. 如果在做出決策時信息是確定的，那么這種問題就是一種確定性的DAR問題；如果決策時信息未知或者不確定，則可以看作是隨機性的DAR問題。這兩者也可以看作是完美信息和不完美信息的差別。

根據上述兩個方面，我們可以得到四種分類如下圖：

emmmm好像還是不太清楚的樣子，那我們再說的詳細點，完美信息需要考慮所有現在和未來運作有關的信息，例如(1)所有的潛在的用戶有哪些；(2) 這些潛在的用戶是否會變成真正的用戶；(3)客戶的具體需求量；(4) 未來每一次運作中可能出現的整個過程，比如車輛的行駛路線，每位顧客的接送等等。

上述這些信息如果與我們的預期相差不大，那么這樣的問題就能夠很好地逼近實際情況。上述表格中的Static and stochastic就是指決策者必須在開始之前在(2)-(4)中的一個或多個信息未知的情況下為所有事情做出決策，例如車輛的數量和行駛路線等等。剩下的相信大家就可以舉一反三啦。

4.算法

好了，上面叨叨了這么多，相信大家對這個問題已經有了一些基本的認識。有了問題，就要解決問題，目前解決DAR問題及其變種問題的算法大致可以分成兩種：精確算法和啟發(fā)式算法。這個分類相信也在各位讀者的意料之中。

精確算法

關注我們公眾號的小伙伴肯定知道，精確算法能夠求出問題的最優(yōu)解，當問題的規(guī)模比較小的時候，精確算法能夠在可接受的時間內找到最優(yōu)解，但是問題的規(guī)模變大以后，求解所需要的計算量和存儲空間都會急速增長。

而求解DAR問題的精確算法基本上都是基于Branch-and- Bound的，有Branch-and- cut、Branch-and-Price、Branch-and-price-and-cut幾種。

其中Cordeau (2006)最早將Branch and cut算法應用到DAR問題上，Garaix et al. (2010, 2011) 則是應用了Branch and price算法，而在Branch and price and cut算法上，Qu and Bard (2015) and Gschwind and Irnich (2015) ,也給出了很好的應用。篇幅原因在這里就不對具體的內容做過多的介紹了，感興趣的小伙伴可以找一找這些文獻看看。

截至到2016年，一些用精確算法求解的結果大致如下：

注意算例那里的表示是車輛數目/請求數目。

2啟發(fā)式算法

雖然精確性算法在小規(guī)模的算例上能夠在可接受的時間內得到最優(yōu)解，但是由于DAR問題是NP-Hard問題，所以研究的精力更多的是放在研究有效和高效的啟發(fā)式算法上。而且我們在上文中也說過，從實際應用的角度出發(fā)，實際需求會需要能夠更快響應的算法。下面列舉幾個在解DAR問題時常用的方法，其中很多方法是我們公眾號的老伙伴了，經常關注的小伙伴應該也會比較熟悉。

1. Insertion Heuristics      這種方法比較簡單，能夠在較短的時間內找到可行解，但是解的質量不如元啟發(fā)式算法。最早的應用由Jaw et al. (1986)完成。如今這種方法也被作為一種輔助用于找到可行解的方法在運用( Xiang et al., 2008; Wong et al., 2014; Markovi ′c et al., 2015 ),。

2. Tabu SearchCordeau and Laporte (2003)是最早提出在DAR問題中運用禁忌搜索算法的，他們使用了比較簡單的鄰域動作(將一個請求從一條路線轉移到另一條路線)，有效果不錯的多樣化策略，例如對頻繁移動這一行為進行懲罰，暫時接受不可行解。

3. Simulated Annealing在DAR問題上，SA并沒有像其它方法那樣被廣泛的應用，少數幾位作者( Mauri et al., 2009; Zidi et al., 2012; Reinhardt et al., 2013 )實現了標準的利用SA解DAR問題并取得了一定成果。

4. Variable Neighborhood SearchParragh et al. (2009)提出了第一個用于解決DAR問題的VNS算法，解決的是一個雙目標的DAR問題。

5. Large Neighborhood Search在這個算法的研究上Ropke and Pisinger (2006)為帶時間窗的接送問題設計的自適應大領域搜索算法為該算法在DAR問題上的應用打下了基礎( Lehuédéet al., 2014;  Masmoudi et al., 2016; Molenbruch et al., 2017a )等人都曾為DAR問題設計LNS算法。

參考文獻

• Cordeau, J.-F. , Laporte, G. , 2003. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transp. Res. Part B: Methodol. 37 (6), 579–594 .

• Garaix, T. , Artigues, C. , Feillet, D. , Josselin, D. , 2010. Vehicle routing problems with alternative paths: an application to on-demand transportation. Eur. J. Oper. Res. 204 (1), 62–75 .

• Garaix, T. , Artigues, C. , Feillet, D. , Josselin, D. , 2010. Vehicle routing problems with alternative paths: an application to on-demand transportation. Eur. J. Oper. Res. 204 (1), 62–75 .

• Garaix, T. , Artigues, C. , Feillet, D. , Josselin, D. , 2011. Optimization of occupancy rate in dial-a-ride problems via linear fractional column generation. Comput. Oper. Res. 38 (10), 1435–1442 .

• Gschwind, T. , Irnich, S. , 2015. Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transp. Sci. 49 (2), 335–354 .

• Ho, S. C., Szeto, W. Y., Kuo, Y.-H., Leung, J. M. Y., Petering, M., & Tou, T. W. H. (2018). A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B-Methodological, 111, 395–421. 

• Jaw, J.-J. , Odoni, A.R. , Psaraftis, H.N. , Wilson, N.H. , 1986. A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transp. Res. Part B: Methodol. 20 (3), 243–257 .

• Lehuédé, F. , Masson, R. , Parragh, S.N. , Péton, O. , Tricoire, F. , 2014. A multi-criteria large neighbourhood search for the transportation of disabled people. J. Oper. Res. Soc. 65 (7), 983–10 0 0 .

• Lim, A. , Zhang, Z. , Qin, H. , 2017. Pickup and delivery service with manpower planning in Hong Kong public hospitals. Transp. Sci. 51 (2), 688–705 .

• Markovi ′c, N. , Nair, R. , Schonfeld, P. , Miller-Hooks, E. , Mohebbi, M. , 2015. Optimizing dial-a-ride services in maryland: benefits of computerized routing and scheduling. Transp. Res. Part C: Emerg. Technol. 55, 156–165 .

• Masmoudi, M.A. , Hosny, M. , Braekers, K. , Dammak, A. , 2016. Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem. Transp. Res. Part E: Logist. Transp. Rev. 96, 60–80 .

• Mauri, G. , Antonio, L. , Lorena, N. , 2009. Customers’ satisfaction in a dial-a-ride problem. IEEE Intell. Transp. Syst. Mag. 1 (3), 6–14 .

• Molenbruch, Y. , Braekers, K. , Caris, A. , 2017. Benefits of horizontal cooperation in dial-a-ride services. Transp. Res. Part E: Logist. Transp. Rev. 107, 97–119 .

• Parragh, S.N. , Doerner, K.F. , Hartl, R.F. , Gandibleux, X. , 2009. A heuristic two-phase solution approach for the multi-objective dial-a-ride problem. Networks 54 (4), 227–242 .

• Paquette, J. , Cordeau, J.-F. , Laporte, G. , Pascoal, M.M.B. , 2013. Combining multicriteria analysis and tabu search for dial-a-ride problems. Transp. Res. Part B: Methodol. 52, 1–16 .

• Qu, Y. , Bard, J.F. , 2015. A branch-and-price-and-cut algorithm for heterogeneous pickup and delivery problems with configurable vehicle capacity. Transp. Sci. 49 (2), 254–270 .

• Reinhardt, L.B. , Clausen, T. , Pisinger, D. , 2013. Synchronized dial-a-ride transportation of disabled passengers at airports. Eur. J. Oper. Res. 225 (1), 106–117 .

• Ropke, S. , Pisinger, D. , 2006. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40 (4), 455–472 .

• Wong, K.I. , Han, A.F. , Yuen, C.W. , 2014. On dynamic demand responsive transport services with degree of dynamism. Transp. A: Transp. Sci. 10 (1), 55–73 .

• Xiang, Z. , Chu, C. , Chen, H. , 2008. The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments. Eur. J. Oper. Res. 185 (2), 534–551 .

• Zidi, I. , Mesghouni, K. , Zidi, K. , Ghedira, K. , 2012. A multi-objective simulated annealing for the multi-criteria dial a ride problem. Eng. Appl. Artif. Intell. 25 (6), 1121–1131 .