基于多目標(biāo)優(yōu)化與遺傳算法的公交調(diào)度模型

張荔 　馮鑫鑫 　王會(huì)龍 　張國(guó)增 　張汝峰 　劉昕偉

摘 要：結(jié)合地區(qū)公交現(xiàn)狀制定合理的公交調(diào)度機(jī)制，對(duì)于公共交通發(fā)展有著重要的現(xiàn)實(shí)意義和指導(dǎo)價(jià)值。本文以公交公司運(yùn)營(yíng)成本和乘客出行成本最小化為目標(biāo)函數(shù)，考慮車(chē)輛核載、出行時(shí)間等約束條件建立多目標(biāo)優(yōu)化函數(shù)，構(gòu)建城市公交調(diào)度模型。然后采用遺傳算法進(jìn)行求解，并以黃驊市6路公交進(jìn)行模型檢驗(yàn)。研究表明，優(yōu)化后的公交調(diào)度機(jī)制能夠有效降低公交公司的運(yùn)營(yíng)成本和乘客出行的時(shí)間成本。

關(guān)鍵詞：遺傳算法 多目標(biāo)優(yōu)化 公交調(diào)度 調(diào)度優(yōu)化

1 引言

當(dāng)前我國(guó)的公交系統(tǒng)逐步完善，然而公交系統(tǒng)依然存在票價(jià)不合理、乘客滿(mǎn)意度較低、乘客等車(chē)時(shí)間過(guò)長(zhǎng)等問(wèn)題，因此亟需構(gòu)建適合地域特點(diǎn)的公交調(diào)度模型，實(shí)現(xiàn)統(tǒng)籌調(diào)度。本文從乘客和公交公司雙重角度出發(fā)，建立多目標(biāo)優(yōu)化模型，并通過(guò)遺傳算法進(jìn)行模型求解。最后根據(jù)滄州市渤海新區(qū)地區(qū)特點(diǎn)、公交現(xiàn)狀，對(duì)黃驊市6路公交車(chē)調(diào)度進(jìn)行優(yōu)化檢驗(yàn)。

2 多目標(biāo)優(yōu)化模型建立

2.1 模型假設(shè)

由于在公交調(diào)度優(yōu)化過(guò)程中需要考慮眾多因素，因此對(duì)模型構(gòu)建做出如下假設(shè)[1]：（1）公交車(chē)的車(chē)型統(tǒng)一;（2）公交車(chē)的行駛速度恒定;（3）所有公交車(chē)全程使用統(tǒng)一票價(jià);（4）公交車(chē)運(yùn)行過(guò)程中不考慮上下車(chē)換乘的時(shí)間。

2.2 問(wèn)題分析

在實(shí)際公交運(yùn)營(yíng)過(guò)程中，一方面，要在滿(mǎn)足乘客的正常出行的情況下，最大程度上減少乘客出行成本，另一方面，則需要最大可能的減少公交公司的運(yùn)營(yíng)成本。考慮乘客出行成本與公交公司效益，公交線路優(yōu)化的具體步驟為：

步驟1：模型假設(shè)。根據(jù)公交現(xiàn)狀數(shù)據(jù)，對(duì)模型進(jìn)行初步假設(shè)，提出針對(duì)公交公司和乘客兩者的分治策略;

步驟2：建立模型?；诮y(tǒng)計(jì)數(shù)據(jù)，進(jìn)行模型訓(xùn)練，進(jìn)而構(gòu)建多目標(biāo)優(yōu)化模型構(gòu)建;

步驟3：多目標(biāo)優(yōu)化設(shè)計(jì)。確定影響因素以及經(jīng)驗(yàn)數(shù)值，并結(jié)合構(gòu)架完成的模型結(jié)果，構(gòu)建多目標(biāo)體系;

步驟4：目標(biāo)函數(shù)求解。根據(jù)多目標(biāo)模型，利用遺傳算法對(duì)目標(biāo)函數(shù)進(jìn)行求解;

步驟5：檢驗(yàn)優(yōu)化結(jié)果是否為最優(yōu)解，若達(dá)到優(yōu)化結(jié)果，則輸出優(yōu)化結(jié)果，否則返回步驟1。

2.3 模型構(gòu)建

2.3.1 最小公交運(yùn)營(yíng)成本模型

從公交公司的角度來(lái)看，公交運(yùn)營(yíng)成本所占比重如圖1所示，決定公交運(yùn)營(yíng)成本的主要因素分別為：燃油費(fèi)用、工作人員費(fèi)用、車(chē)輛損耗費(fèi)用、不同載客率影響下的產(chǎn)生費(fèi)用。

在不妨礙乘客利益的情況下，保證主要因素費(fèi)用達(dá)到運(yùn)營(yíng)成本的最小值，公交公司的運(yùn)營(yíng)成本即為最小，因此，針對(duì)以上四個(gè)主要因素建立公交最小運(yùn)營(yíng)成本模型：

（1）

其中，表示從站點(diǎn)到站點(diǎn)的距離;表示司機(jī)及相關(guān)人員的工資費(fèi)用;表示公交平均每公里的油耗;表示一位乘客對(duì)客車(chē)造成的平均損耗;表示在站點(diǎn)上車(chē)的人數(shù)。

2.3.2 最小乘客出行時(shí)間成本函數(shù)模型

乘客出行成本比重如圖2所示，主要分為四大階段：出發(fā)地到公交站、等待公交、乘客上下車(chē)、上車(chē)后最終到達(dá)終點(diǎn)站。

針對(duì)乘客出行的四大階段建立最小出行時(shí)間成本模型：

（2）

其中，，分別表示小區(qū)的長(zhǎng)度、寬度;表示在站點(diǎn)車(chē)內(nèi)的人數(shù);表示在公交車(chē)站等待公交的時(shí)間;表示平均發(fā)車(chē)間隔，表示公交車(chē)在站點(diǎn)停留時(shí)間（和取經(jīng)驗(yàn)常數(shù)）;表示乘客上下車(chē)使用的時(shí)間;表示從站點(diǎn)到站點(diǎn)的距離（）。

2.3.3 約束條件

1）出行時(shí)間約束

為了盡可能減少乘客的出行時(shí)間成本，優(yōu)化過(guò)后帶給乘客的出行成本一定要小于乘客常規(guī)的出行成本，即：

（3）

其中表示乘客自站上車(chē)到站下車(chē)的常規(guī)時(shí)間成本。

2）車(chē)輛核載約束

由于公交車(chē)的核載人數(shù)固定，因此車(chē)輛乘客總?cè)藬?shù)不超過(guò)車(chē)輛的核載人數(shù)，為保證公交公司的運(yùn)營(yíng)成本，將公交車(chē)的平均滿(mǎn)載率約束為不低于60%。

（4）

（5）

3 模型求解

3.1 遺傳算法流程

遺傳算法是通過(guò)二進(jìn)制或者實(shí)數(shù)編碼將問(wèn)題的解表示為“染色體”個(gè)體，然后進(jìn)行種群初始化，對(duì)種群進(jìn)行進(jìn)行一系列的選擇，交叉，變異操作，直至輸出適應(yīng)度最優(yōu)的個(gè)體，得到最終結(jié)果[2]。

1）編碼與種群初始化

首先，采用二進(jìn)制對(duì)問(wèn)題的解進(jìn)行編碼操作，其中每個(gè)染色體就代表在一個(gè)時(shí)間段內(nèi)的發(fā)車(chē)間隔，其次，發(fā)車(chē)的時(shí)間區(qū)間共14個(gè)，針對(duì)發(fā)車(chē)間隔的特點(diǎn)，將客流量的時(shí)間段分為客流高峰期和客流平穩(wěn)期，對(duì)于高峰期的發(fā)車(chē)間隔初始種群設(shè)置為區(qū)間[5，15]任意值，對(duì)于平穩(wěn)期的發(fā)車(chē)間隔初始種群設(shè)置為區(qū)間[15，30]中的任意值。種群初始化產(chǎn)生隨機(jī)數(shù)作為發(fā)車(chē)間隔的取值，并產(chǎn)生一個(gè)128bit的隨機(jī)數(shù)作為初始化路線。

2）選擇操作

利用公交的約束特征，對(duì)個(gè)體進(jìn)行選擇，隨機(jī)選擇個(gè)體比較，選擇兩者中最優(yōu)的個(gè)體進(jìn)入種群，重復(fù)進(jìn)行操作，直至達(dá)到規(guī)定的種群數(shù)量。

3）交叉操作

針對(duì)上文使用的編碼方式，通過(guò)改進(jìn)交叉算子的大小來(lái)進(jìn)行交叉操作。發(fā)車(chē)間隔段和路線選擇段分開(kāi)交叉考慮，發(fā)車(chē)間隔段以6bit為單位隨機(jī)選擇交叉點(diǎn)進(jìn)行交叉，路線選擇段則直接對(duì)該段所有bit選取隨機(jī)交叉點(diǎn)交叉操作。

4）變異操作

變異是通過(guò)賦予基因較小的變異概率實(shí)現(xiàn)，在選取變異基因時(shí)，需要保證變化的染色體所表示的解仍然屬于問(wèn)題的可行解域。隨機(jī)產(chǎn)生變異點(diǎn)以該bit反轉(zhuǎn)作為變異點(diǎn)，再對(duì)該區(qū)間檢查區(qū)域范圍，若不符合區(qū)域范圍則重新變異直至滿(mǎn)足。

4 模型檢驗(yàn)

4.1 基礎(chǔ)數(shù)據(jù)

本文以黃驊市6路公交為研究對(duì)象，對(duì)此線路上各個(gè)時(shí)間段的平均每日客流量進(jìn)行統(tǒng)計(jì)， 6路公交線總長(zhǎng)14公里，34個(gè)站點(diǎn)，固定的發(fā)車(chē)間隔為15分鐘，車(chē)輛的發(fā)車(chē)周期為：7：10—17：30，實(shí)行統(tǒng)一票價(jià)（1元/人）。由每日客流量數(shù)據(jù)分析如圖3所示，將公交的發(fā)車(chē)時(shí)段分為三個(gè)階段：客流高峰期的時(shí)間段為：7：30—8：30，17：30—19：30，客流過(guò)渡期的時(shí)間段為：13：30—15：30，客流平穩(wěn)期的時(shí)間段為：6：30—7：30，8：30—13：30，15：30—17：30，19：30—20：30。

4.2 參數(shù)設(shè)計(jì)

本文使用遺傳算法進(jìn)行求解過(guò)程中，具體的參數(shù)設(shè)置為：初始種群數(shù)：10000高峰期為[5.15]，平穩(wěn)期為[15，30];交叉率為0.5;變異率為0.01。

4.3 結(jié)果及分析

通過(guò)遺傳算法求解過(guò)程，可以得到黃驊市6路公交車(chē)的優(yōu)化的發(fā)車(chē)間隔，高峰期的發(fā)車(chē)間隔為9.2分鐘，過(guò)渡期的優(yōu)化時(shí)間間隔不發(fā)生改變依然為15分鐘，平穩(wěn)期的優(yōu)化時(shí)間間隔為18.6分鐘，考慮到公交發(fā)車(chē)時(shí)間段的實(shí)際情況一般為整數(shù)，進(jìn)一步取整后得到高峰期的發(fā)車(chē)時(shí)間間隔為10分鐘，平穩(wěn)期的優(yōu)化時(shí)間間隔為20分鐘，全天發(fā)車(chē)總次數(shù)為53次，優(yōu)化后的公交站點(diǎn)線路與公交車(chē)原線路相同。

本文針對(duì)黃驊市6路公交調(diào)度問(wèn)題進(jìn)行了深入的研究和優(yōu)化，統(tǒng)計(jì)數(shù)據(jù)顯示，黃驊市2路公交的日平均客流量情況與6路相仿，因此針對(duì)6路公交的優(yōu)化方式同樣適用于黃驊市2路公交。

5 結(jié)論

本文通過(guò)遺傳算法求解多目標(biāo)函數(shù)優(yōu)化模型，實(shí)現(xiàn)公交優(yōu)化調(diào)度模型構(gòu)建，并對(duì)黃驊市6路公交車(chē)調(diào)度進(jìn)行優(yōu)化檢驗(yàn)，研究表明，優(yōu)化后的公交調(diào)度機(jī)制能夠有效降低公交公司運(yùn)營(yíng)成本和乘客出行成本。該多目標(biāo)優(yōu)化調(diào)度模型及相關(guān)算法，可以推廣到其他線路公交的調(diào)度問(wèn)題，進(jìn)而實(shí)現(xiàn)整個(gè)地區(qū)公交服務(wù)體系升級(jí)。

基金項(xiàng)目：2020年滄州市社會(huì)科學(xué)發(fā)展研究課題（動(dòng)態(tài)需求下的城市公交柔性調(diào)度數(shù)學(xué)模型研究-以滄州市渤海新區(qū)為例2020025）;2020年滄州市科學(xué)計(jì)劃自籌經(jīng)費(fèi)項(xiàng)目（204102004）。

參考文獻(xiàn)：

[1]陶浪，馬昌喜，朱昌鋒，等.基于遺傳算法的定制公交路線多目標(biāo)優(yōu)化[J].蘭州交通大學(xué)學(xué)報(bào)，2018，037（002）：31-37.

[2]陳曉旭，項(xiàng)煜，楊超，等.基于遺傳算法的公交線路發(fā)車(chē)間隔優(yōu)化[J].交通與運(yùn)輸，2020（5）.