李凱明，宋瑞，郭小樂(lè)

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

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

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

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

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

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

2 模型建立

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(1)司乘人員運(yùn)營(yíng)成本

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

(2)

(3)

(2)車輛運(yùn)營(yíng)成本

車輛運(yùn)營(yíng)成本C車輛包括車次執(zhí)行成本Ce與車輛使用成本Cu。車次執(zhí)行成本Ce為所有場(chǎng)站所有執(zhí)行的車次(包括正常運(yùn)營(yíng)車次、空駛車次和原地等待)與對(duì)應(yīng)的車次運(yùn)營(yíng)成本的乘積，車輛使用成本Cu為使用的總車輛數(shù)B與車輛使用費(fèi)用C使用的乘積，其中C使用中包含了使用車輛就會(huì)出現(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個(gè)公交首末站A、B、C以及1個(gè)場(chǎng)站D，其中站點(diǎn)A為高鐵站，因此僅考慮A—B、A—C之間的上下行公交線路和3個(gè)站之間可能的空駛線路，不考慮B和C之間的線路。站點(diǎn)A到站點(diǎn)B的行駛時(shí)間為0.7 h；站點(diǎn)A到站點(diǎn)C的行駛時(shí)間為1.2 h；站點(diǎn)A到場(chǎng)站D的行駛時(shí)間為0.3 h；站點(diǎn)B到站點(diǎn)C的行駛時(shí)間為0.5 h；站點(diǎn)B到場(chǎng)站D的行駛時(shí)間為0.8 h；站點(diǎn)C到場(chǎng)站D的行駛時(shí)間為0.8 h。

表1 已知時(shí)刻表

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

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

續(xù)表2

表3 司乘人員情況

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

表4 單位時(shí)間車輛與司乘人員成本

第2節(jié)建立的模型為線性整數(shù)規(guī)劃模型，分支定界法是求解線性整數(shù)規(guī)劃最常用的精確算法。因此使用分支定界法對(duì)該模型進(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次，這是因?yàn)樘崆霸O(shè)置的參數(shù)盡可能地減少了空駛的車次以及駛?cè)腭偝龅能嚧?。從?中可以看到，司乘人員執(zhí)行的任務(wù)全部符合其工作時(shí)間窗要求以及其接續(xù)班次任務(wù)的站點(diǎn)需求。由此驗(yàn)證建立的模型能夠有效地解決考慮司乘人員工作時(shí)間窗的高鐵快巴車輛調(diào)度與人員排班問(wèn)題。

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

表7 不同方案對(duì)比

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

4 結(jié)論

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

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