任婧璇，常孝亭，巫威眺*，靳文舟

(1.華南理工大學(xué)，土木與交通學(xué)院，廣州 510640；2.廣州市黃埔區(qū)住房和城鄉(xiāng)建設(shè)局，廣州 510530)

0 引言

隨著經(jīng)濟(jì)的持續(xù)發(fā)展，我國機(jī)動化水平逐漸提高，據(jù)公安部統(tǒng)計(jì)[1]，截至2022 年3 月底，全國機(jī)動車保有量達(dá)4.02 億輛。隨之產(chǎn)生的交通擁堵等問題日益嚴(yán)峻，公交優(yōu)先的必要性和重要性尤其凸顯。線網(wǎng)優(yōu)化和多模式公交等策略應(yīng)用于公交系統(tǒng)以提高公共交通吸引力。然而，常規(guī)公交的固定線路和固定班次的特性決定了其不適用于需求較為分散的區(qū)域或時(shí)段，因此，產(chǎn)生了具有可響應(yīng)特定需求的公交形式。交通運(yùn)輸部于2020年發(fā)布的《交通運(yùn)輸部關(guān)于推進(jìn)交通運(yùn)輸治理體系和治理能力現(xiàn)代化若干問題的意見》[2]中提出完善交通出行保障政策體系，完善交通運(yùn)輸新業(yè)態(tài)發(fā)展制度，建立定制公交等需求響應(yīng)型出行服務(wù)體系。需求響應(yīng)公交(Demand Responsive Transit,DRT)最早源于為老年人和殘疾人等移動能力受限的特定人群服務(wù)的電話預(yù)約公交(Dial-A-Ride,DAR)，隨著科學(xué)技術(shù)的發(fā)展及人們對出行靈活性和舒適度等需求的增長，開始發(fā)展面向大眾的服務(wù)模式。其特點(diǎn)在于可在某種程度上對需求進(jìn)行響應(yīng)，亦可稱為靈活公交。作為一種介于傳統(tǒng)的常規(guī)公交和出租車之間的兼具靈活性和集約性的出行方式，DRT可服務(wù)個(gè)性化的出行需求，并在每次派遣車輛前，根據(jù)實(shí)際需求及運(yùn)營目標(biāo)規(guī)劃路徑和時(shí)刻表，實(shí)現(xiàn)不同個(gè)性化需求間的共乘，較為靈活地調(diào)整服務(wù)的個(gè)性化和集約化的程度，在未來出行中具有較大的潛力。

根據(jù)DRT 系統(tǒng)的運(yùn)營模式和靈活度將其細(xì)分為：可變線路公交、可變站點(diǎn)公交、需求響應(yīng)接駁公交、站點(diǎn)需求響應(yīng)公交、部分線路可變公交及區(qū)域線路公交等形式[3]。近年來，國內(nèi)發(fā)展出具有相似特性的定制公交服務(wù)，現(xiàn)有定制公交系統(tǒng)多通過提前的線路征集確定線路的起終點(diǎn)及走向和乘客的可選站點(diǎn)[4]。其中，需求響應(yīng)接駁公交(Demand Responsive Feeder Transit,DRFT)是用于接駁大型集散點(diǎn)的需求響應(yīng)公交，為出行的第一公里和最后一公里服務(wù)，其中“一公里”主要指整個(gè)出行過程的最初或最后一段，而并非特指空間上的1 km。

現(xiàn)有DRT 調(diào)度研究多集中在可變線路式公交及需求響應(yīng)接駁公交的路徑規(guī)劃問題，其中，路徑規(guī)劃的站點(diǎn)多直接以需求點(diǎn)作為乘客上車點(diǎn)，與站點(diǎn)相關(guān)的研究多為具有一定需求響應(yīng)特性的定制公交和可變線路公交的線路規(guī)劃，進(jìn)一步轉(zhuǎn)化為不同約束和不同目標(biāo)下的車輛路徑問題(Vehicle Routing Problem,VRP)。例如，QIU等[5]在可變線路公交背景下，將已接受的站點(diǎn)作為臨時(shí)站點(diǎn)，可供被拒絕的需求作為上下車點(diǎn)選擇。需求響應(yīng)接駁公交需求的上下車站點(diǎn)通常由需求自行指定某一車輛可?？空军c(diǎn)或需求所在實(shí)際位置，系統(tǒng)根據(jù)路徑規(guī)劃確定遵照需求意愿或在一定范圍內(nèi)進(jìn)行調(diào)整分配。例如，ZHENG 等[6]研究可變線路公交，其中，乘客指定唯一上下車點(diǎn)，但系統(tǒng)在規(guī)劃路徑時(shí)可將需求分配到附近的集合點(diǎn)。僅JIANG 等[7]考慮了需求離開接駁系統(tǒng)時(shí)可選擇多個(gè)站點(diǎn)作為服務(wù)的終點(diǎn)，在高峰期運(yùn)力不足的情況下服務(wù)盡量多的需求?，F(xiàn)實(shí)中，需求進(jìn)入接駁系統(tǒng)時(shí)通常有多個(gè)步行可達(dá)站點(diǎn)可供選擇，需求間共同的可達(dá)站點(diǎn)可提高共乘的可能性，從而提高運(yùn)輸效率。REN等[8]考慮需求有多個(gè)不同等級的備選站點(diǎn)下的需求可取舍的接駁系統(tǒng)。

在需求的時(shí)間要求方面，較為典型的為帶時(shí)間窗的VRP問題，其中，需求點(diǎn)的服務(wù)必須在特定的時(shí)間段內(nèi)開始，該時(shí)間段即為時(shí)間窗。在此基礎(chǔ)上進(jìn)一步發(fā)展的考慮同時(shí)取送貨的PDP問題(Pickupand-Delivery Problem)兼顧了取貨點(diǎn)和送貨點(diǎn)的時(shí)間窗。在乘客運(yùn)輸中，則對應(yīng)了DAR 問題中乘客上車點(diǎn)和下車點(diǎn)可開始服務(wù)的時(shí)間段，其上車點(diǎn)的時(shí)間窗表示最早出發(fā)時(shí)間至最晚出發(fā)時(shí)間之間的時(shí)間段，下車點(diǎn)的時(shí)間窗表示最早到達(dá)時(shí)間至最晚到達(dá)時(shí)間之間的時(shí)間段。除服務(wù)開始時(shí)間的時(shí)間窗外，另一個(gè)常被考慮的時(shí)間需求為行程時(shí)間的長度。在DRT 研究中，需求的時(shí)間要求亦是重要的路徑規(guī)劃約束，例如，JIANG等[7]考慮需求的時(shí)間窗和以行程時(shí)間為基礎(chǔ)的服務(wù)質(zhì)量優(yōu)化高峰期接駁公交路徑；REN 等[8]考慮需求指定的上車時(shí)間窗；安久煜等[9]在去程回程雙向的高鐵接駁公交路徑優(yōu)化問題中考慮回程時(shí)間應(yīng)晚于去程時(shí)間；陳汐等[10]在通勤定制公交中考慮上車時(shí)間窗為期望出發(fā)時(shí)間附近浮動一定的緩沖時(shí)間；LU 等[11]將需求響應(yīng)接駁公交的乘客分為前往換乘點(diǎn)的和從換乘點(diǎn)出發(fā)的兩種類型，并對兩種類型需求的期望時(shí)間分別進(jìn)行一定的偏移，得到時(shí)間窗；LI 等[12]考慮需求響應(yīng)接駁公交的背景下乘客指定1個(gè)上車時(shí)間窗，且其位置信息已知，系統(tǒng)在一定的時(shí)間窗偏離范圍內(nèi)為需求規(guī)劃上車站點(diǎn)和時(shí)間窗。總體而言，現(xiàn)有DRT研究多考慮需求出發(fā)或到達(dá)的單點(diǎn)(上車點(diǎn)或下車點(diǎn))時(shí)間窗，及乘客行程時(shí)間約束。時(shí)間窗的上下界由需求指定，或在需求指定的時(shí)間點(diǎn)附近允許進(jìn)行一定的偏移。

綜上，需求響應(yīng)接駁公交的調(diào)度研究缺乏考慮提高共乘可能性及系統(tǒng)效率的乘客進(jìn)入系統(tǒng)的多項(xiàng)選擇，以及缺少從整體角度對服務(wù)過程的時(shí)間范圍進(jìn)行約束的考慮。以服務(wù)“第一公里”接駁火車站的需求響應(yīng)接駁公交為例，乘客須從家乘坐接駁公交到達(dá)火車站，再乘坐火車到達(dá)最終目的地。接駁公交服務(wù)該出行的前半段，即從家到火車站。因乘坐的火車有固定的發(fā)車時(shí)間，因此，接駁服務(wù)的最晚到達(dá)時(shí)間受該發(fā)車時(shí)間限制。火車發(fā)車時(shí)間除對接駁服務(wù)的到達(dá)時(shí)間有約束外，對接駁服務(wù)的起點(diǎn)也產(chǎn)生影響。尤其是火車發(fā)車時(shí)間很早或很晚，乘客無其他交通方式可選，則對接駁公交寄予更多希望，可能對上車位置的要求進(jìn)行一定的妥協(xié)，即添加候選站點(diǎn)。另一方面，從出行目的角度考慮，出行的目的在于到達(dá)目的地，而非移動過程本身。在出發(fā)之前，乘客處于舒適的居住地，可進(jìn)行生產(chǎn)力工作或休閑娛樂；一旦出發(fā)，乘客則處于活動受限且舒適度下降的移動過程。因此，乘客希望盡量推遲出發(fā)時(shí)間，而為保證不晚于接駁終點(diǎn)的最晚到達(dá)時(shí)間，乘客對出發(fā)時(shí)間的推遲應(yīng)有界限，即設(shè)置一個(gè)最早出發(fā)時(shí)間。最早出發(fā)時(shí)間和最晚到達(dá)時(shí)間之間的間隔由乘客依據(jù)對接駁系統(tǒng)的速度和舒適性等因素的預(yù)期進(jìn)行設(shè)定。由此，乘客對接駁服務(wù)全過程的開始和結(jié)束時(shí)間設(shè)置上下界，即全服務(wù)時(shí)間窗。區(qū)別于常見的出發(fā)或到達(dá)的單點(diǎn)時(shí)間窗將運(yùn)輸服務(wù)視為割裂的上車、在車及下車這3 段，全服務(wù)時(shí)間窗從整體上把握為乘客提供的運(yùn)輸服務(wù)，綜合了乘客對出發(fā)、到達(dá)及行程時(shí)間的要求，將服務(wù)水平的決定權(quán)部分讓渡給乘客。這一設(shè)置符合接駁公交系統(tǒng)中接駁終點(diǎn)的高時(shí)效性以及乘客對從居住地到出行過程的抵觸。而現(xiàn)有文獻(xiàn)中卻鮮有研究這一符合實(shí)際的時(shí)間窗要求。

有鑒于此，本文提出考慮需求的多個(gè)互斥候選站點(diǎn)和包括需求最早出發(fā)時(shí)間和最晚到達(dá)時(shí)間的全服務(wù)過程時(shí)間窗的服務(wù)出行第一公里的需求響應(yīng)接駁公交調(diào)度問題，實(shí)現(xiàn)對車隊(duì)規(guī)模配置和車輛路徑的聯(lián)合優(yōu)化；并在基于實(shí)際路網(wǎng)的案例上進(jìn)行實(shí)驗(yàn)，分析候選站點(diǎn)和全服務(wù)時(shí)間窗對系統(tǒng)性能和乘客行程時(shí)間的影響。

1 模型建立

1.1 問題描述

本文的需求響應(yīng)接駁公交系統(tǒng)以大型接駁站為需求服務(wù)終點(diǎn)，車輛從車場出發(fā)，訪問并服務(wù)站點(diǎn)后將需求送至目的接駁站。需求在預(yù)約系統(tǒng)內(nèi)提交出行預(yù)約，預(yù)約信息包含候選上車站點(diǎn)集合，目的接駁站及全服務(wù)時(shí)間窗。不同于普通意義上的出發(fā)或到達(dá)時(shí)間窗，全服務(wù)時(shí)間窗指在上車站點(diǎn)的最早出發(fā)時(shí)間及到達(dá)出行終點(diǎn)的最晚到達(dá)時(shí)間。運(yùn)營方在收到預(yù)約需求后，首先，需求進(jìn)行站點(diǎn)分配及車輛路徑規(guī)劃，然后，經(jīng)預(yù)約系統(tǒng)向乘客反饋具體的服務(wù)信息。由此可見，本文研究的需求響應(yīng)公交系統(tǒng)調(diào)度所涉及的子問題較多，包含車隊(duì)規(guī)模的確定，需求的互斥候選站點(diǎn)的選擇及車輛路徑問題。預(yù)約系統(tǒng)示例如圖1所示。

圖1 預(yù)約系統(tǒng)示例Fig.1 Illustration of a reservation system

需求響應(yīng)接駁公交系統(tǒng)示例如表1 和圖2 所示。假設(shè)需求的全服務(wù)時(shí)間窗在以下路徑構(gòu)建過程中均不會被違反。若每個(gè)需求只指定一個(gè)上車站點(diǎn)，需求1，2，3分別選擇站點(diǎn)1，3，5，此時(shí)車輛須分別訪問3個(gè)站點(diǎn)才能服務(wù)所有乘客，即車輛路徑1為車場-站點(diǎn)1-站點(diǎn)3-站點(diǎn)5-終點(diǎn)，路徑距離為12。若每位乘客均可選擇多個(gè)候選站點(diǎn)，需求a選擇步行可達(dá)范圍內(nèi)的站點(diǎn)1和站點(diǎn)2，需求2選擇站點(diǎn)3和站點(diǎn)4，需求3選擇站點(diǎn)4和站點(diǎn)5。此時(shí)，車輛僅通過訪問1 個(gè)站點(diǎn)(站點(diǎn)4)即可服務(wù)乘客2 和乘客3。另外，在站點(diǎn)2服務(wù)乘客1相較于站點(diǎn)1也可以減少車輛的行駛距離。由此，需求的站點(diǎn)選擇結(jié)果為需求1為站點(diǎn)2，需求2為站點(diǎn)4，需求3為站點(diǎn)4；車輛路徑2為車場-站點(diǎn)2-站點(diǎn)4-終點(diǎn)，路徑距離為8。兩種情況下的路徑如圖2所示。

表1 示例系統(tǒng)的距離矩陣Table 1 Distance matrix of sample DRFT system

圖2 需求響應(yīng)接駁公交系統(tǒng)示例Fig.2 Illustration of a DRFT system

為降低問題維度，本文基于候選站點(diǎn)構(gòu)建虛擬站點(diǎn)到實(shí)際需求集合和實(shí)際站點(diǎn)集合的映射，并構(gòu)建考慮節(jié)點(diǎn)關(guān)系與空間距離的虛擬節(jié)點(diǎn)間的阻抗矩陣，將本文的復(fù)雜調(diào)度問題轉(zhuǎn)化為帶有全服務(wù)時(shí)間窗和容量約束的車隊(duì)規(guī)模確定和車輛路徑問題(Fleet Size Determination and Vehicle Routing Problem with Capacity and Full-Service Time Windows,FSVRP-C-FSTW)。

1.2 問題預(yù)處理

1.2.1 需求集合與站點(diǎn)集合

為描述基于需求候選站點(diǎn)需求響應(yīng)公交的調(diào)度問題，將實(shí)際潛在站點(diǎn)集合記為S，實(shí)際需求集合記為R。需求集合中的每個(gè)需求r的信息包括由最早出發(fā)時(shí)間和最晚到達(dá)時(shí)間構(gòu)成的全服務(wù)時(shí)間窗[er,lr]和從潛在站點(diǎn)集合中選擇的若干站點(diǎn)構(gòu)成的候選站點(diǎn)集合Ur(Ur?S)。以圖2 所示的接駁公交系統(tǒng)為例，需求信息如表2所示，其中，所有需求的全服務(wù)時(shí)間窗均假設(shè)為[0,15]。需求的互斥候選站點(diǎn)的選擇即從每個(gè)需求指定的多個(gè)候選站點(diǎn)中選擇，該設(shè)定使各站點(diǎn)的需求量構(gòu)成具有一定的隨機(jī)性，因此，增大了車輛路徑規(guī)劃的難度。為降低問題維度，從實(shí)際候選站點(diǎn)的角度出發(fā)，將被多個(gè)需求選擇的同一實(shí)際站點(diǎn)復(fù)制若干次，得到對應(yīng)同一實(shí)際站點(diǎn)的多個(gè)包含不同需求信息的虛擬站點(diǎn)。經(jīng)以上步驟構(gòu)建的虛擬站點(diǎn)集合記為P。從而，實(shí)際需求集合R、實(shí)際潛在站點(diǎn)集合S及虛擬站點(diǎn)集合P之間構(gòu)成以下映射。

表2 需求信息示例Table 2 Illustration of demand information

f1:P→R為虛擬站點(diǎn)集合到實(shí)際需求集合的滿射但非單射；f2:P→S為虛擬站點(diǎn)集合到實(shí)際潛在站點(diǎn)集合的非滿射非單射(存在未被任何實(shí)際需求選擇的站點(diǎn))。以圖2 的接駁公交系統(tǒng)和表2的需求信息為例，該系統(tǒng)對應(yīng)的實(shí)際需求集合、實(shí)際潛在站點(diǎn)集合及構(gòu)建的虛擬站點(diǎn)集合如表3 所示，集合間的映射如圖3所示。

表3 需求與站點(diǎn)集合示例Table 3 Illustration of request set and stop set

圖3 集合映射示例Fig.3 Illustration of mappings

1.2.2 阻抗矩陣的構(gòu)建

為定義虛擬站點(diǎn)之間及其與車輛出發(fā)車場和接駁終點(diǎn)間的阻抗，本文的需求響應(yīng)公交問題可定義在完全有向圖G=(V,A) 上，其中，節(jié)點(diǎn)集合V=O∪P∪D，O={0}為代表車場的單元素集合；P={1,2,…,|P|}為生成的虛擬站點(diǎn)集合，記虛擬站點(diǎn)數(shù)量為n，即 |P|=n；D={n+1} 為表示接駁終點(diǎn)的單元素集合。A為集合V中節(jié)點(diǎn)間弧的集合。

基于虛擬站點(diǎn)集合P與實(shí)際需求集合R和實(shí)際站點(diǎn)集合S間的映射關(guān)系，本文將節(jié)點(diǎn)間的阻抗定義為節(jié)點(diǎn)間關(guān)系與空間距離的結(jié)合。實(shí)際站點(diǎn)集合S中兩兩之間及車場和接駁終點(diǎn)與實(shí)際站點(diǎn)間的行駛時(shí)間可通過直線距離和路徑距離等方式測算，對集合P中虛擬站點(diǎn)兩兩之間的距離及行駛時(shí)間須由虛擬站點(diǎn)到實(shí)際站點(diǎn)間的映射關(guān)系確定，即及，使轉(zhuǎn)化后的問題與原問題的約束、目標(biāo)及解相同。

考慮需求指定多個(gè)候選站點(diǎn)的特點(diǎn)，本文定義并量化節(jié)點(diǎn)間的需求對應(yīng)與空間關(guān)系，引入矩陣Θ和矩陣Φ分別表示節(jié)點(diǎn)間的需求對應(yīng)關(guān)系和位置關(guān)系，其中，元素θij和φij分別表示節(jié)點(diǎn)i和j(i,j∈V)是否對應(yīng)同一實(shí)際需求或同一實(shí)際站點(diǎn)，其值由表4 確定。若節(jié)點(diǎn)i和j均為虛擬站點(diǎn)，即i,j∈P，則θij和φij為邏輯判斷得到的布爾值的整數(shù)型(0 或1)。為系統(tǒng)描述所有候選站點(diǎn)的需求對應(yīng)關(guān)系，引入平均候選站點(diǎn)數(shù)量(記為uˉ)和與之相關(guān)的需求同質(zhì)度(記為HP)指標(biāo)定量化描述所有需求。假設(shè)指定u(u∈?+)個(gè)候選站點(diǎn)的需求量為mu，則指定不同候選站點(diǎn)的需求量之和為需求集合R的基數(shù)，即。由候選站點(diǎn)的構(gòu)建過程可計(jì)算所有的候選站點(diǎn)數(shù)量，即集合P的基數(shù)為，所有候選站點(diǎn)間的需求對應(yīng)參數(shù)之和為。由此，所有需求的平均候選站點(diǎn)數(shù)量，所有候選站點(diǎn)的需求同質(zhì)度

表4 θij,φij 的確定Table 4 Determination of values of θij,φij

1.3 模型假設(shè)

為描述考慮候選站點(diǎn)和全服務(wù)時(shí)間窗的需求響應(yīng)公交調(diào)度問題，做如下假設(shè)：

(1)需求所指定的出發(fā)時(shí)間窗下界和到達(dá)時(shí)間窗上界之間的時(shí)間間隔須大于其候選起點(diǎn)至訖點(diǎn)間的直接行駛時(shí)間的最大值；

(2)假設(shè)需求集合R每個(gè)需求的需求量均為1，若存在某個(gè)需求的需求量大于1，則將其復(fù)制裂變成多個(gè)需求量為1的預(yù)約信息相同的需求；

(3)服務(wù)過程中不存在換乘；

(4)乘客按照規(guī)劃的時(shí)間到達(dá)既定站點(diǎn)，不考慮乘客的晚到和不到情況；

(5)假設(shè)可使用車輛足以服務(wù)所有需求。每輛車完成1個(gè)車次任務(wù)，即將所有需求送至接駁終點(diǎn)站后即結(jié)束行程，不考慮單車執(zhí)行多車次任務(wù)或返回車場。

1.4 模型參數(shù)

主要模型參數(shù)解釋如下：

G=(V,A)——節(jié)點(diǎn)集合V和節(jié)點(diǎn)間弧的集合A構(gòu)成的有向圖，其中，V=O∪P∪D，即節(jié)點(diǎn)集合包含車場集合O={0}，虛擬站點(diǎn)集合P={1,2,…,n}，終點(diǎn)集合D={n+1} ；

R——實(shí)際需求集合，R={1,2,…,|R|}；

K——車輛集合，K={1,2,…,|K|}；

Q——車輛的額定載客量(人·車-1)；

[ei,li]——節(jié)點(diǎn)i∈V的全服務(wù)時(shí)間窗，若i∈P，表示虛擬站點(diǎn)的全服務(wù)時(shí)間窗，即在上車站點(diǎn)上車的最早出發(fā)時(shí)間和到達(dá)接駁站的最晚到達(dá)時(shí)間，虛擬站點(diǎn)的全服務(wù)時(shí)間窗應(yīng)與其對應(yīng)的實(shí)際需求的全服務(wù)時(shí)間窗相同，即，若i∈O∪D，表示車場或接駁終點(diǎn)的全服務(wù)時(shí)間窗，兩者均設(shè)置為整個(gè)規(guī)劃時(shí)段；

c1——車輛k的啟動成本(元·車次-1)；

c2——車輛單位距離運(yùn)行成本(元·km-1)；

s——平均每位乘客在站服務(wù)時(shí)間(s·人-1)；

tij和dij——節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的行駛時(shí)間(s)和路徑距離(km)，取決于節(jié)點(diǎn)間的需求及空間關(guān)系，由構(gòu)建的阻抗矩陣確定；

Tik——輔助變量，表示車輛k在節(jié)點(diǎn)i開始服務(wù)的時(shí)間；

Lik——輔助變量，表示車輛k離開節(jié)點(diǎn)i時(shí)的載客量；

Xijk——決策變量，表示車輛k是否從節(jié)點(diǎn)i直接行駛到節(jié)點(diǎn)j的0-1 變量，若是，值為1，否則為0。

1.5 FSVRP-C-FSTW模型

基于以上映射和阻抗矩陣的構(gòu)建，本文將考慮候選站點(diǎn)和全服務(wù)時(shí)間窗的需求響應(yīng)接駁公交調(diào)度問題轉(zhuǎn)化為帶有全服務(wù)時(shí)間窗和容量約束的車隊(duì)規(guī)模確定和車輛路徑問題(FSVRP-C-FSTW)進(jìn)行建模求解。

式(1)為目標(biāo)函數(shù)，表示該優(yōu)化問題以最小化總成本為目標(biāo)，總成本包括固定成本和可變成本，其中，固定成本為用于服務(wù)的車隊(duì)規(guī)模與單位車輛啟動成本之積，可變成本即單位距離成本與總路徑距離的乘積。式(2)～式(4)保證所有實(shí)際需求均在其指定的候選站點(diǎn)被服務(wù)，其中，式(2)表示1 個(gè)虛擬站點(diǎn)最多被1 輛車服務(wù)1 次；式(3)保證僅指定1 個(gè)候選站點(diǎn)的需求一定在其指定的站點(diǎn)被服務(wù)；式(4)保證指定了多個(gè)候選站點(diǎn)的實(shí)際需求僅在其中一個(gè)站點(diǎn)被服務(wù)。式(5)～式(7)保證車輛從車場出發(fā)，訪問服務(wù)若干站點(diǎn)后到達(dá)接駁終點(diǎn)，其中，式(5)保證車輛從車場出發(fā)，若車輛從車場出發(fā)后訪問站點(diǎn)服務(wù)需求，則車輛啟用，否則車輛不啟用；式(6)保證虛擬站點(diǎn)的流平衡；式(7)表示所有從車場出發(fā)的車輛最后均在接駁終點(diǎn)結(jié)束服務(wù)。式(8)～式(10)為載客量約束，式(8)保證車輛空車從車場出發(fā)；式(9)確保車輛離開任意點(diǎn)時(shí)的載客量不超過其容量；式(10)確保車輛離開任意點(diǎn)時(shí)的載客量不低于該點(diǎn)的需求量和離開前一節(jié)點(diǎn)時(shí)的載客量之和。式(10)和式(11)保證車輛路徑中不含有子回路。式(12)和式(13)為全服務(wù)時(shí)間窗約束，式(12)保證車輛到達(dá)接駁終點(diǎn)的時(shí)間不晚于其服務(wù)的所有需求的最晚到達(dá)時(shí)間；式(13)保證車輛在任意虛擬站點(diǎn)的開始服務(wù)時(shí)間不早于該點(diǎn)需求的最早出發(fā)時(shí)間。式(14)為決策變量的取值約束。

2 模型求解

2.1 精確解

該模型為混合整數(shù)非線性規(guī)劃，其非線性特點(diǎn)由非線性約束式(10)～式(12)決定。為簡化模型求解，將式(10)進(jìn)行線性化處理，即

將式(11)進(jìn)行線性化處理，即

式中：Mij=max{li-ti,n+1+s(1-φij)+tij-ej,0} 。

將式(12)進(jìn)行線性化處理，即

式中：M為足夠大的正數(shù)。

經(jīng)過對模型中非線性約束進(jìn)行線性化處理，模型轉(zhuǎn)化為混合整數(shù)線性規(guī)劃模型。本文調(diào)用Gurobi 求解器求解模型，其中，為避免因交換車輛下標(biāo)k而導(dǎo)致的相同解，本文引入車輛編號對稱性消除約束，即要求較小下標(biāo)的需求由較小下標(biāo)的車輛提供運(yùn)輸服務(wù)[13]，其中，需求的服務(wù)需在多個(gè)候選站點(diǎn)中進(jìn)行選擇。為消除同一實(shí)際站點(diǎn)的多個(gè)需求服務(wù)時(shí)的次序不同帶來的相同解，引入同站需求序列唯一性約束，即車輛服務(wù)某一實(shí)際站點(diǎn)時(shí)，優(yōu)先選擇較小標(biāo)號的需求。以圖3 和表3 中虛擬站點(diǎn)和需求間的對應(yīng)關(guān)系為例，假設(shè)車輛額定載客量為2，對應(yīng)相同車輛路徑的多個(gè)解如表5所示。

表5 對應(yīng)相同車輛路徑的多個(gè)解Table 5 Multiple solutions representing same vehicle routes

其中，4個(gè)解均對應(yīng)相同的路徑，即一輛車在實(shí)際站點(diǎn)s2服務(wù)實(shí)際需求r1，另一輛車在實(shí)際站點(diǎn)s4服務(wù)實(shí)際需求r2和r3。通過引入約束可將解2～解4消除，僅保留解1，即

考慮單個(gè)需求與多個(gè)候選站點(diǎn)之間的對應(yīng)關(guān)系，式(18)保證標(biāo)號為1 的實(shí)際需求對應(yīng)的所有虛擬需求中有且僅有一個(gè)被標(biāo)號為1 的車輛服務(wù)。式(19)保證任意虛擬需求及與其對應(yīng)同一實(shí)際需求的其他虛擬需求被服務(wù)的車輛的編號應(yīng)不大于服務(wù)編號小于該實(shí)際需求對應(yīng)的任意虛擬需求的車輛的編號。式(20)保證不同需求在同一實(shí)際站點(diǎn)被服務(wù)時(shí)，標(biāo)號較小的實(shí)際需求對應(yīng)的站點(diǎn)優(yōu)先被選擇。

經(jīng)過以上步驟求解得到的為在虛擬節(jié)點(diǎn)網(wǎng)絡(luò)上的車輛路徑，通過虛擬站點(diǎn)到實(shí)際需求與實(shí)際站點(diǎn)的映射關(guān)系可得到在實(shí)際路網(wǎng)上的需求的站點(diǎn)分配結(jié)果與車輛路徑。

2.2 自適應(yīng)鄰域模擬退火算法

本文研究的問題可視為帶有全服務(wù)時(shí)間窗和容量約束的車隊(duì)規(guī)模確定和車輛路徑問題(FSVRP-C-FSTW)，即帶有復(fù)雜約束的車輛路徑問題，此類問題為NP難問題，在問題規(guī)模稍大時(shí)即無法實(shí)現(xiàn)精確求解，因此，本文設(shè)計(jì)了一種啟發(fā)式算法用于求解，該算法針對問題特征設(shè)計(jì)4種鄰域結(jié)構(gòu)，并參考文獻(xiàn)[14]在模擬退火算法框架下引入自適應(yīng)鄰域機(jī)制。算法主要框架為在內(nèi)層循環(huán)中不斷選擇鄰域結(jié)構(gòu)并生成新解更新當(dāng)前解；在外層循環(huán)中更新溫度和鄰域選擇參數(shù)，并更新當(dāng)前最優(yōu)解。

2.2.1 解的表示

算法初始化時(shí)，將解初始化為虛擬站點(diǎn)的隨機(jī)序列，序列長度等于實(shí)際需求量，每個(gè)虛擬站點(diǎn)分別對應(yīng)不同的實(shí)際需求，保證所有需求均被服務(wù)。解對應(yīng)的實(shí)際路徑則通過首先激活1輛車，根據(jù)虛擬站點(diǎn)的序列依次插入當(dāng)前車輛路徑，當(dāng)后續(xù)節(jié)點(diǎn)加入違反全服務(wù)時(shí)間窗和載客量約束時(shí)，新增車輛并置為當(dāng)前車輛，然后，繼續(xù)依次插入當(dāng)前車輛路徑，以此循環(huán)，直至解的所有節(jié)點(diǎn)均已被插入某車輛路徑。由此可知，算法執(zhí)行過程中產(chǎn)生的解均滿足載客量和全服務(wù)時(shí)間窗約束，解的目標(biāo)函數(shù)值則通過其對應(yīng)的實(shí)際路徑參考目標(biāo)函數(shù)式(1)計(jì)算得到。以圖3 和表3 中的虛擬站點(diǎn)和需求間的對應(yīng)關(guān)系為例，假設(shè)車輛的額定載客量為2，不考慮時(shí)間窗約束，表示為3-5-1的解對應(yīng)的實(shí)際路徑為車輛1在站點(diǎn)s3和s4分別服務(wù)r2和r3，車輛2在站點(diǎn)s1服務(wù)r1。

2.2.2 鄰域結(jié)構(gòu)

算法內(nèi)層循環(huán)中涉及的鄰域結(jié)構(gòu)包括：交換、插入、逆轉(zhuǎn)和需求重置這4 種鄰域。以圖3 和表3的需求為例，為更清楚地展示不同鄰域結(jié)構(gòu)的操作過程，在圖3的需求基礎(chǔ)上增加指定站點(diǎn)s2和s5的需求r4，分別對應(yīng)虛擬站點(diǎn)集合P中的新增元素7和元素8。不同鄰域結(jié)構(gòu)作用于相同解得到的結(jié)果如圖4所示，左側(cè)為原解，其中，灰色格子代表鄰域操作選擇的位置；右側(cè)表示不同鄰域作用后的新解，其中，灰色格子代表新解相對于原解的改動。前3 種鄰域均需要隨機(jī)選擇序列上的2 個(gè)位置，交換鄰域?qū)?個(gè)位置上的虛擬站點(diǎn)進(jìn)行交換，插入鄰域通過將選中的較前位置的虛擬站點(diǎn)插入到較后位置的虛擬站點(diǎn)之后，逆轉(zhuǎn)鄰域則將2個(gè)位置間的虛擬站點(diǎn)序列進(jìn)行翻轉(zhuǎn)。以上3 種鄰域結(jié)構(gòu)均不改變需求的站點(diǎn)分配情況。需求重置鄰域通過選擇序列上的1個(gè)位置，將該位置的需求重置到其他候選站點(diǎn)，即實(shí)現(xiàn)了需求的站點(diǎn)重分配。

圖4 鄰域結(jié)構(gòu)示例Fig.4 Illustration of neighborhood structure

圖4 中的虛擬站點(diǎn)3 經(jīng)過需求重置，更換為虛擬站點(diǎn)4。其需求重置過程須首先參考圖3中節(jié)點(diǎn)集合的映射，得知虛擬站點(diǎn)3 對應(yīng)實(shí)際需求為r2，然后，將該點(diǎn)重置為該需求r2對應(yīng)的其他虛擬站點(diǎn)，即為虛擬站點(diǎn)4。

內(nèi)層循環(huán)中鄰域選擇通過輪盤賭實(shí)現(xiàn)，每個(gè)鄰域的選擇概率為該鄰域結(jié)構(gòu)下已產(chǎn)生解的平均值除以所有鄰域結(jié)構(gòu)下產(chǎn)生解的平均值，因此，每次外循環(huán)迭代中需更新的鄰域選擇參數(shù)即包括每個(gè)鄰域已產(chǎn)生解的目標(biāo)函數(shù)的平均值，及所有鄰域結(jié)構(gòu)已生成解的目標(biāo)函數(shù)的平均值。

2.2.3 算法流程

該算法的具體流程如下：

Step 1 初始化。生成初始解，并置為當(dāng)前解x和當(dāng)前最優(yōu)解x*。當(dāng)前溫度T初始化為初始溫度T0。鄰域選擇概率初始化為相同的概率。

Step 2 若當(dāng)前溫度T＞最低溫度Tf，執(zhí)行內(nèi)層循環(huán)，即Step 3；否則，執(zhí)行Step 5。

Step 3 內(nèi)層循環(huán)。

Step 3.1 判斷是否滿足內(nèi)層迭代終止條件，若是，執(zhí)行Step 4；否則，執(zhí)行Step 3.2。

Step 3.2 輪盤賭選擇鄰域結(jié)構(gòu)，并在相應(yīng)鄰域內(nèi)產(chǎn)生新解x。

Step 3.3 若新解優(yōu)于當(dāng)前解，則更新當(dāng)前解；否則，以exp(-ΔT)的概率接受新解為當(dāng)前解，其中，Δ=f′-f，表示新解目標(biāo)函數(shù)值f′和當(dāng)前解的目標(biāo)函數(shù)值f間的差。轉(zhuǎn)至Step 3.1。

Step 4 比較并更新當(dāng)前最優(yōu)解、溫度和鄰域選擇參數(shù)。轉(zhuǎn)至Step 2。

Step 5 輸出當(dāng)前最優(yōu)解。

3 算例研究

3.1 算例信息

本文以圖5 所示的實(shí)際路網(wǎng)為案例基礎(chǔ)進(jìn)行實(shí)驗(yàn)，以廣州大學(xué)城內(nèi)90個(gè)公交站點(diǎn)為潛在站點(diǎn)，其中，大學(xué)城穗石村總站作為車場，構(gòu)建面向廣州南站考慮候選站點(diǎn)和全服務(wù)時(shí)間窗的需求響應(yīng)接駁公交系統(tǒng)。由于本文設(shè)想的公交系統(tǒng)尚未落地，因此，實(shí)驗(yàn)中的客流需求將依據(jù)實(shí)際路網(wǎng)生成。站點(diǎn)信息、站點(diǎn)間的行駛距離與行駛時(shí)間等信息均通過調(diào)用高德地圖API 獲取。為分析模型性能并分析候選站點(diǎn)和全服務(wù)時(shí)間窗，本文生成了不同規(guī)模的需求場景(實(shí)際需求量分別為9，15，30，45)，并分別在Gurobi 求解器中精確求解模型和利用自適應(yīng)鄰域模擬退火的啟發(fā)式算法求解模型，以驗(yàn)證模型和本文設(shè)計(jì)算法的有效性。除此之外，對可在求解器內(nèi)快速求解的小規(guī)模算例進(jìn)行需求參數(shù)修改，包括候選站點(diǎn)和時(shí)間窗參數(shù)，通過求解器求解修改后的算例分析候選站點(diǎn)和全服務(wù)時(shí)間窗對系統(tǒng)性能的影響。

圖5 案例的接駁終點(diǎn)和潛在站點(diǎn)Fig.5 Destination and potential stops

為明確不同算例下需求所包含的站點(diǎn)和時(shí)間窗參數(shù)，設(shè)計(jì)具有9 個(gè)實(shí)際訂單需求，指定20 個(gè)候選站點(diǎn)，即對應(yīng)20個(gè)虛擬需求的案例，需求指定的候選站點(diǎn)及全服務(wù)時(shí)間窗如表6所示。

表6 需求訂單信息Table 6 Demand information

車場及終點(diǎn)的時(shí)間窗設(shè)置為5:30-8:00。為分析候選站點(diǎn)對系統(tǒng)性能的影響，以表6 為基礎(chǔ)，所有訂單的候選站點(diǎn)僅保留第1個(gè)站點(diǎn)，其余信息不變，生成訂單僅指定唯一上車站點(diǎn)的案例。為分析全服務(wù)時(shí)間窗對系統(tǒng)性能的影響，以表6 為基礎(chǔ)，候選站點(diǎn)信息不變，對時(shí)間窗進(jìn)行修改得到多種時(shí)間約束下的案例。

實(shí)驗(yàn)所需參數(shù)設(shè)置如表7所示。其中，模型參數(shù)設(shè)置如下：車輛額定載客量根據(jù)實(shí)際需求量不同分別設(shè)置為3，5，7，10；車輛啟動成本考慮駕駛員薪資和車輛折舊等因素，因車輛均為小車型，且算例中僅考慮單車次服務(wù)，因此，參考文獻(xiàn)[15]將車輛啟動成本設(shè)置為20元·車次-1；車輛單位行駛距離成本主要包括燃料成本，設(shè)置為1 元·km-1。在站服務(wù)時(shí)間設(shè)置為20 s。算法參數(shù)設(shè)置如下：初始溫度為500，最低溫度為1，降溫率為0.997，內(nèi)循環(huán)迭代次數(shù)為300。算例在配置為Intel(R) Core(TM)i7-7560U CPU@2.40 GHz，16 GB RAM 的計(jì)算機(jī)上利用MATLAB調(diào)用Gurobi求解器及編程實(shí)現(xiàn)自適應(yīng)鄰域模擬退火算法求解。

表7 參數(shù)設(shè)置Table 7 Parameters

3.2 算例分析

3.2.1 模型與算法性能分析

為分析車輛編號對稱性消除和同站需求序列唯一性式(18)～式(20)對模型求解的作用，將式(1)～式(9)，式(13)～式(20)構(gòu)成的模型記為模型1，式(1)～式(9)，式(13)～式(17)構(gòu)成的模型記為模型2，分別用于求解不同規(guī)模的算例，模型求解時(shí)間限制在1 h內(nèi)；同時(shí)，本文設(shè)計(jì)的自適應(yīng)鄰域模擬退火算法也用于求解不同規(guī)模的算例，以驗(yàn)證該算法的有效性，結(jié)果如表8所示。結(jié)果表明，在小規(guī)模算例下，兩個(gè)模型在求解器中均求得最優(yōu)解，式(18)～式(20)的加入有效加速了模型用于小規(guī)模算例的求解。在實(shí)際需求量為15和 |P|=37 對應(yīng)的算例下，不同模型求解得到相同的目標(biāo)值，但模型1的GAP小于模型2，即模型1 得到的下界高于模型2，表明式(18)～式(20)的加入對于下界的提升有一定作用。而在實(shí)際需求量為30 和 |P|=64 對應(yīng)的算例下，模型1 未能在規(guī)定時(shí)間內(nèi)求得可行解，表明式(18)～式(20)的加入增加了模型的求解難度。通過比較求解器和啟發(fā)式算法求解的結(jié)果可得，在小規(guī)模算例下，本文設(shè)計(jì)的自適應(yīng)鄰域模擬退火啟發(fā)式算法求得的解可達(dá)到最優(yōu)，求解時(shí)間介于模型1和模型2 之間；對于稍大規(guī)模的算例，啟發(fā)式算法在顯著少于求解器求解時(shí)間內(nèi)，求得的解的目標(biāo)函數(shù)值(即總成本)低于求解器在規(guī)定時(shí)間內(nèi)求得的結(jié)果。

表8 模型與算法對比Table 8 Comparison of models and algorithms

綜上所述，車輛編號對稱性消除和同站需求序列唯一性約束的引入對于模型在求解器中的精確求解可在一定程度上加速下界的提升，從而加速小規(guī)模算例的求解。自適應(yīng)鄰域模擬退火算法在小規(guī)模算例中可求得最優(yōu)解，在稍大規(guī)模算例下可在較短時(shí)間內(nèi)求得較優(yōu)的解。

3.2.2 候選站點(diǎn)的引入對系統(tǒng)的影響

根據(jù)算例的需求信息、模型參數(shù)及式(1)～式(9)和式(13)～式(20)求解結(jié)果分析候選站點(diǎn)的引入對系統(tǒng)的影響，對實(shí)際需求量為9 和 |P|=20 的案例中需求指定的候選站點(diǎn)進(jìn)行刪減，得到30個(gè)案例，案例信息如表9所示。案例1即為表6對應(yīng)的基準(zhǔn)案例，假設(shè)需求指定的多個(gè)候選站點(diǎn)均按步行距離升序排列。案例30即為所有需求僅指定唯一上車站點(diǎn)的案例，其他案例均由案例1進(jìn)行需求的候選站點(diǎn)的修改得到，其中，在減少需求指定站點(diǎn)數(shù)量時(shí)，優(yōu)先刪減距離較遠(yuǎn)站點(diǎn)，即表6第2列中靠后的站點(diǎn)。求解所有案例，得到服務(wù)需求所需車隊(duì)規(guī)模、車輛總路徑長度、乘客平均行程時(shí)間和目標(biāo)值，即總成本。系統(tǒng)總成本和乘客平均行程時(shí)間均與Hp，即虛擬站點(diǎn)的需求同質(zhì)度相關(guān)，如圖6 所示。就總體趨勢而言，虛擬站點(diǎn)的需求同質(zhì)度較高時(shí)，系統(tǒng)總成本較低，同時(shí)，乘客平均行程時(shí)間較長。原因是，較高的需求同質(zhì)度值代表車輛訪問多個(gè)不同的虛擬站點(diǎn)中任意1個(gè)均可服務(wù)某個(gè)需求，從而放松了需求服務(wù)對車輛路徑的限制，成本得以向目標(biāo)方向優(yōu)化，得到較小的總成本；總成本的降低主要源于需求共乘可能性增加帶來的所需車隊(duì)規(guī)模的減少，導(dǎo)致乘客行程時(shí)間的增加。其中，需求指定多個(gè)候選站點(diǎn)的不同案例結(jié)果中，相同的總路徑長度對應(yīng)不同的乘客平均時(shí)間的原因在于路徑服務(wù)的站點(diǎn)序列和需求序列的不同。

表9 候選站點(diǎn)對系統(tǒng)的影響Table 9 Effect of candidate stops on system

圖6 候選站點(diǎn)對成本和乘客行程時(shí)間的影響Fig.6 Effect of candidate stops on costs and users'ride time

為進(jìn)一步觀察候選站點(diǎn)對路徑細(xì)節(jié)的影響，基準(zhǔn)案例和需求僅指定唯一上車站點(diǎn)的案例，即案例1 和案例30 路徑的實(shí)際站點(diǎn)序列和實(shí)際服務(wù)的需求序列信息如表10所示。在服務(wù)相同需求的情況下，案例1使用3輛車，固定成本為60元，總路徑長度為91938 m，路徑成本為91.938 元，總成本為151.938 元；案例30 需4 輛車，固定成本為80 元，總路徑長度為118150 m，路徑成本為118.15 元，總成本為198.15元。相較于案例30，考慮候選站點(diǎn)的案例1 的固定成本和路徑成本分別減少25%和22.19%，總成本減少了23.32%。結(jié)果表明，相較于每個(gè)乘客僅指定唯一上車站點(diǎn)的情況，考慮候選站點(diǎn)可增加需求間共乘的可能性，減少所需車輛數(shù)及總路徑長度，由此帶來固定成本和可變成本的降低；同時(shí)，車輛數(shù)及行駛距離的減少對于交通所帶來的一系列外部問題(例如，環(huán)境污染和交通噪聲等)亦有一定程度的緩解作用。

表10 有無候選站點(diǎn)的對比結(jié)果Table 10 Comparison results of candidate stops

3.2.3 全服務(wù)時(shí)間窗對系統(tǒng)的影響

為分析包含最早出發(fā)時(shí)間和最晚到達(dá)時(shí)間全服務(wù)時(shí)間窗的引入對系統(tǒng)的影響，本文對比實(shí)際需求量為9 的算例下含行程時(shí)間約束和單點(diǎn)一端時(shí)間窗約束的需求響應(yīng)公交的路徑優(yōu)化結(jié)果。其中，行程時(shí)間的最大值由全服務(wù)時(shí)間窗的寬度(如表6的最后1列)決定，單點(diǎn)一端時(shí)間窗指僅指定出發(fā)或到達(dá)的時(shí)間窗，且時(shí)間窗僅指定上界(到達(dá)點(diǎn)的時(shí)間窗上界，即最晚到達(dá)時(shí)間，如表6 的第4 列)或下界(上車點(diǎn)的時(shí)間窗下界，即最早出發(fā)時(shí)間，如表6的第3 列)。以表6 為基礎(chǔ)案例1，即需求指定最早出發(fā)時(shí)間及最晚到達(dá)時(shí)間。其余案例包含的時(shí)間約束信息如表11所示。另以需求僅指定唯一上車站點(diǎn)的案例30 為基礎(chǔ)，進(jìn)行時(shí)間約束的修改，如表11所示。案例的結(jié)果如表12所示，包括使用車輛數(shù)、總路徑長度、總成本及乘客平均行程時(shí)間。結(jié)果表明，在需求僅指定唯一上車站點(diǎn)時(shí)，相較于全服務(wù)時(shí)間窗約束，單一端點(diǎn)的時(shí)間窗上(下)界約束或同等寬度的全服務(wù)時(shí)間窗約束下的乘客行程時(shí)間增加0.5%，車輛數(shù)減少1 輛，總路徑距離減少23.3%，總成本減少24%。在需求指定多個(gè)候選站點(diǎn)時(shí)，相較于全服務(wù)時(shí)間窗約束，單一端點(diǎn)的時(shí)間窗上(下)界約束或同等寬度的全服務(wù)時(shí)間窗約束下的乘客行程時(shí)間減少5%左右，車輛總路徑距離減少了約5%，總成本減少約3%，下降幅度較唯一上車站點(diǎn)的情況較小。原因是，基準(zhǔn)案例中包含起點(diǎn)最早出發(fā)時(shí)間和終點(diǎn)最晚到達(dá)時(shí)間的全服務(wù)時(shí)間窗約束，暗含乘客的行程時(shí)間在全服務(wù)時(shí)間窗寬度范圍內(nèi)的約束。而放松其中1 個(gè)約束則可增加需求間共乘的可能性。唯一上車站點(diǎn)的案例30的車隊(duì)規(guī)模仍有優(yōu)化空間，因此，其余時(shí)間要求較為松弛的案例36～40 均實(shí)現(xiàn)了車隊(duì)規(guī)模的減少以及總路徑距離和總成本的降低。而基準(zhǔn)案例因基準(zhǔn)案例1中使用的車隊(duì)規(guī)模已是最小值，即所有車輛均滿載，所以，增加的需求共乘可能性導(dǎo)致車輛總行駛距離降低，從而降低乘客平均行程時(shí)間。對比站點(diǎn)不同情況下的不同時(shí)間要求可得，相較于僅指定唯一上車站點(diǎn)的情況，考慮候選站點(diǎn)的案例下放松時(shí)間要求所帶來的成本和乘客行程時(shí)間的改善較小，由此可得，候選站點(diǎn)的引入彌補(bǔ)了全服務(wù)時(shí)間窗較緊的時(shí)間要求對路徑成本和乘客行程時(shí)間的負(fù)面影響。

表11 不同案例的時(shí)間約束信息Table 11 Time constraints for instances

表12 不同時(shí)間約束的對比結(jié)果Table 12 Comparison results for different time constraints

4 結(jié)論

本文得到的主要結(jié)論如下。

(1)基于乘客的多個(gè)可達(dá)站點(diǎn)及對最早出發(fā)時(shí)間和最晚到達(dá)時(shí)間的要求，研究考慮候選站點(diǎn)和全服務(wù)時(shí)間窗的需求響應(yīng)公交調(diào)度問題，該問題包含乘客的站點(diǎn)選擇，車隊(duì)規(guī)模的確定，及車輛路徑等子問題。為降低問題維度，首先，分析站點(diǎn)與需求間的關(guān)系，然后，構(gòu)建虛擬站點(diǎn)到實(shí)際需求和實(shí)際站點(diǎn)的映射關(guān)系，建立基于節(jié)點(diǎn)關(guān)系和空間距離的阻抗矩陣，將問題轉(zhuǎn)化為帶有全服務(wù)時(shí)間窗和容量約束的車隊(duì)規(guī)模確定和車輛路徑問題(FSVRP-CFSTW)模型。模型求解中，為避免因僅交換車輛編號而導(dǎo)致的若干重復(fù)解，增加車輛編號對稱性消除約束，即考慮候選站點(diǎn)的車輛編號對稱性消除和同站需求序列唯一性的約束，測試結(jié)果表明，該約束的引入可加速模型求解。為求解較大規(guī)模算例，基于問題特征設(shè)計(jì)多種鄰域結(jié)構(gòu)和基于多種鄰域的自適應(yīng)鄰域模擬退火算法，在多規(guī)模算例下驗(yàn)證了該算法的效率。

(2)以廣州大學(xué)城公交子網(wǎng)絡(luò)為例，基于實(shí)際路網(wǎng)生成案例進(jìn)行求解，驗(yàn)證模型及系統(tǒng)性能分析，并分析候選站點(diǎn)和全服務(wù)時(shí)間窗對系統(tǒng)性能的影響。結(jié)果表明：①需求的全服務(wù)時(shí)間窗和首個(gè)候選站點(diǎn)不變的情況下，所有需求構(gòu)成的所有虛擬站點(diǎn)間的需求同質(zhì)度的較高值可降低系統(tǒng)成本；②全服務(wù)時(shí)間窗相較于單點(diǎn)的一端時(shí)間窗和同等寬度的行程時(shí)間約束增加了路徑的成本和乘客的行程時(shí)間，但考慮候選站點(diǎn)情況下的增幅相對唯一上車站點(diǎn)情況下的增幅較為微小。換言之，候選站點(diǎn)的引入彌補(bǔ)了全服務(wù)時(shí)間窗較緊的時(shí)間要求對路徑成本和乘客行程時(shí)間的負(fù)面影響。