朱曉鋒

（廣州松田職業(yè)學(xué)院 信息工程學(xué)院，廣東 廣州 511370）

固定路線公交網(wǎng)絡(luò)和居民區(qū)連接的最后一公里接駁是公共交通面臨的主要挑戰(zhàn)之一。解決該問題的可行方法是規(guī)劃﹑設(shè)計和實施高效的支線運(yùn)輸服務(wù)［1］。傳統(tǒng)上，運(yùn)輸服務(wù)分為兩大類：固定路線（FRT）和需求響應(yīng)（DRT），F(xiàn)RT 不符合個人旅行的需求（接送地點(diǎn)或者下車地點(diǎn)的位置）和預(yù)定的時間表，而DRT 則提供門到門式的服務(wù)［2］。因此，與FRT 相比，DRT 能提供更高的便利性以及更低的運(yùn)營成本和更高的服務(wù)水平，尤其在低密度住宅區(qū)內(nèi)。

DRT 是帶時間窗的車輛路徑選擇問題（VRP）和提貨運(yùn)輸問題（PDP）的擴(kuò)展［3］。類似于具有多個時間窗口的VRP［4］，具有多個時間窗口的DRT 可以比單個時間窗口問題節(jié)省更多的里程。為了滿足乘客個性化的出行需求，設(shè)定乘客的最大和最小預(yù)期乘車時間，在不增加其他乘客在途時間的情況下追求最短的路線距離。

本文研究的另一個主要動機(jī)是要解決DRT 的乘客滿意度問題，其中涉及許多因素，例如公交車票價，交通擁堵和環(huán)境等。一些文獻(xiàn)研究了考慮顧客滿意度的VRP，但涉及DRT 的較少［5］。在不失一般性的前提下，它僅與支線運(yùn)輸操作中的預(yù)期乘車時間有關(guān)，即當(dāng)乘車時間在最小和最大期望值之間時，滿意度范圍為0 到1。顯然，更大的乘客滿意度和更多的車輛提供直接服務(wù)，這將增加總里程和運(yùn)營支出。因此，有必要研究乘客滿意度和總里程之間的最佳關(guān)系，以權(quán)衡服務(wù)質(zhì)量和運(yùn)營成本。

本文研究的主要目的是開發(fā)一種基于乘客多個時間窗口與滿意度的DRT 優(yōu)化模型，以提高服務(wù)質(zhì)量和降低運(yùn)營成本。重點(diǎn)研究以下兩個關(guān)鍵問題：1）協(xié)調(diào)乘客上車時間窗引導(dǎo)和支線運(yùn)輸路線選擇過程，以權(quán)衡總里程數(shù)和乘客滿意度；2）開發(fā)一種啟發(fā)式求解算法，以有效地產(chǎn)生所提出模式的可接受解。最后，通過實例仿真證明所提出的方法，并將該模型應(yīng)用于實際的DRT 優(yōu)化設(shè)計過程中。

1 問題描述

DRT 是一種門到門的運(yùn)輸服務(wù)，可為需求響應(yīng)型乘車人員的接駁問題提供解決方法［6］。人們通常將其描述為基本車輛路徑和調(diào)度問題的擴(kuò)展［7］，其中：車輛路徑問題（VRP）分配了一些車輛訪問一組地理位置分散的位置，接送問題（PDP）將貨物數(shù)量從某些取貨地點(diǎn)移動到某些交貨地點(diǎn)。但是，到目前為止討論的VRP 和PDP 與DRT 之間也存在明顯差異。VRP 和PDP 專注于貨物運(yùn)輸，而DRT 則關(guān)注人員運(yùn)輸。因此，與VRP 和PDP 相比，DRT 解決了更多其他問題，并且更加復(fù)雜。對于DRT 的回顧，它們大多數(shù)與服務(wù)和乘客便利性有關(guān)。由于FRT 人口密度低而效率不高，因此在這些調(diào)度區(qū)域，尤其是交通基礎(chǔ)設(shè)施薄弱的地區(qū)，DRT 表現(xiàn)更好［8］。

一般情況下，乘客是在特定的時間窗口中乘車的，從而導(dǎo)致具有時間窗口的VRP（VRPTW）和具有時間窗口的PDP（PDPTW）［9］。對于VRPTW 和PDPTW 的最新回顧，當(dāng)車輛返回停車場后可以立即采取另一條路線時，會出現(xiàn)另一種變化形式，稱為多次使用車輛的路線問題［10］。DRT 都是通過各種目標(biāo)解決的，包括最小化車隊以降低運(yùn)營成本，路線的最短長度或行程時間［11］，所需的最小車隊規(guī)模班車服務(wù)［1］，乘車時間和乘客等待時間。巧合的是，目標(biāo)通常不會影響DRT 的屬性，可以采用類似的模型和算法來解決具有不同目標(biāo)的問題。

DRT 問題屬于NP 難題，啟發(fā)式方法是最常用于DRT 以處理大量的車輛路線和調(diào)度方式。一些學(xué)者試圖通過先生成一組可行的路徑，然后搜索微調(diào)初始解來發(fā)展路徑構(gòu)建啟發(fā)式方法［3-4］。除了已開發(fā)的基于路徑構(gòu)建的啟發(fā)式算法外，還經(jīng)常采用三種廣泛使用的元啟發(fā)式方法來應(yīng)對VRPTW，例如進(jìn)化算法［3］，禁忌搜索［7］和遺傳算法［10］。

本文提出一種DRT，其提供的服務(wù)可以方便地將需求點(diǎn)的乘客運(yùn)送到火車站［1］。利用手機(jī)APP 和開放的GIS 工具，我們可以獲取研究區(qū)域內(nèi)部分乘客的出行信息、交通網(wǎng)絡(luò)。每位乘客都有一個或幾個可選的上車時間窗口，以及一個最小和最大的預(yù)期乘車時間。在設(shè)計路線的過程中，每輛車都從停車場開始，到火車站結(jié)束，在指定的時間段內(nèi)訪問需求點(diǎn)接駁乘客，以滿足諸如時間窗和預(yù)期乘車時間等現(xiàn)實約束條件。揭示接駁巴士路線設(shè)計效率與乘客滿意度和總里程之間的最佳關(guān)系，建立混合整數(shù)規(guī)劃模型以設(shè)計從選定的需求點(diǎn)到火車站的路線，并從多個優(yōu)選的時間窗口引導(dǎo)需求點(diǎn)的乘客在指定的時間段內(nèi)出行［12］。

我們的目標(biāo)是找到同時將旅客滿意度降低的損失和設(shè)計的支線路線的總里程成本降至最低的模型。為了確保提出的DRT 模型與實際情況完全吻合，本研究做以下假設(shè)：

1）允許需求點(diǎn)的乘客在一個或幾個首選時間窗口內(nèi)上車。調(diào)查火車站周圍每個需求點(diǎn)的乘客數(shù)量，不考慮他們之間的乘客流量。

2）需求點(diǎn)﹑停車場和鐵路站點(diǎn)之間的距離和行駛時間是使用百度GIS 獲取的。

3）每個需求點(diǎn)只能被一輛車輛覆蓋一次。

4）乘客的滿意度與乘車時間無關(guān)，乘客滿意度下降的損失可以估計。

2 模型建立

為了便于模型表示，表1 中匯總了下文中使用的所有定義和符號。

表1 數(shù)學(xué)模型中的參數(shù)和變量

將所提出的問題表示為以下混合整數(shù)規(guī)劃（MIP）：

在該公式中，目標(biāo)函數(shù)由式（1）表示，以使乘客滿意度降低的損失和設(shè)計支線的總里程成本最小化。約束（2）表示每輛車至少訪問一個需求點(diǎn)。約束（3）保證每個需求點(diǎn)僅由一輛車輛覆蓋。約束（4a）和（4b）保證每輛車最終都在停車場候選點(diǎn)啟動。約束（5a）和（5b）確保每輛車最終都在火車站結(jié)束。約束（6）將車輛服務(wù)的每個需求點(diǎn)（火車站和停車場除外）設(shè)置為具有完全相同的進(jìn)出弧。約束（7）用于車輛路徑中的子行程消除。約束（8a）和（8b）用于計算車輛k覆蓋的相鄰需求點(diǎn)i和j的到達(dá)時間。約束（9）保證了車輛k到達(dá)需求點(diǎn)i的時間滿足其多個行駛時間窗口的一個；約束（10a）和（10b）用于計算車輛k覆蓋的相鄰需求點(diǎn)i和j的負(fù)載能力。約束（11）保證每條路線上的乘客人數(shù)必須小于車輛的載客量。約束（12）和（13）確保每條路線的行駛距離和時間必須滿足其上限和下限。

3 用于解決DRT 改進(jìn)的Bat 算法

所提出的模型是VRP 的擴(kuò)展，其精確算法無法在可接受的時間內(nèi)解決大規(guī)模實例。蝙蝠算法（BA）是一種群體智能算法，用于模擬蝙蝠在獵物中的回聲定位行為［13］。為了避免BA 的不成熟收斂，將BA 與其他智能算法相結(jié)合是解決該問題的有效方法。群組搜索優(yōu)化器（GSO）是一種群體智能算法，可以模擬自然界中動物的行為以尋找生存資源。BA和GSO 之間的同源性決定了它們具有自然的融合特性［14］，目前很少見到混合算法。

在本文中，設(shè)計了一個混合BA 來解決DRT 問題，根據(jù)問題的特點(diǎn)重新定義了編碼方案、生成初始種群的啟發(fā)式算法、更新的位置和速度公式。

3.1 編碼方案

每只蝙蝠具有位置和速度兩個特征，在解搜索空間中抽象為一個潛在解。速度矢量是蝙蝠的運(yùn)動方向。根據(jù)問題的特點(diǎn)，構(gòu)造了DRT 的位置向量X=（x1，x2，…xI+K），包括兩部分：元素xi（1≤i≤│I│）為需求點(diǎn)編號，元素xi（│I│+1≤i≤│I│+│K│）為車輛編號。它們都是實數(shù)。根據(jù)該值xi，確定車輛和需求點(diǎn)在向量中的位置，從而得到任意車輛訪問需求點(diǎn)的順序?；谪澬脑?，我們也知道車輛從哪個停車場出發(fā)。例如2 輛車4 個需求點(diǎn)的可行解決方案為（0.1 1.3 0.4 0.7 0.2 0.5），兩條車輛路線為4-2-1 和3。

3.2 適應(yīng)性評估

根據(jù)解決方案的編碼規(guī)則，每個候選解決方案必須滿足約束（3）～（7），并且可能違反約束（10），（12）～（14）。為了解決這個問題，我們將那些約束作為懲罰項納入適應(yīng)性評估功能中。因此，在本文的研究中，修正的目標(biāo)函數(shù)如下：

本文的目標(biāo)函數(shù)直接用于評估個人的滿意度。

3.3 生成初始種群的啟發(fā)式算法

影響DRT 模型的許多復(fù)雜因素導(dǎo)致難以隨機(jī)生成對此問題的一種可行的解決方案。因此，設(shè)計了一種啟發(fā)式算法來生成初始種群，具體步驟如下：

步驟1：讀取DRT 模型的輸入數(shù)據(jù)，包括：I、M、Q、Dmax、Tmin.

步驟2：隨意選擇停車場m，然后讓i=m和N'=I。對于位于停車場的每輛車km，轉(zhuǎn)到第3 步以構(gòu)建路線。

步驟4：N'=N'-{j}。如果N'=?，輸出結(jié)果；否則，請轉(zhuǎn)到步驟3。

3.4 蝙蝠速度和位置的更新規(guī)則

在混合BA 中，每個蝙蝠i當(dāng)時會自我更新t如果所有蝙蝠都聚集在同一位置，則通過跟蹤全局最優(yōu)值，導(dǎo)致拒絕搜索其余解空間。從GSO 的想法中汲取了教訓(xùn)，即“少數(shù)群外流浪隨機(jī)行走”，一些蝙蝠隨機(jī)產(chǎn)生頭角和距離，并交換部分矢量位置以遍歷解空間以保持群的多樣性。在t時間對每個蝙蝠i的位置和速度進(jìn)行更新的公式如下：

其中，fi=fmin+（fmax-fmin）β（β∈［0，1］）是每個蝙蝠的回聲頻率i；X*表示當(dāng)前的全局最優(yōu)解；li是介于0 和最大搜索距離之間的隨機(jī)距離lmax；φt+1是介于0 和最大搜索角度之間的隨機(jī)頭角θmax；表示對應(yīng)于該角度的向量；ε，β和rand是間隔［0，1］中的均勻分布的隨機(jī)數(shù)。

3.5 蝙蝠的本地搜索規(guī)則

當(dāng)所有蝙蝠逐漸收斂到同一位置時，當(dāng)前最優(yōu)蝙蝠以一定的概率σ隨機(jī)行走產(chǎn)生一個新的位置，其中At代表所有蝙蝠的平均響度；ε∈［0，1］是一個隨機(jī)數(shù)。

3.6 混合蝙蝠算法的特定步驟

步驟1：初始化參數(shù)，包括m和Iter_max 等等。

步驟4：計算總體多樣性以獲得一定的隨機(jī)干擾操作概率，并干擾當(dāng)前對新位置的最優(yōu)解X*=X*+εAt。重新排列所有現(xiàn)有的蝙蝠以更新當(dāng)前的最佳解決方案。

步驟6：讓t=t+1。如果t＜Iter_max，轉(zhuǎn)到步驟3；否則，輸出結(jié)果。

4 實例仿真

為了證明所提出的模型在設(shè)計支線公交網(wǎng)絡(luò)到城市軌道交通中的適用性，本研究選擇了一個火車站（M），六個停車場（D1-D6）和總共十五個需求點(diǎn)（C1-C15））在中國南昌市進(jìn)行案例研究。圖1為這些車輛訪問點(diǎn)的分布圖（百度），其中黃色圓圈代表停車場，紅色小氣球代表客戶點(diǎn)，白色正方形代表火車站。表2 中顯示了乘客數(shù)量及其在租車點(diǎn)中的首選時間窗口和預(yù)期乘車時間。案例研究中使用的關(guān)鍵參數(shù)如下：

圖1 車輛需求點(diǎn)的空間分布

表2 需求點(diǎn)的基本信息

接駁公交線路最大載客量：Q=12；

車輛路線最大長度：Dmax+9 公里；

車輛路線的最短行駛時間：Tmin=3 分鐘；

運(yùn)營成本：c1=6.5 元/公里；

旅客滿意度降低的損失：c2=1 元/人；

混合算法的參數(shù)：N=100，MaxIter=200，α=0.9，γ=0.9，lmax=5、θmax=45 °。

如前所述，該模型可以解決兩個維度，即車輛接駁的乘客數(shù)量的分配以及車輛路線。表3 總結(jié)了分配結(jié)果，包括每個需求點(diǎn)的上車時間、乘車時間和滿意度。以到達(dá)需求點(diǎn)C5 的車輛為例，車輛在8:15 離開停車場D1，8:27 到達(dá)火車站M，在需求點(diǎn)C5 的乘客8:17 上車，乘坐時間約為10.2 分鐘。由于他們的預(yù)期乘坐時間為5 分鐘到10 分鐘，滿意度的計算公式為（20-10.2）/（20-5）=0.65。表3 還指導(dǎo)乘客從幾個首選時間窗口在指定時間段內(nèi)出行。

表3 車輛接駁乘客的分配結(jié)果

表4 列出了每輛車的路線計劃，其中為這三輛車選擇了兩個停車場D1 和D4。它們的總行駛里程分別為3.1 km，3.1 km 和3.0 km，它們的總行駛時間分別為12.2 分鐘，12.5 分鐘和12.1 分鐘。從表2，3和4 中可以看出，路線的總里程和時間分別為9.2 公里和36.8 分鐘，其總乘客滿意度為96.4。也可以獲取每個點(diǎn)的車輛載重量的變化。以路線1 為例，車輛將離開停車場D1，分別到達(dá)需求點(diǎn)C5，C6，C7，C8和C1，并在火車站M 處終止。一輛空車從D1 出發(fā)，該車輛首先在C5 停下來接駁兩名乘客，因此C5 和C6 之間載有2 名乘客；然后，這輛車前往C6，載有三名乘客，因此C6 和C7 之間載有5 名乘客；然后這輛車前往C7，C8 和C15 接駁四名乘客，一名乘客和兩名乘客，因此C7 和C8 之間分別為9，C8 和C15 之間分別為10，C15 和M 之間分別為12 和12。最后，這輛車拜訪了M，以運(yùn)送12 名乘客。在這種情況下，路線1 每個點(diǎn)的車輛裝載量可描述為：{D1（0），C5（2），C6（5），C7（9），C8（10），C15（13），M（0）}，對于路線2 和3，類似地為：{D4（0），C14（1），C11（5），C12（6），C10（8），M（0）} 和{D4（0），C13（3），C2（4），C4（6），C3（7），C1（10），C9（12），M（0）}。

表4 每輛車的路線和調(diào)度計劃

此外，與傳統(tǒng)的DRT 相比，我們的研究具有其獨(dú)特的功能。圖2 揭示了所提出的模型與具有單一時間窗口的DRT（DRTSTW）之間的差異。與配備DRTSTW 的DRT 相比，提出模型的行駛里程和滿意度損失將分別降低1.4 公里和7.1%。原因是車輛在多個時間窗口之一內(nèi)的任何時間到達(dá)需求點(diǎn)將減少無效的行駛里程和時間。因此，在實際應(yīng)用中允許乘客選擇多個旅行時間窗口非常重要。如上所示，通過實例證明所提出的模型是有效的。

圖2 提出模型與傳統(tǒng)DRT 的結(jié)果比較

5 結(jié)論

本文提出了一種具有多個時間窗口的DRT 優(yōu)化方法，以揭示總里程數(shù)與乘客滿意度之間的關(guān)系。與現(xiàn)有研究不同，提出的方法具有以下特點(diǎn)：1）提供一個交互過程，設(shè)計支線運(yùn)輸路線并指導(dǎo)乘客選擇最佳上車時間窗口；2）開發(fā)結(jié)合BA 和GSO 的混合算法，以有效地為所提出的模型提供可接受的解決方案。所提出模型的可行性和適用性以解決最優(yōu)性的實例進(jìn)行了說明。結(jié)果表明，與傳統(tǒng)的DRT 模型相比，該模型的總行駛里程減少了15.2%，總滿意度提高了7.1%。隨著車輛數(shù)量的增加，總滿意度和里程數(shù)都略有增加。