[發明專利]一種公交車輛調度方法

無效

• 申請號: 201110451000.X
• 申請日: 2011-12-29
• 公開（公告）號: CN102542791A
• 公開（公告）日: 2012-07-04
• 發明（設計）人: 左興權;水新國;張天樂;陳程;仇晨曄
• 申請（專利權）人: 北京郵電大學
• 主分類號: G08G1/00
• 分類號: G08G1/00
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 謝安昆;宋志強

技術領域

本發明涉及交通領域的車輛調度技術，尤其涉及一種公交車輛調度方法。

背景技術

車輛調度問題(vehicle?scheduling?problem，VSP)是運輸調度(transport?scheduling)中的一個重要領域。根據涉及的約束限制，VSP歸納起來大致可以分為里程約束、車型約束、滿載約束、非滿載約束和時間窗約束五類。車輛調度問題具有非常廣泛的實際應用場景，但由于實際場景的復雜性，車輛調度問題根據不同的應用場景分為很多種具體的問題。

針對時間窗約束的VSP，即發車時刻點確定情況下的車輛調度問題，目前在進行車輛調度處理時主要有兩種方式，一種是手工調度，一種是用車輛調度系統調度。

手工調度需要消耗很多的人力，從而導致極大的運營成本、且效率低下。

而現存的車輛調度系統所采用的車輛調度方案主要分為兩種，第一種是順序方式，即先解決車輛調度問題再解決人員調度問題，也就是說，在解決車輛調度問題時沒有考慮人員調度的因素，第二種是整合方式，即同時進行車輛和人員調度。

順序方式在解決車輛調度問題時沒有考慮人的因素，比如司機的休息時間、用餐時間等，從而使得車輛調度最優化可能會限制之后的人員調度，甚至都無法產生有效的人員調度解決方案，實用性比較低。

整合方式在解決車輛調度問題的同時也試圖解決人員調度問題，這樣在建立解決方案模型時，變量數目會增大很多，因而解決起來難度很大，生成車輛調度方案的效率太低，比如，Freling等人提出的算法解決一條線路的車輛調度問題需要86分鐘，最快的也需要40分鐘左右，在實際應用中，常常會遇到由于各種臨時出現的問題而需重新生成車輛調度方案的情況，比如，部分車輛出現故障，此時，需要馬上重新生成新的車輛調度方案，若生成車輛調度方案的時間太長，無疑會影響所有車輛的正常運行，從而使得這種方式的實用性受到限制。

綜上所述，現有技術的公交車輛調度方案在解決車輛調度問題時，普遍存在實用性較低、且生成效率低下的問題。

發明內容

有鑒于此，本發明提出一種公交車輛調度方法，可提高車輛調度方案的實用性和生成效率。

為達到上述目的，本發明實施例的技術方案是這樣實現的：

一種公交車輛調度方法，其特征在于，包括以下步驟：

S1、根據一初始發車時刻點、需要的發車時刻表、司機休息時間、最大等待時間和最長工作時間，為一車輛確定包含至少一個發車時刻點的可用發車時間范圍；

S2、在所述可用發車時間范圍內分別任意選擇一屬于發車時刻表的發車時刻點，將選擇的發車時刻點作為元素，生成所述初始發車時刻點對應車輛的一發車時刻點序列block；

返回執行步驟S2，直至選擇完所有可用發車時間范圍內、且屬于發車時刻表的發車時刻點，生成由發車時刻點序列block構成的集合；

S3、返回執行步驟S1，為每個初始發車時刻點生成其對應車輛的發車時刻點序列block的集合；

S4、生成N條有限的以位為長度的染色體，所述染色體的每一位對應于一初始發車時刻點；

對所述N條染色體進行初始化，得到N條初始化后的染色體；所述初始化后的每條染色體中一初始發車時刻點唯一地對應一發車時刻點序列block；

S5、將當前的N條染色體作為第一N條染色體進行交叉處理，對交叉后的N條染色體進行變異處理，對變異后的N條染色體和所述第一N條染色體進行選擇處理，得到選擇處理后的N條新染色體，作為步驟S5的當前N條染色體；

S6、重復執行步驟S5直至達到預定的次數，得到最優染色體；

S7、對所述最優染色體按覆蓋次數進行調整，使得未覆蓋以及重復覆蓋的發車時刻點減少；根據調整后每個初始發車時刻點及其對應的發車時刻點序列block對車輛進行調度。

本發明的有益效果為，通過采用遺傳算法，得到較佳公交車輛調度方案，再對所述公交車輛調度方案進行調整，得到滿足實際需要的公交車輛調度方案，同時，在遺傳算法的設計中考慮了司機休息時間、最大等待時間等，使得本發明方案在實施時更加具備可行性，提高了公交車輛調度方案的實用性。而且，采用本發明方案，可極大地提高公交車輛調度方案的生成效率。

附圖說明

圖1為本發明實施例的方法流程圖；

圖2為本發明實施例的初始發車時刻點發出的block遍歷過程示意圖；

圖3為本發明實施例的初始發車時刻點發出的block集合示意圖；