公交線路的車輛調(diào)度問題_2001年全國大學(xué)生數(shù)學(xué)建模競賽B題.pdf

文章編號 1671 2250 2002 01 0014 05 公交線路的車輛調(diào)度問題 2001 年全國大學(xué)生數(shù)學(xué)建模競賽 B 題 何永強(qiáng)1 黃 劍2 陸新根1 1 浙江萬里學(xué)院工程技術(shù)系 98 級學(xué)生 寧波 315100 2 浙江萬里學(xué)院計(jì)算機(jī)系 00 級學(xué)生 寧波 315100 指導(dǎo)教師 郭秋麗 岑仲迪 摘 要 通過計(jì)算機(jī)模擬仿真得到各間隔的參數(shù) 而后轉(zhuǎn)化為多目標(biāo)規(guī)劃再求解 對已有的數(shù)據(jù)進(jìn)行分析 運(yùn) 用模糊聚類分析法 將一工作日分為若干段 問題 1 對模型 1 考慮了乘客的上下車人次都是定長 均勻 分布 通過計(jì)算機(jī)仿真求得各間隔的參數(shù) 然后通過多目標(biāo)規(guī)劃進(jìn)行求解 并得到最終解 對于模型 2 我們考慮了乘客的上下車人數(shù)都是服從 Poisson 分布 用 Monte Carlo 法進(jìn)行仿真 然后通過多目標(biāo)規(guī)劃進(jìn)行求解 并得到最終解 問題 2 在求解過程中時(shí)間段的劃分對其程序有很大程度的影響 在實(shí)際采集數(shù)據(jù)中應(yīng)當(dāng)注意到各個時(shí) 間段 關(guān) 鍵 詞 模糊聚類 多目標(biāo)規(guī)劃 Monte Carlo 仿真 中圖分類號 O29 文獻(xiàn)標(biāo)識碼 A 1 問題重述 公共交通是城市交通的重要組成部分 作好公交車的調(diào)度對于完善城市交通環(huán)境 改進(jìn)市民出行狀況 提高公交公司的經(jīng)濟(jì)和社會效益 都具有重要意義 下面考慮一條公交線路上公交車的調(diào)度問題 其數(shù)據(jù)來 自我國一座特大城市某條公交線路的客流調(diào)查和運(yùn)營資料 該條公交線路上行方向共 14 站 下行方向共 13 站 該文給出的是典型的一個工作日兩個運(yùn)行方向各站上下車的乘客數(shù)量統(tǒng)計(jì) 公交公司配給該線路同一 型號的大客車 每輛標(biāo)準(zhǔn)載客 100人 據(jù)統(tǒng)計(jì)客車在該線路上運(yùn)行的平均速度為 20km h 1 運(yùn)營調(diào)度要求 乘客候車時(shí)間一般不要超過 10min 早高峰時(shí)一般不要超過 5min 車輛滿載率不應(yīng)超過 120 一般也不要 低于 50 試根據(jù)這些資料和要求 為該線路設(shè)計(jì)一個便于操作的全天 工作日 的公交車調(diào)度方案 包括兩個起點(diǎn)站 的發(fā)車時(shí)刻表 一共需要多少輛車 這個方案以怎樣的程度照顧到了乘客和公交公司雙方的利益等等 如何將 這個調(diào)度問題抽象成一個明確 完善的數(shù)學(xué)模型 指出求解模型的方法 根據(jù)實(shí)際問題的要求 如果設(shè)計(jì)更好的 調(diào)度方案 應(yīng)如何采集運(yùn)營數(shù)據(jù) 有關(guān)每條線路 上行 下行 每站 A0 A13 在每小時(shí) 5B00 23B00 內(nèi)上車與 下車人數(shù)的統(tǒng)計(jì)數(shù)據(jù)見表格 詳見 www 163 com 教育頻道 第 15 卷 第 1期 浙江萬里學(xué)院學(xué)報(bào) Vol 15 No 1 2002 年 3 月 Journal of Zhejiang Wanli University Mar 2002 收稿日期 2001 10 09 作者簡介 何永強(qiáng) 1981 男 浙江義烏人 黃劍 1982 男 浙江衢州人 陸新根 1979 男 浙江海寧人 本文曾獲 2001 年全國大學(xué)生數(shù) 學(xué)建模競賽浙江省二等獎 根據(jù)數(shù)學(xué)論文署名的國際慣例 作者排序參照姓名的拼音順序 2 問題分析 2 1 影響問題分析的主要因素 影響該問題的主要因素有汽車的數(shù)量 乘客人數(shù)與到站規(guī)律 發(fā)車間隔及線路上的其它隨機(jī)因素對車 輛運(yùn)行的干擾 評價(jià)公共汽車運(yùn)行結(jié)果的指標(biāo)很多 一般說來 好的運(yùn)行效果主要應(yīng)做到以下三點(diǎn) 1 總留乘時(shí)間要少 以減少乘客等待時(shí)間 提高服務(wù)質(zhì)量 其中 總留乘時(shí)間 E 第 i 車站留乘人數(shù) 留乘時(shí)間 2 滿載率高 運(yùn)行車公里數(shù)要少 其中 車公里數(shù) 車次數(shù) 線路長度 3 客人數(shù)小于 50人時(shí) 總空車時(shí)間 E 50 某車某一段乘客數(shù) 運(yùn)行時(shí)間 顯然 減少乘客等待時(shí)間和減少運(yùn)行車公里數(shù)兩個要求相互矛盾 如何在這些目標(biāo)中找一個合理的匹 配關(guān)系 是運(yùn)輸管理中的一個重要問題 我們可以利用計(jì)算機(jī)仿真得到不同車輛配置 不同發(fā)車間隔 不同 乘客流量下的總留乘時(shí)間 車公里數(shù)等 2 2 汽車 車站和乘客 實(shí)體是汽車 車站和乘客 此外所指的汽車屬性包括在車場排隊(duì)還是運(yùn)行 運(yùn)行至哪一點(diǎn) 運(yùn)行時(shí)間 車 上乘客人數(shù)等 而乘客的屬性有等車 等車時(shí)間 乘車 車站的屬性則是該站是否有乘客等車 系統(tǒng)中所涉及 的事件有首站發(fā)車事件 到達(dá)中途站事件 到達(dá)終點(diǎn)站事件 乘客到達(dá)事件 上 下車事件 1 首站發(fā)車活動 根據(jù)發(fā)車時(shí)刻表從首站發(fā)車 這要考慮是否到了發(fā)車時(shí)刻及車場是否有車可發(fā) 還 要考慮首站的上車人數(shù) 到達(dá)下一站的時(shí)間 2 到達(dá)中途站活動 這需計(jì)算在本站上下車的人數(shù) 確定乘車人數(shù)及時(shí)間 預(yù)測汽車下一個的后續(xù)活 動的出現(xiàn)時(shí)間 累加運(yùn)行公里數(shù) 3 末站調(diào)頭活動 就是確定汽車的去向 是立即發(fā)車還是等待發(fā)車 2 3 模糊聚類分析法劃分不同時(shí)間段 為了便于調(diào)度 根據(jù)所提供的上下車人次的數(shù)據(jù)和我國實(shí)際的上下班制度 我們對時(shí)間段按照模糊聚 類分析法進(jìn)行進(jìn)一步劃分 分為不同時(shí)間段高峰期 低潮期 一般期 3 模型建立 3 1 車輛調(diào)度策略及其仿真 該題是一個動態(tài)的變化過程 無法就某個時(shí)刻單獨(dú)取出單獨(dú)考慮 并且在整個車輛運(yùn)行過程中 隨機(jī)的 因素較多 難以準(zhǔn)確地把握 無法較為簡便 準(zhǔn)確的求出評價(jià)調(diào)度方案的指標(biāo) 如 總的空車時(shí)間 總留乘時(shí) 間 車公里數(shù) 所以我們運(yùn)用了仿真的思想將其動態(tài)的過程進(jìn)行模擬 以求出各個評價(jià)指標(biāo) 首先 根據(jù)表格給出的數(shù)據(jù) 以及實(shí)際生活的情況 也為了簡化仿真的復(fù)雜度 我們將一個工作日分為 n 個時(shí)間段 根據(jù)已有的數(shù)據(jù)確定一個發(fā)車間隔的范圍 如 在高峰期發(fā)車的間隔為 1 5min 而在低潮期發(fā)生 間隔為 10 15min 一般時(shí)段發(fā)車間隔 7 10min 第二步 對第一個時(shí)間段進(jìn)行仿真搜索 先設(shè)定這一時(shí)段的發(fā)車間隔 在仿真過程中 計(jì)算出各個仿真 時(shí)刻每一輛車的載客數(shù) 車輛的位置 以及各個站點(diǎn)的等待的人數(shù) 并對所需要的評價(jià)指標(biāo)進(jìn)行累加 在結(jié) 束時(shí) 得出該發(fā)車間隔所對應(yīng)的評價(jià)指標(biāo) 及在結(jié)束時(shí) 運(yùn)行狀態(tài)的各個車的具體狀態(tài) 如 位置 載客量 第三步 對所求得的評價(jià)指標(biāo)進(jìn)行分析 求得最佳的評價(jià)指標(biāo)組合以及所對應(yīng)最佳發(fā)車間隔 第四步 對下一個時(shí)段進(jìn)行仿真 在開始讀入上一個階段的最佳發(fā)車間隔做仿真 結(jié)束時(shí)的運(yùn)行車輛的 狀態(tài) 改變發(fā)車間隔繼續(xù)仿真 同理得出最佳的時(shí)間間隔 此處讀入上一仿真結(jié)束時(shí)的運(yùn)行車輛的狀態(tài) 并 對其進(jìn)行的延續(xù) 可更好的對相鄰的時(shí)間的進(jìn)行銜接 更符合實(shí)際 使得出的解更有可信度 如此循環(huán) 求得 各個階段的最佳發(fā)車間隔 便可制定出最佳的發(fā)車間隔 3 2 模型 3 2 1 模型假設(shè) 15 第 1 期何永強(qiáng) 黃 劍 陸新根 公交線路的車輛調(diào)度問題 1 單位時(shí)間內(nèi)到達(dá)第 i 個車站的人數(shù)服從定長 均勻 分布 2 車上每位乘客在以后各站下車人數(shù) 服從定長 均勻 分布 3 考慮各站的上下車都是同時(shí)進(jìn)行 每位乘客的上下車時(shí)間都相等 4 各輛汽車的最大容量是指車內(nèi)座席數(shù)和有效站面積上的站立人數(shù) 5 汽車的運(yùn)行時(shí)間只包括乘客上下車時(shí)間和必要的運(yùn)行時(shí)間 不考慮其它時(shí)間 6 在同一時(shí)間段內(nèi)按等間隔發(fā)車 以方便工人操作 7 假設(shè)車上載客人數(shù)小于 50 為空車 以 50 此刻車上人數(shù) 為缺載人數(shù) 總空車時(shí)間 E i 號車缺載人數(shù) 運(yùn)行時(shí)間 8 假設(shè)未搭上車的乘客為留乘乘客 總留乘時(shí)間 E 第 i 個車站留乘人數(shù) 留乘時(shí)間 9 高峰時(shí) t間F5min 非高峰時(shí) t間 6 13min 晨間和夜間 t間E7 15min 3 2 2 參數(shù)說明 t間 發(fā)車間隔 A 加權(quán)系數(shù) 3 2 3 模型求解 以下用模糊聚類法將一工作日數(shù)單位時(shí)間段 歸劃為更為概括的時(shí)段 第一步 確定各時(shí)間段的特征指標(biāo) Vij 它是時(shí)間段 Ti和Tj相應(yīng)各站的上車人數(shù)比 第二步 數(shù)據(jù)標(biāo)準(zhǔn)化處理 采用極差正規(guī)化公式 Uij Vij minVij max Vij minVij 第三步 標(biāo)定 采用夾角余弦公式 rij E 18 k 1uikuikE 18 k 1u 2 ikE 18 k 1u 2 ik其中rij表示各時(shí)間段之間的相似程度 第四步 分類 再由 rij來判別它們的類別 分類結(jié)果如下 5B00 6B00 6B00 9B00 9B00 16B00 16B 00 19B00 19B00 22B00 22B00 23B00經(jīng)計(jì)算 機(jī)仿真得出 5B00 6B00時(shí)間段系列數(shù)據(jù) 見表 1 從表 1 可以看出 空車時(shí)間及車公里數(shù)與 總留乘時(shí)間是相互矛盾的要求 即總空車時(shí)間 和車公里數(shù)減少了 總留乘時(shí)間必然增加 它們 分別代表了公交公司的利益和乘客的利益 此 時(shí)間主要考慮兩個方面 總留乘時(shí)間和車公里 數(shù) 為了計(jì)算方便 現(xiàn)使它們的量綱一致 即車 公里數(shù) 平均速度 使后者的單位成為時(shí)間的單 位 可歸為一個雙目標(biāo)規(guī)劃 表 1 用模糊聚類法得出的 5B00 6B00時(shí)間段系列數(shù)據(jù) 發(fā)車間隔 min 總空車時(shí)間 min 總留乘時(shí)間 min 車次行駛 路程數(shù) km 總車量數(shù) 7 8 9 10 11 12 13 14 15 11677 10282 9277 4 8642 2 8140 8 7166 7 6651 7 6327 1 6067 5 0 0 0 0 72 1 247 2 663 6 679 7 1156 3 263 234 204 3 204 3 175 1 175 1 146 146 146 13 12 10 9 8 8 7 7 6 R min f t間 f t間 表示總留乘時(shí)間與發(fā)車間隔 t間 的函數(shù) H min g t間 g t間 表示車總運(yùn)行時(shí)間與發(fā)車間隔 t間 的函數(shù) 而在實(shí)際調(diào)度中 調(diào)度者總是權(quán)衡總留乘時(shí)間和汽車總的 運(yùn)行時(shí)間 選擇一個令雙方都滿意的調(diào)度方案 稱為有效調(diào)度方 案 因此分別對目標(biāo)函數(shù) R 和H 賦予權(quán)重1 A和 A 0 AF1 將上式化為單目標(biāo)規(guī)劃模型 min W A R H 1 A 加權(quán)系數(shù) A稱為調(diào)度偏好系數(shù) A值由調(diào)度者自己決定 列舉 5B00 6B00 時(shí)間段內(nèi)的加權(quán)系數(shù) 由偏好系數(shù)加權(quán)法 可得 結(jié)果見表 2 表 2 5B00 6B00 時(shí)間段經(jīng)加權(quán)調(diào)整后的發(fā)車間隔 顧客 偏好系數(shù) 公交公司 偏好系數(shù) 發(fā)車間隔 min 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 13 13 13 11 11 11 11 11 9 16浙江萬里學(xué)院學(xué)報(bào)2002年 3月 為了顧及雙方的利益 取 A為 0 5 所以可得 5B00 6B00 的發(fā)車間隔為 11min 以后各個時(shí)間段都是用 這種方法進(jìn)行求解見表 3 并根據(jù)發(fā)車間隔可以制定出發(fā)車時(shí)間表 見表 4 表 3 各時(shí)間段的發(fā)車間隔 時(shí)間段 發(fā)車間隔 min 6B00 9B00 9B00 16B00 16B00 19B00 19B00 20B00 22B00 23B00 2 11 4 11 15 表 4 各時(shí)間段的調(diào)度方案 時(shí)間段 發(fā)車間隔 min 首發(fā)時(shí)間 本時(shí)段 所需車數(shù) 5B00 6B00 6B00 9B00 9B00 16B00 16B00 19B00 19B00 22B00 22B00 23B00 11 2 11 4 11 15 5B05 6B00 9B02 16B00 19B04 22B00 8 69 29 29 11 6 3 2 4 模型 1 的討論 從模型 1中可考查的是單位時(shí)間內(nèi)到達(dá)車站的人數(shù)是服從定長分布 在一般的現(xiàn)實(shí)生活中到達(dá)車站的 人數(shù)是服從泊松 Poisson 分布 下面對模型 1 進(jìn)行改進(jìn) 稱之為模型 2 3 3 模型 2 3 3 1 模型假設(shè) 1 單位時(shí)間內(nèi)乘客到達(dá)第 i 個車站的人數(shù)服從泊松 Poisson 分布 2 車上每位乘客在以后各站下車人數(shù) 服從泊松 Poisson 分布 3 其余假設(shè)和模型 1 相同 3 3 2 參數(shù)說明 zk 總空車時(shí)間 slt 總留乘時(shí)間 cl 車公里數(shù) A 加權(quán)系數(shù) 3 3 3 模型求解 用蒙特卡洛 Monte Carlo 法進(jìn)行仿真 Monte Carlo 法的基本思想是通過某種 試驗(yàn)0的方法 求出某一 隨機(jī)變量的平均值 并用此作為所求事件出現(xiàn)的概率或所討論隨機(jī)變量的期望值 第一步 變均勻分布為泊松分布 求出某一發(fā)車間隔 ti時(shí)的一組評價(jià)指標(biāo) zk1 slt1 cl1 第二步 多次求發(fā)車間隔為 ti時(shí)的評價(jià)指標(biāo) 求出平均 zk E zki i slt E slti i cl E cli i 表 5 用蒙特卡洛法仿真得出的 5B00 6B00 時(shí)間段的系列數(shù)據(jù) 發(fā)車間隔 min 總空車時(shí)間 min 總留乘時(shí)間 min 車次行駛 路程數(shù) km 總車量數(shù) 7 8 9 10 11 12 13 14 15 110717 12782 11516 9843 4 9457 7528 6 7362 6434 6131 87 1142 2290 1670 1 1900 4392 11140 16638 20708 263 234 204 3 204 3 175 1 175 1 146 146 146 14 12 11 9 9 8 7 7 7 第三步 求出各個發(fā)車間隔的 平均評價(jià)指標(biāo) 經(jīng)計(jì)算機(jī)仿真得出 5B00 6B 00 時(shí)間段系列數(shù)據(jù) 見表 5 主要考慮兩個方面 總留乘時(shí) 間和車公里數(shù) 為了計(jì)算方便 現(xiàn) 使它們的量綱一致 即車公里數(shù) 平均速度 使后者的單位成為時(shí)間 的單位 要使得顧客和公交公司雙 方都滿意 顯然這兩者之間是存在 矛盾的 可歸為一個雙目標(biāo)規(guī)劃 R min f t間 f t間 表示總留乘時(shí)間與發(fā)車間隔 x 的函數(shù) H min g t間 g t間 表示車總運(yùn)行時(shí)間與發(fā)車間隔 x 的函數(shù) 在實(shí)際調(diào)度中 調(diào)度者總是權(quán)衡總留乘時(shí)間和汽車總的運(yùn)行時(shí)間 選擇一個令雙方都滿意的調(diào)度方案 稱為有效調(diào)度方案 因此分別對目標(biāo)函數(shù) R 和 H 賦予權(quán)重 1 A和 A 0 AF1 將上式化為單目標(biāo)規(guī)劃 17 第 1 期何永強(qiáng) 黃 劍 陸新根 公交線路的車輛調(diào)度問題 模型 minW A R H 1 A 加權(quán)系數(shù) A稱為調(diào)度偏好系數(shù) A值由調(diào)度者自 己決定 列舉 5B00 6B00 時(shí)間段內(nèi)的加權(quán)系數(shù) 用偏好系 數(shù)加權(quán)法 可得結(jié)果見表 6 為了顧及雙方的利益 取 A為 0 5 所以可得5B00 6B00的發(fā)車間隔為 13min 以后各個時(shí)間段都是用 這種方法進(jìn)行求解見表 7 并根據(jù)發(fā)車間隔可以制定 出發(fā)車時(shí)間表 見表 8 表 6 5B00 6B00 時(shí)間段經(jīng)加權(quán)調(diào)整后的發(fā)車間隔 顧客 偏好系數(shù) 公交公司 偏好系數(shù) 發(fā)車間隔 min 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 13 13 13 13 13 13 13 13 13 表 7 各時(shí)間段的發(fā)車間隔 時(shí)間段發(fā)車間隔 min 6B00 9B00 9B00 16B00 16B00 19B00 19B00 22B00 22B00 23B00 3 13 2 7 15 表 8 各時(shí)間段的調(diào)度方案 時(shí)間段 發(fā)車間隔 min 首發(fā)時(shí)間 本時(shí)段 所需車數(shù) 5B00 6B00 6B00 9B00 9B00 16B00 16B00 19B00 19B00 22B00 22B00 23B00 13 3 13 2 7 15 5B08 6B00 9B04 16B00 19B05 22B00 7 35 21 75 23 6 參考文獻(xiàn) 1 葉其孝 大學(xué)生數(shù)學(xué)建模競賽輔導(dǎo)教材 一 二 三 四 M 1 長沙 湖南教育出版社 19991 2 盧開澄 單目標(biāo) 多目標(biāo)與整數(shù)規(guī)劃 M 1 北京 清華大學(xué)出版社 19991 3 周義倉 赫孝良 數(shù)學(xué)建模實(shí)驗(yàn) M 1 西安 西安交通大學(xué)出版社 19991 The Problem on Bus Route Dispatching 2001 Mathematical Contest in Modeling Problem B HE Yong qiang1 HUANG Jian2 LU Xin gen 1 Department of Engineering Technology of Zhejiang Wanli University Ningbo 315100 P R China 2 Department of Computer of Zhejiang Wanli University Ningbo 315100 P R China Abstract T he parameters of each interval were obtained by simulating on computer and turned into mult i objec tive planning in order to solve the problem The avaiable data were analyzed T he method of fuzzy assembling type was applied and one