陳可嘉 方云飛 駱佳藝

（福州大學(xué)經(jīng)濟(jì)與管理學(xué)院 福州350116）

0 引言

叫車(chē)接送運(yùn)輸（dial-a-ride transportation，DART）是指乘客打電話到運(yùn)營(yíng)中心告知其接送需求（包括接送起點(diǎn)和終點(diǎn)）后，運(yùn)營(yíng)中心的調(diào)度員根據(jù)乘客預(yù)約信息規(guī)劃路線，并指派車(chē)輛接送用戶，完成接送任務(wù)的面向預(yù)約的運(yùn)輸方式[1-2]。這種運(yùn)輸方式作為公共交通運(yùn)輸?shù)?種補(bǔ)充形式，主要是為行動(dòng)不便的老年人和殘疾人設(shè)計(jì)門(mén)到門(mén)的接送服務(wù)，所使用的車(chē)輛配備有輪椅坡道或者輪椅升降機(jī)，車(chē)內(nèi)除了正常的座位，還配有擔(dān)架位、輪椅位，以滿足乘客的不同需求，為他們的出行提供便利。隨著老年人口比例逐年上升，以及醫(yī)療保健服務(wù)不斷發(fā)展，叫車(chē)接送運(yùn)輸?shù)男枨罅咳找嬖鲩L(zhǎng)?？紤]到運(yùn)輸對(duì)象多為特殊群體，為了設(shè)計(jì)合適的運(yùn)輸路線以避免用戶就醫(yī)延誤、實(shí)現(xiàn)高質(zhì)量的服務(wù)，過(guò)去40年來(lái)，叫車(chē)接送問(wèn)題（Dial-a-ride Problem，DARP）已經(jīng)被研究人員廣泛探討[3]。

DARP是車(chē)輛路徑問(wèn)題（vehicle routing problem，VRP）的延伸。然而，DARP不同于VRP及其擴(kuò)展問(wèn)題，因?yàn)镈ARP涉及到人而不是貨物的運(yùn)輸。DARP滿足乘客給定接送起點(diǎn)和終點(diǎn)的接送需求，并且可同時(shí)服務(wù)多名乘客。因此，DARP關(guān)注乘客在特殊要求下出行服務(wù)的高水平高質(zhì)量。一般情況下，DARP旨在最大限度地降低車(chē)輛運(yùn)營(yíng)成本（主要與車(chē)輛行駛成本相關(guān)），同時(shí)達(dá)到乘客可接受的服務(wù)水平（主要包括服務(wù)時(shí)間窗要求、位置資源要求和乘坐時(shí)間限制等）。

盡管DARP是1個(gè)NP-hard問(wèn)題，但目前學(xué)者對(duì)這個(gè)問(wèn)題已經(jīng)進(jìn)行了諸多研究，大量的啟發(fā)式方法被提出并廣泛應(yīng)用于這個(gè)問(wèn)題。孫博等[4]針對(duì)隨機(jī)正態(tài)分布乘客需求的DARP問(wèn)題，提出基于集對(duì)分析的調(diào)度方法，得到較好的結(jié)果。孫繼洋等[5]設(shè)計(jì)了基于引力模型的啟發(fā)式算法，有效解決了考慮乘客動(dòng)態(tài)需求的DARP問(wèn)題。Parragh等[6]分析了多車(chē)型DARP問(wèn)題，提出了1種基于變鄰域搜索的啟發(fā)式算法。H?me[7]設(shè)計(jì)了1種自適應(yīng)插入啟發(fā)式算法，有效解決了只考慮單一車(chē)輛的DARP。Parragh和Schmid[8]針對(duì)DARP提出了1種高效的混合算法，將變鄰域搜索（variable neighborhood search，VNS）集成到列生成中，并將其與大鄰域搜索（Large Neighborhood Search，LNS）相結(jié)合，在較短的計(jì)算時(shí)間內(nèi)得到了較好的結(jié)果。Muelas等[9]給出了1種用于處理大城市或人口稠密地區(qū)中常見(jiàn)的大規(guī)模情景DARP問(wèn)題的分布式VNS算法，并在舊金山市進(jìn)行測(cè)試，得到了較好的結(jié)果。Ritzinger等[10]考察了帶時(shí)間窗的DARP問(wèn)題，提出了1種基于動(dòng)態(tài)規(guī)劃思想的元啟發(fā)式算法，并將其集成到大鄰域搜索框架中。Tripathy等[11]基于改進(jìn)蟻群優(yōu)化算法來(lái)研究多車(chē)型DARP問(wèn)題。Masmoudi等[12]設(shè)計(jì)了1種混合遺傳算法，為不同類(lèi)型用戶、多車(chē)型車(chē)隊(duì)規(guī)劃車(chē)輛路徑。關(guān)于解決該問(wèn)題的精確算法，文獻(xiàn)中很少出現(xiàn)。Cordeau[13]針對(duì)DARP設(shè)計(jì)了精確的分支切割算法，并且求解了多達(dá)4輛車(chē)和48個(gè)出行需求的實(shí)例。基于Cordeau的研究，Ropke等[14]建立了1個(gè)新的模型，減少了變量和約束的數(shù)量，求解了多達(dá)8輛車(chē)和96個(gè)出行需求的DARP實(shí)例。Liu等[15]同樣采用了分支切割方法，解決了1個(gè)實(shí)際生活中的叫車(chē)接送問(wèn)題，同時(shí)考慮了多次出行，多類(lèi)型車(chē)輛，多類(lèi)型需求等因素。

近年來(lái)，越來(lái)越多的實(shí)際限制因素被學(xué)者們考慮并進(jìn)行DARP研究，不同類(lèi)型的車(chē)輛[16-18]，如多個(gè)車(chē)場(chǎng)[19]，和乘客需求等[20-21]。但之前關(guān)于DARP的文獻(xiàn)中普遍都有1個(gè)假設(shè)，即每輛車(chē)結(jié)束工作的車(chē)場(chǎng)與開(kāi)始工作的車(chē)場(chǎng)必須相同。Kek等[22]首次提出靈活車(chē)場(chǎng)的概念，即允許車(chē)輛自由在任何車(chē)場(chǎng)開(kāi)始和結(jié)束其路線，并將其考慮進(jìn)車(chē)輛路徑問(wèn)題的研究中。實(shí)驗(yàn)證實(shí)引入靈活車(chē)場(chǎng)假設(shè)的車(chē)輛路徑問(wèn)題的行駛成本比固定車(chē)場(chǎng)車(chē)輛路徑問(wèn)題的行駛成本最多可降低近50%。Markov等[23]考慮了1個(gè)帶靈活車(chē)場(chǎng)的垃圾回收車(chē)輛路徑問(wèn)題，通過(guò)對(duì)現(xiàn)實(shí)案例的測(cè)試，實(shí)驗(yàn)表明允許車(chē)輛靈活返回車(chē)場(chǎng)能夠?qū)④?chē)輛行駛距離平均節(jié)約14.6%。

靈活車(chē)場(chǎng)是1種在實(shí)踐中較少出現(xiàn)的情況，因此在大多數(shù)研究中常常被忽略。然而，合適地使用這種靈活性，允許車(chē)輛結(jié)束任務(wù)車(chē)場(chǎng)不同于開(kāi)始工作車(chē)場(chǎng)，可以顯著地節(jié)約車(chē)輛行駛成本?；诖?，筆者在現(xiàn)有研究的基礎(chǔ)上引入靈活車(chē)場(chǎng)的假設(shè)，研究了1個(gè)新的DARP擴(kuò)展問(wèn)題——靈活多車(chē)場(chǎng)多類(lèi)型的叫車(chē)接送問(wèn)題（Multiple Depots Heterogeneous Dial-a-ride Problem with Flexible Depots，MDHDARP-FD），以總行駛成本最小為目標(biāo)，構(gòu)建了MDHDARP-FD的混合整數(shù)非線性規(guī)劃數(shù)學(xué)模型。為使該模型易于求解，對(duì)原模型進(jìn)行約束線性化、變量聚合和添加有效不等式等處理，形成1個(gè)新的線性規(guī)劃模型，并利用數(shù)學(xué)規(guī)劃求解器CPLEX進(jìn)行求解。通過(guò)典型算例以及系列算例的測(cè)試，驗(yàn)證了該模型的有效性。

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

MDHDARP-FD旨在設(shè)計(jì)1組車(chē)輛路線以滿足一定數(shù)量的接送需求。每個(gè)需求包括到指定的出發(fā)地接乘客并將其送至指定的目的地。乘客可能在出發(fā)地或者目的地指定時(shí)間窗，要求在時(shí)間窗內(nèi)被服務(wù)。如果車(chē)輛太早到達(dá)，就得等到時(shí)間窗的開(kāi)始時(shí)間才能開(kāi)始服務(wù)。另外，MDHDARP-FD還需要滿足一系列約束，比如車(chē)輛行駛時(shí)間，乘客乘車(chē)時(shí)間，車(chē)輛位置資源等。目標(biāo)是最小化所有車(chē)輛的總行駛成本。

本文中，MDHDARP-FD作為標(biāo)準(zhǔn)DARP的擴(kuò)展問(wèn)題，在DARP基礎(chǔ)上考慮了多車(chē)場(chǎng)和多類(lèi)型。其中，多類(lèi)型是指使用的車(chē)輛上配備有多種位置資源類(lèi)型（例如常規(guī)座位、輪椅位、擔(dān)架位）和接送的乘客具有不同位置資源需求類(lèi)型。另外，與現(xiàn)有文獻(xiàn)中的標(biāo)準(zhǔn)DARP和一些擴(kuò)展問(wèn)題不同，MDHDARP-FD假設(shè)具有靈活車(chē)場(chǎng)，即車(chē)場(chǎng)對(duì)所有車(chē)輛開(kāi)放，每輛車(chē)可以在不同的車(chē)場(chǎng)開(kāi)始和結(jié)束其路線。只要能使成本最小化，每輛車(chē)可以在任何車(chē)場(chǎng)停止其路線。通過(guò)引入車(chē)輛結(jié)束路線時(shí)返回車(chē)場(chǎng)的靈活性，可以減少其行駛時(shí)間和叫車(chē)接送服務(wù)的總運(yùn)營(yíng)成本。

傳統(tǒng)的DARP問(wèn)題中，假設(shè)有1個(gè)同類(lèi)型車(chē)輛構(gòu)成的車(chē)隊(duì)，所有車(chē)輛都有相同的用戶承載量，并且往返于單一車(chē)場(chǎng)，接送單一類(lèi)型的用戶；與傳統(tǒng)的DARP問(wèn)題相比，MDHDARP-FD考慮更為一般的情形，包括多個(gè)車(chē)場(chǎng)，多類(lèi)型用戶，每個(gè)用戶不同的資源需求（例如常規(guī)座位和輪椅位置），相應(yīng)的車(chē)隊(duì)擁有不同類(lèi)型車(chē)輛，每輛車(chē)配備不同類(lèi)型及數(shù)量的資源。

1.2 符號(hào)說(shuō)明

集合和參數(shù)。

V：點(diǎn)集，V=M∪P∪D∪M’，其中M和M’分別表示出發(fā)車(chē)場(chǎng)和返回車(chē)場(chǎng)的集合，P和D分別表示乘客需求起點(diǎn)和需求終點(diǎn)的集合。

A：弧集。

R：車(chē)輛位置資源集合。

K：車(chē)輛集合。

C rk：車(chē)輛k上配備位置資源r的數(shù)量。

：節(jié)點(diǎn)j對(duì)位置資源r的需求數(shù)量。

L：乘客最大乘車(chē)時(shí)間。

T k：車(chē)輛k的最大行駛時(shí)間。

si：節(jié)點(diǎn)i的服務(wù)時(shí)間。

[ei，l i]：節(jié)點(diǎn)i的服務(wù)時(shí)間窗。

cij：從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛成本。

tij：從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間決策變量。

：車(chē)輛k經(jīng)過(guò)?。╥，j）時(shí)為1，否則為0。

：車(chē)輛k在節(jié)點(diǎn)i的開(kāi)始服務(wù)時(shí)間。

：離開(kāi)節(jié)點(diǎn)i時(shí)車(chē)輛k上位置資源r的使用量。

1.3 模型構(gòu)建

基于上述參數(shù)和決策變量，建立MDHDARP-FD的混合整數(shù)非線性規(guī)劃模型P0見(jiàn)式（1）～（16）。

上述模型中，式（1）為目標(biāo)函數(shù)，表示最小化所有車(chē)輛的總行駛成本；式（2）～（3）確保每個(gè)乘客被服務(wù)的次數(shù)只有1次，并且每個(gè)乘客的起點(diǎn)和終點(diǎn)由同1輛車(chē)服務(wù)；式（4）～（6）限制每輛車(chē)k從車(chē)場(chǎng)m(k)出發(fā)，并在服務(wù)結(jié)束時(shí)可以返回到任意1個(gè)車(chē)場(chǎng)；式（7）表示每個(gè)需求節(jié)點(diǎn)的時(shí)間窗約束；式（8）和式（9）分別表示每輛車(chē)的最大行駛時(shí)間約束和每個(gè)乘客的最大乘車(chē)時(shí)間約束；當(dāng)車(chē)輛k經(jīng)過(guò)弧（i，j）時(shí)，式（10）和式（11）分別定義了節(jié)點(diǎn)j的開(kāi)始服務(wù)時(shí)間和離開(kāi)節(jié)點(diǎn)j時(shí)車(chē)輛位置資源的使用量；式（12）～（13）表示車(chē)輛位置資源使用量約束；式（14）～（16）分別定義了0-1整數(shù)決策變量、非負(fù)連續(xù)型決策變量和非負(fù)整數(shù)決策變量。

與傳統(tǒng)的DARP模型相比，約束式（4）和式（5）在傳統(tǒng)DARP問(wèn)題中每輛車(chē)到達(dá)路線終點(diǎn)后需返回出發(fā)車(chē)場(chǎng)上的基礎(chǔ)上，使每輛車(chē)可以在不同的車(chē)場(chǎng)開(kāi)始和結(jié)束其路線；約束式（7）和式（8）除了設(shè)置乘客需求起點(diǎn)和需求終點(diǎn)的集合外，還包括了出發(fā)車(chē)場(chǎng)和返回車(chē)場(chǎng)的集合，使得車(chē)輛的路線具有靈活性；約束式（16）使車(chē)輛上配備的位置資源類(lèi)型多樣化，并滿足接送乘客的不同位置資源需求類(lèi)型。

2 模型重構(gòu)

上述MDHDARP-FD問(wèn)題考慮了多個(gè)車(chē)場(chǎng)、多類(lèi)型位置資源和乘客需求，并且假設(shè)車(chē)輛可以在服務(wù)結(jié)束時(shí)回到任何1個(gè)車(chē)場(chǎng)，比標(biāo)準(zhǔn)的DARP更復(fù)雜。因此，想要直接求解原模型P0是非常困難的。為了使MDHDARP-FD易于求解，本文對(duì)P0模型進(jìn)行重構(gòu)，進(jìn)行了約束線性化、變量聚合和添加有效不等式等處理，獲得1個(gè)新的模型。

在約束線性化過(guò)程中，非線性約束被重寫(xiě)為等價(jià)的線性約束，因此原模型轉(zhuǎn)化為線性規(guī)劃模型。在變量聚合過(guò)程中，本文將具有相同性質(zhì)的決策變量進(jìn)行聚合，以減少變量數(shù)量，降低問(wèn)題規(guī)模。此外，還引入了一些有效不等式來(lái)強(qiáng)化模型。上述重構(gòu)過(guò)程參考了文獻(xiàn)[19]中提到的方法。詳細(xì)描述如下。

2.1 約束線性化

在模型P0中，約束式（10）和式（11）是非線性的，因此P0不能直接使用線性規(guī)劃求解器進(jìn)行求解。為此，本文引入了1個(gè)很大的正數(shù)M來(lái)線性化這2個(gè)約束。

以約束式（10）為例，當(dāng)車(chē)輛k經(jīng)過(guò)?。╥，j）即=1時(shí)，我們有≥+si+t ij，否則約束（10）不起作用。因此，約束式（10）可以重寫(xiě)為

式中：M為1個(gè)很大的正數(shù)。

同樣的，車(chē)輛位置資源的使用量約束（11）可以重寫(xiě)為

通過(guò)引入1個(gè)很大的正數(shù)M，將非線性約束式（10）和式（11）可以分別由等價(jià)線性約束式（17）和式（18）代替，原模型也轉(zhuǎn)換為線性規(guī)劃模型，并且新的線性規(guī)劃模型的解與原模型解一致，從而使得線性規(guī)劃求解器能夠求解本文問(wèn)題。

2.2 變量聚合

根據(jù)前面MDHDARP-FD問(wèn)題的描述，每個(gè)需求節(jié)點(diǎn)（需求起點(diǎn)或需求終點(diǎn)）只被1輛車(chē)訪問(wèn)1次，那么所有與車(chē)輛無(wú)關(guān)的服務(wù)時(shí)間變量都可以用1個(gè)簡(jiǎn)單的變量代替。具體來(lái)說(shuō)，對(duì)1個(gè)固定的節(jié)點(diǎn)i∈P∪D，所有k∈K的都可以被變量Bi代替。因此，時(shí)間窗約束式（7）可以等價(jià)于約束式（19）～（21）。

式中：Ki為位于出發(fā)車(chē)場(chǎng)i的車(chē)輛集合。因?yàn)樾枨蠊?jié)點(diǎn)i∈P∪D只可能被1輛車(chē)經(jīng)過(guò)1次，而車(chē)場(chǎng)i∈M∪M'可能被多輛車(chē)經(jīng)過(guò)，因此在式（20）中使用聚合后的變量Bi，在式（19）和式（21）中仍然使用以區(qū)分不同的車(chē)輛。

類(lèi)似的，約束式（9）和式（10）可以分別替換為式（22）和式（23）～（25）。

另外，式（23）～（25）可以用2.1描述的方法進(jìn)一步轉(zhuǎn)化為線性約束。

通過(guò)聚合除出發(fā)車(chē)場(chǎng)和終點(diǎn)車(chē)場(chǎng)之外每個(gè)節(jié)點(diǎn)上的時(shí)間變量，可以減少整個(gè)MDHDARP-FD問(wèn)題中變量和約束的數(shù)量，模型的復(fù)雜性大大降低。

2.3 有效不等式

盡管原模型P0已經(jīng)轉(zhuǎn)化為線性規(guī)劃模型，并且隨著變量聚合，決策變量和約束的數(shù)量都減少了，但是求解MDHDARP-FD仍然是困難的。為了有效地解決這個(gè)問(wèn)題，引入多個(gè)不等式來(lái)減少所考慮問(wèn)題的搜索空間。

如果1輛車(chē)經(jīng)過(guò)?。╦，i），由于j點(diǎn)時(shí)間窗下界為e j，最早到達(dá)i點(diǎn)時(shí)間為e j+d j+t ji，那么最早服務(wù)i點(diǎn)的時(shí)間為e j+d j+t ji或ei，具體取決于二者的大小。當(dāng)?shù)竭_(dá)i點(diǎn)時(shí)間e j+d j+t ji小于i點(diǎn)時(shí)間窗下界ei，則需要等待至ei才開(kāi)始服務(wù)；當(dāng)?shù)竭_(dá)i點(diǎn)時(shí)間e j+d j+t ji大于i點(diǎn)時(shí)間窗下界ei，則無(wú)需等待。考慮到每1個(gè)節(jié)點(diǎn)i∈P∪D只能被1輛車(chē)經(jīng)過(guò)，因此時(shí)間窗下界可以強(qiáng)化為約束式（26）。

通過(guò)考慮反向弧，時(shí)間窗上界可以強(qiáng)化為約束式（27）。

同樣的，位置資源的使用量的下界也可以強(qiáng)化為約束式（28）。

通過(guò)引入多個(gè)有效不等式，能夠進(jìn)一步收緊時(shí)間窗的上下界窗口，強(qiáng)化不同車(chē)輛在?。╦，i）上的優(yōu)先關(guān)系，并確保同1個(gè)請(qǐng)求的2個(gè)節(jié)點(diǎn)在同1條路線上。

3 算例分析

為了驗(yàn)證上述模型的有效性，本文選取文獻(xiàn)[19]中提供的datasetU和datasetE這2組算例進(jìn)行測(cè)試。2組算例來(lái)源于奧地利格拉茨市紅十字會(huì)在病人運(yùn)輸領(lǐng)域的真實(shí)情況，在接送老年人和殘疾人的情況下，一些乘客可能要求坐輪椅接送，而另一些乘客可能使用常規(guī)車(chē)輛座位；在運(yùn)送病人的情況下，乘客可能需要用擔(dān)架運(yùn)送。其中，datasetU組算例考慮單一類(lèi)型的位置資源和乘客需求，datasetE組算例引入了4種位置資源類(lèi)型，并且不同的乘客對(duì)這4種位置資源的需求不同。所選用的算例中車(chē)輛數(shù)量范圍為2～4輛，乘客需求數(shù)量范圍為16～30個(gè)。與文獻(xiàn)[19]類(lèi)似，我們?cè)趯?shí)驗(yàn)時(shí)假設(shè)有4個(gè)車(chē)場(chǎng)（坐標(biāo)分別為[-5，-5]，[5，5]，[-5，5]，[5，-5]），可用車(chē)輛最初分布于不同車(chē)場(chǎng)，第1輛車(chē)安排到第1個(gè)車(chē)場(chǎng)，第2輛車(chē)安排到第2個(gè)車(chē)場(chǎng)，以此類(lèi)推。與文獻(xiàn)[19]不同的是，MDHDARP-FD假設(shè)車(chē)輛具有靈活車(chē)場(chǎng)，即車(chē)場(chǎng)對(duì)所有車(chē)輛開(kāi)放，每輛車(chē)可以在任何車(chē)場(chǎng)結(jié)束其路線。

本文借助數(shù)學(xué)規(guī)劃求解器CPLEX12.6.3，在Intel Core i5 2.50GHz處理器、8GB內(nèi)存、Windows 7系統(tǒng)的電腦上運(yùn)行求解。

3.1 典型算例實(shí)驗(yàn)與結(jié)果分析

以datasetE組算例中的Ea4-16作為典型算例進(jìn)行實(shí)驗(yàn)。算例Ea4-16中有4輛車(chē)，需要完成16個(gè)乘客的接送需求。4輛車(chē)分別位于[-5，-5]，[5，5]，[-5，5]，[5，-5]這4個(gè)車(chē)場(chǎng)。每輛車(chē)上配備有3個(gè)常規(guī)座位（其中1個(gè)員工座位、2個(gè)病人座位）、1個(gè)擔(dān)架位、1個(gè)輪椅位。車(chē)輛最大行駛時(shí)間為240 min。

乘客需求信息見(jiàn)表1。每個(gè)乘客需求包含1個(gè)需求起點(diǎn)和1個(gè)需求終點(diǎn)。序號(hào)1～16為乘客需求起點(diǎn)的信息，序號(hào)17～32為對(duì)應(yīng)的需求終點(diǎn)信息。所有的點(diǎn)在[-10，10]2的歐式平面隨機(jī)生成。其中一半的需求在起點(diǎn)設(shè)時(shí)間窗，一半在終點(diǎn)設(shè)時(shí)間窗。時(shí)間窗長(zhǎng)度為15 min。每個(gè)需求節(jié)點(diǎn)（需求起點(diǎn)或需求終點(diǎn)）的服務(wù)時(shí)間為3 min，乘客最長(zhǎng)乘車(chē)時(shí)間為30 min。不同的乘客對(duì)4種位置資源的需求不同。

表1 算例Ea4-16的乘客需求信息Tab.1 Passengers'demand information of Example Ea4-16

對(duì)于上述典型算例，混合整數(shù)非線性規(guī)劃模型重構(gòu)后共有20 385個(gè)約束條件，3 852個(gè)變量，其中3 780個(gè)整數(shù)變量。運(yùn)用CPLEX進(jìn)行求解，用時(shí)1 661.44 s，主要結(jié)果見(jiàn)表2。根據(jù)求解結(jié)果繪制出車(chē)輛接送路線，見(jiàn)圖1，相應(yīng)的最優(yōu)接送路線列于表3中。

表2 算例Ea4-16的模型求解結(jié)果Tab.2 Model solution results of Example Ea4-16

圖1 算例Ea4-16的車(chē)輛接送路線圖Fig.1 Route for vehicles of Example Ea4-16

表3 算例Ea4-16的最優(yōu)接送路線Tab.3 Optimal route of Example Ea4-16

從算例結(jié)果可以看出，本文所建立的模型能在滿足車(chē)輛行駛時(shí)間約束、乘客乘車(chē)時(shí)間約束、車(chē)輛位置資源約束、時(shí)間窗約束等的基礎(chǔ)上，得到1組實(shí)現(xiàn)乘客接送需求的最優(yōu)車(chē)輛路線。并且，由圖1（d）和表3可知，車(chē)輛1和車(chē)輛2在接送結(jié)束后并沒(méi)有返回其出發(fā)車(chē)場(chǎng)，而是返回距離接送結(jié)束點(diǎn)最近的車(chē)場(chǎng)，能夠減少車(chē)輛的行駛時(shí)間，從而使得所有車(chē)輛總行駛成本更小。

3.2 系列算例實(shí)驗(yàn)與結(jié)果分析

本文從文獻(xiàn)[19]提供的Dataset U和Dataset E這2組算例中各選取8個(gè)算例進(jìn)行實(shí)驗(yàn)，并將求解結(jié)果與文獻(xiàn)[13]、文獻(xiàn)[17]和文獻(xiàn)[19]的結(jié)果進(jìn)行比較（見(jiàn)表4）。表4中“MDHDARP-FD”列、“MD-H-DARP”列、“H-DARP”列、“2-index-DARP”列和“DARP”列分別表示本文MDHDARP-FD的最優(yōu)值、文獻(xiàn)[19]中MD-H-DARP的最優(yōu)值、文獻(xiàn)[17]中H-DARP和2-index-DARP的最優(yōu)值和文獻(xiàn)[13]中“DARP”的最優(yōu)值?！癎1（%）”列“、G2（%）”列、“G3（%）”列和“G4（%）”列分別給出了MDHDARP-FD和MD-H-DARP、H-DARP、2-index-DARP和DARP最優(yōu)值之間的差距。另外，表4中還給出了MDH-DARP-FD以s為單位的計(jì)算時(shí)間，用CPU表示。

表4 系列算例求解結(jié)果及比較Tab.4 Comparison results of examples

從表4可以看出，對(duì)于所有的測(cè)試算例，MDHDARP-FD的最優(yōu)值都小于MD-H-DARP、H-DARP、2-index-DARP和DARP的最優(yōu)值，這意味著叫車(chē)接送服務(wù)的總行駛成本可以隨著靈活車(chē)場(chǎng)的引入而減少。對(duì)于具有單一類(lèi)型的情況（Dataset U），MDHDARP-FD較MD-H-DARP總行駛成本平均降低1.54%，較H-DARP平均降低4.56%，而平均需要15 973.13 s才能獲得最優(yōu)解。對(duì)于具有多類(lèi)型的情況（Dataset E），MDHDARP-FD較MD-H-DARP和H-DARP的總行駛成本分別平均下降1.51%和4.33%，平均運(yùn)行14 907.09 s得到最優(yōu)解。值得注意的是，MDHDARP-FD最優(yōu)解與H-DARP最優(yōu)解之間的差距可以達(dá)到10%以上，例如Ua4-16和Ea4-16。

4 結(jié)束語(yǔ)

本文研究了DARP的1個(gè)新的擴(kuò)展問(wèn)題MDHDARP-FD，首次將靈活車(chē)場(chǎng)引入叫車(chē)接送問(wèn)題，并以總行駛成本最小為優(yōu)化目標(biāo)，構(gòu)建MDHDARP-FD的混合整數(shù)非線性規(guī)劃模型。為使該模型易于求解，進(jìn)行一系列降低原模型復(fù)雜度的處理，如約束線性化、變量聚合、添加有效不等式等措施，從而獲得1個(gè)解空間較小的新線性規(guī)劃模型。最后，通過(guò)典型算例以及一系列標(biāo)準(zhǔn)算例驗(yàn)證了模型的有效性，證實(shí)了叫車(chē)接送服務(wù)的總行駛成本可以隨著靈活車(chē)場(chǎng)的引入而減少。由于MDHDARP-FD問(wèn)題是1個(gè)NP-Hard問(wèn)題，當(dāng)問(wèn)題規(guī)模增大時(shí)，難以利用精確算法來(lái)快速求解。因此，在未來(lái)的研究工作中，我們將設(shè)計(jì)基于禁忌搜索、領(lǐng)域搜索等智能算法框架的高效問(wèn)題解決方案，以在可接受的計(jì)算時(shí)間內(nèi)獲得高質(zhì)量的問(wèn)題近似解。。