分支定價(jià)割平面法求解帶時(shí)間窗和人力分配的車輛路徑問題

蘇欣欣，伊廷剛，秦 虎

分支定價(jià)割平面法求解帶時(shí)間窗和人力分配的車輛路徑問題

蘇欣欣1，伊廷剛2，秦 虎1

(1. 華中科技大學(xué)，管理學(xué)院，武漢 430074；2. 聯(lián)勤保障部隊(duì)供應(yīng)局，武漢 430000)

本文研究了帶時(shí)間窗和人力分配的車輛路徑問題，并提出用分支定價(jià)割平面法來求其最優(yōu)解。分支定價(jià)割平面法首先根據(jù)Dantzig-Wolfe分解技術(shù)將問題的數(shù)學(xué)模型分解為基于路徑的主問題模型和求最短路徑的子問題模型，然后利用列生成和標(biāo)簽算法在主問題和子問題之間進(jìn)行迭代，并使用割平面法調(diào)整可行區(qū)域來求得主問題的最優(yōu)松弛解，最后采用基于車輛數(shù)目和弧的分支策略獲取原問題的整數(shù)解。算法中加入了兩種加速策略：雙向標(biāo)簽算法和遞減搜索空間法。通過對(duì)多組算例進(jìn)行測(cè)試，驗(yàn)證了模型和算法的準(zhǔn)確性，并分析了患者數(shù)目和車輛數(shù)目對(duì)結(jié)果的影響，也說明了割平面法具有提高算法效率的作用。最后，對(duì)大規(guī)模算例進(jìn)行測(cè)試的結(jié)果也為實(shí)際應(yīng)用提供了理論依據(jù)。

車輛路徑問題；人力分配；分支定價(jià)割平面法；救護(hù)車；列生成

0 引 言

隨著我國(guó)社會(huì)經(jīng)濟(jì)的快速發(fā)展，人們對(duì)自身健康的關(guān)注意識(shí)逐漸提高，尤其對(duì)醫(yī)療救助方面的相關(guān)服務(wù)提出了更高的質(zhì)量要求。人力和救護(hù)車是維持醫(yī)院正常運(yùn)轉(zhuǎn)的重要醫(yī)療資源，合理調(diào)度人力和救護(hù)車不僅是滿足患者健康需求的重要因素，更是提高院前服務(wù)水平的關(guān)鍵。

醫(yī)院調(diào)動(dòng)救護(hù)車一般有兩種情況：緊急救助和非緊急救助。在緊急救助的情況下，急救中心需要根據(jù)病人病情的危急程度和地理位置做出應(yīng)急響應(yīng)，安排救護(hù)車和相關(guān)醫(yī)療人員進(jìn)行爭(zhēng)分奪秒的搶救，保障人民群眾的健康與生命。此情況大多數(shù)出現(xiàn)于重大突發(fā)性事故和自然災(zāi)害中，并已有相當(dāng)多的學(xué)者對(duì)此類問題進(jìn)行了廣泛的研究，可參考文獻(xiàn)[1-3]。在非緊急救助的情況下，救護(hù)車的主要作用是有效地轉(zhuǎn)移位于不同地理位置的患者到醫(yī)院。有些患者由于年老或傷痛的原因無法獨(dú)自前往醫(yī)院而需要家屬陪同，因此救護(hù)車不但要轉(zhuǎn)移患者，還要一同轉(zhuǎn)移其陪同家屬。甚至有些受傷的病人需要輪椅或者擔(dān)架的輔助才能移動(dòng)，救護(hù)車上必須配備除了司機(jī)之外的輔助人員幫助患者操作輪椅或者擔(dān)架。至此，在醫(yī)院提供非緊急救助轉(zhuǎn)移服務(wù)并且患者有轉(zhuǎn)移時(shí)間窗需求的背景下，本文將研究帶時(shí)間窗和人力分配的車輛路徑問題(Manpower Allocation and Vehicle Routing Problem with Time Windows，MAVRPTW)。

MAVRPTW在帶時(shí)間窗的車輛路徑問題基礎(chǔ)上，增加了每輛車的人員分配。為了盡可能地轉(zhuǎn)移所有患者，醫(yī)院需要同時(shí)考慮以下兩個(gè)問題：① 在每輛救護(hù)車上配備若干名輔助人員；② 為每一輛救護(hù)車設(shè)計(jì)行駛路線。在MAVRPTW問題中，救護(hù)車和輔助人員從醫(yī)院出發(fā)接受患者的轉(zhuǎn)移請(qǐng)求，最終返回醫(yī)院。此問題要求滿足以下條件：(1)患者及其陪同家屬要一同被接送至醫(yī)院；(2)患者的轉(zhuǎn)移時(shí)間必須在患者要求的時(shí)間窗之內(nèi)。(3)救護(hù)車配備的輔助人員數(shù)目必須滿足車上每一位患者的需求；(4)救護(hù)車上的總?cè)藬?shù)不能超過車輛的載人限制。由于救護(hù)車的數(shù)目有限，存在一些患者未能被轉(zhuǎn)移而需要被外包給其他團(tuán)隊(duì)，因此會(huì)產(chǎn)生額外費(fèi)用。MAVRPTW問題的目標(biāo)是使得醫(yī)院完成所有患者轉(zhuǎn)移的總費(fèi)用最少，包括未完成轉(zhuǎn)移請(qǐng)求的外包費(fèi)用、雇傭輔助人員的費(fèi)用和車輛總行程的費(fèi)用。

MAVRPTW問題的示例如圖1所示，假設(shè)車輛的載人限制=12。從圖中可以直觀地發(fā)現(xiàn)，患者1的轉(zhuǎn)移人數(shù)為2，表示該患者需要1位家屬陪同，同時(shí)該患者需要2位輔助人員。其他患者的轉(zhuǎn)移需求同樣可以在圖中找到。需要指出的是一些細(xì)節(jié)在圖中被省略了，因?yàn)樗鼈儫o法說明這個(gè)示例的主要特點(diǎn)。路徑1轉(zhuǎn)移了3位患者，總轉(zhuǎn)移人數(shù)為6，車上配備了2個(gè)輔助人員，因此該車輛一共載有8個(gè)人。由于患者5的轉(zhuǎn)移時(shí)間窗無法滿足，因此患者5不能被此車輛轉(zhuǎn)移。路徑2也轉(zhuǎn)移了3位患者，并配備了3個(gè)輔助人員，車輛一共載有11個(gè)人。由于車輛的載人限制，患者5不能被車輛2轉(zhuǎn)移，最終患者5只能被外包。

圖1 MAVRPTW問題的示例

MAVRPTW既考慮到了人員的分配，又考慮到了車輛路線的設(shè)計(jì)。近年來，已有若干學(xué)者開始研究與MAVRPTW相關(guān)的問題。Kim某人[4]介紹了一種多階段的帶有人力團(tuán)隊(duì)調(diào)度的車輛路徑問題。在這個(gè)問題中需要按照給定的順序執(zhí)行客戶的多個(gè)任務(wù)，且每個(gè)任務(wù)由一組團(tuán)隊(duì)執(zhí)行。他們提出了一種基于粒子群優(yōu)化的啟發(fā)式算法。2012年，Pureza等[5]首次提出了帶有多個(gè)配送人員的車輛路徑問題，并采用禁忌搜索算法和蟻群算法對(duì)該問題進(jìn)行求解。Munari等[6]針對(duì)帶有多個(gè)配送人員的車輛路徑問題首次提出了分支定價(jià)割平面法求解該問題，實(shí)驗(yàn)結(jié)果證明了該算法具有一定優(yōu)勢(shì)并得到了文獻(xiàn)中未知的上界。蘇欣欣等人[7]在該問題的基礎(chǔ)上，對(duì)某些約束和目標(biāo)進(jìn)行一定的改進(jìn)，并設(shè)計(jì)了禁忌搜索算法處理該問題。Li等人[8]首次提出具有同步約束的人力路徑問題，該問題的任務(wù)是安排一組擁有不同技能的工人一起完成一系列的工作。針對(duì)該問題，他們建立了數(shù)學(xué)模型，并提出了一種模擬退火算法來求解此問題。Luo等[9]提出了分支定價(jià)割平面法來求解具有同步約束的人力路徑問題，與CPLEX進(jìn)行對(duì)比，證明了分支定價(jià)割平面法具有求解更多算例最優(yōu)解的能力。根據(jù)香港非緊急救護(hù)車轉(zhuǎn)移患者的現(xiàn)象，2017年，Lim等人[10]提出了帶有時(shí)間窗和人員排班的多程取送貨的車輛路徑問題。為求解決這個(gè)問題，他們提出了多循環(huán)的局部搜索元啟發(fā)式算法，并在局部搜索過程中引入了變鄰域下降法。隨后，Zhang等[11]結(jié)合實(shí)際情況首次提出了帶人力分配的車輛路徑問題(Manpower Allocation and Vehicle Routing Problem，MAVRP)，并建立了對(duì)應(yīng)的數(shù)學(xué)規(guī)劃模型，最終采用若干變鄰域搜索算法對(duì)此問題進(jìn)行求解。

本文提出的MAVRPTW問題在Zhang等[11]的基礎(chǔ)上，考慮了患者的轉(zhuǎn)移時(shí)間窗需求。這雖然使得問題更加復(fù)雜，為醫(yī)院安排救護(hù)車轉(zhuǎn)移患者的服務(wù)提出了更高的要求，但是卻給患者帶來了便利，并進(jìn)一步提升了院前服務(wù)水平。在求解算法方面，提出使用分支定價(jià)割平面法來得到MAVRPTW問題的最優(yōu)解，并在該精確算法中加入兩種加速策略：雙向標(biāo)簽算法和遞減搜索空間法。通過對(duì)多組算例進(jìn)行測(cè)試，驗(yàn)證了本文所提出精確算法的高效性和準(zhǔn)確性，并分析了相關(guān)參數(shù)對(duì)結(jié)果的影響，同時(shí)也證實(shí)了割平面法具有提高算法效率的作用，最后，對(duì)大規(guī)模算例進(jìn)行測(cè)試的結(jié)果也為實(shí)際應(yīng)用提供了理論依據(jù)。

1 數(shù)學(xué)模型

MAVRPTW是在車輛路徑問題的基礎(chǔ)上加入了人力分配問題，這會(huì)使得問題更加復(fù)雜。它不僅需要考慮車輛的路線和調(diào)度決策，還要決定每輛車分配的輔助人員數(shù)目。從數(shù)學(xué)模型的角度來看，帶人力分配的模式會(huì)給問題帶來更多的決策變量，也會(huì)使得原路徑優(yōu)化問題增加更多關(guān)于人力分配的復(fù)雜約束。為構(gòu)建數(shù)學(xué)模型，定義相關(guān)參數(shù)如下：

決策變量如下：

根據(jù)上述參數(shù)，本文描述的問題可歸結(jié)為如下數(shù)學(xué)模型：

2 Dantzig-Wolfe分解

上述的數(shù)學(xué)模型中含有大量的約束和變量，這使得計(jì)算過程相當(dāng)復(fù)雜。為了求得該問題的最優(yōu)解，我們使用Dantzig-Wolfe分解技術(shù)將該數(shù)學(xué)模型分解為一個(gè)基于可行路徑的Set Packing主問題和一個(gè)帶資源限制的最短路徑子問題。

2.1 Set Packing主問題模型

決策變量：

通過上述定義，可以將MAVRPTW問題的數(shù)學(xué)模型轉(zhuǎn)化為下面的Set Packing模型，并稱之為主問題(Master Problem，MP)：

式中，式(14)表示最小化轉(zhuǎn)移所有患者的總成本；式(15)表示每個(gè)點(diǎn)最多被轉(zhuǎn)移一次；式(16)表示路徑數(shù)目不能超過車輛總數(shù)目；式(17)表示變量屬性。

2.2 子問題模型

3 分支定價(jià)割平面法

本文使用分支定價(jià)割平面法來求得主問題的最優(yōu)整數(shù)解。其基本原理是利用列生成和標(biāo)簽法來搜索隊(duì)列中節(jié)點(diǎn)的線性松弛最優(yōu)解并在此過程中利用割平面法加入有效不等式提高松弛解的下界，并使用分支定界算法來對(duì)節(jié)點(diǎn)進(jìn)行分支搜索。在搜索過程中，如果節(jié)點(diǎn)的下界大于等于全局上界，那么這個(gè)節(jié)點(diǎn)可以刪除；如果節(jié)點(diǎn)的下界小于全局上界，解為整數(shù)時(shí)更新全局上界，解為分?jǐn)?shù)時(shí)要根據(jù)分支策略進(jìn)行分支。當(dāng)隊(duì)列為空或者全局下界等于全局上界時(shí)，算法終止。下面本文將詳細(xì)描述算法的各個(gè)部分。

3.1 初始解的生成

本文采用貪婪算法生成初始解。假設(shè)車輛數(shù)目足夠，算法最初使每一輛救護(hù)車對(duì)應(yīng)一個(gè)空路徑，隨機(jī)分配輔助人員，然后循環(huán)將患者插入這些路徑中的最優(yōu)為止，保證插入該患者后路徑的費(fèi)用最少，直至沒有患者可以插入到路徑中為止，那么一個(gè)初始解完成，并將其作為樹的根節(jié)點(diǎn)。

3.2 標(biāo)簽算法

為了提高算法的速度，使用占優(yōu)準(zhǔn)則來減少在標(biāo)簽算法中擴(kuò)展的標(biāo)簽數(shù)量。在已有的標(biāo)簽中，占優(yōu)準(zhǔn)則可以確定一個(gè)子集，保證最優(yōu)路徑在這些占優(yōu)標(biāo)簽中產(chǎn)生。不在子集中的標(biāo)簽，即被占優(yōu)的標(biāo)簽，將會(huì)被丟棄，防止做無效擴(kuò)展，從而加快算法速度。

3.3 遞減搜索空間

遞減搜索空間(decremental state-space relaxation)是由Boland等人[12]在2006首次提出的一種加快求解子問題速度的方法。在標(biāo)簽算法中，該方法首先將一個(gè)點(diǎn)只能被一條路徑訪問的條件進(jìn)行松弛，即允許一個(gè)點(diǎn)被一條路徑多次訪問。在最終得到的路徑中，若存在一個(gè)點(diǎn)被訪問多次，則限制該點(diǎn)只能被路徑訪問一次，并重新對(duì)子問題進(jìn)行求解，直至最終得到的路徑中每一個(gè)點(diǎn)只被該路徑訪問一次為止。

3.4 割平面法

3.5 分支策略與整數(shù)解

4 實(shí)驗(yàn)結(jié)果及分析

4.1 算例說明

分支定價(jià)割平面法使用Java語(yǔ)言進(jìn)行編寫，并使用CPLEX(Studio1251)求解受限主問題。運(yùn)行環(huán)境采用Intel(R)Core(TM)i7-4790 CPU @ 3.60GHz(8.00 GB內(nèi)存)，且實(shí)驗(yàn)中的計(jì)算時(shí)間以秒為單位進(jìn)行統(tǒng)計(jì)。

按照時(shí)間窗的緊湊程度和點(diǎn)的分布規(guī)律，Solomon測(cè)試算例被劃分為6種類型。我們?cè)诿總€(gè)類型中隨機(jī)選擇4個(gè)算例，因此本文中一共有24個(gè)標(biāo)準(zhǔn)測(cè)試算例。由于每一個(gè)標(biāo)準(zhǔn)測(cè)試算例包含100個(gè)患者，為了更全面、更充分地研究分支定價(jià)割平面法的性能，對(duì)每一個(gè)算例選取部分?jǐn)?shù)據(jù)生成具有不同患者數(shù)目的測(cè)試算例，并定義含有0～20個(gè)患者的算例為小規(guī)模算例，含有20～50個(gè)患者的算例為中規(guī)模算例，含有50～100個(gè)患者的算例為大規(guī)模算例。

4.2 與CPLEX對(duì)比實(shí)驗(yàn)

為了驗(yàn)證分支定價(jià)割平面法的準(zhǔn)確性，將其與CPLEX進(jìn)行比較，并采用小規(guī)模算例進(jìn)行測(cè)試。針對(duì)每一個(gè)標(biāo)準(zhǔn)算例，選擇每一個(gè)算例的前11個(gè)點(diǎn)和前21個(gè)點(diǎn)，分別組成含有10個(gè)患者和20個(gè)患者的小規(guī)模算例。設(shè)置分支定價(jià)割平面算法和CPLEX運(yùn)行每一個(gè)算例的時(shí)間限制為7 200s，且只運(yùn)行一次。

表1 小規(guī)模算例求解結(jié)果(10個(gè)患者、2輛車)

20個(gè)患者、4輛車的小規(guī)模算例的求解結(jié)果如表2所示。從實(shí)驗(yàn)數(shù)據(jù)可知，在7 200s內(nèi)，只有10個(gè)算例CPLEX能求得最優(yōu)解。對(duì)比獲得的最優(yōu)解，分支定價(jià)割平面法的求解結(jié)果與之相同且求解時(shí)間遠(yuǎn)低于CPLEX的求解時(shí)間。對(duì)于CPLEX未能求出最優(yōu)解的14個(gè)算例，分支定價(jià)割平面法均以很短的時(shí)間求出了最優(yōu)解。實(shí)驗(yàn)結(jié)果說明了分支定價(jià)割平面法的正確性，并且相比CPLEX具有一定的效率。

表2 小規(guī)模算例求解結(jié)果(20個(gè)患者、4輛車)

4.3 靈敏度分析

由于患者數(shù)目和車輛數(shù)目直接影響分支定價(jià)割平面法的計(jì)算結(jié)果，因此本文將分析這兩個(gè)參數(shù)的變化對(duì)計(jì)算結(jié)果的影響。

針對(duì)以上24個(gè)算例，使用中等規(guī)模的數(shù)據(jù)進(jìn)行分析，患者數(shù)目選取30和40，車輛數(shù)目選取6、7和8。這樣的取值不但使得測(cè)試算例具有代表性，而且能保證算法的求解效率。計(jì)算結(jié)果分別統(tǒng)計(jì)在表3和表4中。在這兩個(gè)表中，斜體的數(shù)據(jù)表示算法由于超出內(nèi)存僅能返回的最小上界。

實(shí)驗(yàn)結(jié)果表明，當(dāng)患者數(shù)目一定時(shí)，增大車輛數(shù)目能夠降低轉(zhuǎn)移患者的總費(fèi)用，同時(shí)也提高了問題的復(fù)雜度，使得算法的求解時(shí)間增長(zhǎng)。當(dāng)車輛數(shù)目一定時(shí)，患者數(shù)目的增長(zhǎng)，增加了轉(zhuǎn)移患者的總費(fèi)用，同樣也使得問題的求解難度增強(qiáng)。

表3 中規(guī)模算例求解結(jié)果(30個(gè)患者)

表4 中規(guī)模算例求解結(jié)果(40個(gè)患者)

4.4 割平面法的測(cè)試與分析

本文提出的精確算法是在分支定價(jià)的基礎(chǔ)上加入了割平面法，從而達(dá)到提高松弛解下界，有效減少分支定界中分支的作用。為了驗(yàn)證割平面法的有效性，分別將分支定價(jià)割平面法和不包含割平面法的分支定價(jià)算法對(duì)大規(guī)模算例進(jìn)行了測(cè)試。測(cè)試算例的規(guī)模為50個(gè)患者和15輛車，實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)于表5中。

表5 大規(guī)模算例求解結(jié)果(50個(gè)患者、15輛車)

從表5中可以看出，在24個(gè)算例中分支定價(jià)割平面法可以得到14個(gè)最優(yōu)解，而不包含割平面法的分支定價(jià)算法只能獲得9個(gè)最優(yōu)解。在兩種算法均得到最優(yōu)解的情況下，分支定價(jià)割平面法獲得最優(yōu)解的求解時(shí)間明顯低于分支定價(jià)算法的求解時(shí)間，只有算例MA-R201和MA-R207的求解時(shí)間略高于分支定價(jià)算法的求解時(shí)間。對(duì)比兩種算法得到的最小上界，分支定價(jià)割平面法得到的結(jié)果大部分低于分支定價(jià)算法得到的結(jié)果，只有算例MA-RC205分支定價(jià)割平面法得到的結(jié)果大于分支定價(jià)算法得到的結(jié)果，且相對(duì)誤差僅為0.26%。從本質(zhì)上分析，是由于割平面法能夠優(yōu)化主問題的數(shù)學(xué)模型，快速提高松弛解下界，使得算法可以對(duì)無效節(jié)點(diǎn)進(jìn)行及早剪枝，從而達(dá)到節(jié)約大量存儲(chǔ)空間和求解時(shí)間的作用。

4.5 分支定價(jià)割平面法求解規(guī)模的測(cè)試

為了研究分支定價(jià)割平面法能夠求解的算例規(guī)模，本文對(duì)以上24個(gè)算例使用兩種不同的大規(guī)模算例進(jìn)行了測(cè)試，并將測(cè)試結(jié)果統(tǒng)計(jì)在圖2中。從圖2中可知，當(dāng)患者數(shù)目為50、車輛數(shù)目為20時(shí)，71%的算例可以通過分支定價(jià)割平面法得到最優(yōu)解；而當(dāng)患者數(shù)目為70、車輛數(shù)目為25時(shí)，僅有42%的算例可以通過分支定價(jià)割平面法得到最優(yōu)解。算例的患者數(shù)目和車輛數(shù)目是影響分支定價(jià)割平面法能否求解該算例的關(guān)鍵因素。在實(shí)際應(yīng)用中，此測(cè)試結(jié)果也為使用分支定價(jià)割平面法求解MAVRPTW問題提供了一定的參考和依據(jù)。

圖2 分支定價(jià)割平面法求解大規(guī)模算例的統(tǒng)計(jì)結(jié)果

5 結(jié) 論

本文研究了帶時(shí)間窗和人力分配的車輛路徑問題(MAVRPTW)，并使用分支定價(jià)割平面法求解此問題。分支定價(jià)割平面法首先根據(jù)Dantzig-Wolfe分解技術(shù)將問題的數(shù)學(xué)模型分解為基于路徑的主問題模型和求最短路徑的子問題模型，然后利用列生成和標(biāo)簽算法在主問題和子問題兩者之間進(jìn)行迭代，并使用割平面法調(diào)整可行區(qū)域來求得主問題的最優(yōu)松弛解，最后采用基于車輛數(shù)目和弧的分支策略獲取原問題的整數(shù)解。算法中加入了兩種加速策略：雙向標(biāo)簽算法和遞減搜索空間法。通過對(duì)多組算例進(jìn)行測(cè)試，證實(shí)了模型和算法的正確性，分析了患者數(shù)目和車輛數(shù)目對(duì)結(jié)果的影響，同時(shí)也說明了割平面法具有節(jié)約存儲(chǔ)空間和提高算法效率的作用。最后，對(duì)大規(guī)模算例進(jìn)行測(cè)試的結(jié)果也為實(shí)際應(yīng)用提供了理論依據(jù)。

未來的研究中，在算法上，我們將探索精確算法與啟發(fā)式算法進(jìn)行結(jié)合，從而提高算法的計(jì)算效率。在問題模型上，我們將對(duì)MAVRPTW問題進(jìn)行擴(kuò)展，如同時(shí)考慮患者被轉(zhuǎn)移和被送回的請(qǐng)求，從而提高醫(yī)院的服務(wù)水平。

[1] 傅芳, 吳佩珊. 救護(hù)車智能化調(diào)度的現(xiàn)狀分析與思考[J]. 電腦與電信, 2019: 8-9.

[2] 劉冠男, 曲金銘, 李小琳, 等. 基于深度強(qiáng)化學(xué)習(xí)的救護(hù)車動(dòng)態(tài)重定位調(diào)度研究[J]. 管理科學(xué)學(xué)報(bào), 2020, 23(2): 39-53.

[3] JEONG Y, JEONG H, KO J. Optimal decisions on the quantity and locations of. ambulances for the timely response to emergency requests[J]. Fire Science and Engineering, 2017, 31(3): 137-143.

[4] KIM B I, KOO J, PARK J. The combined manpower- vehicle routing problem for multi-staged services[J]. Expert systems with Applications, 2010, 37(12): 8424-8431.

[5] PUREZA V, MORABITO R, REIMANN M. Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW[J]. European Journal of Operational Research, 2012, 218(3): 636-647.

[6] MUNARI P, MORABITO R. A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen[J]. Top, 2018, 26(3): 437-464.

[7] 蘇欣欣, 秦虎, 王愷. 禁忌搜索算法求解帶時(shí)間窗和多配送人員的車輛路徑問題[J]. 重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2020, 37(1): 20-30.

[8] LI Y, LIM A, RODRIGUES B. Manpower allocation with time windows and job-teaming. constraints[J]. Naval Research Logistics (NRL), 2005, 52(4): 302-311.

[9] LUO Z, QIN H, ZHU W, et al. Branch-and-price-and-cut for the manpower routing. problem with synchronization constraints[J]. Naval Research Logistics (NRL), 2016, 63(2): 138-171.

[10] LIM A, ZHANG Z, QIN H. Pickup and delivery service with manpower planning in Hong Kong public hospitals[J]. Transportation Science, 2017, 51(2): 688-705.

[11] ZHANG Z, QIN H, WANG K, et al. Manpower allocation and vehicle routing problem in non-emergency ambulance transfer service[J]. Transportation research part E: logistics and transportation review, 2017, 106: 45-59.

[12] BOLAND N, DETHRIDGE J, Dumitrescu I. Accelerated label setting algorithms for the elementary resource constrained shortest path problem[J]. Operations Research Letters, 2006, 34(1): 58-68.

[13] JEPSEN M, PETERSEN B, Spoorendonk S, et al. Subset- row inequalities applied to the vehicle-routing problem with time windows[J]. Operations Research, 2008, 56(2): 497-511.

[14] DESAULNIERS G, DESROSIERS J, Solomon M M, et al. A unified framework for deterministic time constrained vehicle routing and crew scheduling problems[M]. Boston, Fleet management and logistics. Springer, 1998: 57-93.

[15] SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265.

Branch-and-Price-and-Cut Algorithm for the Manpower Allocation and Vehicle Routing Problem with Time Windows

SU Xin-xin1, YI Ting-gang2, QIN Hu1

(1. School of Management, Huazhong University of Science and Technology, Wuhan 430074, China; 2. Joint Support Force Supply Bureau, Wuhan 430000, China)

This paper studies the manpower allocation and vehicle routing problem with time windows (MAVRPTW) and proposes a branch-and-price-and-cut algorithm to obtain its optimal solution. The algorithm first decomposes the mathematical model of the original problem into a master model based on routes and a subproblem model for the shortest path problem according to the Dantzig-Wolfe decomposition. It then employs a column generation method and a label-setting algorithm to calculate between the master problem and the subproblems iteratively. Moreover, subset-row cuts are generated to adjust the feasible region during these processes. Finally, by obtaining the optimal solution to the linear relaxation of the main problem, the algorithm adopts branching strategies based on the vehicle number and arc for the integer solutions of the problem. In order to improve the efficiency of the algorithm, we use two accelerating strategies: a bidirectional label-setting algorithm and a decremental state-space relaxation. Comparisons with CPLEX show that the algorithm performs well in terms of stability and efficiency. By carrying out extensive computational experiments, we not only analyze the influence of the number of patients and vehicles on the results, but also find that the cutting plane method is capable of improving the efficiency of the algorithm. Finally, test results of large-scale instances provide a theoretical basis for practical application.

vehicle routing problem; manpower allocation; branch-and-price-and-cut algorithm; ambulance; column generation

U116.2

A

10.19961/j.cnki.1672-4747.2021.04.016

1672-4747(2021)04-0075-12

2021-04-14

2021-05-29

2021-06-02

2021-04-14～04-21； 05-28～05-29

國(guó)家自然科學(xué)基金創(chuàng)新研究群體項(xiàng)目(71821001)；國(guó)家自然科學(xué)基金面上項(xiàng)目(71971090)；國(guó)家自然科學(xué)基金面上項(xiàng)目(71571077)

蘇欣欣(1991—)，女，漢族，博士，研究方向?yàn)檐囕v路徑優(yōu)化，E-mail：D201577825@hust.edu.cn

秦虎(1980—)，男，漢族，湖北武漢人，教授，研究方向?yàn)檐囕v路徑優(yōu)化，E-mail：tigerqin@hust.edu.cn

蘇欣欣，伊廷剛，秦虎. 分支定價(jià)割平面法求解帶時(shí)間窗和人力分配的車輛路徑問題[J]. 交通運(yùn)輸工程與信息學(xué)報(bào)，2021, 19(4): 75-86.

SU Xin-xin, YI Ting-gang, QIN Hu. Branch-and-Price-and-Cut Algorithm for the Manpower Allocation and Vehicle Routing Problem with Time Windows[J]. Journal of Transportation Engineering and Information, 2021, 19(4): 75-86.

(責(zé)任編輯：劉娉婷)