分時段配送車輛調度問題的禁忌搜索算法

[摘要] 建立了分時段配送車輛調度問題的數學模型，同時采用禁忌搜索算法計算優化的配送線路和配送時間，并采用實例進行仿真計算。計算結果表明算法的計算效率較高，收斂速度較快，計算結果也比較穩定。

[關鍵詞] VSP問題禁忌搜索算法車輛調度

目前，物流配送車輛調度問題的研究主要集中于軟時間窗或硬時間窗的配送車輛調度問題，其求解困難，而且企業的配送成本也往往會很高。本文對不同客戶的實際配送需求進行分析，提出了分時段配送車輛調度問題，即要求以最少的車輛、最少的費用在客戶選擇的時間段（時間段可由企業預先確定，并供客戶自由選擇）內完成配送任務。分時段配送車輛調度問題的解決能夠有效促進企業以盡可能低的成本，提供較高水平的客戶服務，具有十分重要的現實意義。

禁忌搜索算法是求解最優解的智能化算法，它引入了人工智能技術，仿效人類行為，并應用一些學習規則確定搜索方向，以避免解的局部循環。目前，禁忌搜索算法在車輛調度領域得到了廣泛的應用，如Gendreau、Jiefeng、Barbarosoglu、I-Ming Chao、蔡延光、郎茂祥等都曾利用禁忌搜索算法求解配送車輛調度問題，并取得了多項研究成果。本文設計的禁忌搜索算法求解分時段配送車輛調度問題，不僅可以取得良好的計算結果，而且算法的計算效率較高，計算結果也較穩定

一、問題描述

本文提出的分時段配送車輛調度問題是指將配送時間劃分成上午和下午兩個時段，客戶自由選擇。與硬時間窗的配送車輛調度問題相比，時間約束比較寬松，求解相對容易，而且能夠使企業能夠在滿足客戶配送要求的前提下，以較低的成本完成配送任務。分時段配送車輛調度問題的求解步驟如下：

1.客戶根據自身的時間安排選擇上午配送或下午配送，上午時段和下午時段的劃分可以由企業根據具體情況來設定。

2.對分時段配送車輛調度問題采用禁忌搜索算法進行求解，獲取滿足客戶配送要求的優化的車輛運行線路。

3.計算到達每個配送點的預定時間，再根據道路交通狀況計算預定到達的時間窗。然后通知客戶在該時間窗內準備接收貨物。

二、數學模型

一般地，分時段配送車輛調度問題的具體描述為：有一個配送中心，使用容量為Q噸的車輛給n個配送點P1，P2，P3，…，Pn配送商品。已知配送點i的貨運量為gi(i=1，2， …，n)，且gi

1.指定在某一天送貨，并要求在上午配送。

2.指定在某一天送貨，并要求在下午配送。

求在滿足各配送點時間約束的前提下配送費用最小的車輛運行線路，并計算到達每個配送點的配送時間。

一般認為，派出一輛車的固定費用遠遠高于車輛行駛費用，所以求解目標確定為在極小化車輛的前提下，再極小化運輸費用。

為了方便構造數學模型，將配送中心編號為0，配送點i編號為1，2， …，n。定義變量如下：

cij表示從配送點i到配送點j的運輸成本，與兩點之間的距離成正比。

si表示到達配送點i的時間，由始發時間（ST）、行駛時間(t)、卸貨時間(ut)構成。

tij表示從配送點i到配送點j的行駛時間；uti表示在配送點i進行裝卸作業的時間。

Pti表示第i個配送點的時間約束，Pti=1表示上午時段，Pti=2表示下午時段。

則可得分時段配送車輛調度問題的數學模型如下：

三、 算法設計

輸入：各配送點的配送任務和各配送點間的距離。

輸出：優化的車輛調度安排和達到各配送點的預定時間窗。

原理：采用禁忌搜索算法進行求解。

算法的主要步驟如下：

步驟1：選定一個初始解Xpop；令禁忌表tabu list=Φ；

步驟2：若滿足終止準則，則轉步驟4；否則在一定搜索方向產生移動值Fmove，在Xpop的領域D(Xpop)中選擇出滿足禁忌要求的侯選解CD（Xpop），轉步驟3。

步驟3：在CD（Xpop）中選一個評價最好的解Xbest，令Xpop=Xbest，更新禁忌表tabu list，轉步驟2。

步驟4：輸出計算結果，停止。

其中，初始解、領域結構、禁忌表、禁忌長度、評價函數的確定是禁忌搜索算法設計的核心，此外還包括終止準則的確定。

1.初始解。任何禁忌搜索算法需要一個初始解以開始其局部搜索過程，本算法將以隨機方式產生初始解。但初始解必須滿足以下條件：

（1)每條線路上車輛運輸能力的限制。

(2)客戶選擇時間段的要求。

(3)每條線路的上午配送點數量基本保持一致，這主要是為了確保每條線路的上午配送任務比較均衡，而且還可以使每條線路完成上午配送任務的時間比較接近。

2.領域結構。禁忌搜索算法是一種基于領域搜索技術的算法，本文將領域結構確定為同一時間段內任意兩個城市的互換(SWAP)操作，每個狀態的領域解有C2n1+ C2n2=n1*(n1-1)/2+ n2*(n2-1)/2個，其中n1表示上午配送點的數量，n2表示下午配送點的數量。

3．禁忌表。禁忌表用于記錄已經到達過的局部最優點，這樣在下一次搜索中，就可以利用禁忌表的信息，不再或有選擇的搜索這些點，以此來跳出局部最優點。在搜索過程中，局部最優點會被作為禁忌對象加入禁忌表的最末位置，隨著新解的不斷加入，老解將從禁忌表的頭部刪除，從而實現自動解禁。

4.禁忌長度。禁忌長度是指被禁忌對象不允許被選取的迭代步數。當禁忌表中的禁忌對象經過一定步數的移動后，該禁忌對象即被解禁，并可以作為下一步的搜索方向。本文采取定長禁忌長度，其值大小可根據問題的規模來確定。

5.評價函數。采用禁忌搜索算法求解分時段配送車輛調度問題時，首先判斷侯選解是否滿足約束條件，然后計算侯選解的目標函數值。本文以目標函數作為解的評價方法，在滿足約束條件的前提下，其目標函數值越優，則解的質量越高。如果當前最優解不是禁忌對象，則可以作為下一步的搜索方向。

6.終止準則。程序運行超過給定的最大迭代步數時，則算法終止。

四、實驗分析

下面以配送點數為12的非滿載VSP為例，配送點編號i為1，2，…，12；配送中心的編號i為0；配送點i坐標為(xi ，yi) ，單位為公里。每個配送點的配送貨物的量為gi （gi

表 配送點數為12非滿載VSP的原始數據

假設每輛車的平均行駛速度為40公里/小時；車輛的噸位 Q = 5 噸；始發時間 ST = 8點；午餐時間 LT = 1個小時（午餐時間安排在上午配送完成之后）。

根據，求出各點之間的距離矩陣，假設cij=cji，cii＝M(M為一趨于無窮大的正數)；再確定運輸車輛的數量。

迭代步數取100，計算時間0.3s，程序仿真的結果如下：

1.行使總里程為345公里，通過枚舉法可以證實為全局最優解。

2.優化的車輛運行線路為：

線路1：0-10-3-6-7-4-1-0運輸量：4.5噸

線路2：0-12-5-8-9-11-2-0運輸量：5噸

相應的配送時間安排為：

3.計算到達每個配送點的時間窗。假設配送時間誤差Φ確定為正負15分鐘，則到達每個配送點的時間窗為：

五、結論

本文首先根據不同的客戶需求提出了分時段配送車輛優化調度問題，然后建立了數學模型，并作了補充說明。該數學模型具有較高的實用與理論價值，而且表述清晰，直觀，易于理解。另外，本文還設計了禁忌搜索算法求解分時段配送車輛優化調度問題，并運用實例進行實驗計算。計算結果表明，該算法能夠獲得較好的計算結果，而且算法的計算效率較高，計算結果也較穩定。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。