基于改進分支定價算法的ASC車輛路徑問題

周 紅，朱 瑾

（上海海事大學物流科學與工程研究院,上海 201306）

0 引言

自主駕駛無人跨運車(Autonomous Straddle Carrier，ASC)是一種應用在自動化集裝箱碼頭上的移動機器人，依靠人工智能技術能夠實現自主定位、自主導航、面對突發狀況能夠做出智能決策，并且能夠自主規劃出集裝箱水平運輸的最優路徑[1]。AGV與ASC都是自動化集裝箱碼頭上的水平運輸車輛，主要的區別在于ASC不需要與岸橋和自動軌道吊直接交互，可以獨立完成集裝箱的裝卸工作，裝卸效率高。ASC的車輛路徑問題就是為每臺ASC尋找一條可行且高效的路徑，使ASC完成一系列的集裝箱轉運工作。由于涉及到的作業量大、ASC數量多且碼頭環境復雜，ASC車輛路徑問題受到越來越多的關注。

基于ASC作業的獨立性，可以將ASC車輛路徑問題建模為帶硬時間窗的同時取送貨問題（PDPTW）。關于車輛路徑問題的求解算法，已經有許多學者進行了深入研究。例如，姚錦寶等[2]用改進的蟻群算法對同時取貨送貨車輛路徑問題進行求解，賈方方等[3]采用改進的粒子群優化算法對同時取貨送貨車輛路徑問題進行求解，陳秀娟等[4]用改進的蟻群算法求解了逆向物流中的車輛路徑問題，武小平等[5]設計遺傳算法求解了不確定配送條件下的車輛路徑問題。文獻[6，7]提出了基于禁忌搜索和導引式局部搜索的混合式啟發式算法求解同時取貨送貨問題，文獻[8]提出一種混合遺傳算法求解了帶硬時間窗的車輛路徑問題，但這些方法都是基于近似的方法，能夠得到可行解但并不是最優解。近年來關于VRP及其一系列變體問題的研究大都將其轉化為大規模整數規劃問題來求解。在精確算法的相關研究中，最基本的方法為分支定界算法，雖然能夠從理論上保證在有限時間內獲得最優解，但在實際計算中存在著計算耗時巨大的情況。Desrosiers等[9]首次提出將列生成算法與分支定界算法結合起來對車輛路徑問題進行求解，Barnhart等[10]將其命名為分支定價算法。文獻[11]針對自動化集裝箱碼頭ASC的車輛路徑問題，以車輛運輸成本最低為目標建立優化模型，提出了一種基于分支定界和列生成算法的精確算法，但在模型中沒有考慮ASC的載荷量約束，并且子問題的求解依賴于主問題的對偶變量，每次迭代需要重新對子問題建模，影響算法的求解效率。文獻[12]提出了ASC車輛路徑問題的多目標優化模型，用分支定價算法求解，并與單目標車輛路徑問題對比，驗證了多目標模型的有效性和靈活性。車輛路徑問題的子問題通常是帶資源約束的最短路徑問題（ESPPRC）。文獻[13]提出了K循環消除方法提高對子問題松弛問題下界的約束。文獻[14，15]分別提出了標簽算法和列生成算法，并應用到車輛路徑問題中，標簽算法通過迭代過程對標簽逐步修正，可以在搜索過程中刪除大量標簽，提高算法效率，用列生成算法求解了ESPPRC的松弛問題。文獻[16]引入了子集-行不等式，極大地改進了分支定價算法中每個節點的下界，但增加了定價問題的復雜性。文獻[17]提出了一種基于隱枚舉法的精確求解方法，極大地縮小了搜索空間。

在分支定價算法的框架中設計合理的加速策略以提高車輛路徑問題中定價子問題的求解效率仍然是目前的研究熱點。基于此，本文以最小化ASC總行駛距離為目標，考慮ASC的載荷量以及每個作業點的時間窗和需求量等因素，建立帶硬時間窗的ASC車輛路徑問題的混合整數規劃模型，并改進分支定價算法求解模型，即將脈沖算法嵌入列生成算法提高子問題的求解效率。最后通過求解不同規模的算例驗證了模型和算法的有效性，并對影響算法效率的相關因素進行了靈敏度分析。

1 問題描述與數學模型

1.1 問題描述

ASC車輛路徑問題可以描述為將集裝箱的運輸任務分配給ASC，以滿足每個作業點（提箱點/卸箱點）的時間窗約束、ASC的載荷量約束和ASC的數量約束。假設前一個任務的卸箱點為后一個任務的提箱點，并以最小化ASC總行駛距離為目標函數，將ASC車輛路徑問題建模為帶硬時間窗的同時取送貨問題（PDPTW）。

為符合PDPTW的數學框架，簡化搜索空間結構，首先根據自動化集裝箱碼頭的堆場環境圖構建ASC-PDPTW運輸網絡，用有向圖G=（P，A）表示，由作業點集P={0，1，2，...，n，n+1} 和弧集A組成，作業點0和n+1表示車場，n+1為虛擬節點，代表終點，定義節點n到n+1的距離為0，其他n個作業點集記為N={1，2，...，n}。ASC的集合記為V={1，2，...，k}，每個作業點i（i∈N）都有給定的需求量di、所需的作業時間si和時間窗[ai，bi]，ai，bi分別表示該作業的最早開始時間和最晚開始時間，ASC早到必須等待，但不能在最晚作業時間bi之后到達。其中車場的時間窗[a0，b0]=[an+1，bn+1]表示作業完成的周期。ASC的最大載荷量為q，tij表示ASC從作業點i行駛到作業點j(i，j∈N)的行駛時間，cij表示ASC訪問運輸網絡中每個弧段的成本（行駛距離）。

假設q，ai，bi，di，cij均為非負整數，tij，si為正整數。引入兩個決策變量x和s，對每個弧段(i，j)和每一輛車k，定義

其中i≠j，i≠n+1，j≠0，sik定義為車輛k在i點開始作業的時間，若k不在i點作業則sik無意義，本文假設a0=0，即對于所有的ASC均有s0k=0。

本文所解決的問題是改進分支定價算法求解ASC最優行駛路徑，在各個作業點的時間窗內完成所有的運輸任務，并使得ASC總行駛距離最短。

1.2 數學模型

以最小化ASC總行駛距離為目標建立ASC-PDPTW混合整數規劃模型。

其中約束條件(7)可以線性化為：

Mij是一個很大的常數，可以縮小到max{bi+tij-aj}，{i，j}∈A。

式(1)表示最小化ASC總行駛距離，式(2)保證每個作業點只能被一輛ASC訪問且僅訪問一次，式(3)表示每輛ASC的載荷量不能超過q，式(4)～式(6)確保每輛ASC由車場出發，依次完成作業后仍回到車場，式(7)表示ASC從作業點i行駛到作業點j的時間約束，式(8)表示ASC到達作業點的時間必須滿足時間窗約束，式(9)表示若第k輛ASC從i行駛到j，則xijk=1，否則為0，式(10)給出了ASC數量上限。

2 模型分解

建立的模型中只有賦值約束(2)是車輛耦合約束，其余的約束條件均分別處理各ASC。因此可以將模型化為具有對角結構的線性規劃問題，然后用列生成算法求解，從Dantzig-Wolf分解原理出發，將模型分解為帶資源約束的最短路徑定價子問題和變量數目很大的主問題。

2.1 ASC-PDPTW主問題

設Ω為車輛k(k∈V)的可行路徑集合，隨著問題規模的增大，可行路徑的數目呈現爆炸式增長，因此不能把所有的可行路徑都在模型中顯性的表示出來。本文從單純形法的理論出發，將問題轉化為求解滿足約束的若干條可行路徑，并使得目標函數值最小。主問題即為包含這若干條可行路徑的集合劃分問題。

設Ω為車輛k(k∈V)的可行路徑集合，二進制決策變量xkijp=1表示車輛k在它的可行路徑集合中的路徑p(p∈Ω)中從i到j，否則為0，ykp表示車輛k是否經過路徑p，則有：

通過xkijp可以定義一條路徑的花費為；車輛k訪問客戶點i的次數為aki，?k∈V,?i∈N,?p∈Ω。

在列生成算法中，并不是所有的列都顯性的表達出來，主問題的列集合僅限于已經生成的列，在所有可行路徑集合中找到滿足條件和目標函數的路徑Ω'，稱為受限主問題(Restricted Master Problem，RMP)。RMP的模型表示如下：

2.2 ASC-ESPPRC定價子問題

ASC車輛路徑問題的子問題是帶資源約束的最短路徑問題（ASC-ESPPRC），是NP難問題。為了找到向RMP可行路徑集Ω'中添加的路徑，ASC-ESPPRC定價子問題是在考慮約束(3)至(9)的條件下最小化可行路徑的節約成本，由原問題分解得到的模型為：

3 改進的分支定價算法

本文從包含部分路徑的RMP出發，采用脈沖算法求解ASC-ESPPRC定價子問題，將子問題的解為負的列加入RMP重新求解，如此迭代直到子問題的解為非負則得到了RMP的最優解。將得到的解采用弧分支策略得到最優整數解。圖1是改進分支定價算法（Improved branch-andprice algorithm，IBP）的流程圖。

圖1 IBP算法流程圖

3.1 脈沖算法

脈沖算法是通過對已得到的部分路徑遞歸搜索，在擴展過程中部分路徑所包含的節點會被不斷擴展到最終作業點或剪枝不滿約束條件的路徑。良好的定界策略能夠大大縮小搜索空間，提高算法的求解效率，脈沖算法過程中包含三個不同的剪枝策略。圖2為脈沖算法流程圖。

圖2 脈沖算法流程圖

3.1.1 符號說明

G：訪問作業節點（路徑）有向圖；

ns：脈沖算法的起始節點；

ne：脈沖算法的終止節點；

S：當前節點的路徑信息；

S*：獲得的最優路徑；

r(S)：當前路徑節約成本的累加和；

q(S)：當前路徑載荷量的累加和；

t(S)：行駛到當前路徑花費的時間；

Δ：定界算法中時間變化步長；

[tu，td]：定界過程的時間范圍；

ASC每行駛到一個節點，就會運行脈沖算法進行遞歸搜索。執行上述三個不同的剪枝策略嘗試縮小搜索空間，最后到達節點ne的脈沖包含了從ns到ne的所有信息。

3.1.2 脈沖算法流程

針對ASC-ESPPRC定價子問題，求解過程可以分為兩個階段。首先通過定界（Bound）算法計算出到達每個節點的最低成本（cost），該過程稱為定界。然后運行脈沖（Pulse）算法進行路徑搜索。此時通過定界算法得到的每個節點的最低成本用于剪枝，能夠去掉不好的路徑。

求解過程如圖3所示。a)～d)將當前獲得的部分路徑S、當前路徑節約成本r(S)、當前載荷量累加和q(S)和當前花費的時間t(S)初始化。e)運行定界算法確定ASC行駛到各個節點時的最低成本，如3.2.2所述。f)執行脈沖過程。通過不同的剪枝策略得到最優路徑S*，如3.2所述。最后輸出最優路徑。

圖3 脈沖算法

3.2 脈沖過程剪枝策略

脈沖過程主要包括三個剪枝策略：

If_Feasible：用于檢查ASC行駛到當前節點時是否滿足約束條件；

Check_Bound：用于檢查到達當前節點時的cost是否小于等于通過Bound算法求得的最低cost，若不是則該條路徑被剪枝；

Rollback：用于回溯操作，即檢查是否有滿足三角不等式的節點，使得比原來的路徑成本更低，若有則原來的路徑被剪枝。

脈沖剪枝策略的執行過程如圖4所示，其中Ψ+(ni)表示從當前節點出發后的入度節點。

圖4 脈沖剪枝策略

3.2.1 檢查約束剪枝策略

當ASC到達當前節點時，首先檢查是否滿足模型的約束條件，即時間窗約束，載荷量約束以及完成任務的周期約束。運行If_Feasible剪枝策略，當行駛到節點ni時檢查是否形成循環、是否超出載荷量q以及是否違反時間窗約束。若其中任何一個不滿足，這條路徑為不可行路徑，將被剪枝。

為檢查當前路徑是否有循環，本文設置一個標記函數標記在當前路徑中已經訪問過的節點，若訪問過則該部分路徑被剪枝。對于載荷量約束，若ASC在行駛到下一節點時載荷量超出，則該部分路徑被剪枝。對于時間窗約束，若ASC在bi后到達則該部分路徑被剪枝，若在ai前到達則需要等待到ai才可以作開始作業。

3.2.2 定界剪枝策略

定界算法用于求解ASC行駛到不同節點時，在不同最晚到達時間下的最低成本，最終得到ASC在不同時間到達該點的成本矩陣。定義為邊界值的上界，隨著路徑的變化更新，運行定界算法后得到每個節點ni∈N在當前的時間t(S)下的最小節約成本，記為。定界算法的執行過程如圖5所示。最低成本矩陣記為，其中為達到最低成本時的時間。

圖5 定界策略

tu是訪問車場的時間窗上界，Δ是非負的時間步長，訪問節點的最晚到達時間從tM開始每次減少一個時間步長，直到減小到td。即當訪問節點ni時，首先設置到達該節點的最晚到達時間為t(S)=tM-Δ，求得的最優解為當前最小節約成本的下界。若此時t(S)≠td，則繼續設置該節點的最晚到達時間為t(S)=tu-Δ，計算最優解。此后的過程重復上述操作，直到當前訪問節點的t(S)=td。此時得到不同節點在不同最晚到達時間下的最小成本矩陣。

3.2.3 回溯剪枝策略

由于脈沖算法是通過遞歸的方式尋找路徑，因此采用深度優先搜索尋找路徑節點。深度優先搜索的缺點是選擇了分支定界樹上的分支后必須遍歷完，但不一定得到最優解，此時需要返回重新搜索。本文采用回溯策略，在獲得部分路徑的最后一個節點就執行回溯操作，尋找是否有更優的路徑，若有則替換當前最優部分路徑。如圖6所示，假設有部分路徑Ssi從節點ns出發到達ni，然后訪問節點nl，最終到達nk。回溯剪枝策略會在重新判斷到達終點前選擇的節點，S'SK為回溯操作后可選擇的另一條路徑，由Ssi直接擴展到節點ni，不經過nl直接到達nk。此時需要進一步判斷路徑S'SK是否滿足以下約束：1)S'SK?SSK；2)t(S'SK)≤t(SSK)；3)r(S'SK)≤r(SSK)；4)q(S'SK)≤t(SSK)。

圖6 回溯剪枝策略示意圖

由上述分析易知，約束1)，4)顯然滿足，因此只需要判斷約束2)，3)是否滿足。若滿足則用S'SK替換SSK，即原路徑被剪枝。

3.3 列生成算法與整數解

由列生成求解得到的RMP的最優解可以是整數或浮點數，若為整數則與當前上界相比較，小于當前上界則更新上界值并剪枝。對于浮點數解，若小于當前上界則在求得的變量中選擇最接近0.5的變量進行分支，得到兩條路徑S1和S2，S1中包括弧段(i，j)，S2不經過i點到達j，刪除當前節點同時將分支節點加入分支定界搜索樹。若大于當前上界則不需要分支。

4 實驗結果分析

本實驗使用Eclipse JDK 4.3.0版本，在Java多線程中調用Cplex求解模型，實現了本文IBP算法。進行實驗的計算機參數為Inter(R) Core(TM)i5-8250U CPU @ 1.60GHz 1.80GHz。

實驗首先在Solomon標準測試集中選取5組小規模算例，分別用分支定界算法和IBP算法求解，并用本文IBP算法求解得到了部分較大規模Gehring&Homberger算例的最優解，同時對影響算法效率的相關因素進行靈敏度分析。

4.1 對比實驗及小規模算例測試結果

在Eclipse中編寫分支定界算法，調用Cplex求解小規模算例，并與改進的分支定價算法求解結果對比。從Solomon標準測試集中選取5組小規模算例進行測試，測試結果如表1所示。圖7為相同規模下傳統分支定界算法與IBP算法求解時間的對比。

表1 分支定界算法IBP算法小規模算例結果對比

圖7 分支定界算法與IBP算法效率對比

通過表1可以看出兩個算法求解的ASC行駛總距離基本吻合，平均誤差小于1，且IBP算法求解時間比分支定界算法平均值短11.37s。通過圖7更可直觀看出，隨著問題復雜程度的上升，IBP算法效率高于分支定界算法。

選取不同類型的算例測試算法的有效性。C類算例表示作業點集中在部分區域，R類算例表示作業點隨機分布，RC類算例表示作業點既有集中分布、也有隨機分布的。表2為改進的分支定價算法在不同測試集下的計算結果。表3列出了三類算例的部分ASC車輛行駛路徑。

表2 改進的分支定價算法求解結果

表3 IBP算法求解部分算例路徑

由表2、表3可得，隨著問題規模的增加，迭代次數不斷增加，即子問題求解次數增加。求解時間R類＜RC類＜C類，即作業點越分散計算時間越短。作業點數量相同條件下，隨機分布的R類算例，路徑數比C類算例和RC類算例多，每條路徑中訪問的作業點數量少，需要的ASC數量多，C類算例中每條路徑的作業點數目分配較均勻，所需的ASC數量較少。即作業點越分散求解時間越短，但所需ASC數量越多。

4.2 較大規模算例求解結果

在Gehring&Homberger數據集中選取了7組較大規模的C類算例求解，作業點規模為200、400、600，設置可接受的最大求解時間為2小時，定界策略中的時間步長。實驗結果如表4所示。

表4 較大規模算例求解結果

由表4可得，IBP算法能夠用于求解一些較大規模的ASC車輛路徑問題，并且能在不同規模算例和可接受的時間范圍內求得最優解。問題規模與求解時間成正比，但得到的可行路徑數目與求解時間不一定成正比，這與算例本身的數據復雜程度有關。可行路徑少的算例中每條路徑的作業點較多，ASC的利用率較低；可行路徑多的算例中ASC利用率較高。

4.3 靈敏度分析

在IBP算法中，子問題求解過程中定界策略對求解效率起關鍵作用，另外ASC的載荷量也會直接影響求解結果。因此分析定界策略中不同時間步長與不同ASC載荷量對算法求解效率的影響。為保證實驗的一般性，從Solomon標準測試集中選取6組作業點規模相同的算例進行實驗。分別分析定界策略中不同的時間步長和ASC不同載荷量對算法求解效率的影響。

1）定界策略的時間步長

為研究不同時間步長下的定界策略對算法的效率影響，在其他參數不變的條件下，每組算例依次設置步長為4、8、12、16、20進行測試。實驗結果如表5所示。

表5 不同時間步長靈敏度分析

由表5縱向來看，隨著算例規模的增加和問題本身復雜程度的上升，算法的求解時間不斷增加，但都能夠在0.5小時內得到最優解；橫向來看，上述6個算例從Δ=4增加到Δ=20，算法求解時間逐漸減少，求解效率分別提升了36%、48%、40%、16.4%、69%和42.7%。驗證了時間步長對算法效率的影響，時間步長越大得到的成本矩陣規模越小，求解時間越短。

2）ASC不同的載荷量

為研究ASC在不同載荷量下對實驗結果的影響，選取6組算例進行測試，在其他參數不變的情況下，設置可接受的求解時間為2小時以內，分別設置ASC載荷量為200、400、600、800和1000進行測試。實驗結果如表6所示。

表6 ASC不同載荷量靈敏度分析

由表6 可得，對于數據簡單的小規模算例，如c101.100和c102.100，不同載荷量下得到的最優路徑相同，隨著ASC載荷量的增加，求解時間呈減少趨勢，最大差值為1.487s和4.757s，ASC不同載荷量對求解時間的影響小于5s。對于數據較復雜的算例，如c201.100和c221.200，q＜600時無法在可接受時間范圍內得到最優解，q≥600時能得到最優解，在q=600時求解時間最短，此后得到的路徑數趨于穩定，即隨著ASC載荷量的增大，最優解趨于穩定。對于較大規模算例，如c121.200和c221.200，c121.200在不同載荷量下得到最優解的時間差值小于6s，c122.200由q=400增加到q=600時得到最優解，隨著q的增加求解時間基本穩定。由上述分析可得，ASC載荷量越大算法的求解效率越高，對于數據簡單的算例對求解時間的影響小于7s，對于數據復雜的算例，ASC達到一定的載荷量后得到的最優路徑趨于穩定。驗證了ASC不同載荷量對算法效率的影響，且不同的算例能夠求得最優的ASC載荷量。

5 結語

本文建立了自動化集裝箱碼頭ASC-PDPTW混合整數規劃模型，提出了一種求解ASC車輛路徑問題改進的分支定價算法。用脈沖算法求解定價子問題并嵌入分支定價算法框架中，定界過程中包含三種剪枝策略，用于有效縮小解搜索空間，提高求解效率。設計了小規模算例的對比實驗；求解并分析了較大規模算例的實驗結果，并進一步對不同的時間步長和ASC載荷量進行靈敏度分析。作業點在20至100內小規模算例的求解時間比傳統分支定界算法平均提高11.37s；作業點在200至600的較大規模算例能夠在可接受時間范圍內求得最優解，即該算法不僅能夠更加快速的求解小規模算例，也能夠在可接受時間范圍內求解一些較大規模算例。在靈敏度分析中，隨著定界策略中時間步長增加到20，求解效率平均提高42.01%；隨著ASC載荷量的增加，對于數據簡單的算例得到的最優解基本穩定，對于數據復雜的算例，載荷量越大求解效率越高，在達到最優載荷量后最優路徑不再變化，求解時間會增加。實驗結果驗證了本文所建立模型的可行性，提出的IBP算法能夠有效提高求解ASC最優行駛路徑的效率。