基于禁忌搜索算法求解定位-運輸路線安排問題

1、基于禁忌搜索算法求解定位運輸路線安排問題林暉鋼1，胡大偉1，徐麗蕊1，21 長安大學汽車學院，西安（710064）2 陜西工業(yè)職業(yè)技術學院工商管理系，陜西咸陽（712000）摘 要：定位運輸路線安排問題（location routing problems, LRP）是集成化物流系統(tǒng)分銷網(wǎng)絡設計和管理決策中的難題，也是任何一個大型物流配送企業(yè)必須要面對的問題。由于LRP 的NPHARD屬性，其求解方法目前大多局限在將定位配給問題（location allocation problems, LAP）的輸出作為車輛路線安排問題（vehicle routing problems, VRP）的輸入而求解

2、。然而，在LAP 最優(yōu)的前提下求出的VRP 的最優(yōu)并不一定就是LRP 的最優(yōu)解，從而導致這樣的處理方式不可避免的會陷入局部最優(yōu)解的狀態(tài)。本文針對多站點定位運輸路線安排問題（multi-depot location routing problems, MDLRP）數(shù)學模型，用Lingo 軟件對小規(guī)模測試數(shù)據(jù)情形進行了驗證, 然后采用禁忌搜索法(TS）分別求解LAP 和對應的每一個設施的VRP ，并將VRP 的結果作為LAP 的輸入，再將LAP 解及其鄰域解作為VRP 輸入不斷反復循環(huán)求解MDLRP ，并在此基礎上對較大規(guī)模測試數(shù)據(jù)進行了仿真運算。結果表明采用禁忌搜索方法求解一定規(guī)模的MDLRP

3、快速有效。關鍵詞：定位運輸路線安排問題；定位配給問題；車輛路線問題；禁忌搜索1. 引言設施定位、車輛路線各自作為單獨的問題，國內(nèi)外已有較多學者進行了研究，其理論也已比較完善，這些研究為物流管理的優(yōu)化決策奠定了堅實的基礎。國外一批學者對LRP 進行了一系列的研究1。LRP 的概念認為：在設施（制造廠、庫存點或分銷中心）相對于客戶的位置、貨物的配給、貨物運輸?shù)能囕v路線安排之間存在相互依賴的關系，根據(jù)這種關系來進行綜合優(yōu)化與管理；相比單一的物流系統(tǒng)優(yōu)化問題，LRP 更加貼近目前物流系統(tǒng)復雜的實際特征，對進一步優(yōu)化整個物流系統(tǒng)，降低系統(tǒng)成本具有一定的理論價值和現(xiàn)實意義。而當前大部分學者對LRP 的研究

4、都局限在將LAP 的輸出作為VRP 的輸入而進行求解，這種方法得出的LRP 解往往并不是最優(yōu)的?；谶@樣一個現(xiàn)實情況，本文將LAP 和VRP 綜合統(tǒng)籌考慮，得出了相應的MDLRP 優(yōu)化解，首先用C+編程軟件與Lingo 軟件對小規(guī)模數(shù)據(jù)集（8點數(shù)據(jù)集）進行了計算及其對比驗證本文算法計算結果的精確性，然后對較大規(guī)模數(shù)據(jù)（25點、50點、100點數(shù)據(jù)集）用本文算法求出了相應的優(yōu)化解，證明了本文算法對求解MDLRP 問題的有效性和準確性。2. MDLRP 參數(shù)定義及其數(shù)學模型與驗算本文研究的LRP 模型基于如下假設：客戶數(shù)量、位置及需求已知；候選設施位置及容量已知；各客戶需求均能得到滿足且每個客戶只

5、由一輛車服務；每輛車在完成全部運輸任務后回到出發(fā)點；各線路的總需求小于或等于車輛的容量；車輛類型給定。2.1 參數(shù)定義ijk x 在路線 k 上，如果點 i 在 j 之前值為1，否則為0；i y 如果建立 i 設施則值為1，否則為0；ij z 如果客戶 j 由設施 i 來服務則值為1，否則為0；R 配送設施點潛在位置的集合；J 所有客戶點的集合；V 所有車輛集合；N 代表客戶的數(shù)量；ij C i ，j 兩點之間的距離（作為i ，j 兩點間的運輸費用）；S R J =U 所有客戶點和潛在設施點的集合；r G 設施r 建設和運行的固定成本；k F 使用車輛 k 的固定成本；r V 設施 r 的最大

6、容量；j q 客戶 j 的需求量；k Q 車輛 k 的容量；2.2 多站點定位配給問題的數(shù)學模型Min +R i Jj ijk V k k ijk S i S j V k ij r R r r x F x C y G. s t ：=V k S i ijk x, 1 J j ， （1）, k S i J j ijk j Q x q V k ， （2）R r y V zq r r J j rj j , 0， （3）=S i Sj pjk ipk x x , 0 V k ，, S p i j （4）R r J j rjk x, 1 V k ， （5）( 1rlk ljk rj l S xx z +

7、， R r ，J j ， V k （6）10或=ijk x ， , , , , j i V k S j i （7）10或=r y ， , R r （8）10或=ij z ，, R i J j （9）在上述這個模型中，目標函數(shù)為總成本（包括設施建設和運作成本、運輸成本以及車輛投入及其使用成本）最小。約束（1）保證每一個客戶只由一個運輸車輛服務；約束（2）為運輸車輛容量約束條件；約束（3）為倉庫的容量限制條件；約束（4）保證路線連續(xù)；約束（5）保證每一個運輸工具的路線只能從一個設施駛出；約束（6）保證客戶只能由選中的設施提供服務；約束（7）（9）表示0、1變量約束。2.3 模型檢驗由于目前學術界并

8、不存在任何定位路線問題的測試數(shù)據(jù)。為了檢驗此模型的正確性，本文以VRP 的Solomon 測試數(shù)據(jù)源R101數(shù)據(jù)系列為基礎隨機產(chǎn)生包含3個候選設施點和5個客戶需求點的數(shù)據(jù)組，對定位路線問題數(shù)學模型進行檢驗。通過產(chǎn)生1100范圍內(nèi)的8個隨機數(shù)對應于100個客戶中的各個客戶編號，將其中三個作為本算例中候選設施點的數(shù)據(jù)，其余5個作為客戶點的數(shù)據(jù)。這樣隨機產(chǎn)生的一組候選設施點和客戶，潛在設施點的坐標、容量和建設成本如表1所示；客戶點的坐標和需求量如表2所示。車輛容量取40，車輛固定成本取30。表1 潛在設施點的坐標、容量和建設成本 X 坐標10 Y 坐標43 設施點的容量70 建設成本 200表2 客

9、戶點的坐標和需求量 C2C3C4C5 X 坐標3050104545 Y 坐標6035206510 客戶需求量161919 用Lingo10.0對MDLRP 模型進行編程，計算時間為156s ，結果表明兩個設施被選中，對應的目標函數(shù)值為666.406，從而證明了本文帶容量約束的MDLRP 數(shù)學模型的正確性。3. 禁忌搜索算法介紹TS （Tabu Search）算法是近年來受到普遍關注的一種高效率的現(xiàn)代啟發(fā)式優(yōu)化算法，該算法由F.Glover 2于1986年首先提出，進而形成一套完整算法34。并隨著計算機技術的發(fā)展而成功的應用于各個領域，解決了大量復雜的優(yōu)化問題。近幾年，該算法被廣泛領域引入，如水

10、火電聯(lián)合經(jīng)濟調(diào)度3、電力系統(tǒng)無功優(yōu)化4 、輸電系統(tǒng)最優(yōu)規(guī)劃5 以及交通運輸系統(tǒng)規(guī)劃5等領域，并取得了一定研究成果。部鄰域搜索陷入局部最優(yōu)的不足，禁忌搜索算法用一個禁忌表記錄下已經(jīng)到達過的局部最優(yōu)點，在下一次搜索中，利用禁忌表中的信息不再或有選擇地搜索這些點，以此來跳出局部最優(yōu)點。本文利用禁忌搜索算法求解組合優(yōu)化問題時，首先產(chǎn)生一個初始解作為當前解，然后在當前解的鄰域中搜索若干鄰域解，取其中的最好解作為新的當前解。為了避免對已搜索過的局部最優(yōu)解的重復，禁忌搜索算法使用禁忌表記錄已搜索的局部最優(yōu)解的歷史信息，這使得算法可在一定程度上避開局部最優(yōu)點，從而開辟新的搜索區(qū)域。本文設計的禁忌搜索算法流程圖

11、如圖1所示，禁忌搜索算法的特點是使用了禁忌技術。所謂禁忌就是禁止重復前面搜索，為了回避局 圖1 禁忌搜索算法流程圖禁忌搜索算法作為一種人工智能算法，涉及解的表示、解的評價、鄰域解的構造及算法終止準則，并且實現(xiàn)的技術問題是算法的關鍵，不同的算法策略將會對解的好壞產(chǎn)生重要影響。禁忌搜索算法的主要策略有：禁忌對象和禁忌長度的確定、候選集的產(chǎn)生方法、特赦規(guī)則以及終止規(guī)則。解的表示89不同編碼方式的運行時間和適應度函數(shù)值以及目標函數(shù)值計算的復雜程度不同，并且編碼方式也影響著解空間的大小。一般來說，在與車輛路線問題有關問題的求解中都采用自然數(shù)編碼的方式，而自然數(shù)編碼方式也存在著如下三種不同形式：第一種，客

12、戶和配送中心共同排列的編碼方式。第二種，車輛和客戶對應排列的編碼方式。第三種，客戶直接排列的編碼方式。根據(jù)本文研究問題的特征，本文采用第三種編碼方式，即客戶直接排列的編碼方式確定一組MDLRP 的初始可行解。禁忌對象的確定禁忌對象是指禁忌表中被禁的元素。由于解狀態(tài)的變化可分為解的簡單變化、解向量分量的變化和目標值變化三種情況，則在確定禁忌對象時也有對解的簡單變化進行禁忌、對解的分量變化進行禁忌及對解的目標值變化進行禁忌三種情況。一般來說，對解的簡單變化進行禁忌比對解的分量變化進行禁忌和對解的目標值變化進行禁忌的受禁范圍要小，因此可能造成計算時間的增加，但其優(yōu)點是提供了較大的搜索范圍。解分量的變

13、化和目標函數(shù)變化的禁忌范圍要大，這減少了計算的時間，可能引發(fā)的問題時禁忌的范圍增大以至陷入局部最優(yōu)點。根據(jù)定位配給問題和車輛路線問題的特點，可采用對解的簡單變化進行禁忌的方法。其原理是：當解從x 變化到y(tǒng) 時，Y 可能是局部最優(yōu)解，為了避開局部最優(yōu)解，禁忌y 這一解再度出現(xiàn)，可采用如下禁忌規(guī)則：當y 的鄰域中有比它更優(yōu)的解時，選擇更優(yōu)的解；當Y 為N (y的局部最優(yōu)解時，不再選Y ，而選比y 稍差的解。禁忌長度的確定禁忌長度是指被禁對象不允許被選取的迭代步數(shù)，一般是給被禁忌對象x 一個數(shù)L(稱為禁忌長度 ，要求禁忌對象x 在L 步迭代內(nèi)被禁，在禁忌表中采用Tabu(x=L記憶，每迭代一步，該項

14、指標做運算Tabu(x=L-1，直到Tabu(x=0時解禁。禁忌長度在同一問題求解過程中是固定的，但是隨問題規(guī)模的不同取不同的值，一般來說，問題規(guī)模越大，禁忌長度越長。禁忌長度短會造成循環(huán)，也可能在一個局部最優(yōu)解附近循環(huán)。禁忌長度長會造成算法的記憶存儲量增加，使得算法計算時間增加，還可能造成算法無法繼續(xù)計算下去。本文L 取為常數(shù)，L =為鄰域中鄰居的總個數(shù) ，這種規(guī)則容易在算法中實現(xiàn)。 候選集的產(chǎn)生方法候選集合由鄰域中的鄰居組成。常規(guī)的方法是從鄰域中選擇若干個目標值或評價值最佳的鄰居入選。有時這種計算量較大，而且容易導致局部收斂的情況，所以本文采用不在鄰域的所有鄰居中選擇，而是在鄰域中的一部分

15、鄰居中隨機選擇若干個目標值或評價值最佳的狀態(tài)實現(xiàn)部分鄰居的選取。由于考慮到計算時間的復雜度問題，本文設計每次對當前解隨機進行5次鄰域解產(chǎn)生操作，將其作為當前解的候選集。在定位階段既要確定配送中心數(shù)目，又要選擇具體的配送中心，因此設計兩種鄰域搜索方法，分別是 “客戶交換”和“客戶插入”操作。根據(jù)本文特點，在路線優(yōu)化階段，設計隨機從插入法、2-opt 、路線內(nèi)2swap 和路線間2-swap 四種鄰域搜索方法中選擇其中一種來產(chǎn)生鄰域解，這樣增強了禁忌搜索算法的搜索性能，擴大了搜索范圍，以便能在車輛行駛費用方面得到更好的改進。插入法插入法是考慮一條路線中任意一個點插入到其他路線中的方法，即從一條路線

16、中隨機選擇一個點，插入到另一條路線中隨機選擇的兩個點之間，如圖2，從一條路線中隨機選擇點4，另一條路線中隨機選擇點7，通過插入法，則路線由012340和056780變?yōu)?1230和0567480。 代表選中DC ，代表客戶， 和代表路線圖2 插入法示意圖 2opt將當前路線中的k 條邊用另外k 條邊代替，這種變換稱為k opt 10, 最為常見的是2opt ，主要思想是隨機選擇兩個點i 和j ，將邊(i,i+1、(j,j+1用(i,j、(i+1,j+1代替，如圖3所示，隨機選擇2和5，進行2opt 交換，則路線由01234560變?yōu)?1254360。 代表選中DC ，代表客戶，和 代表路線圖3

17、 2opt 交換法示意圖11 路線內(nèi)2Swap路線內(nèi)2swap 主要思想是交換一條路線上兩個點的位置，如圖4所示，隨機選擇2和5，進行路線內(nèi)2Swap ，則路線由01234560變?yōu)?1534260。路線間2Swap路線間2swap 主要思想是交換不同路線上兩個點的位置，如圖5所示，隨機選擇兩條路線上的兩個點2和5，進行路線間2Swap ，則路線由01230和04560變?yōu)?1530和04260。這種思想在車輛路線問題的客戶分配中可以起到優(yōu)1化分組的作用。 代表選中DC ，代表客戶，和代表路線圖4 2Swap 路線內(nèi)交換法示意圖 圖5 2swap 路線間交換示意圖特赦規(guī)則在禁忌搜索算法的迭代過

18、程中，會出現(xiàn)候選集中的全部對象都被禁忌，或某一對象被禁，但若解禁后其目標值將下降情況。在這樣的情況下，為了達到全局的最優(yōu)，讓一些禁忌對象重新可選，這種方法稱為特赦，相應的規(guī)則稱為特赦規(guī)則，也即解禁原則。本文采用基于評價值的特赦規(guī)則。即在整個計算過程中，記憶已出現(xiàn)的最好解bestx ，當候選集中被禁忌解的鄰域中，出現(xiàn)一個解nowx 優(yōu)于bestx，則解禁nowx使其自由，并更新為當前解和最好解。 評價函數(shù)評價函數(shù)賦予候選集合中每一個元素一個實數(shù)值，通過評價函數(shù)值來選取下一步計算的替代點。領域搜索中需要對在得到的幾個解中選擇質(zhì)量最優(yōu)的解作為新的當前解，為了提高算法效率，在定位階段評價解的優(yōu)劣時，我

19、們通過目標函數(shù)預測值來比較這幾個解的質(zhì)量。預測方法是：根據(jù)求解的設施定位方案，在滿足設施容量約束的前提下，將客戶分配至距離最近的設施點，假設設施與客戶間的運輸路線為直線距離，并且不考慮車輛路線，而采用各客戶與設施點距離總和作為目標函數(shù)預測值。而在路線優(yōu)化階段，則用配送路線方案的目標函數(shù)值作為評價函數(shù)，對候選解進行評價和選取最優(yōu)值。其目標函數(shù)值越優(yōu)，則解的質(zhì)量越高。終止準則67禁忌搜索是一種啟發(fā)式算法，希望在可接受的時間里能得到一個滿意的解。終止規(guī)則就是確定什么時候終止算法，通常使用的有以下幾種方法：確定步數(shù)終止；頻率控制原則； 目標值變化控制原則； 目標值偏離程度原則。為便于算法實現(xiàn)，本文綜合

20、方法和方法，采用事先確定最大迭代代數(shù)和最好解保持不變的最大連續(xù)迭代步數(shù)作為終止規(guī)則。4. 實例計算及結果分析本文中所有計算實例中的單位距離運輸費用均取為1；對于8點數(shù)據(jù)由于有可比對象（LINGO 計算結果），為了對比方便程序當中車輛費用取為30；而對于25點、50點和100點的數(shù)據(jù)由于沒有可比對象，所以在程序中車輛容量暫時設定為：50，90，150；車輛費用暫時分別設定為30，0，0；當然也可以根據(jù)需要自行設定。根據(jù)模型檢驗中的8點數(shù)據(jù)，對本文禁忌搜索算法運用C+語言編程計算，對應的參數(shù)設置如下：禁忌長度取為3，最大迭代次數(shù)max_cons_iter取為800，候選解數(shù)量取為5，LRP 迭代次

21、數(shù)取為20時，得出目標函數(shù)的結果如表3所示。表3 計算結果選中的設施對應的車輛路線 目標函數(shù)值CPU 運行時間120-4-1-0 ，0-2-5-00-3-0666.406 0.0922秒根據(jù)上表可以看出，由本文算法模擬計算，得出的結果與我們應用Lingo10.0對MDLRP 模型8點數(shù)據(jù)進行編程計算得出的目標函數(shù)值完全相同，并且計算20次得出該最優(yōu)解的頻率為85%以上，計算機運行時間也很快。從而驗證了本文程序的有效性。在solomon 數(shù)據(jù)集中R101數(shù)據(jù)集合（見表4）中隨機選取其中5個客戶點作為設施節(jié)點，其余20個作為客戶點，用本文算法進行編程計算在相應的參數(shù)設置為：禁忌長度取為5，最大迭代次數(shù)max_cons_iter取為8000，候選解數(shù)量取為25，LRP 迭代次數(shù)取為50時，計算20次得出的最好結果如表5所示，最好結果出現(xiàn)的頻率為75%以上。表4 設施點坐標、容量、建設費用和客戶點坐標、需求量潛在設施容量 建設費用客戶需求量客戶X Y 需求量客戶 需求量65121665102017201919表5 計算結果選中的設施對應的車輛路線 目標函數(shù)值CPU 運行時間1 2 50-5-1-7-13-0 ，0-12-10-00-6-15-9-0 ，0-1-3-8-16-00-17-18-0 ，0-2-11-4