遺傳算法在多類型的車輛人員排班系統中的應用與研究

梁劍波+柴群

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

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

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

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

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

行車計劃是組織線路運營的具體作業計劃，它將指導各個車組運營生產的全過程。它也為提高公共交通的整體服務水平提供了有力的依據。好的行車計劃將大大提高對乘客的服務質量，使乘客對公共交通感到方便而且便捷。公交車輛人員排班的最終目的是生成一份行車計劃。行車計劃是線路始末站及重點中途站所有的行車時刻表，它規定了在該路運營的各個班次車輛每個周轉車次到達和離開該站的時間、行車間隔、及換班等。……