多區(qū)域通勤定制公交線路規(guī)劃模型及求解算法

陳 汐，王印海，劉劍鋒，馬曉磊*,1b

(1.北京航空航天大學(xué)a.交通科學(xué)與工程學(xué)院，b.大數(shù)據(jù)科學(xué)與腦機(jī)智能高精尖創(chuàng)新中心，北京100191；2.美國(guó)華盛頓大學(xué)土木和環(huán)境工程系，西雅圖98195，美國(guó)；3.北京城建設(shè)計(jì)發(fā)展集團(tuán)股份有限公司，北京100071)

0 引 言

近年來(lái)，“公交優(yōu)先”已發(fā)展成為應(yīng)對(duì)城市交通問(wèn)題的主要手段之一，且鼓勵(lì)構(gòu)建多元化的公共交通服務(wù)模式已經(jīng)成為城市交通的主流發(fā)展方向.在此背景下，定制公交開(kāi)始在我國(guó)投入運(yùn)營(yíng).定制公交是指通過(guò)集中整合個(gè)體的交通出行需求，為出行起終點(diǎn)、出行時(shí)間、服務(wù)需求相同或相似的人群提供專(zhuān)門(mén)定制的公共交通服務(wù)方式[1-2].

定制公交作為一種需求響應(yīng)式公交服務(wù)模式，國(guó)內(nèi)外學(xué)者已經(jīng)對(duì)其進(jìn)行了相關(guān)的研究.Liu和Ceder[1]對(duì)中國(guó)定制公交的發(fā)展現(xiàn)狀、設(shè)計(jì)流程及運(yùn)營(yíng)模式做出了系統(tǒng)的梳理.線路設(shè)計(jì)作為定制公交服務(wù)設(shè)計(jì)的重要一環(huán)，受到了許多學(xué)者的關(guān)注.目前研究多以設(shè)計(jì)優(yōu)化模型為主，優(yōu)化目標(biāo)主要關(guān)注乘客的出行和運(yùn)營(yíng)成本這兩方面.胡郁蔥等[2]針對(duì)多點(diǎn)對(duì)多點(diǎn)運(yùn)營(yíng)模式，以運(yùn)營(yíng)商成本最小為優(yōu)化目標(biāo)構(gòu)建模型并采用遺傳算法求解.Tong等[3]在基于時(shí)空可達(dá)的定制公交服務(wù)模式設(shè)計(jì)問(wèn)題的基礎(chǔ)上，建立了以最小化不可達(dá)乘客數(shù)量為目標(biāo)的規(guī)劃模型，并采用拉格朗日松弛算法求解.Ma 等[4]以乘客出行成本、運(yùn)營(yíng)收入及成本為優(yōu)化目標(biāo)建立模型，并設(shè)計(jì)了遺傳算法對(duì)定制公交線路方案進(jìn)行了實(shí)證分析.Lyu 等[5]基于乘客的出行選擇行為構(gòu)建了以最大化運(yùn)營(yíng)商收益為目標(biāo)的優(yōu)化模型，并設(shè)計(jì)了啟發(fā)式算法求解.申嬋和崔洪軍[6]基于可靠性最短路的概念提出了一種定制公交線路優(yōu)化方法及模型，并設(shè)計(jì)了禁忌搜索方法進(jìn)行求解.

綜上所述，盡管目前已有研究取得了很多成果，但有以下幾個(gè)方面依舊值得進(jìn)一步討論.首先，乘客出行成本優(yōu)化方面，在模型構(gòu)建時(shí)應(yīng)考慮其他出行方式.第二，多數(shù)研究中模型為單目標(biāo)優(yōu)化模型.實(shí)際上，采取多目標(biāo)優(yōu)化方法求解Pareto解可以捕獲沖突目標(biāo)之間的變化關(guān)系，為運(yùn)營(yíng)者提供更多的信息.第三，如何針對(duì)通勤這種出行模式的特點(diǎn)構(gòu)建相應(yīng)的線路設(shè)計(jì)模型需進(jìn)一步討論.

基于以上考慮，本文提出了一個(gè)針對(duì)通勤模式的定制公交多目標(biāo)優(yōu)化模型，該模型同時(shí)考慮了乘客出行成本和定制公交的運(yùn)營(yíng)成本.特別針對(duì)乘客出行成本，目標(biāo)函數(shù)考慮了乘客選擇定制公交的實(shí)際出行時(shí)間與“最短路時(shí)間”之差，這里“最短路”是指出租車(chē)服務(wù)模式或單點(diǎn)對(duì)單點(diǎn)的定制公交運(yùn)營(yíng)模式，即兩個(gè)站點(diǎn)間直達(dá)所需時(shí)間；并設(shè)計(jì)了一個(gè)兩階段啟發(fā)式算法求解該模型的Pareto解，最后通過(guò)案例驗(yàn)證了模型和方法的有效性.

1 通勤定制公交線路設(shè)計(jì)模型

1.1 多區(qū)域通勤定制公交的運(yùn)營(yíng)模式

本文只討論早高峰通勤定制公交的線路設(shè)計(jì)問(wèn)題.通勤者出發(fā)地通常為某個(gè)小區(qū)(居住區(qū))，而目的地為某個(gè)工作地點(diǎn)(工作區(qū)).因此，通勤定制公交可以視為從居住地區(qū)域(多區(qū)域)與工作地區(qū)域(單區(qū)域)之間的線路設(shè)計(jì)問(wèn)題.

如圖1所示，假設(shè)每個(gè)居住地區(qū)域有若干出發(fā)地站點(diǎn)，每個(gè)出發(fā)地站點(diǎn)為上車(chē)站點(diǎn)(不允許下車(chē)).工作地區(qū)域有若干目的地站點(diǎn)，每個(gè)目的地為下車(chē)站點(diǎn)(不允許上車(chē)).該問(wèn)題可以描述為：在需求已知的情況下，每一條定制公交線路行車(chē)路徑中，有若干個(gè)上車(chē)站點(diǎn)與下車(chē)站點(diǎn).其中，每條線路中各上車(chē)站點(diǎn)的目的地必須包含在該線路的下車(chē)站點(diǎn)里.且每條線路必須先經(jīng)過(guò)居住區(qū)域，再將乘客運(yùn)送到工作區(qū)域.圖1描述的情況中包含2條線路(用2輛車(chē)運(yùn)營(yíng)).

在本文中，每個(gè)出行需求p包含4個(gè)屬性，即出發(fā)地o(p)，目的地d(p)，期望出發(fā)時(shí)間ot(p)，和期望到達(dá)時(shí)間dt(p).其中乘客上車(chē)時(shí)間窗滿足ω為15～30 min 的緩沖時(shí)間參數(shù)，且ot(p)+ω ＜dt(p).此外，乘客到達(dá)目的地的時(shí)間應(yīng)早于dt(p)以避免遲到；因此，本文研究的問(wèn)題可以視為PDPTW(Pickup and Delivery Problem with Time-Windows)問(wèn)題的特殊情形[3].

圖1 多區(qū)域通勤定制公交運(yùn)營(yíng)模式Fig.1 Example of multi-region operation mode for commuting CB

1.2 模型描述

令G=(N,A)為交通網(wǎng)絡(luò)，N為定制公交備選站點(diǎn)(場(chǎng)站，居住地和工作地)；A為交通網(wǎng)絡(luò)中的弧，滿足A={(i,j):i∈N,j∈N,i≠j}.每個(gè)弧(i,j)之間的距離定義為d(i,j)＞0，其中d(i,j)=d(j,i)；車(chē)輛在弧(i,j)之間的通行時(shí)間定義為T(mén)(i,j)＞0.決策變量定義如表1所示.

表1 模型中決策變量含義Table1 Decision variables in the model

模型的假設(shè)如下：

(1)出行需求已知，且每個(gè)需求p包含乘客的人數(shù)為n(p).

(2)若出行需求符合某線路的站點(diǎn)的服務(wù)范圍，則該需求所對(duì)應(yīng)的乘客會(huì)選擇該線路出行.

(3)兩個(gè)站點(diǎn)間的通行時(shí)間T(i,j)=d(i,j)v，其中，v為車(chē)輛的平均行駛速度(km/h).

(4)場(chǎng)站為虛擬站點(diǎn).為簡(jiǎn)化模型，車(chē)輛k的出發(fā)點(diǎn)b(k)(場(chǎng)站)與第一個(gè)上車(chē)站點(diǎn)之間，以及最后一個(gè)下車(chē)站點(diǎn)與車(chē)輛k的到達(dá)點(diǎn)e(k)(場(chǎng)站)之間的線路成本為0.

1.3 模型建立

在實(shí)際運(yùn)營(yíng)中，根據(jù)出行需求，一個(gè)上車(chē)站點(diǎn)可能會(huì)對(duì)應(yīng)不同的下車(chē)站點(diǎn)；相似地，一個(gè)下車(chē)站點(diǎn)也可能會(huì)對(duì)應(yīng)不同的上車(chē)站點(diǎn).因此，需要將上下車(chē)站點(diǎn)拆分以使得起終點(diǎn)一一對(duì)應(yīng)[7].經(jīng)過(guò)處理，需求所對(duì)應(yīng)的上車(chē)站點(diǎn)集合為H={h1,h2,…,hn}，上車(chē)站點(diǎn)所對(duì)應(yīng)的下車(chē)站點(diǎn)集合為W={w1,w2,…,wn}.因此，乘客的出行需求點(diǎn)可用集合R=H?W表示.

本文的優(yōu)化目標(biāo)是兼顧乘客與運(yùn)營(yíng)商兩方面效益，即最小化乘客出行時(shí)間成本和定制公交運(yùn)營(yíng)成本兩個(gè)目標(biāo).

(1)乘客的出行成本.

第一個(gè)優(yōu)化目標(biāo)為最小化乘客的出行成本，包含兩部分：第一部分為乘客乘坐定制公交的實(shí)際出行時(shí)間與“最短路時(shí)間”之差，這里“最短路”是指出租車(chē)服務(wù)模式，即兩個(gè)站點(diǎn)間直達(dá)所需時(shí)間.第二部分為乘客的等待時(shí)間，這里等待的時(shí)間是乘客期望到達(dá)時(shí)間dt(p)與實(shí)際到達(dá)目的地時(shí)間之差.以上兩個(gè)指標(biāo)目的是提升出行效率，減少出行時(shí)間的浪費(fèi).

首先，令hkt(i)為車(chē)輛k在上車(chē)站點(diǎn)i接載乘客后的出發(fā)時(shí)間為

式中：si為站點(diǎn)上下車(chē)的服務(wù)時(shí)間.因此，對(duì)于每個(gè)需求p，從居住地i[o(p)]到工作地j[d(p)]的出行時(shí)間成本指標(biāo)為

因此，第一個(gè)目標(biāo)函數(shù)F1為最小化全體乘客的平均出行時(shí)間成本為

(2)運(yùn)營(yíng)成本.

第二個(gè)優(yōu)化目標(biāo)F2為最小化運(yùn)營(yíng)車(chē)輛數(shù)，即使用盡可能少的車(chē)輛來(lái)服務(wù)所有乘客需求，達(dá)到降低運(yùn)營(yíng)成本的目的.

本文假定定制公交的服務(wù)車(chē)型相同，即每輛車(chē)的載客人數(shù)相同.

(3)約束條件.

首先，每個(gè)乘客只能由一輛車(chē)服務(wù)，即

第二，定制公交服務(wù)過(guò)程中不允許換乘行為，即

式(6)和式(7)表明乘客p被車(chē)輛k在上車(chē)站點(diǎn)i接載后由同一輛車(chē)k送到目的地n+i.

第三，乘客需在dt(p)之前到達(dá)目的地.

第四，車(chē)輛k應(yīng)先訪問(wèn)乘客p的居住地再訪問(wèn)工作地.

第五，線路中相鄰站點(diǎn)間的通行時(shí)間關(guān)系應(yīng)滿足

式中：G為一個(gè)充分大的數(shù).

第六，定制公交需保證乘客“一人一座”[1].因此，車(chē)輛到達(dá)站點(diǎn)接載乘客后車(chē)內(nèi)乘客數(shù)量應(yīng)滿足：

式中：Lk(i)為車(chē)輛k經(jīng)過(guò)站點(diǎn)i后的累計(jì)客流，rp(j)為后繼站點(diǎn)j的乘客數(shù)，C(k)為車(chē)型的載客容量.

第七，決策變量取值范圍為

2 求解算法

由于多目標(biāo)優(yōu)化模型各目標(biāo)之間會(huì)存在沖突，因此求解的目標(biāo)是找到Pareto 解集[8].然而，由于PDPTW類(lèi)問(wèn)題屬于典型的NP-hard 問(wèn)題，且在處理實(shí)際問(wèn)題中規(guī)模較大，因此采用啟發(fā)式算法求解問(wèn)題是主要的手段之一[3].本文設(shè)計(jì)了一種兩階段啟發(fā)式算法求解模型，第一階段生成初始Pareto 解集；第二階段采用鄰域搜索算子更新Pareto解集.

2.1 生成初始解

首先，本文采用sweep-based算法生成初始線路集[7,9].該算法的主要思路是將出行需求按“多點(diǎn)對(duì)單點(diǎn)”的運(yùn)營(yíng)模式進(jìn)行線路設(shè)計(jì)，具體步驟如下.

Step 1對(duì)于同一個(gè)時(shí)間段dt(p)到達(dá)同一個(gè)目的地d(p)的乘客，令其出發(fā)地集合為lo={l1,l2,…,li,…,ln}.在車(chē)輛k從起點(diǎn)b(k)出發(fā)之后，從l0中隨機(jī)選擇一個(gè)乘客的出行起點(diǎn)li.這樣，由車(chē)輛k服務(wù)的線路可以初始化定義為Vk：b(k)-S1-d(p)-e(k)，其中，S1=li.

Step 2從l0中選擇站點(diǎn)lj繼續(xù)插入到Vk中，選擇站點(diǎn)的原則按照與前一個(gè)站點(diǎn)的距離大小來(lái)進(jìn)行，即優(yōu)先選擇離前繼站點(diǎn)距離最近的站點(diǎn)，并且滿足：

式(17)和式(18)表示選擇插入的站點(diǎn)li+1要盡可能離目的地越來(lái)越近.

Step 3判斷新插入的站點(diǎn)lj是否滿足約束條件式(8)～式(13).如果滿足，將站點(diǎn)放入車(chē)輛k所服務(wù)的線路Vk之中，并更新線路.更新之后將lj從l0中刪除.否則，返回Step 2 直到選擇一個(gè)可行的站點(diǎn)插入.

Step 4重復(fù)Step 2和Step 3直到?jīng)]有站點(diǎn)可以添加到Vk之中，這樣由車(chē)輛k運(yùn)送的線路Vk被確定.

Step 5重復(fù)Step 1～Step 4 直至到達(dá)d(p)的每個(gè)需求都被覆蓋，對(duì)于每個(gè)目的地站點(diǎn)都按該方法進(jìn)行線路的初始化，這樣就得到一個(gè)初始的線路集合TR，線路集中每條線路都是多點(diǎn)對(duì)單點(diǎn)的運(yùn)營(yíng)模式，如圖2所示.

圖2 多點(diǎn)對(duì)單點(diǎn)模式線路示例Fig.2 Example of route for multi-origin to one destination

接下來(lái)引入了一個(gè)插入算子嘗試將線路集中某個(gè)線路中的站點(diǎn)分配到其他的線路中，以達(dá)到削減車(chē)輛數(shù)，減少車(chē)輛成本的目的.由Pareto 解的定義，式(4)的目標(biāo)函數(shù)中每減少一輛車(chē)，就可能出現(xiàn)一個(gè)新的Pareto解.因此，經(jīng)過(guò)該算子的操作，得到初始Pareto 解集Ypareto.具體步驟如下，如圖3所示.令TR={TR1,TR2,…,TRn}是由sweep-based算法產(chǎn)生的初始線路集合.

Step 1從TR中隨機(jī)選擇一個(gè)線路TRi，嘗試將TRi中的站點(diǎn)分配到其他線路中.

Step 2從TR{TRi}中再選擇一個(gè)線路TR*，檢測(cè)TRi中的目的地是否與TR*中的目的地一樣.如果不一致，算子將嘗試在TR*中搜索可以插入的位置.

Step 3在TR*中搜索可以插入的位置，將TRi中的站點(diǎn)分配到TR*中.如果TR*中沒(méi)有可以插入的位置，那么算子返回Step 2繼續(xù)搜索可以插入的線路.

Step 4重復(fù)Step 2和Step 3 直到TRi中的站點(diǎn)全部被分配到其余站點(diǎn).如果TRi中的站點(diǎn)全部被分配到其余站點(diǎn)，則削減了一個(gè)車(chē)輛數(shù)，更新線路集與Pareto 解集，并從TR中刪除TRi和TR*；否則，TR與TRi保持不變.

Step 5重復(fù)Step 1～Step 4 直到TR中的線路數(shù)(車(chē)輛數(shù))不能進(jìn)一步減少，這樣得到新的線路集合.

圖3 插入算子操作步驟Fig.3 Relocation operator procedure

2.2 更新Pareto解集

第二階段采用鄰域搜索方法進(jìn)一步改進(jìn)初始解[6].本文設(shè)計(jì)了兩種鄰域搜索算子對(duì)初始Pareto解集進(jìn)行更新.

(1)Relocate算子.

該算子隨機(jī)選擇某Pareto 解對(duì)應(yīng)線路集中的一條線路，并在該線路中隨機(jī)選擇兩個(gè)站點(diǎn)并置換位置，如圖4所示.

(2)Swap算子.

該算子隨機(jī)選擇某個(gè)Pareto 解中的對(duì)應(yīng)線路集中的兩條線路，并交換兩個(gè)線路中的目的地站點(diǎn)及其對(duì)應(yīng)的出發(fā)地站點(diǎn)，如圖5所示.

圖4 Relocate 算子示例Fig.4 Example of relocate operator

綜上所述，本文提出的啟發(fā)式算法的操作步驟如表2所示.

圖5 Swap 算子示例Fig.5 Example of swap operator

表2 兩階段啟發(fā)式算法步驟Table2 Overview of two-stage heuristic

3 案例分析

本文通過(guò)幾組算例驗(yàn)證模型和算法的有效性.論文中其他參數(shù)如下.車(chē)輛在每個(gè)?？空军c(diǎn)的服務(wù)時(shí)間按以下方式計(jì)算.首先，對(duì)于每個(gè)上車(chē)站點(diǎn)，服務(wù)時(shí)間[7](單位：s)為

式中：ni為在站點(diǎn)i服務(wù)的乘客總數(shù).類(lèi)似地，對(duì)于每個(gè)下車(chē)站點(diǎn)，服務(wù)時(shí)間為

假定車(chē)型載客量為45人/輛；定制公交的行駛速度為40 km/h[1]；出租車(chē)行駛速度為45 km/h[1].

本文采用了三種算例，每種算例有不同的出行需求.圖6 給出了其中一個(gè)算例的信息，該研究區(qū)域有兩個(gè)居住地區(qū)域和一個(gè)工作地區(qū)域，每個(gè)區(qū)域有若干個(gè)上車(chē)或下車(chē)站點(diǎn)[7].該算例中包含175個(gè)上車(chē)站點(diǎn)(居住地)，5個(gè)下車(chē)站點(diǎn)(工作地).本文案例中乘客的期望出發(fā)時(shí)間在集中在區(qū)間[6:30,10:30]，期望到達(dá)時(shí)間集中在區(qū)間[07:00,11:00].

圖6 算例示意圖Fig.6 Benchmark instance

表3給出了3組算例的基本信息、Pareto解中最優(yōu)乘客出行成本和最小車(chē)輛數(shù)兩種線路方案集所對(duì)應(yīng)的目標(biāo)函數(shù)值，以及所有Pareto 解的平均值.結(jié)果表明，隨著車(chē)輛數(shù)的增加乘客的出行成本會(huì)顯著降低，這是由于車(chē)輛數(shù)的增加會(huì)減少線路中間站點(diǎn)的個(gè)數(shù)從而減少出行成本.圖7給出了案例1中所得到的Pareto解的前沿面，也代表了不同的線路方案集.根據(jù)Pareto解的定義[8]，每個(gè)解均處于非支配地位，每個(gè)解所對(duì)應(yīng)的目標(biāo)函數(shù)值不同，即每個(gè)方案?jìng)?cè)重于不同的優(yōu)化目的.因此，本文所提出的算法為決策者提供了不同的可行方案，可根據(jù)實(shí)際情況靈活選擇.

本文進(jìn)一步分析了乘客選擇定制公交所產(chǎn)生的出行成本，并與出租車(chē)進(jìn)行了比較.比較的指標(biāo)包括出行時(shí)間，票價(jià)(出租車(chē)為車(chē)費(fèi))與總成本.這里的總成本為票價(jià)成本與時(shí)間價(jià)值成本之和.其中定制公交和出租車(chē)票價(jià)計(jì)算參照文獻(xiàn)[1].時(shí)間價(jià)值成本根據(jù)年人均收入和年平均工作時(shí)間計(jì)算[4]，根據(jù)已有資料，人均時(shí)間價(jià)值成本按0.85元/min計(jì)算.因此，本文將乘客的出行時(shí)間和提前到達(dá)的等待時(shí)間換算為時(shí)間價(jià)值成本.

圖7 算例Pareto 解(前沿面)Fig.7 Pareto solutions of benchmark problem

表3 模型的Pareto 解Table3 Model results with Pareto solutions

對(duì)于每個(gè)算例，計(jì)算了全部Pareto解中每個(gè)乘客出行需求的出行時(shí)間，票價(jià)與總成本，并對(duì)所有乘客的計(jì)算結(jié)果求平均值.圖8給出了每組案例中乘客選擇定制公交與出租車(chē)所產(chǎn)生的出行成本的比較結(jié)果.相比于出租車(chē)，選擇定制公交會(huì)多出30%左右的出行時(shí)間成本，但是費(fèi)用可以節(jié)省70%左右，并且總成本上定制公交也具有一定的優(yōu)勢(shì).因此，可以看出，定制公交可作為公共交通服務(wù)模式中一種很好的補(bǔ)充形式，為出行者提供更多的選擇.

4 結(jié) 論

本文提出了一種針對(duì)通勤定制公交的線路設(shè)計(jì)方法，以多區(qū)域到單區(qū)域的定制公交運(yùn)營(yíng)模式為基礎(chǔ)，構(gòu)建了多目標(biāo)線路規(guī)劃模型，綜合考慮了乘客出行成本與運(yùn)營(yíng)成本兩個(gè)方面.同時(shí)設(shè)計(jì)啟發(fā)式算法求解該模型并利用案例進(jìn)行了驗(yàn)證，并給出了定制公交不同線路中乘客的出行成本，并與出租車(chē)進(jìn)行對(duì)比，結(jié)果體現(xiàn)了定制公交可作為多元化公共交通服務(wù)模式中的一種補(bǔ)充形式，在未來(lái)研究中可將模型推廣至其他類(lèi)型的定制公交，以期為定制公交的線路設(shè)計(jì)方法提供相關(guān)理論依據(jù).