考慮司乘人員工作時間窗的高鐵快巴車輛調度與人員排班綜合優化

李凱明，宋瑞，郭小樂

(北京交通大學 綜合交通運輸大數據應用技術交通運輸行業重點實驗室，北京 100044)

為建設“公交都市”、滿足居民日益多樣化的出行需求，解決常規公交在高峰期或地鐵停運期間運力不足的問題，北京公交集團開通了新型公交服務產品——高鐵快巴。高鐵快巴原計劃根據高鐵旅客到京情況進行線路、發車時刻的調整，因此其調度、排班方案等相比傳統公交更加靈活，也聯系得更加緊密，牽一發而動全身。但由于缺乏理論指導，目前高鐵快巴仍使用傳統運營模式，即采用固定間隔30 min發車、單線路調度的模式，導致乘客體驗差、企業成本高，如2018年春節期間開通的兩條高鐵快巴春運專線發車近6000次，但上座率卻不到20%。不當的運營模式所導致的空車率高等問題顯而易見，而司乘人員也有反映工作時間較長等問題。因此有必要針對高鐵快巴的車輛調度與人員排班優化問題進行研究。

公共交通系統優化包括線網、時刻表、車輛調度、人員排班優化4個環節，研究者通常依次對各個環節進行優化[1-3]。由于每個環節相互緊密關聯，依次對各個環節進行優化可能導致僅出現局部最優解[4]，而綜合優化能夠統籌考慮各個環節，因此近年來同時考慮兩個甚至更多環節的綜合優化逐漸受到更多的學者關注。

Prileszky等[5]分析了車輛調度與人員排班問題的綜合優化方法和序貫法的主要步驟和面臨的問題，并提出了一種交互式優化方法，該方法能提高手工作業的效率。Lam等[6]提出了考慮司機之間可以互相交換車輛的約束模型，將該方法與序貫法進行對比，發現其優化效果更好。Dominguez-Martin等[7]利用車輛路徑模型構建調度與排班綜合優化模型并通過分支定界法求解不等式。de Athayde Prata[8]將調度和排班綜合優化看作多商品的最大覆蓋問題，在此基礎上建立多目標優化模型，并采用PESA-II算法進行求解。文獻[9-10]為多車場的整體優化提出了基于列生成和拉格朗日啟發式算法兩種模型。Mesquita等[11-12]基于多商品網絡流模型和集劃分/覆蓋模型建立了調度與排班綜合優化的整數線性規劃模型，分別運用了精確、啟發式以及模糊的分支定界法對其進行求解。de Groot等[13]通過將多車場的大型問題進行分割，分別對每部分進行整體優化，能夠有效節省計算時間。而Haase等[14]創造性地從司乘人員的網絡結構出發(絕大多數研究都是從車輛的網絡結構出發)，構建單車場-同種車型的集覆蓋模型，而后使用列生成算法混合分支定界法求解。

以上研究主要探討了車輛調度與人員排班的綜合優化問題，但建立的模型均默認司乘人員可以執行一天內所有的車次，缺少對司乘人員工作時間安排的考慮。如司乘人員實際排班的班次通常都有相應的工作時間要求(即司乘人員的工作時間窗要求)，包括單班與整班，整班又包括早班和晚班[15]。而高鐵快巴運營的靈活性也導致車輛在途時間相對多變，對人員排班提出了更高的要求，因此有必要考慮司乘人員工作時間窗的高鐵快巴車輛調度與人員排班問題，在保證完成班次任務的前提下，盡可能考慮司乘人員的時間需求，促進多樣化公交服務規范化運營，從而更好地滿足乘客多樣性需求，提高城市公交服務水平，提升公共交通的公眾吸引力。

基于此，本文針對高鐵快巴的車輛調度與人員排班綜合優化問題(integrating vehicle scheduling problem and driver scheduling problem，VDSP)進行研究，引入司乘人員的工作時間窗，并提出了相應的綜合優化模型，最后利用分支定界法求解算例,說明了模型的正確性與有效性。

2 模型建立

2.1 問題描述與假設

本文所研究的問題屬于典型的VDSP問題，是車輛調度問題(vehicle scheduling problem，VSP)與人員排班問題(driver scheduling problem，DSP)的結合，研究中通常使用集分割/覆蓋模型(set-partitioning/covering formulation)對其進行建模。可以將其詳細描述為：某城市公交車場站集合為D，則某公交場站d∈D，在已知其司乘人員集合s∈S以及其高鐵快巴線路的正常運營車輛班次(以下簡稱車次)數量及其起始站點、到發站時刻的情況下，建立時空網絡Gd=(Nd,Ad)(其中，Nd代表公交場站d的車輛到發時刻，Ad代表Nd之間的車輛運行行為)，求解設計高鐵快巴車次以及司乘人員任務m∈Md(i,j)的最優方案，其中，Md(i,j)為以起始站點的發車時刻升序排列的司乘人員班次任務集合。

為簡化問題，做以下假設：

(1)車次(包括正常運營車次、空駛車次和原地等待)以起始站點的發車時刻的時間數列升序排列，若發車時刻相同則按照到達時刻升序排列，與司乘人員班次任務一一對應；

(2)所有車輛與司乘人員班次任務所需成本已經確定；

(3)不考慮場站的公交車輛限制；

(4)在時空網絡構建中，若某一車次與間隔最近的車次滿足空駛時間條件，則兩個車次之間插入可能的空駛車次；若兩個車次時間間隔較大(超過兩倍站點返回場站的時間)，則中間不插入原地等待或空駛車次，車輛插入可能的返回場站車次；

(6)司乘人員的相鄰工作班次任務間隔必須滿足最小停留時間；

(7)司乘人員可以在首末站點以及場站進行工作交接；

(8)司乘人員對工作時間均有不同要求，執行班次需滿足時間窗約束(即各司乘人員工作時間的上下限約束)，需滿足最大工作時間要求。

2.2 目標函數

車輛調度與人員排班綜合優化的目標是最小化公交企業的運營成本。而運營成本C總分為車輛運營成本C車輛與司乘人員運營成本C乘務員。

minC總=C車輛+C乘務員。

(1)

(1)司乘人員運營成本

司乘人員運營成本C乘務員為所有場站所有執行的司乘人員班次任務與對應的班次任務運營成本的乘積加上司乘人員更換車輛所帶來的額外成本C換。班次任務運營成本由班次任務運營時間與單位時間運營成本的乘積求得。

(2)

(3)

(2)車輛運營成本

車輛運營成本C車輛包括車次執行成本Ce與車輛使用成本Cu。車次執行成本Ce為所有場站所有執行的車次(包括正常運營車次、空駛車次和原地等待)與對應的車次運營成本的乘積，車輛使用成本Cu為使用的總車輛數B與車輛使用費用C使用的乘積，其中C使用中包含了使用車輛就會出現的成本如車輛維護成本、車輛折舊成本等。

(4)

(5)

(6)

綜上所述，車輛調度與人員排班綜合優化的目標函數如式(7)所示：

(7)

2.3 約束條件

模型的約束條件如下：

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

3 算例研究

考慮有3個公交首末站A、B、C以及1個場站D，其中站點A為高鐵站，因此僅考慮A—B、A—C之間的上下行公交線路和3個站之間可能的空駛線路，不考慮B和C之間的線路。站點A到站點B的行駛時間為0.7 h；站點A到站點C的行駛時間為1.2 h；站點A到場站D的行駛時間為0.3 h；站點B到站點C的行駛時間為0.5 h；站點B到場站D的行駛時間為0.8 h；站點C到場站D的行駛時間為0.8 h。

表1 已知時刻表

按照假設插入駛入駛出、空駛、等待等車次，并將所有時空網絡點的時間數列升序排列，同時將車次(包括正常運營車次、空駛車次和原地等待)以起始站點的發車時刻的時間數列升序排列，若發車時刻相同則按照到達時刻升序排列。構建時空網絡，具體如表2所示。該場站共有8名司乘人員，具體工作時間窗情況如表3所示。

表2 時空網絡表

續表2

表3 司乘人員情況

計算時取司乘人員平均行車單位時間成本為2 元/h，平均等待單位時間成本為0.4 元/h[16]；由于司乘人員更換線路帶來的隱性成本C換取50元/(人·次)。依照目前高鐵快巴運營現狀，其車輛核載人數為10人，人均票價為15.32元。高鐵快巴預計滿載率為50%，平均運營速度為15 km/h，單車運營成本為4.8元/km[17]；參考司乘人員行車成本與等待成本之間的比例，取單車等待成本為正常車次成本的1/5；為盡可能地減少車輛的使用數量，車輛使用費用C使用取盡可能大的值2000元/(車·次)[18]。由此求得單位時間車輛與司乘人員費用如表4所示。

表4 單位時間車輛與司乘人員成本

第2節建立的模型為線性整數規劃模型，分支定界法是求解線性整數規劃最常用的精確算法。因此使用分支定界法對該模型進行求解，最終得到最優解如表5、表6所示。最優解使用車輛數為6輛，總成本為22 382.79元，其中車輛使用成本為12 000元，正常車次成本3 533.3元，駛入駛出車次成本3 456.88元，空駛車次成本545.26元，等待成本45.048元，司乘人員的成本為2 805.3元。

表5 車輛調度方案

表6 司乘人員排班方案

從表5中可以看到，最終執行的車次有53次，其中正常車次20次，駛入駛出車次26次，空駛車次3次，等待車次4次，這是因為提前設置的參數盡可能地減少了空駛的車次以及駛入駛出的車次。從表6中可以看到，司乘人員執行的任務全部符合其工作時間窗要求以及其接續班次任務的站點需求。由此驗證建立的模型能夠有效地解決考慮司乘人員工作時間窗的高鐵快巴車輛調度與人員排班問題。

為了驗證模型的優越性，設計另外兩種方案。其中方案A是目前高鐵快巴所使用的方案即為單線路調度，車輛調度與人員排班獨立進行優化，用以驗證本文提出的模型對比現有方案的優越性；方案B為目前一般公交運營時所使用的方案即為多線路調度，車輛調度與人員排班獨立進行優化的方案，用以驗證綜合優化對比獨立優化的優越性。具體對比如表7所示。

表7 不同方案對比

從表7中可以看出，本文提出的綜合優化方案相比于方案A減少2 208.7元，優化率為8.98%；相比于方案B減少1 111.4元，優化率為4.73%。若采取目前高鐵快巴的運營方案，需要15個司乘人員才能夠滿足運營需求且執行車次達到60個，所以總運營成本最高；在獨立的對車輛調度與人員排班進行優化后，執行車次減少為55車次，需要12個司乘人員才能夠運營；而綜合優化方案，執行車次為53車次，司乘人員數也減少為8個人，總運營成本最低。由此可以驗證考慮乘務員時間窗的綜合優化方案相比于獨立的優化方案，在解決高鐵快巴的調度與人員排班問題上具有更好的應用效果。

4 結論

針對創新型公交服務產品高鐵快巴與常規公交相比在時間上更加靈活的特性，充分考慮司乘人員對工作時間的特殊要求，引入司乘人員時間窗，將車輛調度與人員排班進行綜合優化，利用時空網絡構建以企業運營成本最小為優化目標的高鐵快巴車輛調度與人員排班綜合優化模型，最后利用分支定界法計算出最優的車輛調度與人員排班方案，結果表明該模型能夠有效解決高鐵快巴的車輛調度與人員排班問題,減少司乘人員數量、降低運營成本，從而為公交管理部門、企業提供輔助決策。

但是本文僅使用了企業的運營成本作為目標函數進行優化，缺乏對夜間乘客等待時間成本的考慮。同時在最優化方案中司乘人員的工作量相差較大，如何平衡司乘人員之間的工作量也是下一步的研究方向。