考慮均衡滿載率的多車型定制公交調(diào)度模型

管欣宇，祝佳祥

(1.深圳市城市交通規(guī)劃設計研究中心有限公司，廣東 深圳 518057；2.吉林大學 交通學院，吉林 長春 130022)

隨著城市道路網(wǎng)愈演愈烈的擁擠和交通資源的日益緊張，人們對公共交通系統(tǒng)提出了更高要求，希望用低碳綠色、快捷方便的公共交通方式滿足點到點式的出行需求，定制公交也因此應運而生。定制公交為滿足更多人的出行需求，無法像私人出行方式一樣即到即走，乘客會產(chǎn)生一定的等待時間。同時，定制公交的補貼方式與傳統(tǒng)公交也有差異，運營方面臨著更大的盈利壓力。因此，在制定定制公交運行計劃時應同時考慮乘客和運營方的利益進行靈活調(diào)度。

在多車型定制公交調(diào)度問題中，需要重點研究發(fā)車時刻和多車型配置，在發(fā)車時刻方面，Ceder[1]應用四種類型數(shù)據(jù)制定了四種方法確定發(fā)車頻率；陳維亞等[2]考慮客流需求波動及車輛運行時間的隨機變動情況，建立了公交線路服務頻率優(yōu)化模型；孫傳姣等[3]研究了不同調(diào)度形式組合和發(fā)車頻率的優(yōu)化。

在多車型配置方面，Ceder等[4-5]研究了基于均衡載客量和均勻發(fā)車間隔條件下的多車型時刻表設計問題；張思林等[6]以均勻發(fā)車間隔為準則，同步優(yōu)化公交線路的發(fā)車時刻表和車型組合；楊信豐等[7]研究了多車型快速公交的車型調(diào)度問題，并設計了Pareto解集求解算法；Sun等[8]根據(jù)公交需求波動研究了多車型條件下的時刻表優(yōu)化模型；Dell等[9]研究了公交線網(wǎng)下的多車型車輛配置和發(fā)車間隔確定的雙層規(guī)劃模型；邵文等[10]在靈活型接駁公交路徑規(guī)劃問題中，研究了路徑規(guī)劃與混合車型的協(xié)同調(diào)度模型。

目前，國內(nèi)外在多車型公交調(diào)度方面的研究主要以均勻發(fā)車間隔為發(fā)車機制，這種發(fā)車機制可有效避免乘客長時間等待，但無法保證運營方的單車收益。為兼顧乘客和運營方的利益，本文提出了均衡滿載率的發(fā)車機制和最大發(fā)車間隔約束，并研究了發(fā)車時刻的遞推公式。通過對乘客需求時間分布的統(tǒng)計和預測，在符合發(fā)車機制和發(fā)車間隔的約束下，以運營方收益最大和乘客等待時間最小為目標，構(gòu)建多目標規(guī)劃模型，并設計了遺傳算法求解。

1 研究問題描述

定制公交運營方和乘客之間存在著一種固有矛盾，運營方目的是增加盈利，由于希望加大發(fā)車間隔，以此來實現(xiàn)積累乘客并壓縮運營成本的目標；而乘客的期望是獲得良好的出行體驗，希望縮短發(fā)車間隔，以此減少自身的等待時間并保證車內(nèi)的舒適度。

為緩解運營方和乘客之間的矛盾，本文設計了一種新的發(fā)車方案：

1)通過“一人一座，人滿發(fā)車”(“滿”指的是滿足一定滿載率要求)的制度保證乘客在車內(nèi)的舒適度和運營方的單次發(fā)車收益。

2)根據(jù)不同車型的載客量和運營成本不同的特性，在需求的時間分布較離散時選取小車型以縮短乘客的等待時間，減少運營方的成本；在需求較集中時選取大車型使乘客不需要等待過長時間的同時又能增加運營方的收入。

因此，本文所研究的基于均衡滿載率的多車型定制公交優(yōu)化調(diào)度為：運營方可根據(jù)乘客的預約出行申請，以每次發(fā)車都盡可能接近滿載的方式動態(tài)調(diào)整發(fā)車時間和發(fā)車車型，從而保證運營方和乘客的雙方利益。

2 模型

2.1 模型假設

本文主要研究工作園區(qū)與居住地之間的通勤定制公交線路，OD模式為一對多。基于實際場景，提出以下假設：

1)假設乘客的預約需求分布已知，且乘客預約時刻即為開始等待發(fā)車時刻。

2)假設每次利用同種車型發(fā)車的成本相同。

2.2 變量及參數(shù)說明

模型中包含的主要參數(shù)及決策變量如表1所示。

表1 模型參數(shù)

2.3 多車型調(diào)度分析

2.3.1 乘客需求時間分布

根據(jù)實際預約情況的統(tǒng)計數(shù)據(jù)或IC卡與GPS數(shù)據(jù)的可視化分析[11]，可知道乘客出行需求的時間分布。為更好地利用數(shù)據(jù)、減少求解過程中反復統(tǒng)計數(shù)據(jù)的工作量，本文采用最小二乘法將乘客預約需求數(shù)據(jù)擬合成隨時間遞增的累計乘客數(shù)量曲線，公式為

y=ploy(x).

(1)

2.3.2 運營方收益分析

運營方的收益主要指票價收入減去運營成本。對于多車型定制公交而言，不同車型的票價是相同的，但不同車型的容量和運營成本不同，導致安排不同車型運送乘客對于運營方的收益不同。運營方收益可表示為

(2)

2.3.3 乘客等待時間分析

乘客的等待時間可分為兩個方面考慮。首先，從整體效益上應該考慮盡量縮短所有乘客的平均等待時間；其次，從個體效益上應該盡量減少需求零散時期個別乘客等待時間過長的情況。因此，乘客等待時間要結(jié)合總體平均等待時間和最大等待時間，公式為

(3)

2.3.4 發(fā)車機制設計

發(fā)車時刻由選擇車型、滿載率要求及最大發(fā)車間隔確定。車輛必須達到一定的滿載率要求才能夠發(fā)車，當車輛已經(jīng)滿載或達到最大發(fā)車間隔時則立即發(fā)車。

(Pi-O)≤Ni≤Piorhi=Hmax.

(4)

2.4 模型整合

(5)

(6)

s.t.

(7)

(8)

0≤x≤xmax;

(9)

(10)

tmax=max(h1,h2,…,hn).

(11)

式(5)、式(6)為目標函數(shù)，分別為運營方收益最大和乘客等待時間最??；式(7)為發(fā)車約束，當發(fā)車間隔小于最大發(fā)車間隔時，需要滿足一定滿載率要求才能發(fā)車，當達到最大發(fā)車間隔時立刻發(fā)車；式(8)為發(fā)車時刻遞推算式，通過上一輛車的發(fā)車時刻和當前車輛的乘客數(shù)，計算當前車輛的可行發(fā)車時間；式(9)為運營時間約束；式(10)為乘客總體平均等待時間算式，為便于運算可將乘客需求視為連續(xù)值；式(11)為最大等待時間計算式。

3 模型求解算法

多車型調(diào)度的核心目標是求解不同車型組合和該車型組合下每輛車的發(fā)車時刻，該問題屬于非線性混合整數(shù)規(guī)劃問題，求解比較復雜。所以本文通過設置合理的發(fā)車機制，建立了發(fā)車時刻的遞推公式，將混合整數(shù)規(guī)劃問題轉(zhuǎn)變?yōu)榍蠼廛囆秃蜐M載率的整數(shù)規(guī)劃問題。

由于遺傳算法提供了一種求解非線性、多目標等復雜優(yōu)化問題的通用框架，并且具有較強的全局搜索和并行搜索能力，是一種實用、高效、魯棒性強的優(yōu)化技術(shù)。因此，本文利用遺傳算法對模型進行求解。

3.1 染色體編碼及種群初始化

本文研究的問題是確定不同車型的發(fā)車時刻表，根據(jù)設計的發(fā)車機制，可以通過確定車型容量和剩余座位的方式計算出可行發(fā)車時刻，再判斷可行發(fā)車時刻是否超過最大發(fā)車間隔，若未超過，可行發(fā)車時刻即為最終發(fā)車時刻，若超過，則以最大發(fā)車間隔來確定發(fā)車時刻。

因此，染色體應包含的信息為選擇的車型和剩余座位數(shù)，這兩個變量都可以用整數(shù)進行編碼，染色體為長度為2N的整數(shù)基因序列。前N個基因為所選擇的車型，后N個基因為剩余座位。

以網(wǎng)絡教學為主體的課堂教學模式是指在課堂教學中絕大部分教學內(nèi)容及其過程以網(wǎng)絡教學方式進行的教學模式。網(wǎng)絡教學內(nèi)容包括網(wǎng)絡教學展示、網(wǎng)絡習題測評、網(wǎng)絡教學互動以及教師與學生家長的有關(guān)教育教學的網(wǎng)絡聯(lián)系，等等。在以網(wǎng)絡教學為主體的課堂教學過程中，網(wǎng)絡教學融入的比例很高，至少超過50%，非網(wǎng)絡教學只占課堂教學內(nèi)容及其過程的一小部分。在網(wǎng)絡教學為主體的課堂教學模式中，教師對教學過程的把控往往相對困難，因為這種模式的大部分時間已經(jīng)處于新型的網(wǎng)絡課堂教學模式之中，教師不可能再按照過去的經(jīng)驗式、當面人對人的管理方式管理教學過程。

N的大小可以持悲觀態(tài)度進行確定，認為乘客均由小型車運送且存在一次最大發(fā)車情況。

3.2 適應度函數(shù)

種群會向適應度函數(shù)值小的方向進化，因此，要將求最大值的目標函數(shù)改為求最小值。

3.2.1 歸一化處理

由于運營方收益和等待時間兩個函數(shù)值的量綱不同，所以要進行歸一化。同時，可根據(jù)兩個目標值對系統(tǒng)的重要程度賦予權(quán)重，處理后的適應度函數(shù)為

(12)

3.2.2 適應度函數(shù)計算方法

適應度函數(shù)的計算主要包括兩個目標函數(shù)值的計算及歸一化函數(shù)計算兩部分。

運營方收益可通過累計乘車人數(shù)和相應車型組合下的用車成本計算求得。

乘客等待時間的計算首先需要利用擬合后的乘客需求時間序列函數(shù)構(gòu)造可行發(fā)車時間遞推函數(shù)。然后利用可行發(fā)車時間遞推函數(shù)、車型組合序列和剩余空座序列計算可行發(fā)車時間，并判斷是否超過最大發(fā)車間隔，得到最終發(fā)車時間。最后根據(jù)最終發(fā)車時間計算乘客的總體平均等待時間和最大等待時間。

得到運營方收益和乘客等待時間后再根據(jù)適應度函數(shù)計算相應的函數(shù)值。

3.3 遺傳操作

選擇操作以輪盤賭選擇法為主，適應度比例選擇法為輔。交叉操作采用單點交叉方式，先確定交叉位置再交換相應的基因。變異操作采用高斯變異方式，依據(jù)變異概率判斷是否變異，然后隨機確定變異的基因位進行變異。

4 案例分析

某工作園區(qū)為了讓晚上加班的員工能夠便宜、快速地回家，在園區(qū)內(nèi)設置了晚間定制公交，運營時間為20：00—22：00。對統(tǒng)計的乘客需求進行函數(shù)擬合，可得乘客需求時間分布函數(shù)為

y=-0.1116x2+4.507x+1.478.

(13)

現(xiàn)有大型車和小型車兩種定制公交，屬性如表2所示。

表2 兩種定制公交屬性信息

模型所需的其他參數(shù)如表3所示。

表3 模型參數(shù)取值

遺傳算法的基本參數(shù)經(jīng)大量實驗最終取得如下效果較好值，其中染色體長度為2*15，種群規(guī)模為50，最大進化代數(shù)為200，交叉概率為0.6，變異概率為0.1。

運用所建立的多目標規(guī)劃模型和設計的遺傳算法，運用MATLAB軟件編程對該案例進行求解，求解信息經(jīng)整理后如表4所示。

表4 考慮均衡滿載率的發(fā)車信息

考慮均衡滿載率發(fā)車運營計劃的運營收益為810元，乘客的總平均等待時間為5.553 min，最大等待時間為15 min。

為驗證考慮均衡滿載率效果，比較使用11 min固定發(fā)車間隔，且采用8輛大車、3輛小車的情況(人數(shù)少的3班車采用小車)，詳細信息如表5所示。

表5 固定時間間隔的發(fā)車信息

固定發(fā)車間隔的發(fā)車計劃使得資源沒有得到很好利用。對運營方而言，發(fā)車時刻88的大車人數(shù)為29，沒有達到單車滿載率要求，甚至已經(jīng)形成單車虧損了，同樣，發(fā)車間隔120的小車也形成了單車虧損。于乘客而言，總平均等待時間為5.574，相對有所增加，而且在人數(shù)超過車輛容量時乘客的乘車體驗也會下降。

綜上分析，考慮均衡滿載率的調(diào)度方法能夠更充分地利用多車型車輛資源，可減少乘客的等待時間，為乘客提供更舒適的乘車體驗，且滿足運營方單車盈利的要求。

5 結(jié) 論

本文探討了多車型定制公交優(yōu)化調(diào)度問題，重點研究考慮均衡滿載率的發(fā)車機制設計對多車型定制公交調(diào)度的影響。以運營方收益最大和乘客等待時間最小為優(yōu)化目標，建立模型并設計算法求解最優(yōu)的車型組合和發(fā)車時刻，為研究定制公交運行計劃開拓思路。根據(jù)不同客流時間分布，科學選取合理車型并制定相應的發(fā)車時間，可高效利用運力、減少乘客等待時間及滿足運營方收益要求。

本文考慮了單條線路的運行計劃制定，通過算例驗證了所提模型和算法的有效性，未來定制公交將會進一步響應實時變化需求，考慮實變需求下的運營調(diào)度問題。