新常態(tài)下重慶會(huì)議型酒店發(fā)展研究

包代佳

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

關(guān)鍵詞：禁忌搜索；車輛調(diào)度；路徑規(guī)劃

本文為2017年中國物流學(xué)會(huì)、中國物流與采購聯(lián)合會(huì)研究課題計(jì)劃項(xiàng)目：“基于禁忌搜索算法的車輛協(xié)作與路徑規(guī)劃研究”（項(xiàng)目編號(hào)：2017CSLKT3-071）

中圖分類號(hào)：F27 文獻(xiàn)標(biāo)識(shí)碼：A

收錄日期：2017年5月24日

引言

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

一、問題描述與模型建立

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

目標(biāo)函數(shù)為：

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

二、算法設(shè)計(jì)

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

（一）初始解。設(shè)該客戶為當(dāng)前節(jié)點(diǎn)c，該運(yùn)輸車輛在此線路裝載的貨物量為demand=q（c），該車輛運(yùn)輸?shù)拈L度為d，根據(jù)節(jié)約里程法求得一個(gè)初始解x0。

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

（三）候選集。候選集中一般存放鄰域中的已經(jīng)比較過的最優(yōu)點(diǎn)，候選集的大小設(shè)定為一固定常數(shù)。

（四）禁忌移動(dòng)。T表示一個(gè)禁忌表，表中記錄被禁忌的元素，通過鄰域結(jié)構(gòu)選擇不同的禁忌方式。

（五）特赦準(zhǔn)則。當(dāng)有一個(gè)要被禁忌的解的值比目前任何一個(gè)解都好，則釋放該解，并將此解作為最好解。

（六）終止條件?？梢栽O(shè)置一個(gè)數(shù)值，當(dāng)運(yùn)算次數(shù)達(dá)到該數(shù)時(shí)則結(jié)束，或者設(shè)置一個(gè)最優(yōu)值，目標(biāo)值達(dá)到或接近于最優(yōu)值時(shí)則結(jié)束運(yùn)算。

三、算例分析

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

設(shè)置其禁忌長度為10，迭代步數(shù)選取500，則對(duì)該算例計(jì)算10次，運(yùn)用Matlab軟件對(duì)其算法進(jìn)行運(yùn)行，得到的結(jié)果如表2所示。（表2）

通過計(jì)算結(jié)果可以得出：通過對(duì)該實(shí)例進(jìn)行10次運(yùn)算求解，解的質(zhì)量都比較優(yōu)異，求得最短運(yùn)輸距離為104.3km，最長運(yùn)輸距離為114.2km，平均運(yùn)輸距離為108.5km；第5次運(yùn)算迭代步數(shù)最少，為256次。10次求解中第9次求的解最優(yōu)，計(jì)算的配送總距離最短為104.3km，運(yùn)輸路線為：路線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。禁忌搜索算法比其他算法計(jì)算效率更高，收斂速度更快。初始解的選取先用節(jié)約里程算法獲得，大大減少迭代次數(shù)，更快獲得最優(yōu)解。

四、結(jié)論

本文通過運(yùn)用禁忌搜索算法對(duì)車輛配送路線進(jìn)行規(guī)劃，并運(yùn)用實(shí)例進(jìn)行了驗(yàn)證，禁忌搜索算法在路徑規(guī)劃方面取得廣泛推廣，計(jì)算效率快，得出的結(jié)果質(zhì)量較高，很穩(wěn)定。在對(duì)初始解的選取上先運(yùn)用節(jié)約算法獲得一個(gè)初始解，這樣能夠大大縮短運(yùn)算時(shí)間，快速取得計(jì)算結(jié)果。

主要參考文獻(xiàn)：

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

[2]李文.物流配送同時(shí)取送貨低碳車輛調(diào)度模型及其QEA研究[D].浙江工業(yè)大學(xué)，2015.

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

[4]傅成紅，符卓.一種毗鄰信息改進(jìn)的車輛路徑問題禁忌搜索算法[J].系統(tǒng)工程，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]劉霞，齊歡.帶時(shí)間窗的動(dòng)態(tài)車輛路徑問題的局部搜索算法[J].交通運(yùn)輸工程學(xué)報(bào)，2008.5.