定制公交可變線(xiàn)路設(shè)計(jì)研究

熊丹

（首都經(jīng)濟(jì)貿(mào)易大學(xué)管理工程學(xué)院，北京 100070）

1 研究背景

改革開(kāi)放初期，中國(guó)以自行車(chē)為主要的交通工具，到20 世紀(jì)90 年代則以公交車(chē)為主要交通工具。21世紀(jì)初，國(guó)家提出了以公共交通為優(yōu)先發(fā)展對(duì)象的戰(zhàn)略。

近年來(lái)，隨著國(guó)家城鎮(zhèn)化進(jìn)程的不斷推進(jìn)、人口不斷向城市聚集，導(dǎo)致了城市人口的不斷增加，城市交通擁堵的問(wèn)題日益嚴(yán)重。一方面，城市居民的交通出行需求日漸增加，而公共交通的種類(lèi)單一，導(dǎo)致城市交通供需矛盾日益尖銳。另一方面，截至2019年，中國(guó)私人汽車(chē)的擁有量達(dá)到22 508.99 萬(wàn)輛，城市道路擁堵已成為常態(tài)。為了減少個(gè)人對(duì)私家車(chē)的過(guò)度依賴(lài)，大力發(fā)展多元化的公共交通將成為一個(gè)突破口。

定制公交近年來(lái)發(fā)展迅速，它以提供靈活可靠的服務(wù)為宗旨。青島、北京、深圳、成都等城市率先開(kāi)通定制公交。但隨著經(jīng)濟(jì)的發(fā)展，點(diǎn)對(duì)點(diǎn)式的定制公交已經(jīng)不能滿(mǎn)足乘客的出行需求。定制公交可變線(xiàn)路應(yīng)運(yùn)而生，具有更加靈活、便捷的特點(diǎn)[1]。為了吸引更多的私家車(chē)用戶(hù)選擇公交系統(tǒng)出行，減少道路擁堵，特別是在人口密集的地區(qū)，因此提出了定制公交可變線(xiàn)路的概念[2]。定制公交可變線(xiàn)路是定制公交線(xiàn)路的一個(gè)創(chuàng)新，線(xiàn)路更為靈活?？勺兙€(xiàn)路突出此類(lèi)公交服務(wù)不是點(diǎn)對(duì)點(diǎn)式的直達(dá)服務(wù)，而是根據(jù)此區(qū)域內(nèi)乘客的出行需求，定制公交線(xiàn)路。在一定程度上能更好滿(mǎn)足此出行區(qū)域內(nèi)乘客個(gè)性化的出行需求，提高定制公交的服務(wù)水平，彌補(bǔ)其不足之處。

2 定制公交可變線(xiàn)路營(yíng)運(yùn)規(guī)則

2.1 服務(wù)規(guī)則

定制公交可變路線(xiàn)分為靜態(tài)定制公交可變線(xiàn)路和動(dòng)態(tài)定制公交可變線(xiàn)路。靜態(tài)定制公交可變線(xiàn)路只允許乘客提前預(yù)約，在路線(xiàn)設(shè)計(jì)前已經(jīng)充分了解乘客的預(yù)約出行信息。動(dòng)態(tài)定制公交可變線(xiàn)路允許乘客提前預(yù)約和實(shí)時(shí)預(yù)訂，除路線(xiàn)設(shè)計(jì)前生成的旅客出行信息外，車(chē)輛運(yùn)行過(guò)程中還將生成實(shí)時(shí)的旅客預(yù)約信息。本文以靜態(tài)定制公交可變路線(xiàn)為研究對(duì)象，將其服務(wù)過(guò)程分為乘客預(yù)約、路線(xiàn)設(shè)計(jì)和信息反饋3個(gè)階段[3]。

乘客預(yù)約階段：當(dāng)乘客計(jì)劃出行時(shí)，乘客通過(guò)電話(huà)、購(gòu)買(mǎi)的預(yù)訂卡、互聯(lián)網(wǎng)、手機(jī)等方式將個(gè)人基本信息、出行起訖點(diǎn)、上車(chē)時(shí)間和特殊要求等告知調(diào)度中心，進(jìn)行預(yù)約。

線(xiàn)路設(shè)計(jì)階段：調(diào)度中心將預(yù)約申請(qǐng)信息儲(chǔ)存到數(shù)據(jù)庫(kù)中，在預(yù)約截止后，調(diào)度中心根據(jù)數(shù)據(jù)庫(kù)中出行需求數(shù)據(jù)，在結(jié)合天氣、路況等客觀(guān)條件下，根據(jù)相關(guān)線(xiàn)路設(shè)計(jì)規(guī)則對(duì)定制公交線(xiàn)路進(jìn)行設(shè)計(jì)。

信息反饋階段：調(diào)度中心將線(xiàn)路設(shè)計(jì)的結(jié)果通知乘客。調(diào)度中心向乘客發(fā)送上車(chē)時(shí)間、上車(chē)地點(diǎn)以及公交車(chē)輛信息等。

2.2 行駛規(guī)則

定制公交可變線(xiàn)路設(shè)計(jì)必須從首站出發(fā)，依次經(jīng)過(guò)各個(gè)候選站點(diǎn)，不允許逆向行駛，最后到達(dá)末站。通過(guò)合理的站線(xiàn)設(shè)計(jì)，保證定制公交依照最優(yōu)線(xiàn)路行駛，且定制公交車(chē)輛上安裝有智能運(yùn)營(yíng)系統(tǒng)，可以幫助其進(jìn)行速度調(diào)整，確保定制公交按照預(yù)先設(shè)計(jì)的時(shí)間到達(dá)站點(diǎn)。

2.3 拒絕規(guī)則

被拒的申請(qǐng)是不符合規(guī)則的申請(qǐng)。例如，起點(diǎn)和終點(diǎn)不在定制公交可變線(xiàn)路的服務(wù)范圍內(nèi)，預(yù)定上車(chē)時(shí)間不在定制公交可變線(xiàn)路的服務(wù)時(shí)間內(nèi)。

3 遺傳模擬退火算法

遺傳算法在第一階段產(chǎn)生了可行解，模擬退火算法在第二階段對(duì)解集進(jìn)行了調(diào)整，并在保證解可行的基礎(chǔ)上，對(duì)解集進(jìn)行了迭代改進(jìn)，使目標(biāo)函數(shù)值盡可能得最優(yōu)。以遺傳算法為框架，在執(zhí)行遺傳操作的過(guò)程中加入了退火操作，為體現(xiàn)所設(shè)計(jì)算法和現(xiàn)有算法的區(qū)別與改進(jìn)，現(xiàn)分別闡述這3 種算法的基本思想和原理[4]。

遺傳模擬退火算法是遺傳算法和模擬退火算法結(jié)合產(chǎn)生的混合算法。遺傳算法具有全局尋優(yōu)能力，但局部搜索能力較差，因此在求解模型時(shí)會(huì)早熟，引起局部收斂，最終形成局部最優(yōu)解。模擬退火算法有很強(qiáng)的局部搜索能力，可在解空間搜索全局最優(yōu)解，但對(duì)搜索空間的整體把握較差。

遺傳算法是群智能優(yōu)化算法，遺傳算法使用一個(gè)種群去進(jìn)行搜索，經(jīng)過(guò)操作后用種群中的最優(yōu)個(gè)體作為全局最優(yōu)解。模擬退火算法只是對(duì)一個(gè)解不斷地進(jìn)行操作，然后最終得到一個(gè)全局最優(yōu)解。遺傳算法的操作對(duì)象是若干個(gè)個(gè)體，模擬退火算法的操作對(duì)象是一個(gè)個(gè)體，所以很自然地想到，在遺傳算法經(jīng)過(guò)選擇、交叉和變異操作后，對(duì)產(chǎn)生的子代種群中的若干個(gè)或者全部個(gè)體進(jìn)行模擬退火操作。遺傳模擬退火算法計(jì)算的基本思想是綜合兩種算法的優(yōu)點(diǎn)，提升搜索性能和計(jì)算速度。

4 定制公交可變線(xiàn)路設(shè)計(jì)模型

分別從乘客、運(yùn)營(yíng)商、社會(huì)的角度出發(fā)，以乘客的在車(chē)時(shí)間、車(chē)輛營(yíng)運(yùn)成本、污染物排放3 個(gè)因素構(gòu)建模型。目標(biāo)是在成功收到調(diào)度中心信息反饋乘客的出行需求、備選站點(diǎn)位置及服務(wù)人數(shù)確定的情況下，某一區(qū)域所有乘客的通勤需求被滿(mǎn)足的基礎(chǔ)上，為定制公交可變線(xiàn)路確定最優(yōu)的開(kāi)行方案，包括車(chē)輛的數(shù)量、車(chē)輛的行駛路線(xiàn)等[5-6]。

問(wèn)題的基本假設(shè)如下：①乘客在設(shè)置的居住區(qū)域只上車(chē)不下車(chē)，在工作區(qū)域只下車(chē)不上車(chē)；②不同站點(diǎn)間的距離已經(jīng)確定；③只使用一種車(chē)輛參數(shù)已知的公交車(chē)型；④車(chē)輛在所有線(xiàn)路上勻速行駛，不考慮交通擁堵因素。

模型參數(shù)如表1 所示。

表1 模型參數(shù)

4.1 目標(biāo)函數(shù)

綜合考慮了乘客在車(chē)時(shí)間成本、車(chē)輛運(yùn)營(yíng)成本、環(huán)境污染成本來(lái)構(gòu)建定制公交可變線(xiàn)路設(shè)計(jì)的目標(biāo)函數(shù)。

4.1.1 乘客在車(chē)時(shí)間成本

對(duì)于乘客來(lái)說(shuō)，乘客希望通勤時(shí)間最短。由于在出行前定制公交可變線(xiàn)路設(shè)計(jì)的調(diào)度中心會(huì)將上車(chē)時(shí)間、上車(chē)地點(diǎn)、車(chē)輛信息等告知乘客，所以本文認(rèn)為乘客的候車(chē)時(shí)間為0。在可變線(xiàn)路設(shè)計(jì)模型的構(gòu)建中，著重考慮乘客的在車(chē)時(shí)間成本。乘客在車(chē)時(shí)間成本如下所示：

4.1.2 車(chē)輛運(yùn)營(yíng)成本

定制公交可變線(xiàn)路由于目前的運(yùn)載量和運(yùn)營(yíng)規(guī)模相比傳統(tǒng)公交較低，所以應(yīng)盡可能保障公交運(yùn)營(yíng)公司的利潤(rùn)，降低車(chē)輛運(yùn)營(yíng)成本。在模型中，車(chē)輛運(yùn)營(yíng)成本如下所示：

4.1.3 環(huán)境污染成本

定制公交可變線(xiàn)路的污染排放成本如下所示：

4.2 約束條件

4.2.1 站點(diǎn)服務(wù)約束

在定制公交可變線(xiàn)路的設(shè)計(jì)中，成功收到調(diào)度中心信息反饋的乘客出行需求都應(yīng)被滿(mǎn)足，即至少有一輛定制公交可變線(xiàn)路為其提供服務(wù)。為避免車(chē)輛在站點(diǎn)間循環(huán)行駛，在本模型中規(guī)定同一輛車(chē)對(duì)某一站點(diǎn)的訪(fǎng)問(wèn)次數(shù)不超過(guò)一次，相關(guān)計(jì)算公式如下：

4.2.2 車(chē)輛運(yùn)載量約束

與傳統(tǒng)公交不同的是，定制公交可變線(xiàn)路致力于提供更舒適的服務(wù)，因此定制公交可變線(xiàn)路所能運(yùn)載的最大乘客數(shù)即車(chē)輛的額定載客數(shù)。同時(shí)，為了避免“空車(chē)行駛”的情況發(fā)生，需對(duì)定制公交可變線(xiàn)路設(shè)置最低上座率，相關(guān)計(jì)算公式如下：

4.2.3 避免車(chē)輛淤積約束

定制公交可變線(xiàn)路到達(dá)站點(diǎn)完成服務(wù)后便離開(kāi)前往下一站點(diǎn)，避免車(chē)輛在某站點(diǎn)?？亢笪措x開(kāi)造成車(chē)輛淤積現(xiàn)象，相關(guān)計(jì)算公式如下：

4.2.4 決策變量約束

k車(chē)是否經(jīng)過(guò)弧（i，j）：

j站是否被車(chē)輛k服務(wù)：

4.3 模型的綜合表達(dá)

通過(guò)前文對(duì)目標(biāo)函數(shù)及約束條件的分析與設(shè)置，建立的定制公交可變線(xiàn)路規(guī)劃模型如下。

目標(biāo)函數(shù)：

約束條件：

5 遺傳模擬退火算法的求解步驟

遺傳模擬退火算法以遺傳算法為框架，在遺傳操作過(guò)程中加入模擬退火操作。首先對(duì)種群進(jìn)行初始化，然后通過(guò)選擇操作、交叉操作、變異操作生成新的個(gè)體。最后對(duì)每一個(gè)新個(gè)體進(jìn)行模擬退火操作，產(chǎn)生新一代種群，循環(huán)，直到滿(mǎn)足算法的終止條件為止。

第一，輸入N個(gè)乘客的坐標(biāo)，設(shè)置算法參數(shù)：交叉概率Pc、變異概率Pm、種群規(guī)模NIND、遺傳算法迭代次數(shù)Maxgen。第二，初始化種群，設(shè)置迭代次數(shù)Gen=0。第三，根據(jù)選定的適應(yīng)度函數(shù)進(jìn)行計(jì)算，并保留適應(yīng)度高的，以備下一步操作。第四，根據(jù)交叉概率Pc和變異概率Pm，對(duì)保留個(gè)體進(jìn)行交叉和變異，產(chǎn)生新的個(gè)體。第五，進(jìn)行模擬退火操作，根據(jù)一定的標(biāo)準(zhǔn)來(lái)確定是否接受新的個(gè)體，Gen=Gen+1。第六，設(shè)置算法的終止條件，如果滿(mǎn)足停止循環(huán)，否則模擬退火操作后返回第三步。第七，輸出最優(yōu)解，結(jié)束算法。

6 結(jié)束語(yǔ)

在結(jié)合中國(guó)國(guó)情的情況下，從定制公交可變線(xiàn)路系統(tǒng)的基本特性作為切入點(diǎn)，將其與常規(guī)公交進(jìn)行對(duì)比分析，總結(jié)發(fā)展定制公交可變線(xiàn)路的必要性。以在車(chē)乘客時(shí)間成本、車(chē)輛運(yùn)營(yíng)成本、環(huán)境污染成本最小為優(yōu)化目標(biāo)，建立優(yōu)化模型。采用遺傳模擬退火算法進(jìn)行求解。