熊丹

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

1 研究背景

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

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

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

2 定制公交可變線路營運規(guī)則

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

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

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

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

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

2.2 行駛規(guī)則

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

2.3 拒絕規(guī)則

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

3 遺傳模擬退火算法

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

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

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

4 定制公交可變線路設(shè)計模型

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

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

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

表1 模型參數(shù)

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

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

4.1.1 乘客在車時間成本

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

4.1.2 車輛運營成本

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

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

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

4.2 約束條件

4.2.1 站點服務(wù)約束

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

4.2.2 車輛運載量約束

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

4.2.3 避免車輛淤積約束

定制公交可變線路到達(dá)站點完成服務(wù)后便離開前往下一站點，避免車輛在某站點停靠后未離開造成車輛淤積現(xiàn)象，相關(guān)計算公式如下：

4.2.4 決策變量約束

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

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

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

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

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

約束條件：

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

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

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

6 結(jié)束語

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