徐浩 吳海霞 李婷婷 白雪

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

1 問題重述

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

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

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

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

2 問題分析

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

3 問題假設(shè)

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

4 模型的建立

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

則第i個時間段發(fā)車數(shù)

第i個時間段第j個站平均每輛車人數(shù)

第i個時間段第j個站和第j+1個站之間的車的滿載率

全天平均滿載率

一個工作日發(fā)車總數(shù)

第i個時間段線路上單向車輛數(shù)

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

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

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

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

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

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

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

5 模型的求解

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

5.1 參數(shù)取定

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

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

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

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

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

表1 簡化發(fā)車時刻表

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

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

6 模型的評價與推廣

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

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