宋現(xiàn)敏，張明業(yè)，姜景玲

(1.吉林大學(xué)交通學(xué)院，長(zhǎng)春130022；2.中國(guó)交通運(yùn)輸科學(xué)研究院，北京100029)

0 引 言

城市化建設(shè)速度不斷加快，城市道路資源日益緊張，公共交通具有緩解交通擁堵、提高居民出行效率的作用，故大力發(fā)展公共交通成為各國(guó)的共識(shí).關(guān)于公交線路調(diào)度的研究主要集中在公交發(fā)車頻率和時(shí)刻表優(yōu)化兩方面.

公交發(fā)車頻率優(yōu)化方面：Ceder[1]基于乘客調(diào)查數(shù)據(jù)給出4種確定公交車發(fā)車頻率的方法，兩種基于站點(diǎn)數(shù)據(jù)，兩種基于區(qū)間出行數(shù)據(jù)；Ferguson等[2]考慮低收入人群、弱勢(shì)群體的出行特征，將公平性納入公交頻率設(shè)置問(wèn)題；姚寶珍[3]將綜合集成賦權(quán)法引入公交發(fā)車頻率優(yōu)化中，構(gòu)建以企業(yè)費(fèi)用和乘客費(fèi)用最小為目標(biāo)的發(fā)車頻率優(yōu)化模型；曹蓮英[4]采用多目標(biāo)演化算法求解公交發(fā)車頻率模型，最終求得發(fā)車間隔的全局最優(yōu)解.

公交時(shí)刻表優(yōu)化方面：Palma 等[5]基于公交車數(shù)量，乘客時(shí)間延誤費(fèi)用和不同期望出行次數(shù)，構(gòu)建公交發(fā)車時(shí)刻優(yōu)化模型；竇雪萍[6]以公交網(wǎng)絡(luò)內(nèi)總換乘負(fù)效用最小為目標(biāo)，構(gòu)建公交時(shí)刻表魯棒優(yōu)化模型.近年有學(xué)者對(duì)重疊區(qū)間進(jìn)行研究：洪豆[7]引出公交線路重復(fù)路段的概念，建立以乘客出行成本和企業(yè)運(yùn)營(yíng)成本最小的雙層規(guī)劃模型；湯茹茹[8]考慮多車型的影響，分別建立考慮區(qū)間重疊影響的大型車、小型車、多車型公交調(diào)度模型.

綜上，現(xiàn)有公交調(diào)度研究并沒(méi)有考慮公交線路由不同運(yùn)營(yíng)商運(yùn)營(yíng)的情況，同時(shí)這些線路有一定的區(qū)間重疊.因此，本文構(gòu)建一個(gè)雙層規(guī)劃模型解決多運(yùn)營(yíng)商重疊區(qū)間的公交線路調(diào)度問(wèn)題，由上層模型確定線路分配方案，下層模型確定各公交線路的發(fā)車頻率和發(fā)車時(shí)間，應(yīng)用NSGA-П(Nondominated Sorting Genetic Algorithm P)算法求解模型，并以長(zhǎng)春市南關(guān)區(qū)北側(cè)區(qū)域的公交線網(wǎng)為案例進(jìn)行分析，實(shí)驗(yàn)結(jié)果驗(yàn)證了模型的有效性.

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

1.1 問(wèn)題描述

本文建立一個(gè)雙層規(guī)劃模型對(duì)問(wèn)題進(jìn)行描述，上層模型指政府機(jī)構(gòu)負(fù)責(zé)對(duì)公交線路進(jìn)行分配，目標(biāo)函數(shù)使公交乘客的總出行時(shí)間(包括行程時(shí)間和等車時(shí)間)最??；下層模型為各運(yùn)營(yíng)商各自利潤(rùn)最大，是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，變量是各運(yùn)營(yíng)商運(yùn)營(yíng)公交線路的配車數(shù)和發(fā)車間隔，多運(yùn)營(yíng)商公交調(diào)度優(yōu)化過(guò)程如圖1所示.

為簡(jiǎn)化問(wèn)題，做出以下假設(shè)：

(1)每條線路由一個(gè)運(yùn)營(yíng)商運(yùn)營(yíng)，每個(gè)運(yùn)營(yíng)商運(yùn)營(yíng)不止一條線路；

(2)每條線路行駛路線不改變，仍然經(jīng)過(guò)相同的站點(diǎn)；

(3)站點(diǎn)間客流量保持穩(wěn)定；

(4)乘客均勻到達(dá)公交站點(diǎn).

1.2 參數(shù)定義

設(shè)公交網(wǎng)絡(luò)中有l(wèi)個(gè)公交線路，g個(gè)公交運(yùn)營(yíng)商，參數(shù)定義如表1所示.

1.3 上層模型

政府機(jī)構(gòu)通過(guò)優(yōu)化線路分配方案，使乘客出行時(shí)間達(dá)到最小，運(yùn)營(yíng)商在政府機(jī)構(gòu)確定的線路分配方案下，確定運(yùn)營(yíng)線路的發(fā)車間隔，追求自身的最大利潤(rùn)，線路分配方案為

圖1 多運(yùn)營(yíng)商公交調(diào)度優(yōu)化過(guò)程Fig.1 Optimization process of multi operator bus dispatching

乘客總出行時(shí)間包括乘客在站點(diǎn)的候車時(shí)間和站點(diǎn)間的行程時(shí)間，通往(i,j)站點(diǎn)的乘客在站點(diǎn)i的平均等車時(shí)間為

式中：由3部分組成，分別是車輛k駛離站點(diǎn)1的時(shí)間，OD站點(diǎn)(1,i)的路段行程時(shí)間和公交車在站點(diǎn)i之前(包括站點(diǎn)i)的公交站點(diǎn)停靠時(shí)間，即

線路l內(nèi)第n輛車的發(fā)車間隔為

公交車在站點(diǎn)的?？繒r(shí)間由乘客的上車時(shí)間和下車時(shí)間決定，取兩者中最大值，即

第k輛車在站點(diǎn)i下車的乘客數(shù)等于所有乘坐k車的終點(diǎn)站為i的乘客數(shù)，站點(diǎn)i的上車乘客數(shù)等于乘坐k車，且終點(diǎn)站為i+1 到m的所有乘客數(shù)，計(jì)算公式分別為

表1 參數(shù)定義表Table 1 Parameter definition table

乘客在(i,j)站點(diǎn)間的行程時(shí)間由(i,j)的路段行程時(shí)間和所有經(jīng)過(guò)站點(diǎn)的?？繒r(shí)間組成，即

公交系統(tǒng)內(nèi)，乘客總出行時(shí)間由乘客在站點(diǎn)間的行程時(shí)間和等車時(shí)間構(gòu)成，故本文構(gòu)建模型為

站點(diǎn)(i,j)內(nèi)，選擇由運(yùn)營(yíng)商g運(yùn)營(yíng)線路l的乘客數(shù)為

上層模型的約束為

式(11)和式(12)表示每條線路只能由一個(gè)運(yùn)營(yíng)商運(yùn)營(yíng)，式(13)表示發(fā)車間隔約束，式(14)表示站點(diǎn)上車乘客數(shù)需要滿足車輛容量，式(15)表示線路配車數(shù)滿足線路整體客流量需求.

1.4 下層模型

下層模型為

式(16)表示各運(yùn)營(yíng)商追求自身利潤(rùn)最大化，運(yùn)營(yíng)商g在應(yīng)用線路方案pg時(shí)的利潤(rùn)，為該運(yùn)營(yíng)商運(yùn)營(yíng)所有公交線路的利潤(rùn)之和，即

運(yùn)營(yíng)商g運(yùn)營(yíng)線路l的利潤(rùn)等于收益減去成本，即

2 模型求解

上層模型中，將問(wèn)題描述為一個(gè)0-1整數(shù)線性規(guī)劃問(wèn)題，隱式枚舉法是求解這一類問(wèn)題較好的算法，利用變量只能取0或l值的特性，進(jìn)行分支定界，達(dá)到最優(yōu)解.

下層模型中，由于各運(yùn)營(yíng)商都在追求自身利潤(rùn)最大，一個(gè)目標(biāo)性能的改善往往是以損失其他目標(biāo)性能為代價(jià)，故其解通常是一個(gè)非劣解的集合，即Pareto 解集.帕累托最優(yōu)解指的是從一種分配狀態(tài)到另一種分配狀態(tài)時(shí)，在沒(méi)有使任何人情況變壞的前提下，至少有一個(gè)人變得更好.換言之，下層模型中，各個(gè)目標(biāo)之間會(huì)一直競(jìng)爭(zhēng)直至達(dá)到一種均衡狀態(tài)為止，而在其他運(yùn)營(yíng)商方案不變的情況下，帕累托解即是運(yùn)營(yíng)商能達(dá)到的最優(yōu)解.

NSGA-II 算法(Elitist Non-Dominated Sorting Genetic Algorithm)是一種面對(duì)多目標(biāo)優(yōu)化問(wèn)題的算法，具有運(yùn)行速度快、解集收斂性好等優(yōu)點(diǎn)，通常用于求解帕累托前沿解，本文求解步驟如下.

Step 1初始化，設(shè)定一個(gè)初始的線路分配方案.

Step 2在Step 1 確定的線路分配方案下，通過(guò)下層模型求解出相應(yīng)的帕累托解集.

Step 3將Step 2得到的帕累托解集中的解分別輸入到上層模型中，選擇使上層模型的乘客總出行時(shí)間最小的線路方案，該方案即為對(duì)應(yīng)線路分配方案的最優(yōu)線路方案.

Step 4更新線路方案，重復(fù)Step 2和Step 3.

Step 5選擇使乘客總出行時(shí)間最小的線路分配方案和線路方案，并輸出實(shí)驗(yàn)結(jié)果.

3 案例分析

3.1 實(shí)驗(yàn)背景

選取長(zhǎng)春市南關(guān)區(qū)北部區(qū)域公交網(wǎng)絡(luò)內(nèi)4 條公交線路進(jìn)行分析，這些線路彼此有部分區(qū)間重疊，分別由兩家公交公司運(yùn)營(yíng)，即南通公司和巴士公司，各公交線路信息如表2所示.

表2 公交線路信息表Table 2 Bus line information

客流數(shù)據(jù)采用人工調(diào)查方法，調(diào)查時(shí)間為晚高峰(16:30-17:30)，調(diào)查數(shù)據(jù)為各站點(diǎn)上、下車的乘客數(shù).根據(jù)各公交線路在各站點(diǎn)的上車客流量及乘客站點(diǎn)下車概率表，推算各條線路的OD客流數(shù)據(jù).參數(shù)設(shè)置如下：最小發(fā)車間隔2 min，最大發(fā)車間隔10 min，乘客上車平均速度2.5 s/人，乘客下車平均速度2 s/人，票價(jià)1 元，公交車運(yùn)營(yíng)成本2.07元/km，公交車平均運(yùn)行速度15 km/h.

3.2 實(shí)驗(yàn)結(jié)果分析

對(duì)比分析優(yōu)化前、后方案，優(yōu)化前方案指現(xiàn)狀調(diào)度方案，優(yōu)化后為采用本文模型優(yōu)化后的方案，結(jié)果如表3所示.

由表3 可知，優(yōu)化后的乘客總出行時(shí)間為98 997 min，降低了5.93%.乘客的OD站點(diǎn)固定，同時(shí)假設(shè)公交車輛平均行駛速度固定，故乘客在站點(diǎn)之間的行駛時(shí)間固定，路段行程時(shí)間發(fā)生變化的主要原因是公交車輛在公交站點(diǎn)的?？繒r(shí)間，共減少1 274 min；由于優(yōu)化了線路分配方案及線路內(nèi)各車輛的發(fā)車時(shí)間，乘客總等車時(shí)間下降27.56%，證明了模型的有效性.各公交公司在優(yōu)化后的線路分配方案及相應(yīng)利潤(rùn)如表4所示.

表3 兩種調(diào)度方案對(duì)比Table 3 Comparison of two scheduling schemes

表4 運(yùn)營(yíng)商優(yōu)化前后利潤(rùn)變化Table 4 Profit of operator before and after optimization

表4中，優(yōu)化前后的利潤(rùn)是通過(guò)下層模型計(jì)算得到的，即線路的總收益減去線路總成本，收益為各條線路的票價(jià)收入，成本為公交車輛的運(yùn)營(yíng)成本.在優(yōu)化后的調(diào)度方案中，南通公司分配到6 路和363 路的車輛數(shù)分別為18 veh 和6 veh，巴士公司分配到160 路和312 路的車輛數(shù)分別為21 veh和6 veh，優(yōu)化后的公交發(fā)車時(shí)刻表如表5所示.

表5 優(yōu)化后公交發(fā)車時(shí)刻表Table 5 Bus dispatching timetable after optimization

對(duì)于有重疊區(qū)間的多運(yùn)營(yíng)商公交線路調(diào)度問(wèn)題，客流量的競(jìng)爭(zhēng)主要體現(xiàn)在重疊區(qū)間，因此，對(duì)優(yōu)化前后各條線路在重疊區(qū)間的客流量進(jìn)行細(xì)致分析.

圖2 橫坐標(biāo)為各線路重疊區(qū)間編號(hào)，共有46個(gè)重疊區(qū)間，縱坐標(biāo)為各條線路的累積客流量.重疊區(qū)間的前部分，只有6 路和312 路競(jìng)爭(zhēng)，兩者車輛數(shù)在優(yōu)化后都略有下降，故6路和312路在重疊區(qū)間23 之前變化幅度不大；在這之后，160 路參與競(jìng)爭(zhēng)，同時(shí)160 路的車輛數(shù)增加較為明顯，故160路在重疊區(qū)間的競(jìng)爭(zhēng)力加大，優(yōu)化后的累積客流量加大，而6 路的累積客流量有所降低，體現(xiàn)出調(diào)度方案變化對(duì)各條線路在重疊區(qū)間的影響.

圖2 各條線路重疊區(qū)間累積乘客數(shù)Fig.2 Accumulated number of passengers of each line in overlapping section

乘客對(duì)公交服務(wù)質(zhì)量的最直觀體驗(yàn)是等車時(shí)間，因此，本文對(duì)優(yōu)化前后乘客在重疊區(qū)間的等車時(shí)間進(jìn)行對(duì)比分析，如圖3所示.

圖3 優(yōu)化前后重疊區(qū)間站點(diǎn)等車時(shí)間對(duì)比Fig.3 Comparison of waiting time at overlapping stations before and after optimization

由圖3可得，站點(diǎn)1～6這6個(gè)站點(diǎn)，乘客可選擇的線路為6路和312路，這兩條線路在優(yōu)化后配車數(shù)減少，故乘客等車時(shí)間略有增加；站點(diǎn)7～11 這5個(gè)站點(diǎn)，乘客可供選擇線路為6 路，312 路和160路，因160 路的配車數(shù)有較大增長(zhǎng)，乘客的等車時(shí)間大幅降低.

4 結(jié) 論

本文考慮各公交運(yùn)營(yíng)商在重疊區(qū)間的競(jìng)爭(zhēng)因素，構(gòu)建多運(yùn)營(yíng)商公交調(diào)度的雙層規(guī)劃模型，并選取長(zhǎng)春市南關(guān)區(qū)北部區(qū)域的公交網(wǎng)絡(luò)進(jìn)行案例分析.研究結(jié)論如下：重疊區(qū)間內(nèi)各條線路的乘客數(shù)和乘客等車時(shí)間與線路配車數(shù)和發(fā)車間隔有關(guān)，運(yùn)營(yíng)商可通過(guò)優(yōu)化發(fā)車間隔以提高在重疊區(qū)間的競(jìng)爭(zhēng)力.此外，應(yīng)用本文模型對(duì)公交線網(wǎng)進(jìn)行優(yōu)化，公交乘客總出行時(shí)間降低5.93%，公交線網(wǎng)性能得到較大改善，驗(yàn)證了模型有效性.