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

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

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