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

本期內(nèi)容

1.問題介紹

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

3.問題分類

4. 算法

1.問題介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

3.問題分類

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

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

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

3. 車輛場站：即車輛一趟服務(wù)中開始服務(wù)與結(jié)束服務(wù)的地點(diǎn)。

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

5. 車輛容量：即車輛核載人數(shù)。

6. 乘行時間：乘客乘車時花費(fèi)的時間。

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

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

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

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

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

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

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

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

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

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

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

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

4.算法

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

精確算法

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

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

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

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

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

2啟發(fā)式算法

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

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

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

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

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

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

參考文獻(xiàn)

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