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

在審

• 申請(qǐng)?zhí)枺?/td>: 201810737569.4
• 申請(qǐng)日: 2018-07-06
• 公開（公告）號(hào): CN108960634A
• 公開（公告）日: 2018-12-07
• 發(fā)明（設(shè)計(jì)）人: 郭建國;龍衛(wèi)東;閻磊;雷炳友;田影;沈洋;靳冬冬
• 申請(qǐng)（專利權(quán)）人: 鄭州天邁科技股份有限公司
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06
• 代理公司: 鄭州德勤知識(shí)產(chǎn)權(quán)代理有限公司 41128
• 代理人: 黃紅梅;黃軍委

1.一種基于人車綁定模式的車輛排班算法，其特征在于，包括以下步驟：

(1)構(gòu)造車輛調(diào)度模型并求解，獲得一個(gè)車輛調(diào)度方案；

(2)將車輛調(diào)度方案作為司機(jī)排班問題初始解，迭代進(jìn)行局部搜索改進(jìn)；

(3)在局部搜索過程中，引入破壞重建方法對(duì)當(dāng)前解進(jìn)行擾動(dòng)。

(4)迭代執(zhí)行步驟(2)到(3)N_iter次，N_iter為局部搜索迭代次數(shù)；

(5)迭代執(zhí)行步驟(1)到(3)M_start次，M_start為算法多啟動(dòng)次數(shù)；

(6)改進(jìn)步驟(2)獲得的可行班次鏈，建立SCP模型，獲得更優(yōu)的班次鏈組合。

2.根據(jù)權(quán)利要求1所述的基于人車綁定模式的車輛排班算法，其特征在于：所述車輛班次鏈采用公交班次鏈集合B＝{b₁,b₂,...,b_k}表達(dá)車輛調(diào)度和司機(jī)排班方案，每個(gè)班次鏈b_i包含一輛車、所在車場、執(zhí)行班次編號(hào)、配備司機(jī)及其班制，表示車輛從車場出發(fā)，依次完成若干班次任務(wù)，再回到車場，每個(gè)班次鏈需要配備一個(gè)或兩個(gè)司機(jī)。

3.根據(jù)權(quán)利要求2所述的基于人車綁定模式的車輛排班算法，其特征在于：

步驟(1)中，建立車輛調(diào)度模型，并求解車輛調(diào)度模型獲得車輛班次鏈初始解，

其中，車輛調(diào)度模型BSP為

令c_ij為車輛從班次i終點(diǎn)或停車場i到達(dá)班次j或停車場j的空駛成本，令t_ij為班次i與j的時(shí)間間隔，t_min為班次間最小休息時(shí)間，N_i為班次i執(zhí)行完后可繼續(xù)執(zhí)行的班次任務(wù)集合，即N_i＝{j|j∈V,t_ij≥t_min}，

模型中，x_ki,x_ik,x_ij為決策變量，x_ki表示某輛車是否從停車場k出發(fā)去執(zhí)行班次i，x_ik表示某輛車完成班次i后是否回到停車場k，x_ij表示某輛車執(zhí)行班次i后是否接著執(zhí)行班次j；M是一個(gè)足夠大的正整數(shù)；

求解模型獲得滿足班次間司機(jī)休息時(shí)間規(guī)定的車輛數(shù)最少或空駛成本最低的班次鏈。

4.根據(jù)權(quán)利要求2所述的基于人車綁定模式的車輛排班算法，其特征在于，步驟(2)中，迭代進(jìn)行局部搜索改進(jìn)包括5個(gè)局部搜索算子：

單班次移動(dòng)，將某個(gè)班次鏈i中的某個(gè)班次刪除，并嘗試插入到其他班次鏈j中；

雙班次移動(dòng)，將某個(gè)班次鏈i中的兩個(gè)相鄰班次刪除，并嘗試插入到其他班次鏈j中；

班次鏈交叉，將兩個(gè)班次鏈(i,j)分別截?cái)啵賴L試進(jìn)行組合得到班次鏈(k,l)；

班次鏈合并，將兩個(gè)班次(i,j)合并，嘗試生成一個(gè)新班次鏈K；

班次鏈拆分，將某個(gè)班次鏈i截?cái)啵蓛蓚€(gè)新班次鏈(j,k)；

進(jìn)行迭代搜索時(shí)，單班次移動(dòng)、雙班次移動(dòng)和班次鏈交叉算子按順序執(zhí)行，并在執(zhí)行完畢后調(diào)用班次鏈合并算子，班次鏈拆分算子僅在其他算子難以為司機(jī)提供就餐時(shí)間時(shí)使用。

5.根據(jù)權(quán)利要求4所述的基于人車綁定模式的車輛排班算法，其特征在于：每個(gè)算子執(zhí)行中，先判斷調(diào)整獲得新班次鏈的可行性，若新班次鏈不可行，放棄本次調(diào)整；若可行，優(yōu)先將不可行班次鏈調(diào)整為可行班次鏈，其次調(diào)整班次鏈降低其成本，其中，班次鏈涉及的成本包括車輛固定成本、車輛空駛成本、司機(jī)固定成本和司機(jī)可變成本。

6.根據(jù)權(quán)利要求5所述的基于人車綁定模式的車輛排班算法，其特征在于：所述步驟(3)中的破壞重建方法為將當(dāng)前方案中某個(gè)班次鏈拆分，生成2個(gè)新的班次鏈，或者將兩個(gè)車輛班次鏈破壞，并重組獲得新的班次鏈。

7.根據(jù)權(quán)利要求4所述的基于人車綁定模式的車輛排班算法，其特征在于，所述步驟(6)中，令集合Ω＝{b₁,b₂,...,b_n}為局部搜索所發(fā)現(xiàn)的所有班次鏈，鏈b_i為滿足司機(jī)排班的約束條件，其成本為c_i，建立SCP模型為：

其中，目標(biāo)函數(shù)(5)用于選擇成本最低的班次鏈組合，約束條件(6)保證班次集合中每一個(gè)班次均被所選擇的某個(gè)班次鏈覆蓋。