考慮司乘人員工作時間窗的高鐵快巴車輛調(diào)度與人員排班綜合優(yōu)化

李凱明，宋瑞，郭小樂

(北京交通大學(xué) 綜合交通運輸大數(shù)據(jù)應(yīng)用技術(shù)交通運輸行業(yè)重點實驗室，北京 100044)

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

公共交通系統(tǒng)優(yōu)化包括線網(wǎng)、時刻表、車輛調(diào)度、人員排班優(yōu)化4個環(huán)節(jié)，研究者通常依次對各個環(huán)節(jié)進(jìn)行優(yōu)化[1-3]。由于每個環(huán)節(jié)相互緊密關(guān)聯(lián)，依次對各個環(huán)節(jié)進(jìn)行優(yōu)化可能導(dǎo)致僅出現(xiàn)局部最優(yōu)解[4]，而綜合優(yōu)化能夠統(tǒng)籌考慮各個環(huán)節(jié)，因此近年來同時考慮兩個甚至更多環(huán)節(jié)的綜合優(yōu)化逐漸受到更多的學(xué)者關(guān)注。

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

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

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

2 模型建立

2.1 問題描述與假設(shè)

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

為簡化問題，做以下假設(shè)：

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

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

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

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

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

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

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

2.2 目標(biāo)函數(shù)

車輛調(diào)度與人員排班綜合優(yōu)化的目標(biāo)是最小化公交企業(yè)的運營成本。而運營成本C總分為車輛運營成本C車輛與司乘人員運營成本C乘務(wù)員。

minC總=C車輛+C乘務(wù)員。

(1)

(1)司乘人員運營成本

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

(2)

(3)

(2)車輛運營成本

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

(4)

(5)

(6)

綜上所述，車輛調(diào)度與人員排班綜合優(yōu)化的目標(biāo)函數(shù)如式(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 已知時刻表

按照假設(shè)插入駛?cè)腭偝觥⒖振?、等待等車次，并將所有時空網(wǎng)絡(luò)點的時間數(shù)列升序排列，同時將車次(包括正常運營車次、空駛車次和原地等待)以起始站點的發(fā)車時刻的時間數(shù)列升序排列，若發(fā)車時刻相同則按照到達(dá)時刻升序排列。構(gòu)建時空網(wǎng)絡(luò)，具體如表2所示。該場站共有8名司乘人員，具體工作時間窗情況如表3所示。

表2 時空網(wǎng)絡(luò)表

續(xù)表2

表3 司乘人員情況

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

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

第2節(jié)建立的模型為線性整數(shù)規(guī)劃模型，分支定界法是求解線性整數(shù)規(guī)劃最常用的精確算法。因此使用分支定界法對該模型進(jìn)行求解，最終得到最優(yōu)解如表5、表6所示。最優(yōu)解使用車輛數(shù)為6輛，總成本為22 382.79元，其中車輛使用成本為12 000元，正常車次成本3 533.3元，駛?cè)腭偝鲕嚧纬杀? 456.88元，空駛車次成本545.26元，等待成本45.048元，司乘人員的成本為2 805.3元。

表5 車輛調(diào)度方案

表6 司乘人員排班方案

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

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

表7 不同方案對比

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

4 結(jié)論

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

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