改進模擬退火算法在物流優化中的應用

唐 瓊，伍星華，張振文

（衡陽師范學院 經濟與管理學院，湖南 衡陽 421002）

在物流優化中，物流設施選址、庫存決策和車輛路徑決策一直是三個關鍵問題，以前，學者們分別對這三個領域進行研究，并取得了很多的研究成果。但事實上，在設施、貨物配送、以及運輸貨物的車輛路線決策之間卻存在密切的相互依賴的關系，物流優化應該要根據這種依賴關系來開展［1］。根據這一思想，學者們對物流優化相關問題展開了研究。早期的研究主要集中在三個決策要素的兩兩集成，如選址路徑問題、庫存路徑問題、選址庫存問題等，近年來學者們開始關注三者綜合集成的選址－庫存－路徑問題的研究［2－6］。Liu和Lee最早研究LIRP，他們給出了一個考慮庫存決策的選址－路徑問題的模型，同時針對模型提出了一個兩階段的啟發式算法［7］。進一步的，Liu和Lin針對［7］文兩階段的啟發式算法容易陷入局部最優的缺陷，提出了一種基于模擬退火算法的全局優化啟發式算法［8］。國內，崔廣彬和李一軍首先對選址庫存路徑問題進行了研究［9］。而在最近的研究工作中，Shen和Qi建立了一個以選址、庫存及運輸成本最小為目標函數的非線性規劃模型，同時提出了內嵌分枝定界法的拉格郎日算法求解該模型［10］。唐瓊等基于二層規劃建立了一個選址庫存路徑問題模型，并設計了雙層模擬退火算法求解該模型［11］。

另一方面，整個市場需求的特征發生改變，逐漸趨向個性化、多樣化，這樣導致市場需求變得更隨機，產品生命周期越來越短，企業的成功也越來越取決于其對客戶訂單的響應能力，時間已經成為影響企業競爭優勢的一種新的核心資源［12］。尤其是在路徑安排時，時間已成為影響決策的重要因素。Solomon［13］和 Desrosires等學者［14］最早將時間因素加入到一般車輛路徑問題中，對帶時間窗的車輛路徑問題進行了研究。

本文在前人研究的選址－庫存－路徑模型基礎上，考慮客戶對送貨物時間的要求，引入軟時間窗，建立了帶軟時間窗的選址－庫存－路徑問題（Location Inventory Routing Problem with Soft Time Window，LIRPTW）模型，即如果配送車輛無法將貨物在客戶要求的時間窗內將貨物送達，那么必須按照違反時間窗的長短對配送中心施以相應的懲罰成本。

1.帶軟件時間窗的選址庫存路徑模型

本文研究的LIRPTW是基于集成物流系統的供應鏈二級分銷網絡系統，系統中有一個生產基地，多個配送中心，多個客戶，客戶的庫存策略為多周期隨機存貯策略，從生產基地到各個配送中心的網絡定義為一級網絡，網絡配送中心與客戶構成的網絡定義為二級，配送方式采取循環路線配送的方式。本文模型將同時對以下幾個問題進行決策：（1）選址決策：即從備選配送中心中選出最佳數量的配送中心；（2）分配決策：即將客戶分配給某個已選定的配送中心；（3）路徑決策：即確定每條路線上車輛經過客戶的順序；（4）庫存決策：即確定每條路線上所有客戶的最佳訂貨點及最佳訂貨量。

1.1 模型假設。文中LIRPTW是基于如下假設：（1）客戶需求為單一產品，潛在的配送中心有多個，每個客戶只分配給一個配送中心；（2）建立和經營各備選配送中心的費用為固定值，且已知；（3）客戶的需求是確定性的，同時提前期內需求的分布已知；（4）車輛為同一類型，且每輛貨車在完成配送任務后要求返回到出發點。

1.2 符號說明。J為備選配送中心集合 ｛j｜j＝1，2，…，J｝；K為客戶集合 ｛k｜k＝1，2，…，K｝；V為車輛集合 ｛v｜v＝1，2，…，V｝；Setv表示路線v上客戶的集合；F j為配送中心j的固定投資和管理費用，其中j∈J；C j為從已知生產基地到備選配送中心j的單位產品運輸費用，其中j∈J；C u為使用每一輛貨車的固定成本；DM k為客戶k在一定時期內的總需求量，其中k∈K；f k（t）為客戶k在訂貨提前期L內的需求概率密度函數，其中k∈K；C h為單位商品的存貯費用；C o為每次訂貨的固定費用；C s為單位商品的缺貨費用；d gh表示點g到點h的距離，其中g，h∈J∪K；C t為單位距離貨物的運輸費用；Mup為貨車的最大載重量；Max為貨車的最大服務能力；ET k為達到k點的最早時間，時間窗的上限，其中k∈K；LT k為到達k點的最遲時間，時間窗的下限，其中k∈K；P E表示沒按客戶要求提前將貨物送到客戶平均單位時間的懲罰成本；P L表示沒按客戶要求延遲將貨物送到客戶平均單位時間的懲罰成本；T k為到達k點的時間，其中k∈K；S k為在k點服務時間，其中k∈K；t gh表示從g點到h點所需要的運輸時間，其中g，h∈J∪K；D v為巡回路線v上所有客戶的總需求量，其中v∈V；u v為巡回路線v上所有客戶在提前期L內的平均需求，其中v∈V；r v為巡回路線v上客戶的訂貨點，其中v∈V；Q v為巡回路線v上客戶的訂貨量，其中v∈V；S（r v）為路線v上客戶缺貨數量的期望值，其中v∈V；表示是否選中備選配送中心j，選中y j＝1，沒選中y j＝0，其中j∈J；z jv表示配送中心j是否在巡回路線v上，是取1，否?。?，其中j∈J，v∈V；X vQh表示第v輛貨車是否經過客戶g到客戶h，則為1，否則為0，其中；表示路線v上客戶k是否由配送中心j服務，是取1，否則取0，其中j∈J，k∈K，v∈V。

1.3 數學模型。LIRPTW模型的目標函數是最小化設施選址、庫存和車輛運輸三成本以及違反時間窗付出的懲罰成本之和，這個問題的數學模型為：

模型中，式（1）使物流系統總成本最少，總成本包括設施選址成本、庫存成本和車輛運輸成本以及貨車違反時間窗要承擔的懲罰成本。約束條件（2）表示至少要在備選的配送中心（已知數量）選擇一個配送中心；約束條件（3）任巡回路線上貨車的一次配送過程的配送量不能大于其載重量；約束條件（4）任一貨車的總配送量不能大于其最大的服務能力；約束條件（5）保證每個客戶有且僅能由一個配送中心為其進行配送貨物；約束條件（6）表示任意兩個選定的配送中心之間不存在有路線連接；約束條件（7）保證運輸路線的連續性，貨車不能在停留在客戶處；約束條件（8）保證只有運輸路線經過了該客戶，該客戶才能被指派給其對應的配送中心；等式（9）表示每條路線上配送車輛到達各個客戶的時間；式（10）－（13）0－1為決策變量的約束。

2.模型求解

本文使用兩階段啟發式算法對LIRPTW模型進行求解，即將問題分解成選址和帶軟時間窗的庫存路徑兩個子問題，因此本節介紹求解LIRPTW模型的改進模擬退火算法求解子問題，而在確定車輛路線安排的情況下可用文獻［7］的算法計算最佳訂貨量與訂貨點的方法。選址改進階段通過調整配送中心的布局改進解，側重于選址及分配決策，而庫存路徑階段通過調整路線上的客戶從而達到改進解的作用，側重于路徑和庫存決策。

2.1 初始化。利用就近原則，快速構造初始解。針對每個客戶選擇一個離它最近的配送中心，以直送的形式構成初始路線V t（1＜＝t＜＝v）及初始解X0，并將初始解作為當前解，同時將初始解作為當前最優解，即令X＊＝X0，SC（X＊）＝SC（X0）。初始化最大迭代次數max＿count，禁忌表Tabu，令當前迭代次數count＝0。

2.2 選址改進階段。Step0.初始化初始溫度T，停止溫度T s，溫度下降系數r，最大接受解的次數max＿reci＿iter，連續未找到更好解的最大次數max＿unchang＿iter，最大候選解個數max＿cand＿count。令當前接受解的次數reci＿iter，當前連續未找到更好解的累計次數unchang＿iter，當前候選解數cand＿count都為0。

Step1.利用DROP和SWAP＿LOCATION兩種領域操作在X0的基礎上產生max＿cand＿count個滿足容量限制的解X，將X加入到領域集N（X0）作為候選解。

DROP操作：隨機選擇路線V j，設該路線上的客戶由配送中心D j負責配送貨物，此時D j的狀況為開放的。再選擇一個離路線V j比較近的開放配送中心D i，關閉D i，將V i路線上由D i負責配送的客戶分配給D j。

SWAP＿LOCATION操作：隨機分別選擇兩條路線V i和V j，其中V i上的配送中心為D i，V j上的配送中心為D j，交換兩條路線上的配送中心，即路線V i上客戶由D j服務，路線V j上客戶由D i服務。

Step2.選出領域集N（X0）中最好的解X1，判斷解X1是否在禁忌表中，如果是，轉Step1；不是，則接受X1為當前解，且更新X0＝X1，SC（X0）＝SC（X1），判斷X1是否優于最優解X＊，如SC（X1）＜SC（X＊），接受X1為當前解，X＊＝X1，SC（X＊）＝SC（X1），以及更新禁忌表，轉Step3。

Step3.利用DROP和SWAP＿LOCATION兩種領域操作在解X0的基礎上產生滿足容量限制的解X1。判斷X1是否在禁忌表，如果是，轉Step1，不是，轉Step4。

Step4.令△SC＝SC（X1）－SC（X0），如果△SC＜＝0，則接受X1為當前解，并令X0＝X1，SC（X0）＝SC（X1），unchang＿iter＝0，reci＿iter＝reci＿iter＋1，更新禁忌表。進一步，判斷X1是否優于當前最優解X＊，如果是，則X＊＝X1，SC（X＊）＝SC（X1）。如果exp（－△SC/T）＞random（0，1），接受X1為當前解，并令X0＝X1，SC（X0）＝SC（X1），unchang＿iter＝0，reci＿i ter＝reci＿iter＋1，更新禁忌表。否則，unchang＿iter＝unchang＿iter＋1。

Step5.如果reci＿iter＞max＿reci＿iter或者unchang＿iter＞max＿unchang＿iter，令T＝T＊r，同時判斷程序是否達到選址改進階段終止條件，即判斷T＜T s，如果是，X0＝X＊，SC（X0）＝SC（X＊），轉 Step6；否則轉Step1。

2.3 庫存路徑改進階段。Step6.重復過程Step0至Step5，在這個階段的領域操作為INSERT和SWAP＿ROUTING。INSERT操作：隨機選取兩條路線V i和V j，在路線V i上隨機選取客戶C1，在路線V j上選取離C1距離較近的客戶C2和C3，將C1插入到路線V j上，放在C2和C3中間，順序為C2，C1，C3，并將路線V i上的客戶C1刪除。SWAP＿ROUTING操作：隨機選取兩條路線V i和V j，然后隨機從路線V i上選取客戶C1，從路線V j上隨機選取客戶C2，交換C1和C2。

Step7.判斷當前迭代次數是否達到最大迭代次數，即count＞＝max＿count，如果是，程序終止，輸出最優解X＊和SC（X＊），否則，count＝count＋1，轉Step6。

3.算例分析

3.1 與模擬退火、禁忌算法對比。假定在供應鏈二級分銷網絡系統中，有1個工廠，4個備選的配送中心，15個客戶，且配送中心和客戶分別在一個邊長為20km的正方形地域內，Mup＝150，Max＝1000，車輛平均行駛速度為20km/h，C t＝1，C u＝20，C o＝15，C h＝1，C s＝2，PE＝5，PL＝10。4個備選配送中心的坐標分別為：（18.9，15.2），（8.6，8.4），（7.4，1.0），（13.2，15.1），其他相關的參數：C j分別為：2，3，2，4，F j分別為：250，430，150，240。15個客戶的坐標分別為：（12.8，8.5），（18.4，3.4），（15.4，16.6），（15.5，11.6），（10.6，7.6），（12.5，2.1），（13.8，5.2），（14.8，2.6），（1.8，8.7），（17.1，11.0），（0.2，2.8），（11.9，19.8），（6.4，5.6），（9.6，14.8），（6.7，16.9）；要求提供服務的時間窗分別為：（4.7，10.5），（1.5，6.0），（4.7，10.2），（3.7，8.9），（6.7，12.3），（0.6，5.7），（2.6，6.8），（4.1，10.1），（3.4，8.1），（2.0，6.0），（2.1，6.3），（6.8，12.0），（6.0，10.4），（5.4，9.6），（2.5，8.1）；總需求量分別為：245，345，360，451，523，396，589，450，360，389，461，574，326，465，492；在周期內需求服從均勻分布，下限都為0，上限分別為：5，4，8，9，6，7，6，5，8，7，5，6，8，7，9。用 Matlab6.5編程，算法中涉及的參數值：T＝90，r＝0.9，T s＝10，禁忌表長為7，max＿cand＿count＝5，max＿count＝5，max＿reci＿iter＝20，max＿unchang＿iter＝20。本實驗將本文算法與禁忌搜索和模擬退火算法分別進行了對比，對上述實例，三種算法各執行算法20次，取得到的最好解，其對應的迭代過程中最優解收斂圖如下圖1所示。

圖1 運行收斂圖

本文算法內嵌具有較強的“爬山”能力的禁忌搜索算法來搜索領域解，因此搜索解時能夠跳出局部的最優解，轉向領域解的其他區域，進而獲得更佳的全局最優解。其次為了能快速地跳出局部最優解以及減少不必要的迭代次數，修改了模擬退火算法的收斂準則。再次，為了保證算法在迭代過程中不丟失最優解，利用了禁忌搜索算法的記憶功能。圖1表示本算法在初期的收斂速度非?？?，后期也只需要較少的迭代次數就能找出最優解，且最優解比單獨使用禁忌搜索和模擬退火算法所找到的最優解要好。

3.2 與文［8］算法對比。這一節將本章算法與Liu文算法［8］進行對比，本節構造了小、中和大15組不同問題規模的隨機數例進行測試。算法的有效性主要通過三個指標來衡量：解的質量（算法能尋找到的最優成本）、求解效率即CPU時間和懲罰成本。

3.2.1 實驗的設計。本節的隨機實例構造方法如下：F j服從均勻分布U ［2500，5000］；C j服從均勻分布 U［2，6］；備選配送中心和客戶的坐標都服從均勻分布U［0，100］；客戶k的一年內總需求DMk服從均勻分布U［600，1000］；客戶在提前期L內的需求服從均勻分布U［0，5］；時間窗的上限ET服從均勻分布U ［1，3］；而時間窗的下限則根據上限而隨機確定。設Mup＝300，Max＝4000；車輛平均行駛速度為30，C t＝1，C u＝20，C o＝15，C h＝1，C s＝2，PE＝0.2，PL＝2，Sg＝0.25。本節中的實例規模大小，用m表示備選配送中心的個數，n代表所有客戶的個數。

3.2.2 算法對比分析。在IntelPenitum2.20GHZ內存1GB的聯想計算機上，操作系統為 WindowsXP，用 Matlab6.5編程。算法中涉及的參數值分別為：當10＜＝n＜＝40，max＿reci＿iter＝10；當50＜＝n＜＝100，max＿reci＿iter＝20；當110＜＝n＜＝150，max＿reci＿iter＝30，其余參數同4.1部分。

對每組隨機數據執行算法10次，取運行得到的最優解，得到實驗結果如表1所示。

表1 算法對比結果

表中第3、4和5列表示運行兩種算法得到的最優成本以及改進率，第6、7和8列表示兩種算法尋找最優成本程序所需要的時間以及改進率，第9、10和11列表示兩種算法尋找到的最優解對應的時間懲罰成本及改進率。對于第5列總成本的改進率，可以發現對于小規模問題成本改進率不高，但是隨著問題規模增大，成本改進率越來越大，平均成本改進率為15.5%。對于第8列的算法執行時間改進率，最低是38.4%，最高為61.2%，平均的改進率為56.2%。對于時間懲罰成本的改進率最低為61.2%，最高為95.9%，平均改進率為81.5%。因此，與Liu［8］文相比，本文的算法在執行時間上大約能節約一半的時間并且也能在一定程度上節約總成本。同時，能節約一半以上的時間懲罰成本，說明利用本文算法能大量縮短對客戶的響應時間，由此可見，本文算法能對解的性能作較大的提高。

本文研究了帶軟時間窗的選址－庫存－路徑問題（LIRPTW），建立了LIRPTW模型，并提出了一種改進的結合禁忌搜索和模擬退火算法用于問題求解，最后通過實例演算以及算法對比，結果說明模型和算法的有效性。

本文在庫存方面本問沒有考慮配送中心的周期庫存和安全庫存成本，另一方面本文在處理軟時間窗的問題上，比較簡單，是在考慮選址－庫存－路徑三成本之和最小的前提下，以懲罰成本的方式處理違反時間窗的配送中心。在進一步的研究中，將會在考慮三成本之和的同時，考慮時間因素，同時將模型拓展，并改進本文算法。

［1］ Watson－Gandy C，Dohrn P.Depot location with van salesmen：a practical approach［J］.Omega Journal of Management Science，1973，1（3）：321－329.

［2］Perl J.，Sirisiponsilp S.Distribution networks：facility location，transportation and inventory［J］.International Journal of Physical Distribution ＆ Materials Management，1989，18（5）：18－26.

［3］Jayaraman，V.Transportation，facility location and inventory issues in distribution network design：an investigation［J］.International Journal of Operations ＆ Production Management，1998，18（5）：471－494.

［4］Nozick，L.K.，Turnquist，M.A.Integrating inventory impacts into a fixed－charge model for locating distribution centers［J］.Transportation Research E，1998（34）：173－186.

［5］Nozick，L.K.，Turnquist，M.A.Inventory，transportation，service quality and the location of distribu－tion centers［J］.European Journal of Operational Research，2001，129（2）：362－371.

［6］Ambrosino，D.，Scutella，M.G.Distribution network design：New problems and related models［J］.European Journal of Operational Research，2005，165（3）：610－624.

［7］Liu，S.C.，Lee，S.B..A two－phase heuristic method for the multi－depot location routing problem taking inventory control decisions into consideration［J］.International Journal Advanced Manufacturing Technology，2003，22（11）：941－950.

［8］Liu，S.C.，Lin，C.C..A heuristic method for the combined location routing and inventory problem ［J］.International Journal Advanced Manufacturing Technology，2005，26（4）：372－381.

［9］崔廣彬，李一軍 .基于雙層規劃的物流系統集成定位－運輸路線安排－庫存問題研究［J］.系統工程理論與實踐，2007，27（6）：49－55.

［10］Shen，Z.－J.，Lian，Q..Incorporating inventory and routing costs in strategic location models［J］.European Journal of Operational Research，2007，179（2）：372－389.

［11］唐瓊等 .基于二層規劃的選址庫存路徑問題研究［J］.物流技術，2011（13）：137－142.

［12］Stalk G J.Time－the next source of competitive advantage［J］.Harvard Business Review，1988，66（4）：41－51.

［13］Solomon M.M..Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints［J］.Operations Research，1987（35）：254－264.

［14］ Desrosiers，J.， Soumis， F.，and Desrochers，M.Routing with Time Windows by Column Generation［J］.Networks，1988（14）：545－565.