新常態下重慶會議型酒店發展研究

包代佳

[提要] 目前，對配送車輛路徑問題的研究已經比較成熟。本文運用禁忌搜索算法對車輛路徑調度問題進行研究，先用節約里程法獲得初始解，提出一種新的禁忌方法，大大縮短計算時間，提高運算效率。最后用實例研究，驗證該算法的高效、快速與穩健，給車輛配送路徑問題提供一定參考價值。

關鍵詞：禁忌搜索；車輛調度；路徑規劃

本文為2017年中國物流學會、中國物流與采購聯合會研究課題計劃項目：“基于禁忌搜索算法的車輛協作與路徑規劃研究”（項目編號：2017CSLKT3-071）

中圖分類號：F27 文獻標識碼：A

收錄日期：2017年5月24日

引言

低碳物流體系體現在包裝、運輸、配送等方面，車輛在運輸時優先規劃配送路徑能夠充分縮短客戶的服務時間，從而降低運輸成本，增加企業效益。目前，許多學者對車輛路徑調度問題做了研究，李文提出一種基于多個配送中心并可以同時取送貨物的車輛配送模型。李相勇對配送車輛路徑問題進行建模，用禁忌搜索算法進行計算。傅成紅、符卓根據VRP問題提出一種基于鄰域集合的動態候選集規模的禁忌搜索算法。Willard最早開始研究VRP的禁忌搜索算法，定義鄰域結構為交換算子與逆序排列，并將VRP問題通過轉化形成一個巨巡回。Pureza和Franga提出鄰域結構，將一個客戶點插入到另一條線路中或將兩條線路中的客戶點進行交換。本文提出一種改進的禁忌搜索算法，用節約里程法獲得初始解，縮短搜索時間，更快獲得最優解，通過仿真試驗驗證該模型和算法的有效性和適用性。

一、問題描述與模型建立

一般的車輛路徑問題（VRP）是指給定幾個約束條件并且符合約束，對所有客戶分配合適的運輸路線，使總運輸距離最短。車輛路徑問題（VRP）模型可以描述為：有一個配送中心0和n個待服務的客戶點，客戶集合C={1，2，…，n}，運輸車輛從配送中心出發，完成指定的運輸路線后回到配送中心，車輛集合表示為A={1，2，…，m}，Cm（Cm∈C）表示車輛m∈A所服務的客戶點集合。設每輛車最多的裝載量為Q，客戶點i的需求量為qi，客戶i與客戶j之間的距離為cij，單位運輸費用為a，每輛車的運輸費用系數用l表示，設每個客戶的成功運輸概率為b。本文的模型目標定為總運輸費用最小，在滿足一定的約束條件下建立如下模型：

目標函數為：

約束條件2表示每個客戶點都能被訪問且只能被訪問一次；約束條件3表示將車輛發生運輸失敗的概率限制在b以內，而且每輛車在安排的運輸路線中要滿足車輛容量限制；約束條件4、5、6表示每輛車都是從配送中心出發，每個客戶都能被服務且配送車輛在完成任務后最終返回配送中心；約束條件7表示每個客戶服務情況只有兩種，是對其整數化的約束。

二、算法設計

禁忌搜索算法（TS）是一種局部迭代搜索算法，TS主要使用一種侵略性的局部搜索機制，每迭代一次，算法都探索搜索空間，選擇可能將當前解X推向鄰域N（X）中最好解的移動。初始解的選取對計算過程有很大的影響，本研究先通過節約里程法獲得初始解，再用禁忌搜索算法進行計算，這樣將減少運算次數。本文中的禁忌搜索算法運用步驟為：

（一）初始解。設該客戶為當前節點c，該運輸車輛在此線路裝載的貨物量為demand=q（c），該車輛運輸的長度為d，根據節約里程法求得一個初始解x0。

（二）鄰域結構。鄰域結構通過以下算子構成：交換算子N1（x0，i，j，Gj），換運輸路線中客戶點i和客戶點j的位置；插入算子N2（x0，i，j，Gj），將客戶點i插入到線路中客戶點排j之后；2-opt交換算子N3（x0，i，j，Gj），將客戶點i和客戶點j之間的運輸路線順序逆轉。

（三）候選集。候選集中一般存放鄰域中的已經比較過的最優點，候選集的大小設定為一固定常數。

（四）禁忌移動。T表示一個禁忌表，表中記錄被禁忌的元素，通過鄰域結構選擇不同的禁忌方式。

（五）特赦準則。當有一個要被禁忌的解的值比目前任何一個解都好，則釋放該解，并將此解作為最好解。

（六）終止條件。可以設置一個數值，當運算次數達到該數時則結束，或者設置一個最優值，目標值達到或接近于最優值時則結束運算。

三、算例分析

實例描述：在某一物流企業，設某物流配送中心的坐標為（13.6km，25.4km），選取20個客戶作為實驗分析，目標函數為獲取最短運輸路徑，在該物流中心共有4輛運輸車，每輛車的型號都一樣，一輛車最多裝載10t貨物，不允許超載。每個客戶的需求信息與位置如表1所示。（表1）

設置其禁忌長度為10，迭代步數選取500，則對該算例計算10次，運用Matlab軟件對其算法進行運行，得到的結果如表2所示。（表2）

通過計算結果可以得出：通過對該實例進行10次運算求解，解的質量都比較優異，求得最短運輸距離為104.3km，最長運輸距離為114.2km，平均運輸距離為108.5km；第5次運算迭代步數最少，為256次。10次求解中第9次求的解最優，計算的配送總距離最短為104.3km，運輸路線為：路線1：0-1-5-10-13-6-11-20-0；路徑2：0-12-4-9-15-17-7-0；路徑3：0-16-18-19-3-0；路徑4：0-14-2-8-0。禁忌搜索算法比其他算法計算效率更高，收斂速度更快。初始解的選取先用節約里程算法獲得，大大減少迭代次數，更快獲得最優解。

四、結論

本文通過運用禁忌搜索算法對車輛配送路線進行規劃，并運用實例進行了驗證，禁忌搜索算法在路徑規劃方面取得廣泛推廣，計算效率快，得出的結果質量較高，很穩定。在對初始解的選取上先運用節約算法獲得一個初始解，這樣能夠大大縮短運算時間，快速取得計算結果。

主要參考文獻：

[1]Alan Laurence Erera.Design of Large-Scale Logistics Systems for Uncertain Environments[D].California：University of colifomia，Berkeley，2000.

[2]李文.物流配送同時取送貨低碳車輛調度模型及其QEA研究[D].浙江工業大學，2015.

[3]李相勇.車輛路徑問題模型及算法研究[D].上海交通大學，2007.

[4]傅成紅，符卓.一種毗鄰信息改進的車輛路徑問題禁忌搜索算法[J].系統工程，2010.5.

[5]J.A.G.Willard.Vehieling Routiting Using r-Optimal Tabu Search.M.se.dissertation，ImPerial College，1989.

[6]V.M.Pureza and P.M.Franca.Vehicle routing problems via tabu search metaheuristic.Technical Report Techinical Report CRT-347，Centre for researeh on transportation，1991.

[7]劉霞，齊歡.帶時間窗的動態車輛路徑問題的局部搜索算法[J].交通運輸工程學報，2008.5.