基于生成與選擇模式的公交駕駛員排班問題研究.pdf

1、本文主要研究了公交駕駛員排班問題，公交駕駛員排班問題是指構(gòu)建合法班次集合滿足行車計(jì)劃的要求。求解目標(biāo)是使班次數(shù)目和班次成本最低。本文基于“生成和選擇”的模式對駕駛員排班問題進(jìn)行求解。
　　第一階段:生成候選潛在合法班次集合
　　生成階段主要是采用啟發(fā)式算法，根據(jù)約束條件生成一個(gè)大的候選班次集合。首先，根據(jù)集合覆蓋模型的特點(diǎn)，集合覆蓋模型中的變量對應(yīng)于計(jì)劃中班次，約束條件對應(yīng)工作段。通常，工作段的數(shù)量是非常大的，一方面，大量的

2、工作段會增加生成合法班次的數(shù)量，在實(shí)際的排班計(jì)劃中，不可能生成所有的合法班次;另一方面，過多的工作段會增加約束條件的數(shù)量。本文運(yùn)用基于時(shí)間標(biāo)記法的啟發(fā)式算法減少了參與生成班次的工作段數(shù)量。其次，在對潛在班次分析的基礎(chǔ)上，運(yùn)用樹枚舉算法的思想，生成潛在班次集合。
　　第二階段:班次集合的選擇階段
　　這一部分設(shè)計(jì)了三種不同的遺傳算法，在大量的潛在班次中選擇一個(gè)接近最優(yōu)的解或者最優(yōu)解。運(yùn)用不同的初始化，交叉和變異策略，三種遺傳算