基于禁忌搜索的戰略投送樞紐選址研究

畢海玲，張旭濤，傅 鈺

(軍事交通學院 裝備保障系，天津 300161)

?

● 基礎科學與技術 Basic Science & Technology

基于禁忌搜索的戰略投送樞紐選址研究

畢海玲，張旭濤，傅 鈺

(軍事交通學院 裝備保障系，天津 300161)

為解決戰略投送樞紐的選址與分配問題，將戰略投送網絡選址問題抽象為軸輻式多式聯運問題，建立帶時間約束的0-1整數規劃模型。針對模型的復雜性，設計一種基于特定最短路算法和禁忌搜索的啟發式算法，運用仿真算例驗證算法的收斂性和有效性。研究表明，該算法能有效對模型求解，可為國防交通建設規劃提供決策參考。

戰略投送；樞紐選址；整數規劃；禁忌搜索；最短路算法

戰略投送是指綜合運用國防戰略交通運輸力量，采用多種輸送方式，將戰略縱深軍事力量及裝備投送到遂行任務的地區，以在特定的區域內快速聚焦軍事力量，形成有利態勢，爭取行動主動權的軍事行動[1]。戰略投送在實施過程中，一般首先將人員和物資通過摩托化機動的方式在國防交通樞紐處集結，然后利用國防交通干線通過多種運輸方式集中運輸到離任務點最近的交通樞紐，最后根據任務需求對人員和物資進行分散運輸(摩托化機動)到達配置地域。戰略投送樞紐的選址與分配問題是國防交通規劃與調度中面臨的一個重要問題。現有的戰略投送研究一般屬于定性研究[2-3]，傳統樞紐選址問題研究大多只針對單一運輸網絡建立總成本最小規劃模型[4]，現有多式聯運研究多集中在聯運路線的選擇方面[5]，樞紐選址問題的研究較少，且一般只考慮優化網絡成本。多式聯運中節點之間存在多種運輸方式，節點之間同一方向含有多重邊，使得多式聯運樞紐選址問題變得更為復雜。現有研究[6-7]在求解分配子問題時一般是將其轉化為無容量約束的指派問題，由于在優化過程中需要反復多次求解子問題，運算量很大，算法效率不高。另外，戰略投送對運輸時間有比較高的要求，在樞紐選址建模時必須考慮時間約束，模型求解較為困難。

本文將戰略投送常規樞紐選址問題抽象為帶時間約束的多式聯運軸輻式網絡樞紐選址問題，建立無容量約束多分配0-1整數規劃模型。針對模型參數變量多、組合優化難以定量求解的特點，將問題分解為樞紐選址問題和交通流分配兩個子問題。其中選址問題采用禁忌搜索算法，而對于分配問題，通過節點間的路權比較以及是否滿足時間約束，將多邊網絡簡化為單邊網絡，采用有限迭代的Floyd最短路算法整體求解，使整個算法的計算量大大減少。

1 問題描述及假設

戰略投送中，采用多種運輸方式對人員和物資進行輸送，其過程屬于多式聯運[8]。其中：摩托化機動看作多式聯運中的公路運輸，干線運輸過程采用鐵路運輸或公路運輸；戰略投送網絡可抽象為軸輻式網絡結構[9]，人員和物資的出發點以及最終到達的各配置地域看作網絡中的非樞紐節點，集結點和配置中心可看作網絡中的樞紐節點。本文研究基于以下假設：①樞紐網絡為完全網絡；②樞紐間采用干線運輸時，由于規模效應，運輸成本和成本存在一個折扣系數；③一個非樞紐節點可以與多個樞紐節點相連，非樞紐節點間不能直接相連；④任意起訖點的人員物資運輸最多經過兩個樞紐進行轉運；⑤在采用干線運輸時需要轉運，轉運成本和時間計算在樞紐對之間；⑥樞紐和干線運輸無容量限制。

2 模型構建

2.1 模型參數

2.2 決策變量

2.3 整數規劃模型

基于以上模型假設和模型參數設置，建立戰略投送樞紐選址整數規劃模型：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

?i,j,k,m∈N,s∈S

3 基于特定Floyd最短路的禁忌搜索算法

樞紐選址分配屬于組合優化問題，已經被證明為NP難問題[10]，采用啟發式算法求解是一種普遍的做法。在常見的啟發式算法中，禁忌搜索[11]能模擬人類的思考過程，利用短期和長期禁忌表，避免迂回搜索并能跳出局部最優，對解決此類復雜的組合優化問題非常有效。在搜索過程中，涉及反復多次求解給定樞紐集時，如何確定非樞紐點與樞紐點之間的分配關系以及起訖點間的運輸路線與運輸方式的問題，本文設計了一種特定Floyd最短路算法整體求解。

3.1 特定Floyd最短路算法

Floyd最短路算法是用于整體求解給定權重簡單圖最短路的最常用方法。由于戰略投送運輸網絡中節點間同一方向存在兩種運輸方式，屬于復雜網絡，需要對網絡進行特定簡化。另外，模型中含有時間約束，當以成本為權重的最短路滿足時間約束時，以該最短路作為問題的滿意可行解。當不滿足時間約束時，選擇以時間為權重求解最短路問題，作為問題的滿意可行解。如以時間為權重求解得最短路仍不滿足時間約束，則該樞紐選擇方案不可行。

設p個樞紐構成的樞紐集為H={h1,h2,…,hp}，構造圖G=(N,E)，其中N={1,2,…,n}，eij∈E，取i→j權重最小的邊，于是含有多重邊的多式聯運網絡可以簡化成不含多重邊的簡單圖。令網絡的權矩陣為D=(dij)n×n，當以成本最小化求解最短路時，有

(8)

當以時間最小化求解最短路時，有

(9)

令網絡的路由矩陣為R=(rij)n×n，其中rij=j為節點i到節點j最短路所經過的第一個點的下標。Floyd最短路算法的基本步驟：

(1)輸入權矩陣D(0)=D，R(0)=R。

傳統Floyd算法的復雜度為O(n3)，由于模型假設非樞紐節點只能與樞紐節點連接，如果將樞紐節點與非樞紐節點區分，上述迭代過程僅需要迭代p次即可。由于戰略投送任意節點間的交通流為對稱交通流，i→j與j→i是同一條路線，該模型中分配問題算法的實際復雜度為O(pn2/2)。

3.2 禁忌搜索算法設計

(1)解及鄰域的構造。隨機產生一組節點作為初始樞紐集，采用將一個非樞紐點與樞紐點對換的方法來構造鄰域空間。

(2)評價函數。采用式(1)作為解的評價函數，搜索過程根據評價函數優劣進行移動。

(4)禁忌頻率。將每次運行算法時節點被禁忌的頻率記錄下來并累加作為一種長期記憶，在產生下一次運行算法的初始解時避開那些禁忌頻率高的節點，以使搜索向未搜索過的解空間區域進行。

(5)特赦準則。若某個禁忌候選解優于當前最好解，則解禁此候選解并將其作為當前解和最優解；若候選解均被禁忌，且不存在優于最優解的候選解, 則對候選解中最佳的候選解進行解禁作為當前解。

3.3 算法基本步驟

步驟1 設置禁忌表為空，設置算法的最大運行次數MaxRun，每次運行最大迭代次數MaxIteration和最優解連續不變的迭代次數MaxCount，設置節點禁忌頻率矩陣對應頻率NodeFrequency=0。

步驟2 產生初始解StartingSolution，令當前解CurrentSolution=StartingSolution，最優解BestSolution=CurrentSolution。

步驟3 產生當前解的鄰域，求解鄰域內所有樞紐集的最短路問題，若存在可行解，對可行解根據評價函數進行排序，作為待選解，轉步驟4；若不存在可行解，選擇評價函數最小的樞紐集作為當前解，轉步驟7。

步驟4 最好的待選解是否優于最優解，若是則轉步驟7，若否則轉步驟5。

步驟5 所有解是否都被禁忌，若是選擇最好的候選解作為當前解，若否將非禁忌的最好候選解作為當前解，轉步驟7。

步驟6 將該解作為當前解，并更新最優解，更新禁忌表和禁忌頻率，迭代次數Iteration+1，轉步驟8。

步驟7 更新當前解，更新禁忌表和禁忌頻率，迭代次數Iteration+1，最優解連續不變的迭代次數Count+1。

步驟8 若迭代次數和最優解連續不變的迭代次數均未達到限制，則繼續迭代；若已達到限制，運行次數run+1，并轉步驟9。

步驟9 將禁忌頻率高的節點排除在外，產生新的初始可行解，轉步驟2。

步驟10 運行次數達到最大限制，結束算法，輸出結果。

4 算例

本文算例數據采用仿真方法產生，產生數據時滿足一定規則，以符合實際情況。設置參數值時參考了相關多式聯運樞紐選址文獻[6-7]中的數值與方法。

4.1 數據產生方法

以15個戰略投送節點為例介紹數據產生方法，節點間橫縱坐標從[0，1 000]中抽樣產生(見表1)。

表1 網絡節點編號及坐標

4.2 算法收斂性與有效性檢驗

對上述15節點投送網絡算例進行求解，禁忌搜索算法中的禁忌長度設為7，禁忌頻率設為10。設共建5個樞紐，當初始樞紐集為[2，6，12，14，15]時，記錄迭代過程中當前解目標函數的變化情況并繪圖(如圖1所示)。由圖1可知，在迭代初期的搜索過程中，目標函數迅速收斂，然后在第11次時，目標函數有所上升，這是由于禁忌搜索算法允許接受劣解，并不總是選擇當前最優解作為當前解進行搜索，從而具有跳出局部最優解，在新的區域進行搜索的能力。最終，搜索過程在迭代30次后趨于收斂。因此，算法設計每次運行最大迭代次數為50次，算法重復運行15次后最優解保持不變，故設置算法的最大運行次數為20次。

為檢驗算法有效性，利用上述產生仿真數據的方法，分別產生節點數量為10、15、20、25、30、40、50，樞紐數量為3、5、7、9、11、13、15的投送網絡數據，采用本文提出的算法求解，并與用Complex 12.0軟件和Meng等[12]提出的混合遺傳算法求解的結果做對比(見表2)。采用當前主流規劃軟件Complex求解時，求解時間隨著問題規模的增大而快速增加，當投送網絡節點超過30個時，Complex不能在合理的時間得到最優解，采用啟發式算法則能顯著改善問題的求解時間。本文提出的基于Floyd的禁忌搜索算法的求解速度要高于Meng等[12]提出的混合遺傳算法，這是由于模型求解屬于組合優化問題，禁忌搜索利用禁忌表避免了迂回搜索，使得尋優過程更加高效。

4.3 算例結果與分析

以15節點投送網絡算例結果進行討論，最優樞紐集為[1，5，8，10，14]，對應目標函數值為2.258 1×107元。最優樞紐集的路由矩陣見表3。從表3中不但可以得到非樞紐節點與樞紐節點間的分配關系，如非樞紐節點2全部分配給樞紐節點5，非樞紐節點9點主要分配給樞紐節點8，還可以分配給樞紐節點10；而且還可以得到任意點對間的路線，如節點3到節點9的路線為3→5→8→9，節點1到節點7的路線為1→8→10→7。樞紐間的運輸方式選擇可以觀察最優樞紐集下的路網權矩陣，通過式(8)和式(9)反推得到，在此不再贅述。

表2 基于Floyd的禁忌搜索算法與其他方法性能對比

表3 最優樞紐集下的路由矩陣

表3(續)

采用Floyd最短路算法可以得到樞紐與非樞紐間的分配關系(如圖2所示)。圖2中同心的雙圓表示在該節點處建立樞紐，粗實線代表干線運輸，細實線表示普通公路運輸。觀察圖2可以發現，節點1在地圖中屬于孤點，但卻在該點建立了樞紐，且只有節點3的部分運輸分配到樞紐1。這是由于節點1和各個節點間均有流量，而且距離較遠，如果不建為樞紐而采用通過其他樞紐中轉時，由于節點間的距離滿足三角不等式，勢必會引起總成本的增加。

5 結 語

本文設計的算法能有效對模型求解，其結果能為國防交通建設規劃提供決策參考。考慮到投送成本和時間都與投送距離成正比關系，二者具有高度的正相關性，故本文在對樞紐選址問題進行建模時是以成本作為目標函數，將時間因素放在模型約束里來考慮。戰略投送由于其軍事特性，時間和成本同等重要，有時甚至要優先考慮，未來研究可以將時間作為目標函數，或者將時間、成本、運量等因素綜合考慮。本文研究僅考慮了公、鐵聯運，該模型可以擴展到公、鐵、水、空多種運輸方式。

[1] 管井標, 周赤非, 許瑞明, 等. 戰略投送能力評估方法研究[J]. 軍事運籌與系統工程, 2011, 25(2): 76-80.

[2] 張國全, 陳兆仁, 王春穎, 等. 建制部隊戰略投送需求基本內涵與主要特征分析[J]. 軍事交通學院學報, 2013, 15(6): 1-5.

[3] 海軍. 部隊戰略投送模式研究現狀[J]. 國防交通工程與技術, 2013, 11(4): 1-5.

[4] FARAHANI R Z, HEKMATFAR M, ARABANI A B, et al. Hub location problems: A review of models, classification, solution techniques, and applications[J]. Computers & Industrial Engineering, 2013, 64(4): 1096-1109.

[5] STEADIESEIFI M, DELLAERT N P, NUIJTEN W, et al. Multimodal freight transportation planning: A literature review[J]. European Journal of Operational Research, 2014, 233(1): 1-15.

[6] ISHFAQ R, SOX C R. Hub location-allocation in intermodal logistic networks[J]. European Journal of Operational Research, 2011, 210(2): 213-230.

[7] ALUMUR S A, KARA B Y, KARASAN O E. Multimodal hub location and hub network design[J]. Omega, 2012, 40(6): 927-939.

[8] 畢海玲，張旭濤，傅鈺. 聯合投送背景下運輸網絡彈性研究[J]. 軍事交通學院學報, 2015, 17(8): 83-86.

[9] BI H L, KANG K, ZHANG X T. A biobjective and trilevel programming model for hub location problem in design of a resilient power projection network[J]. Mathematical Problems in Engineering, 2016, 2016: 1-9.

[10] O'kelly M E. A quadratic integer program for the location of interacting hub facilities[J]. European Journal of Operational Research, 1987, 32(3): 393-404.

[11] Martins de Sá E, Contreras I, Cordeau J F. Exact and heuristic algorithms for the design of hub networks with multiple lines[J]. European Journal of Operational Research, 2015, 246(1): 186-198.

[12] MENG Q, WANG X. Intermodal hub-and-spoke network design: incorporating multiple stakeholders and multi-type containers[J]. Transportation Research Part B Methodological, 2011, 45(4): 724-742.

(編輯：史海英)

Hub Location in Strategic Projection Based on Tabu Search

BI Hailing, ZHANG Xutao, FU Yu

(Equipment Support Department, Military Transportation University, Tianjin 300161, China)

To solve the problems of hub location and allocation in strategic projection, the paper firstly abstracts the problem of network location into radiant multimodal transport, and establishes 0-1 integer programming model with time restraint.Then, it designs a heuristic algorithm based on specific shortest path algorithm and Tabu search according to the complexity of the model, and verifies the convergence and validity of the algorithm through simulation example. The research shows that this algorithm can solve the model and provide decision-making reference for planning national defense transportation construction.

strategic projection; hub location; integer programming; Tabu search; shortest path algorithm

2016-11-13；

2017-03-23．

畢海玲(1979—)，女，博士研究生，講師.

10.16807/j.cnki.12-1372/e.2017.06.019

F560

A

1674-2192(2017)06- 0081- 06