遺傳算法在多類型的車輛人員排班系統(tǒng)中的應(yīng)用與研究

梁劍波+柴群

摘要：公交車輛人員排班的主要問題就是在給定時(shí)間點(diǎn)和車次數(shù)的情況下，以最小代價(jià)覆蓋所有的車次。與以往都是針對(duì)單類型車輛的人員排班不同，該文主要提供對(duì)多類型的車輛人員排班的支持。首先利用高效的Auction算法獲取代價(jià)最小的車次分組并根據(jù)分組情況分配車輛的營(yíng)運(yùn)類型；然后使用遺傳算法進(jìn)行隨機(jī)化搜索以獲得最優(yōu)解。實(shí)驗(yàn)表明， 遺傳算法應(yīng)用于多類型的公交車輛人員排班具有很好的效果。

關(guān)鍵詞：車輛人員排班；采樣編碼；Auction算法；遺傳算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8266-02

由于現(xiàn)代交通的快速發(fā)展需要，使得我們的應(yīng)用必須能夠處理多類型的車輛人員排班。為解決客戶和員工都能夠滿足管理的需要，我們對(duì)問題進(jìn)行了重定義并提出了一種新的分段式算法來求解多類型車輛人員排班問題，從而在生成計(jì)劃的同時(shí)考慮了現(xiàn)有營(yíng)運(yùn)管理模式的需要。車輛人員排班[1]作為城市運(yùn)輸領(lǐng)域一個(gè)經(jīng)典的NP-Hard問題受到國(guó)內(nèi)外大量專家學(xué)者的重視和研究。

1 公交車輛人員排班問題描述

行車計(jì)劃是組織線路運(yùn)營(yíng)的具體作業(yè)計(jì)劃，它將指導(dǎo)各個(gè)車組運(yùn)營(yíng)生產(chǎn)的全過程。它也為提高公共交通的整體服務(wù)水平提供了有力的依據(jù)。好的行車計(jì)劃將大大提高對(duì)乘客的服務(wù)質(zhì)量，使乘客對(duì)公共交通感到方便而且便捷。公交車輛人員排班的最終目的是生成一份行車計(jì)劃。行車計(jì)劃是線路始末站及重點(diǎn)中途站所有的行車時(shí)刻表，它規(guī)定了在該路運(yùn)營(yíng)的各個(gè)班次車輛每個(gè)周轉(zhuǎn)車次到達(dá)和離開該站的時(shí)間、行車間隔、及換班等。在給定車次、任務(wù)、車輛類型以及相應(yīng)約束的情況下，求解整體營(yíng)運(yùn)時(shí)間最小的多類型車輛人員的合理調(diào)度方案。

2 數(shù)學(xué)模型的建立與算法設(shè)計(jì)

由于我們要解決的是對(duì)多類型的車輛人員排班問題進(jìn)行研究，需要我們提出兩階級(jí)算法：第一階級(jí)通過使用改進(jìn)的auction算法[2]確定車輛調(diào)度類型，并保證目標(biāo)函數(shù)最?。坏诙A段根據(jù)第一階段分配好的車輛類型使用遺傳算法求解整個(gè)問題的近似最優(yōu)解，并通過集合分割技術(shù)來提高求解效率。在這里，有必要對(duì)研究的公交車輛人員排班中的一些問題進(jìn)行必要的簡(jiǎn)化和假設(shè)， 把實(shí)際的問題抽象為一個(gè)數(shù)學(xué)問題。

1） 車輛類型是指車輛的營(yíng)運(yùn)調(diào)度類型。公交調(diào)度形式有多種，我們的算法中僅考慮正班車調(diào)度和加班車調(diào)度兩種類型；

2） 沒有考慮燃油以及車輛損耗的代價(jià)；

3） 有一份合理的行車時(shí)刻表；

4） 高峰上線車輛數(shù)應(yīng)等于全部車輛總數(shù)。

2.1 定義變量

對(duì)于文中使用到的各個(gè)變量進(jìn)行定義：

1） TimeTable表示行車時(shí)刻表；

2） [Tintervalmax] 表示停站的最大間隔；

3） [Tintervalmin]表示停站的最小間隔；

4） [Ttwoheadmin]表示小兩頭最小間隔；

5） [Tsingle]表示單程行駛時(shí)間

6） [Cmax]表示員工的最大行駛車次數(shù)；

7） [NSingle_bus]表示單班車輛數(shù)；

8） [NDouble_bus]表示雙班車輛數(shù)；

9） [CSMaxIteration]表示算法的最大迭代次數(shù)；

10） SeedSize表示種群數(shù)量；

11） Exception表示客戶期望目標(biāo)值；

12） Cgroup表示分組數(shù)；

13） SeqNum表示車次數(shù)；

14） Cgmax表示最大分組數(shù)量。

2.2 建立數(shù)學(xué)模型

車輛人員排班已被抽象為多種模型，我們將要用到的是QUASI分配模型[3][4]。

QUASI分配模型：

3 試驗(yàn)結(jié)果及有效性分析

本實(shí)驗(yàn)的數(shù)據(jù)是廈門市公交總公司思明分公司某線路的客流數(shù)據(jù)。實(shí)驗(yàn)的基本參數(shù)：個(gè)人PC主頻雙核2.6G，內(nèi)存1G；系統(tǒng)Win2003，實(shí)現(xiàn)語言C#，運(yùn)行容器Asp.Net2.0、Net.Framework2.0。定義數(shù)學(xué)模型中的[α=80%]，[β=20%]。圖1展示了不同規(guī)模問題的求解時(shí)間。在我們的試驗(yàn)中出現(xiàn)過收斂速度過快的情形，所以我們引入了適應(yīng)度尺度變換，主要用的是線性尺度變換來控制遺傳算法的收斂速度，然而如果在全局都使用適應(yīng)度尺度變換就會(huì)導(dǎo)致收斂速度變慢，因此在我們的應(yīng)用中，只在前三分之一的迭代同期內(nèi)使用尺度變換。從而很好的協(xié)調(diào)了群體多樣性與求解效率之間的矛盾。如圖2。

4 總結(jié)

本文對(duì)公交車輛人員排班進(jìn)行了研究。通過合理結(jié)合地域的管理模式，提出了使用Auction算法、DAuction算法以及遺傳算法混合求解多類型車輛人員排班的兩階段算法。通過巧妙的利用約束將Auction算法引入人員排班，大大提高了求解效率.而且使用采樣編碼降低了編碼的復(fù)雜性和轉(zhuǎn)換的效率，減少了存儲(chǔ)空間的使用，也降低了生成初始種群的難度，并且有效的分割了求解空間，提高了搜索效率。

參考文獻(xiàn)：

[1] 北京市公共交通總公司北方交通大學(xué).“城市公共交通運(yùn)營(yíng)調(diào)度管理”[M].北京：中國(guó)鐵道出版社，2001.

[2] Bertsekas D P. Auction Algorithms[D].Laboratory for Information and Decision Systems Massachusetts Institute of Technology Cambridge， MA 02139， USA， 1998.

[3] Richard Freling.Models and Algorithms for Vehicle Scheduling[J].2001.

[4] Huisman D，F(xiàn)reling R，Wagelmans A P M. Multiple-depot integrated vehicle and crew scheduling[R].Tech. report， Econometric Institute， Erasmus University Rotterdam， 2003.

[5] Jingquan Li ，Parallel. Auction Algorithm for Bus Rescheduling[J]. Journal of Scheduling，2003.

[6] 王鵬飛.智能公交之車輛人員排班算法的研究與應(yīng)用[D].濟(jì)南：山東大學(xué)，2006.

[7] 周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2001.

[8] Sebastiaan W. de Grootl， Dennis Huisman. Vehicle and Crew Scheduling： Solving Large Real-World Instances with an Integrated Approach[R].Econometric Institute Report，EI2004-13.endprint

摘要：公交車輛人員排班的主要問題就是在給定時(shí)間點(diǎn)和車次數(shù)的情況下，以最小代價(jià)覆蓋所有的車次。與以往都是針對(duì)單類型車輛的人員排班不同，該文主要提供對(duì)多類型的車輛人員排班的支持。首先利用高效的Auction算法獲取代價(jià)最小的車次分組并根據(jù)分組情況分配車輛的營(yíng)運(yùn)類型；然后使用遺傳算法進(jìn)行隨機(jī)化搜索以獲得最優(yōu)解。實(shí)驗(yàn)表明， 遺傳算法應(yīng)用于多類型的公交車輛人員排班具有很好的效果。

關(guān)鍵詞：車輛人員排班；采樣編碼；Auction算法；遺傳算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8266-02

由于現(xiàn)代交通的快速發(fā)展需要，使得我們的應(yīng)用必須能夠處理多類型的車輛人員排班。為解決客戶和員工都能夠滿足管理的需要，我們對(duì)問題進(jìn)行了重定義并提出了一種新的分段式算法來求解多類型車輛人員排班問題，從而在生成計(jì)劃的同時(shí)考慮了現(xiàn)有營(yíng)運(yùn)管理模式的需要。車輛人員排班[1]作為城市運(yùn)輸領(lǐng)域一個(gè)經(jīng)典的NP-Hard問題受到國(guó)內(nèi)外大量專家學(xué)者的重視和研究。

1 公交車輛人員排班問題描述

行車計(jì)劃是組織線路運(yùn)營(yíng)的具體作業(yè)計(jì)劃，它將指導(dǎo)各個(gè)車組運(yùn)營(yíng)生產(chǎn)的全過程。它也為提高公共交通的整體服務(wù)水平提供了有力的依據(jù)。好的行車計(jì)劃將大大提高對(duì)乘客的服務(wù)質(zhì)量，使乘客對(duì)公共交通感到方便而且便捷。公交車輛人員排班的最終目的是生成一份行車計(jì)劃。行車計(jì)劃是線路始末站及重點(diǎn)中途站所有的行車時(shí)刻表，它規(guī)定了在該路運(yùn)營(yíng)的各個(gè)班次車輛每個(gè)周轉(zhuǎn)車次到達(dá)和離開該站的時(shí)間、行車間隔、及換班等。在給定車次、任務(wù)、車輛類型以及相應(yīng)約束的情況下，求解整體營(yíng)運(yùn)時(shí)間最小的多類型車輛人員的合理調(diào)度方案。

2 數(shù)學(xué)模型的建立與算法設(shè)計(jì)

由于我們要解決的是對(duì)多類型的車輛人員排班問題進(jìn)行研究，需要我們提出兩階級(jí)算法：第一階級(jí)通過使用改進(jìn)的auction算法[2]確定車輛調(diào)度類型，并保證目標(biāo)函數(shù)最?。坏诙A段根據(jù)第一階段分配好的車輛類型使用遺傳算法求解整個(gè)問題的近似最優(yōu)解，并通過集合分割技術(shù)來提高求解效率。在這里，有必要對(duì)研究的公交車輛人員排班中的一些問題進(jìn)行必要的簡(jiǎn)化和假設(shè)， 把實(shí)際的問題抽象為一個(gè)數(shù)學(xué)問題。

1） 車輛類型是指車輛的營(yíng)運(yùn)調(diào)度類型。公交調(diào)度形式有多種，我們的算法中僅考慮正班車調(diào)度和加班車調(diào)度兩種類型；

2） 沒有考慮燃油以及車輛損耗的代價(jià)；

3） 有一份合理的行車時(shí)刻表；

4） 高峰上線車輛數(shù)應(yīng)等于全部車輛總數(shù)。

2.1 定義變量

對(duì)于文中使用到的各個(gè)變量進(jìn)行定義：

1） TimeTable表示行車時(shí)刻表；

2） [Tintervalmax] 表示停站的最大間隔；

3） [Tintervalmin]表示停站的最小間隔；

4） [Ttwoheadmin]表示小兩頭最小間隔；

5） [Tsingle]表示單程行駛時(shí)間

6） [Cmax]表示員工的最大行駛車次數(shù)；

7） [NSingle_bus]表示單班車輛數(shù)；

8） [NDouble_bus]表示雙班車輛數(shù)；

9） [CSMaxIteration]表示算法的最大迭代次數(shù)；

10） SeedSize表示種群數(shù)量；

11） Exception表示客戶期望目標(biāo)值；

12） Cgroup表示分組數(shù)；

13） SeqNum表示車次數(shù)；

14） Cgmax表示最大分組數(shù)量。

2.2 建立數(shù)學(xué)模型

車輛人員排班已被抽象為多種模型，我們將要用到的是QUASI分配模型[3][4]。

QUASI分配模型：

3 試驗(yàn)結(jié)果及有效性分析

本實(shí)驗(yàn)的數(shù)據(jù)是廈門市公交總公司思明分公司某線路的客流數(shù)據(jù)。實(shí)驗(yàn)的基本參數(shù)：個(gè)人PC主頻雙核2.6G，內(nèi)存1G；系統(tǒng)Win2003，實(shí)現(xiàn)語言C#，運(yùn)行容器Asp.Net2.0、Net.Framework2.0。定義數(shù)學(xué)模型中的[α=80%]，[β=20%]。圖1展示了不同規(guī)模問題的求解時(shí)間。在我們的試驗(yàn)中出現(xiàn)過收斂速度過快的情形，所以我們引入了適應(yīng)度尺度變換，主要用的是線性尺度變換來控制遺傳算法的收斂速度，然而如果在全局都使用適應(yīng)度尺度變換就會(huì)導(dǎo)致收斂速度變慢，因此在我們的應(yīng)用中，只在前三分之一的迭代同期內(nèi)使用尺度變換。從而很好的協(xié)調(diào)了群體多樣性與求解效率之間的矛盾。如圖2。

4 總結(jié)

本文對(duì)公交車輛人員排班進(jìn)行了研究。通過合理結(jié)合地域的管理模式，提出了使用Auction算法、DAuction算法以及遺傳算法混合求解多類型車輛人員排班的兩階段算法。通過巧妙的利用約束將Auction算法引入人員排班，大大提高了求解效率.而且使用采樣編碼降低了編碼的復(fù)雜性和轉(zhuǎn)換的效率，減少了存儲(chǔ)空間的使用，也降低了生成初始種群的難度，并且有效的分割了求解空間，提高了搜索效率。

參考文獻(xiàn)：

[1] 北京市公共交通總公司北方交通大學(xué).“城市公共交通運(yùn)營(yíng)調(diào)度管理”[M].北京：中國(guó)鐵道出版社，2001.

[2] Bertsekas D P. Auction Algorithms[D].Laboratory for Information and Decision Systems Massachusetts Institute of Technology Cambridge， MA 02139， USA， 1998.

[3] Richard Freling.Models and Algorithms for Vehicle Scheduling[J].2001.

[4] Huisman D，F(xiàn)reling R，Wagelmans A P M. Multiple-depot integrated vehicle and crew scheduling[R].Tech. report， Econometric Institute， Erasmus University Rotterdam， 2003.

[5] Jingquan Li ，Parallel. Auction Algorithm for Bus Rescheduling[J]. Journal of Scheduling，2003.

[6] 王鵬飛.智能公交之車輛人員排班算法的研究與應(yīng)用[D].濟(jì)南：山東大學(xué)，2006.

[7] 周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2001.

[8] Sebastiaan W. de Grootl， Dennis Huisman. Vehicle and Crew Scheduling： Solving Large Real-World Instances with an Integrated Approach[R].Econometric Institute Report，EI2004-13.endprint

摘要：公交車輛人員排班的主要問題就是在給定時(shí)間點(diǎn)和車次數(shù)的情況下，以最小代價(jià)覆蓋所有的車次。與以往都是針對(duì)單類型車輛的人員排班不同，該文主要提供對(duì)多類型的車輛人員排班的支持。首先利用高效的Auction算法獲取代價(jià)最小的車次分組并根據(jù)分組情況分配車輛的營(yíng)運(yùn)類型；然后使用遺傳算法進(jìn)行隨機(jī)化搜索以獲得最優(yōu)解。實(shí)驗(yàn)表明， 遺傳算法應(yīng)用于多類型的公交車輛人員排班具有很好的效果。

關(guān)鍵詞：車輛人員排班；采樣編碼；Auction算法；遺傳算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8266-02

由于現(xiàn)代交通的快速發(fā)展需要，使得我們的應(yīng)用必須能夠處理多類型的車輛人員排班。為解決客戶和員工都能夠滿足管理的需要，我們對(duì)問題進(jìn)行了重定義并提出了一種新的分段式算法來求解多類型車輛人員排班問題，從而在生成計(jì)劃的同時(shí)考慮了現(xiàn)有營(yíng)運(yùn)管理模式的需要。車輛人員排班[1]作為城市運(yùn)輸領(lǐng)域一個(gè)經(jīng)典的NP-Hard問題受到國(guó)內(nèi)外大量專家學(xué)者的重視和研究。

1 公交車輛人員排班問題描述

行車計(jì)劃是組織線路運(yùn)營(yíng)的具體作業(yè)計(jì)劃，它將指導(dǎo)各個(gè)車組運(yùn)營(yíng)生產(chǎn)的全過程。它也為提高公共交通的整體服務(wù)水平提供了有力的依據(jù)。好的行車計(jì)劃將大大提高對(duì)乘客的服務(wù)質(zhì)量，使乘客對(duì)公共交通感到方便而且便捷。公交車輛人員排班的最終目的是生成一份行車計(jì)劃。行車計(jì)劃是線路始末站及重點(diǎn)中途站所有的行車時(shí)刻表，它規(guī)定了在該路運(yùn)營(yíng)的各個(gè)班次車輛每個(gè)周轉(zhuǎn)車次到達(dá)和離開該站的時(shí)間、行車間隔、及換班等。在給定車次、任務(wù)、車輛類型以及相應(yīng)約束的情況下，求解整體營(yíng)運(yùn)時(shí)間最小的多類型車輛人員的合理調(diào)度方案。

2 數(shù)學(xué)模型的建立與算法設(shè)計(jì)

由于我們要解決的是對(duì)多類型的車輛人員排班問題進(jìn)行研究，需要我們提出兩階級(jí)算法：第一階級(jí)通過使用改進(jìn)的auction算法[2]確定車輛調(diào)度類型，并保證目標(biāo)函數(shù)最小；第二階段根據(jù)第一階段分配好的車輛類型使用遺傳算法求解整個(gè)問題的近似最優(yōu)解，并通過集合分割技術(shù)來提高求解效率。在這里，有必要對(duì)研究的公交車輛人員排班中的一些問題進(jìn)行必要的簡(jiǎn)化和假設(shè)， 把實(shí)際的問題抽象為一個(gè)數(shù)學(xué)問題。

1） 車輛類型是指車輛的營(yíng)運(yùn)調(diào)度類型。公交調(diào)度形式有多種，我們的算法中僅考慮正班車調(diào)度和加班車調(diào)度兩種類型；

2） 沒有考慮燃油以及車輛損耗的代價(jià)；

3） 有一份合理的行車時(shí)刻表；

4） 高峰上線車輛數(shù)應(yīng)等于全部車輛總數(shù)。

2.1 定義變量

對(duì)于文中使用到的各個(gè)變量進(jìn)行定義：

1） TimeTable表示行車時(shí)刻表；

2） [Tintervalmax] 表示停站的最大間隔；

3） [Tintervalmin]表示停站的最小間隔；

4） [Ttwoheadmin]表示小兩頭最小間隔；

5） [Tsingle]表示單程行駛時(shí)間

6） [Cmax]表示員工的最大行駛車次數(shù)；

7） [NSingle_bus]表示單班車輛數(shù)；

8） [NDouble_bus]表示雙班車輛數(shù)；

9） [CSMaxIteration]表示算法的最大迭代次數(shù)；

10） SeedSize表示種群數(shù)量；

11） Exception表示客戶期望目標(biāo)值；

12） Cgroup表示分組數(shù)；

13） SeqNum表示車次數(shù)；

14） Cgmax表示最大分組數(shù)量。

2.2 建立數(shù)學(xué)模型

車輛人員排班已被抽象為多種模型，我們將要用到的是QUASI分配模型[3][4]。

QUASI分配模型：

3 試驗(yàn)結(jié)果及有效性分析

本實(shí)驗(yàn)的數(shù)據(jù)是廈門市公交總公司思明分公司某線路的客流數(shù)據(jù)。實(shí)驗(yàn)的基本參數(shù)：個(gè)人PC主頻雙核2.6G，內(nèi)存1G；系統(tǒng)Win2003，實(shí)現(xiàn)語言C#，運(yùn)行容器Asp.Net2.0、Net.Framework2.0。定義數(shù)學(xué)模型中的[α=80%]，[β=20%]。圖1展示了不同規(guī)模問題的求解時(shí)間。在我們的試驗(yàn)中出現(xiàn)過收斂速度過快的情形，所以我們引入了適應(yīng)度尺度變換，主要用的是線性尺度變換來控制遺傳算法的收斂速度，然而如果在全局都使用適應(yīng)度尺度變換就會(huì)導(dǎo)致收斂速度變慢，因此在我們的應(yīng)用中，只在前三分之一的迭代同期內(nèi)使用尺度變換。從而很好的協(xié)調(diào)了群體多樣性與求解效率之間的矛盾。如圖2。

4 總結(jié)

本文對(duì)公交車輛人員排班進(jìn)行了研究。通過合理結(jié)合地域的管理模式，提出了使用Auction算法、DAuction算法以及遺傳算法混合求解多類型車輛人員排班的兩階段算法。通過巧妙的利用約束將Auction算法引入人員排班，大大提高了求解效率.而且使用采樣編碼降低了編碼的復(fù)雜性和轉(zhuǎn)換的效率，減少了存儲(chǔ)空間的使用，也降低了生成初始種群的難度，并且有效的分割了求解空間，提高了搜索效率。

參考文獻(xiàn)：

[1] 北京市公共交通總公司北方交通大學(xué).“城市公共交通運(yùn)營(yíng)調(diào)度管理”[M].北京：中國(guó)鐵道出版社，2001.

[2] Bertsekas D P. Auction Algorithms[D].Laboratory for Information and Decision Systems Massachusetts Institute of Technology Cambridge， MA 02139， USA， 1998.

[3] Richard Freling.Models and Algorithms for Vehicle Scheduling[J].2001.

[4] Huisman D，F(xiàn)reling R，Wagelmans A P M. Multiple-depot integrated vehicle and crew scheduling[R].Tech. report， Econometric Institute， Erasmus University Rotterdam， 2003.

[5] Jingquan Li ，Parallel. Auction Algorithm for Bus Rescheduling[J]. Journal of Scheduling，2003.

[6] 王鵬飛.智能公交之車輛人員排班算法的研究與應(yīng)用[D].濟(jì)南：山東大學(xué)，2006.

[7] 周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2001.

[8] Sebastiaan W. de Grootl， Dennis Huisman. Vehicle and Crew Scheduling： Solving Large Real-World Instances with an Integrated Approach[R].Econometric Institute Report，EI2004-13.endprint