公交駕駛員排班與輪班問題的模型與算法研究.pdf

1、公交駕駛員調(diào)度問題包含駛員排班與駕駛員輪班兩個(gè)子問題。駕駛員排班與駕駛員輪班問題是公交運(yùn)營中最耗時(shí)和最繁重的任務(wù)，因?yàn)榘嘈偷纳沙３０鞣N各樣的約束，并且不同的公交企業(yè)擁有不同的約束規(guī)則。更為重要的是從公交企業(yè)自身角度來看，公交駕駛員排班與輪班所占據(jù)的預(yù)算支出是最大的。因此，對這兩個(gè)問題進(jìn)行研究非常有必要。
　　論文對北京市的公交駕駛員排班與輪班問題進(jìn)行研究，主要研究問題相應(yīng)的數(shù)學(xué)模型和求解算法。論文的主要工作總結(jié)如下:

2、　　(a)第一部分:公交駕駛員排班問題公交駕駛員排班問題是指為駕駛員生成和選擇一組可行的班型來覆蓋掉所有的車次鏈，其目標(biāo)是極小化總的班次數(shù)。本研究在集劃分與集覆蓋問題的基礎(chǔ)上建立了針對北京市的公交駕駛員排班問題的數(shù)學(xué)模型。
　　考慮到其特殊的約束和目標(biāo)，設(shè)計(jì)了三種求解方法。首先是一個(gè)非常簡單、快捷的貪婪方法;其次，使用一個(gè)樹枚舉算法來快速枚舉出所有的有效班型，將集劃分與集覆蓋問題折減至可操作的規(guī)模;最后，分別采用基于貪婪算法與拉格

3、朗日松弛的啟發(fā)式方法求解折減后的集劃分與集覆蓋問題。
　　用來自北京公交集團(tuán)的數(shù)據(jù)驗(yàn)證了算法的有效性，計(jì)算結(jié)果表明貪婪方法和基于拉格朗日松弛的啟發(fā)式方法能在合理的時(shí)間內(nèi)獲得較好的解，可以進(jìn)一步應(yīng)用于更大規(guī)模的公交駕駛員排班問題。
　　(b)第二部分:公交駕駛員輪班問題論文研究了公交駕駛員均衡輪班問題。該問題是指為公交駕駛員尋找一個(gè)最優(yōu)的班次指派，使得總的工作班時(shí)平均分配給每一個(gè)駕駛員。
　　首先，構(gòu)建了該問題等價(jià)的多層