基于遺傳算法的公交車(chē)調(diào)度問(wèn)題

徐浩 吳海霞 李婷婷 白雪

石家莊鐵道大學(xué) 河北省石家莊市 050000

1 問(wèn)題重述

非線性規(guī)劃模型。

本文以2001年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題為例。

公共交通對(duì)于城市運(yùn)作具有重大意義，已知某大城市有一條公交線路，該線路上行有14站，下行有13站。該線路上的大客車(chē)為同一型號(hào)，標(biāo)準(zhǔn)載客量為100人，客車(chē)平均速度為20公里/小時(shí)。要求，乘客候車(chē)時(shí)間不能超過(guò)10分鐘，早高峰時(shí)不能超過(guò)5分鐘，車(chē)輛的滿載率不能超過(guò)120%，一般也不低于50%。

為該線路設(shè)計(jì)一個(gè)公交車(chē)調(diào)度方案，包括兩個(gè)起點(diǎn)站的發(fā)車(chē)時(shí)刻表；一共需要多少輛車(chē)；這個(gè)方案以怎樣的程度照顧到了乘客和公交公司雙方的利益。

2 問(wèn)題分析

題目要求設(shè)計(jì)調(diào)度方案，則需要求出發(fā)車(chē)間隔，可以設(shè)置發(fā)車(chē)間隔為自變量，利用候車(chē)人數(shù)、公交車(chē)輛數(shù)等因素，推導(dǎo)出滿載率、全天發(fā)車(chē)次數(shù)、所需公交車(chē)輛數(shù)。同時(shí)綜合考慮公交車(chē)公司和乘客的利益，引入公交車(chē)行駛成本和乘客等待成本兩個(gè)概念。對(duì)于公交車(chē)公司來(lái)說(shuō)，發(fā)車(chē)時(shí)間間隔越長(zhǎng)，全天發(fā)車(chē)次數(shù)越少，需要的公交車(chē)越少，成本越低；對(duì)于乘客來(lái)說(shuō)，發(fā)車(chē)間隔越短，乘客等待時(shí)間越短，成本越低。因此公交車(chē)公司和乘客的利益是對(duì)立的，需要考慮在不同的程度下照顧公交公司和乘客的利益，所以引入權(quán)重概念，將多目標(biāo)轉(zhuǎn)化為單目標(biāo)，建立

3 問(wèn)題假設(shè)

（1）假設(shè)每個(gè)時(shí)間段內(nèi)乘客到達(dá)數(shù)服從均勻分布；（2）假設(shè)汽車(chē)一直以平均速度行駛，不受外界因素影響；（3）假設(shè)乘客上下車(chē)時(shí)間非常短，可以忽略不計(jì)；（4）假設(shè)公交車(chē)到達(dá)終點(diǎn)站返回時(shí)可以載客。

4 模型的建立

假設(shè)第i個(gè)時(shí)間段發(fā)車(chē)間隔為ti，時(shí)長(zhǎng)為T(mén)i，第i個(gè)時(shí)間段第j個(gè)站上車(chē)人數(shù)為uij，下車(chē)人數(shù)為vij，（i=1，2，…，m，j=1，2，…，n）。標(biāo)準(zhǔn)載客人數(shù)為P人，路線總長(zhǎng)為L(zhǎng)千米，公交車(chē)平均行駛速度為V千米/小時(shí)，公交車(chē)每公里運(yùn)行成本為C1元/(輛·千米)，乘客每分鐘等待成本為C2元/(人·分鐘)。

則第i個(gè)時(shí)間段發(fā)車(chē)數(shù)

第i個(gè)時(shí)間段第j個(gè)站平均每輛車(chē)人數(shù)

第i個(gè)時(shí)間段第j個(gè)站和第j+1個(gè)站之間的車(chē)的滿載率

全天平均滿載率

一個(gè)工作日發(fā)車(chē)總數(shù)

第i個(gè)時(shí)間段線路上單向車(chē)輛數(shù)

全天所需公交車(chē)輛數(shù)

公交車(chē)公司的目標(biāo)是一個(gè)工作日內(nèi)所有公交車(chē)運(yùn)行成本最低，表示為

乘客的目標(biāo)是一個(gè)工作日內(nèi)所有乘客等待成本最低，表示為

發(fā)車(chē)間隔時(shí)要求高峰期不要超過(guò)5分鐘，非高峰期不要超過(guò)10分鐘，得到發(fā)車(chē)間隔約束條件為

公交車(chē)可以載客人數(shù)較少，但絕對(duì)不能超載，由此得到滿載率約束條件為

引入權(quán)重，將多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)規(guī)劃，得到綜合考慮公交車(chē)公司和乘客雙方總成本的規(guī)劃模型

其中α、β為權(quán)重系數(shù)，且α+β=1。

5 模型的求解

該問(wèn)題是一個(gè)復(fù)雜的規(guī)劃問(wèn)題，用經(jīng)典的優(yōu)化方法難以求解，可以利用遺傳算法進(jìn)行求解。

5.1 參數(shù)取定

對(duì)于編碼方式，本文采用二進(jìn)制編碼；對(duì)于初始種群，可以通過(guò)隨機(jī)生成的方法產(chǎn)生初始種群，本文設(shè)置種群規(guī)模為20；對(duì)于適應(yīng)度函數(shù)，本文設(shè)定適應(yīng)度越小適應(yīng)性越強(qiáng)，將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)；對(duì)于選擇操作，本文選用輪盤(pán)賭法；對(duì)于交叉操作，本文采用單點(diǎn)交叉的方式，交叉概率取0.8；對(duì)于變異操作，本文采用基本位變異，變異概率設(shè)置為0.01；設(shè)置搜索終止的條件為迭代次數(shù)達(dá)到100次。

根據(jù)所給數(shù)據(jù)，上行方向行駛距離14.58千米，下行方向14.61千米。公交車(chē)每公里運(yùn)行燃料花費(fèi)為2~3元，考慮到其他花費(fèi)，設(shè)公交車(chē)每公里運(yùn)行成本C1=10元。乘客每分鐘等待的成本即乘客用等待的時(shí)間所能創(chuàng)造的價(jià)值，以北京為例，通過(guò)訪問(wèn)北京市統(tǒng)計(jì)局官網(wǎng)可知，2016年北京居民人均可支配收入為52530元，第五次全國(guó)人口普查顯示，北京市人均每周工作5.9天，則北京居民一年有365-10-52×1.1=297.8個(gè)工作日。按每天工作8小時(shí)記，則一個(gè)乘客每分鐘等待成本

5.2 結(jié)果的分析與檢驗(yàn)

取權(quán)重系數(shù)α=0.6，β=0.4，可以求得最優(yōu)發(fā)車(chē)間隔，根據(jù)式（1）計(jì)算可得各時(shí)間段發(fā)車(chē)數(shù)，得到簡(jiǎn)化發(fā)車(chē)時(shí)刻及發(fā)車(chē)數(shù)如表1所示。

經(jīng)過(guò)計(jì)算可得一個(gè)工作日總發(fā)車(chē)數(shù)S為524輛，全天平均滿載率R為76.612%。

表1 簡(jiǎn)化發(fā)車(chē)時(shí)刻表

根據(jù)式（5）計(jì)算可得各個(gè)時(shí)間段線路中上下行車(chē)輛數(shù)目如表2所示。

由上表可以看出，早高峰6：00-9：00時(shí)間段所需公交車(chē)數(shù)量最多，為37輛，全天所需公交車(chē)數(shù)目不會(huì)超過(guò)早高峰所需車(chē)輛數(shù)目，所以全天所需公交車(chē)輛數(shù)為37輛。

6 模型的評(píng)價(jià)與推廣

該模型從實(shí)際出發(fā)，綜合考慮了公交車(chē)公司和乘客雙方的利益，建立了總成本最低的非線性規(guī)劃模型，成本系數(shù)的設(shè)定結(jié)合了生活實(shí)際，有較高的可信度。且利用遺傳算法對(duì)復(fù)雜優(yōu)化問(wèn)題進(jìn)行求解，大大縮短了求解時(shí)間。同時(shí)模型具有較高的適用性，對(duì)于不同的城市不同的公交路線，只需要將相關(guān)系數(shù)更正，將觀測(cè)數(shù)據(jù)代入模型，即可得到較為合理的發(fā)車(chē)安排。

表2 線路中上下行車(chē)輛數(shù)目表