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

蘇欣欣，伊廷剛，秦 虎

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

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

(1. 華中科技大學，管理學院，武漢 430074；2. 聯勤保障部隊供應局，武漢 430000)

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

車輛路徑問題；人力分配；分支定價割平面法；救護車；列生成

0 引 言

隨著我國社會經濟的快速發展，人們對自身健康的關注意識逐漸提高，尤其對醫療救助方面的相關服務提出了更高的質量要求。人力和救護車是維持醫院正常運轉的重要醫療資源，合理調度人力和救護車不僅是滿足患者健康需求的重要因素，更是提高院前服務水平的關鍵。

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

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

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

圖1 MAVRPTW問題的示例

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

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

1 數學模型

MAVRPTW是在車輛路徑問題的基礎上加入了人力分配問題，這會使得問題更加復雜。它不僅需要考慮車輛的路線和調度決策，還要決定每輛車分配的輔助人員數目。從數學模型的角度來看，帶人力分配的模式會給問題帶來更多的決策變量，也會使得原路徑優化問題增加更多關于人力分配的復雜約束。為構建數學模型，定義相關參數如下：

決策變量如下：

根據上述參數，本文描述的問題可歸結為如下數學模型：

2 Dantzig-Wolfe分解

上述的數學模型中含有大量的約束和變量，這使得計算過程相當復雜。為了求得該問題的最優解，我們使用Dantzig-Wolfe分解技術將該數學模型分解為一個基于可行路徑的Set Packing主問題和一個帶資源限制的最短路徑子問題。

2.1 Set Packing主問題模型

決策變量：

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

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

2.2 子問題模型

3 分支定價割平面法

本文使用分支定價割平面法來求得主問題的最優整數解。其基本原理是利用列生成和標簽法來搜索隊列中節點的線性松弛最優解并在此過程中利用割平面法加入有效不等式提高松弛解的下界，并使用分支定界算法來對節點進行分支搜索。在搜索過程中，如果節點的下界大于等于全局上界，那么這個節點可以刪除；如果節點的下界小于全局上界，解為整數時更新全局上界，解為分數時要根據分支策略進行分支。當隊列為空或者全局下界等于全局上界時，算法終止。下面本文將詳細描述算法的各個部分。

3.1 初始解的生成

本文采用貪婪算法生成初始解。假設車輛數目足夠，算法最初使每一輛救護車對應一個空路徑，隨機分配輔助人員，然后循環將患者插入這些路徑中的最優為止，保證插入該患者后路徑的費用最少，直至沒有患者可以插入到路徑中為止，那么一個初始解完成，并將其作為樹的根節點。

3.2 標簽算法

為了提高算法的速度，使用占優準則來減少在標簽算法中擴展的標簽數量。在已有的標簽中，占優準則可以確定一個子集，保證最優路徑在這些占優標簽中產生。不在子集中的標簽，即被占優的標簽，將會被丟棄，防止做無效擴展，從而加快算法速度。

3.3 遞減搜索空間

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

3.4 割平面法

3.5 分支策略與整數解

4 實驗結果及分析

4.1 算例說明

分支定價割平面法使用Java語言進行編寫，并使用CPLEX(Studio1251)求解受限主問題。運行環境采用Intel(R)Core(TM)i7-4790 CPU @ 3.60GHz(8.00 GB內存)，且實驗中的計算時間以秒為單位進行統計。

按照時間窗的緊湊程度和點的分布規律，Solomon測試算例被劃分為6種類型。我們在每個類型中隨機選擇4個算例，因此本文中一共有24個標準測試算例。由于每一個標準測試算例包含100個患者，為了更全面、更充分地研究分支定價割平面法的性能，對每一個算例選取部分數據生成具有不同患者數目的測試算例，并定義含有0～20個患者的算例為小規模算例，含有20～50個患者的算例為中規模算例，含有50～100個患者的算例為大規模算例。

4.2 與CPLEX對比實驗

為了驗證分支定價割平面法的準確性，將其與CPLEX進行比較，并采用小規模算例進行測試。針對每一個標準算例，選擇每一個算例的前11個點和前21個點，分別組成含有10個患者和20個患者的小規模算例。設置分支定價割平面算法和CPLEX運行每一個算例的時間限制為7 200s，且只運行一次。

表1 小規模算例求解結果(10個患者、2輛車)

20個患者、4輛車的小規模算例的求解結果如表2所示。從實驗數據可知，在7 200s內，只有10個算例CPLEX能求得最優解。對比獲得的最優解，分支定價割平面法的求解結果與之相同且求解時間遠低于CPLEX的求解時間。對于CPLEX未能求出最優解的14個算例，分支定價割平面法均以很短的時間求出了最優解。實驗結果說明了分支定價割平面法的正確性，并且相比CPLEX具有一定的效率。

表2 小規模算例求解結果(20個患者、4輛車)

4.3 靈敏度分析

由于患者數目和車輛數目直接影響分支定價割平面法的計算結果，因此本文將分析這兩個參數的變化對計算結果的影響。

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

實驗結果表明，當患者數目一定時，增大車輛數目能夠降低轉移患者的總費用，同時也提高了問題的復雜度，使得算法的求解時間增長。當車輛數目一定時，患者數目的增長，增加了轉移患者的總費用，同樣也使得問題的求解難度增強。

表3 中規模算例求解結果(30個患者)

表4 中規模算例求解結果(40個患者)

4.4 割平面法的測試與分析

本文提出的精確算法是在分支定價的基礎上加入了割平面法，從而達到提高松弛解下界，有效減少分支定界中分支的作用。為了驗證割平面法的有效性，分別將分支定價割平面法和不包含割平面法的分支定價算法對大規模算例進行了測試。測試算例的規模為50個患者和15輛車，實驗結果統計于表5中。

表5 大規模算例求解結果(50個患者、15輛車)

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

4.5 分支定價割平面法求解規模的測試

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

圖2 分支定價割平面法求解大規模算例的統計結果

5 結 論

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

未來的研究中，在算法上，我們將探索精確算法與啟發式算法進行結合，從而提高算法的計算效率。在問題模型上，我們將對MAVRPTW問題進行擴展，如同時考慮患者被轉移和被送回的請求，從而提高醫院的服務水平。

[1] 傅芳, 吳佩珊. 救護車智能化調度的現狀分析與思考[J]. 電腦與電信, 2019: 8-9.

[2] 劉冠男, 曲金銘, 李小琳, 等. 基于深度強化學習的救護車動態重定位調度研究[J]. 管理科學學報, 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] 蘇欣欣, 秦虎, 王愷. 禁忌搜索算法求解帶時間窗和多配送人員的車輛路徑問題[J]. 重慶師范大學學報(自然科學版), 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

國家自然科學基金創新研究群體項目(71821001)；國家自然科學基金面上項目(71971090)；國家自然科學基金面上項目(71571077)

蘇欣欣(1991—)，女，漢族，博士，研究方向為車輛路徑優化，E-mail：D201577825@hust.edu.cn

秦虎(1980—)，男，漢族，湖北武漢人，教授，研究方向為車輛路徑優化，E-mail：tigerqin@hust.edu.cn

蘇欣欣，伊廷剛，秦虎. 分支定價割平面法求解帶時間窗和人力分配的車輛路徑問題[J]. 交通運輸工程與信息學報，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.

(責任編輯：劉娉婷)