[發明專利]一種基于人車綁定模式的車輛排班算法

在審

• 申請號: 201810737569.4
• 申請日: 2018-07-06
• 公開（公告）號: CN108960634A
• 公開（公告）日: 2018-12-07
• 發明（設計）人: 郭建國;龍衛東;閻磊;雷炳友;田影;沈洋;靳冬冬
• 申請（專利權）人: 鄭州天邁科技股份有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 鄭州德勤知識產權代理有限公司 41128
• 代理人: 黃紅梅;黃軍委

本發明提供一種基于人車綁定模式的車輛排班算法，(1)構造車輛調度模型并求解，獲得一個車輛調度方案；(2)將車輛調度方案作為司機排班問題初始解，迭代進行局部搜索改進；(3)在局部搜索過程中，引入破壞重建方法對當前解進行擾動。(4)迭代執行步驟(2)到(3)N_iter次，N_iter為局部搜索迭代次數；(5)迭代執行步驟(1)到(3)M_start次，M_start為算法多啟動次數；(6)改進步驟(2)獲得的可行班次鏈，建立SCP模型，獲得更優的班次鏈組合。本發明通過采用迭代局部搜索算法，并在局部搜索過程中，引入破壞重建方法對當前解進行擾動。解決了傳統算中存在的駕駛員勞動效率較低、駕駛員成本較高、駕駛員任務不均衡、可能車輛數增加的問題。

技術領域

本發明涉及一種車輛排班算法，具體的說，涉及了一種基于人車綁定模式的車輛排班算法。

背景技術

公共交通是公眾出行的一種重要的交通方式，也是解決城市交通擁擠問題的重要手段。在公共交通運行體系中，車輛排班是其重要的問題，如何有效地解決這個問題，對公交公司的運營效益和服務質量至關重要。

針對公交調度問題，國內外學者對公交排班問題進行了研究，目前已有一些公交排班問題的研究成果。解決車輛排班問題的方法可分為兩種，即最優化方法和啟發式算法。最優化方法采用傳統的最優化模型如線性規劃模型，并采用列生成技術、分支定界法等算法，優點是得到的調度方案是最優的，缺點是算法運行時間過長，難以應用于規模比較大的實際問題。啟發式算法是根據經驗或者直觀構造的算法，計算復雜性下，能獲得問題的次優解，常見的啟發式算法有禁忌搜索算法、遺傳算法、拉格朗日松弛算法等。

國外針對此類問題的研究相對比較成熟，針對此類問題，一般將問題分為車輛調度和司機排班兩個子問題分階段求解，先基于線路時刻表完成車輛調度，再進行司機任務分配，最后編制司機輪班作業計劃；或者同時考慮調度和司機排班，力求獲得更優的公交作業方案。然而，國外現有的解決方案和算法難以適應于我國的車輛調度和司機排班問題，其原因在于：國外公交企業中司機和車輛關系不固定，一個司機在一天內可駕駛多個車輛；而國內的公交企業通常采用“人車綁定”模式，即一個司機在同一個工作日內駕駛同一車輛。然而，在國內針對此類問題的解決也均采用優化算法，并得到比人工排班具有一定的優化，但是也有一些不足，即采用的此類算法不具有通用性，并未兼顧車輛赫斯基的成本，不能夠反映實際應用的需求；同時目前國內的車輛排班基本上都是根據經驗對其進行排班，不具有科學性，并致使駕駛員勞動效率較低，駕駛員成本較高，駕駛員任務不均衡，可能車輛數增加。

發明內容

本發明的目的是針對現有技術的不足，從而提供了一種設計科學，算法運行時間短的基于人車綁定模式的車輛排班算法。

公交車輛調度和司機排班問題

令集合D＝{d₁,d₂,...,d_m}表示m個停車場，S＝{s₁,s₂,...,s_p}表示p個公交起點或終點車站，某些站點可提供司機就餐、車輛充電等服務。令集合V＝{v₁,v₂,...,v_n}表示一條公交線路上的n個班次任務，任務v_i具有線路編號、行車方向、起始站點、終點站點、發車時間、結束時間、運行時間等屬性。

公交車輛調度與司機排班問題是安排車輛和司機完成公交線路時刻表規定的班次任務，在滿足車輛司機管理規定的前提下最小化公交運行成本。第一，集合V中的每一個班次任務必須由某輛車和某個司機完成；第二，為車輛提供檢修、加油、充電或換電池等所需的時間；第三，必須為司機提供充足的休息時間和就餐時間；第四，盡可能少地使用車輛，減少車輛固定成本和運行成本；同時，盡可能減少所需司機數量和司機工作時間，從而降低司機相關的支出。