梁劍波+柴群

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

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

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2014）34-8266-02

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

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

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

2 數學模型的建立與算法設計

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

1） 車輛類型是指車輛的營運調度類型。公交調度形式有多種，我們的算法中僅考慮正班車調度和加班車調度兩種類型；

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

3） 有一份合理的行車時刻表；

4） 高峰上線車輛數應等于全部車輛總數。

2.1 定義變量

對于文中使用到的各個變量進行定義：

1） TimeTable表示行車時刻表；

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

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

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

5） [Tsingle]表示單程行駛時間

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

7） [NSingle_bus]表示單班車輛數；

8） [NDouble_bus]表示雙班車輛數；

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

10） SeedSize表示種群數量；

11） Exception表示客戶期望目標值；

12） Cgroup表示分組數；

13） SeqNum表示車次數；

14） Cgmax表示最大分組數量。

2.2 建立數學模型

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

QUASI分配模型：

3 試驗結果及有效性分析

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

4 總結

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

參考文獻：

[1] 北京市公共交通總公司北方交通大學.“城市公共交通運營調度管理”[M].北京：中國鐵道出版社，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，Freling 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] 王鵬飛.智能公交之車輛人員排班算法的研究與應用[D].濟南：山東大學，2006.

[7] 周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業(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

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

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

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2014）34-8266-02

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

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

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

2 數學模型的建立與算法設計

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

1） 車輛類型是指車輛的營運調度類型。公交調度形式有多種，我們的算法中僅考慮正班車調度和加班車調度兩種類型；

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

3） 有一份合理的行車時刻表；

4） 高峰上線車輛數應等于全部車輛總數。

2.1 定義變量

對于文中使用到的各個變量進行定義：

1） TimeTable表示行車時刻表；

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

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

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

5） [Tsingle]表示單程行駛時間

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

7） [NSingle_bus]表示單班車輛數；

8） [NDouble_bus]表示雙班車輛數；

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

10） SeedSize表示種群數量；

11） Exception表示客戶期望目標值；

12） Cgroup表示分組數；

13） SeqNum表示車次數；

14） Cgmax表示最大分組數量。

2.2 建立數學模型

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

QUASI分配模型：

3 試驗結果及有效性分析

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

4 總結

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

參考文獻：

[1] 北京市公共交通總公司北方交通大學.“城市公共交通運營調度管理”[M].北京：中國鐵道出版社，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，Freling 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] 王鵬飛.智能公交之車輛人員排班算法的研究與應用[D].濟南：山東大學，2006.

[7] 周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業(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

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

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

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2014）34-8266-02

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

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

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

2 數學模型的建立與算法設計

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

1） 車輛類型是指車輛的營運調度類型。公交調度形式有多種，我們的算法中僅考慮正班車調度和加班車調度兩種類型；

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

3） 有一份合理的行車時刻表；

4） 高峰上線車輛數應等于全部車輛總數。

2.1 定義變量

對于文中使用到的各個變量進行定義：

1） TimeTable表示行車時刻表；

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

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

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

5） [Tsingle]表示單程行駛時間

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

7） [NSingle_bus]表示單班車輛數；

8） [NDouble_bus]表示雙班車輛數；

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

10） SeedSize表示種群數量；

11） Exception表示客戶期望目標值；

12） Cgroup表示分組數；

13） SeqNum表示車次數；

14） Cgmax表示最大分組數量。

2.2 建立數學模型

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

QUASI分配模型：

3 試驗結果及有效性分析

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

4 總結

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

參考文獻：

[1] 北京市公共交通總公司北方交通大學.“城市公共交通運營調度管理”[M].北京：中國鐵道出版社，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，Freling 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] 王鵬飛.智能公交之車輛人員排班算法的研究與應用[D].濟南：山東大學，2006.

[7] 周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業(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