[發明專利]一種基于分割組合優化的公交駕駛員智能排班方法

有效

• 申請號: 202011086792.0
• 申請日: 2020-10-12
• 公開（公告）號: CN112241871B
• 公開（公告）日: 2022-04-22
• 發明（設計）人: 任子暉;高洪昌;王曉娟;張超;趙玉坤;曹培宋;劉思琦;倪金林;潘宇;閆其筠
• 申請（專利權）人: 安徽交欣科技股份有限公司
• 主分類號: G06Q10/10
• 分類號: G06Q10/10;G06Q10/06;G06Q10/04;G06Q50/26;G06F17/10;G08G1/123
• 代理公司: 北京德崇智捷知識產權代理有限公司 11467
• 代理人: 賀征華

1.一種基于分割組合優化的公交駕駛員智能排班方法，其特征在于，包括以下步驟：

步驟一：通過數據采集模塊采集線路基礎數據集、客流數據集、營運數據集；

步驟二：通過行車計劃編制模型模塊根據歷史營運及客流數據分析、預測線路在不同日期、不同天氣下各峰段的平均行駛時間及發車頻次、發車間隔，再結合數據采集模塊中的其他基礎靜態數據，建立模型生成初始的行車計劃表；

步驟三：再通過組合優化分析模塊在初始的行車計劃表基礎上，根據駕駛員每天標準工作時長及其權重值約束條件，對初始行車計劃表中的各路牌及其車次鏈進行分割組合優化，根據組合的權重結果值，搜索出滿足一人一路牌的相對最優的組合結果，即優化組合后的行車計劃表中每個路牌的工作時長基本均衡；

步驟三中的排班結果的具體處理過程如下：

設駕駛員標準工作時長t_Δ＝8對應的權重值ρ_Δ＝180，則對于任意一個被分割組合后的工作時長t_γ，其工作時長對應的權重值ρ_γ為：

對于公交線路來說，一般最大營運時長是18個小時，初始行車計劃表中每個原始路牌的總營運時長不同，按照下面兩種方式處理：

方式一：原始行車計劃表中每個原始路牌的總營運時長均大于等于小時，則直接按照標準工作時長進行分割，其具體處理過程如下：

S1：從原始行車計劃表中第1個路牌的第1個F(1,1)開始，首先選擇F(1,2)跟F(1,1)組合，則形成第1次分割，把第1個路牌分割成兩段，F(1,1)、F(1,2)是第1個分段，對應的營運時長之和已知，設為F(1,3)，......,F(1,n)是第2個分段，對應的營運時長之和已知，設為根據前面工作時長權重值計算公式，可以計算出兩段內營運時長的權重值，設分別為則得到第1次組合的結果值

然后再增加選擇1個車次F(1,3)，形成第2次分割，把第1個路牌分割成兩段，F(1,1)、F(1,2)、F(1,3)是第1個分段，對應的營運時長之和已知，設為F(1,4)，......，F(1,n)是第2個分段，對應的營運時長之和已知，設為根據前面工作時長權重值計算公式，可以計算出每個段內行駛時間的權重值，分別為則第2次組合的結果值

逐步每次多增加選擇1個非空F(1,j)，每次分割都有對應的組合結果值直至選擇到第1個路牌的最后1個非空F(1,j)，j＝1,2,…,n；則最后一次分割后第1段對應的營運時長之和已知，設為分割后第2段對應的營運時長為0，即：根據前面工作時長權重值計算公式，可以計算出第1段內行駛時長的權重值為則最后1次分割組合的結果值

則對于第1個路牌，選擇分割后組合結果值最大的分割方式，當兩個組合結果值相同時，優先選擇分割后第1段內的工作時間短的；

S2：依次從原始行車計劃表中第i個路牌的第1個F(i,1)開始，重復上述步驟，選擇出每個路牌i對應的最優分割，直至到最后一個路牌結束，完成所有原計劃表的分割，得到每個路牌的最優分割；

S3：把最優分割后所有含有非空值F(i,j)的分段，分別放在單獨的路牌上，形成新組合后的行車計劃表，新組合后的行車計劃表中每個路牌的營運時長相對均衡；

方式二：原始行車計劃表中存在路牌的總營運時長小于t_Δ＝8小時，且滿足總營運時長小于t_Δ＝8小時的路牌有γ個，1≤γ＜m，則按照如下分割組合算法：

SS1：依次從總營運時長小于t_Δ＝8小時的γ個路牌中選擇，設所選路牌為z，此路牌中第1個非空數據及最后一個非空數據分別為F(z,j₀)、F(z,j₁)，1≤j₀＜j₁≤n；

SS2：考慮到需要從同一個發車站點發車，則從第j₁+3單次開始，分別從其他的m-1個路牌中選擇F(k,j₁+3)及F(k,j₁+4)兩個數據，與此路牌z的數據集進行組合，則會形成m-1個組合結果，即有m-1個組合后的工作時長，根據組合后的工作時長計算對應的權重值當F(k,j₁+3)為空時，對應的組合后的權重值其他的m-1個路牌分別被分割掉F(k,j₁+3)及F(k,j₁+4)兩個數據后，會被分割成前后兩段，每段對應一個工作時長，若被分割后的兩段中任何一段的工作時長均大于0，則根據被分割后的兩段對應的工作時長計算其權重值，設分別為：則：路牌z分別從其他m-1個路牌分割兩個數據并組合后的m-1個權重結果值為：

若被分割后的兩段中存在一段的工作時長為0，則工作時長為0的那段的權重值取另一段的權重值及組合后的權重值之中的最小值，即此時：路牌z分別從其他m-1個路牌分割兩個數據并組合后的m-1個權重結果值為：或

SS3：繼續從第j₁+3單次開始，分別從其他的m-1個路牌中選擇F(k,j₁+3)、F(k,j₁+4)、F(k,j₁+5)、F(k,j₁+6)四個數據，與此路牌z的數據集進行組合，則會形成m-1個組合結果，即有m-1個組合后的工作時長，根據組合后的工作時長計算對應的權重值當F(k,j₁+3)為空時，對應的組合后的權重值其他的m-1個路牌分別被分割掉F(k,j₁+3)、F(k,j₁+4)、F(k,j₁+5)、F(k,j₁+6)四個數據后，會被分割成前后兩段，每段對應一個工作時長，若被分割后的兩段中任何一段的工作時長均大于0，則根據被分割后的兩段對應的工作時長計算其權重值，設分別為：則：路牌z分別從其他m-1個路牌分割兩個數據并組合后的m-1個權重結果值為：

若被分割后的兩段中存在一段的工作時長為0，則工作時長為0的那段的權重值取另一段的權重值及組合后的權重值之中的最小值，即此時：路牌z分別從其他m-1個路牌分割兩個數據并組合后的m-1個權重結果值為：或

SS4：繼續從第j₁+3單次開始，每次在上述步驟的基礎上分別從其他m-1個路牌中選擇e個數據，直至選擇到F(k,n)，則分割終止，每次分割后與此路牌z的數據集進行組合，則會形成m-1個組合結果，即有m-1個組合后的工作時長，根據組合后的工作時長計算對應的權重值當F(k,j₁+3)為空時，對應的組合后的權重值其他的m-1個路牌分別被分割掉對應的數據后，會被分割成前后兩段，每段對應一個工作時長，若被分割后的兩段中任何一段的工作時長均大于0，則根據被分割后的兩段對應的工作時長計算其權重值，設分別為：則：每次分割后，路牌z分別從其他m-1個路牌分割e個數據并組合后的m-1個權重結果值為：

若被分割后的兩段中存在一段的工作時長為0，則工作時長為0的那段的權重值取另一段的權重值及組合后的權重值之中的最小值，即此時：路牌z分別從其他m-1個路牌分割兩個數據并組合后的m-1個權重結果值為：或

SS5:繼續從第j₁+5單次開始，分別從其他的m-1個路牌中選擇F(k,j₁+5)及F(k,j₁+6)兩個數據，與此路牌z的數據集進行組合，則會形成m-1個組合結果，即有m-1個組合后的工作時長，根據組合后的工作時長計算對應的權重值當F(k,j₁+5)為空時，對應的組合后的權重值其他的m-1個路牌分別被分割掉F(k,j₁+5)及F(k,j₁+6)兩個數據后，會被分割成前后兩段，每段對應一個工作時長，若被分割后的兩段中任何一段的工作時長均大于0，則根據被分割后的兩段對應的工作時長計算其權重值，設分別為：則：路牌z分別從其他m-1個路牌分割兩個數據并組合后的m-1個權重結果值為：

若被分割后的兩段中存在一段的工作時長為0，則工作時長為0的那段的權重值取另一段的權重值及組合后的權重值之中的最小值，即此時：路牌z分別從其他m-1個路牌分割兩個數據并組合后的m-1個權重結果值為：或

SS6：然后再從第j₀-3(j₀＞4)單次開始，分別從其他的m-1個路牌中選擇F(k,j₀-3)及F(k,j₀-4)兩個數據，與此路牌z的數據集進行組合，則會形成m-1個組合結果，即有m-1個組合后的工作時長，根據組合后的工作時長計算對應的權重值當F(k,j₀-3)為空時，對應的組合后的權重值其他的m-1個路牌分別被分割掉F(k,j₀-3)及F(k,j₀-4)兩個數據后，會被分割成前后兩段，每段對應一個工作時長，若被分割后的兩段中任何一段的工作時長均大于0，則根據被分割后的兩段對應的工作時長計算其權重值，設分別為：則：路牌z分別從其他m-1個路牌分割兩個數據并組合后的m-1個權重結果值為：

若被分割后的兩段中存在一段的工作時長為0，則工作時長為0的那段的權重值取另一段的權重值及組合后的權重值之中的最小值，即此時：路牌z分別從其他m-1個路牌分割兩個數據并組合后的m-1個權重結果值為：或

SS7：對于每個路牌z，重復上述步驟，依次得到每次分割組合后的權重結果值；

SS8：再根據路牌z的工作時長按照工作時長權重值計算公式計算把路牌z單獨作為1個路牌的結果值，為：ω_zz＝ρ_zz×ρ_zz×ρ_zz，z＝1,2,…,γ，對于所有的路牌z，對應的組合權重結果有從所有的權重結果中搜索出最優的分割組合結果，得到z個路牌的分割組合結果；

SS9:對于原始行車計劃表中總營運時長大于等于t_Δ＝8小時的路牌，如果沒有被分割，則按照原始行車計劃表中每個原始路牌的總營運時長均大于等于t_Δ＝8小時的步驟，計算出這些路牌分割的最優結果值，得到路牌的分割結果；

步驟四：最后駕駛員智能排班模塊根據優化組合后的一人一路牌的行車計劃表，結合駕駛員上下班地點偏好信息，實現行車計劃中路牌與具體駕駛員的匹配，自動生成每個駕駛員的排班結果。