摘要：文章提出了一種利用禁忌搜索技術(shù)來解決超市免費(fèi)班車最優(yōu)路線的選擇問題的算法，并給出了該算法的具體實(shí)現(xiàn)細(xì)節(jié)。通過實(shí)驗(yàn)數(shù)據(jù)，驗(yàn)證了該算法的有效性。

關(guān)鍵詞：超市；禁忌搜索；最優(yōu)路線

一、引言

隨著我國經(jīng)濟(jì)的發(fā)展，大型超市也被卷入競(jìng)爭(zhēng)的潮流，如何獲得最為廣闊的消費(fèi)市場(chǎng)成為關(guān)注的焦點(diǎn)。因此，一個(gè)大型超市不僅要在其建立之初進(jìn)行選址定位，考察其投入的必要性、可計(jì)算的直接、間接效益，更需要在以后的經(jīng)營中不斷尋找提高其經(jīng)營效益的方法或者措施。在超市的經(jīng)營過程中，存在著許多優(yōu)化決策的問題。本文只討論超市免費(fèi)班車最優(yōu)路線的選擇問題。合理地選擇班車路線，對(duì)增加客戶流、提高服務(wù)質(zhì)量、增加經(jīng)濟(jì)效益以及降低運(yùn)營成本都有很大影響，本文將使用禁忌搜索算法來解決該問題。

二、超市免費(fèi)班車服務(wù)的特點(diǎn)、要求以及數(shù)學(xué)模型

（一）超市免費(fèi)班車服務(wù)的特點(diǎn)

在國內(nèi)，由于受經(jīng)濟(jì)發(fā)展的限制，一些中小城市的中大型超市數(shù)量并不多，選址一般都選在市中心交通比較便利的地段。根據(jù)有關(guān)規(guī)則，一個(gè)大賣場(chǎng)的輻射半徑一般在3至5公里左右。然而在這個(gè)范圍內(nèi)居民點(diǎn)的數(shù)量非常有限，可贏得的消費(fèi)者數(shù)量并不多。因此一些大型超市推出了免費(fèi)購物班車服務(wù)，很大程度上擴(kuò)大了大賣場(chǎng)常規(guī)的“影響半徑”，以達(dá)到增加消費(fèi)者的數(shù)量。同時(shí)，大型超市具有價(jià)格便宜、商品豐富的優(yōu)勢(shì)，如果再加上便利的交通，那么社區(qū)市場(chǎng)將成為其潛在的大市場(chǎng)了。所以，為了努力爭(zhēng)取這個(gè)大市場(chǎng)，大型超市就想盡辦法給消費(fèi)者創(chuàng)造交通便利的條件。于是，提供免費(fèi)購物班車服務(wù)就成了大型超市通用的措施之一。既然許多大型超市已經(jīng)選擇了免費(fèi)購物班車服務(wù)，那么他們肯定都希望能夠花最少的人力、物力和財(cái)力來完成這項(xiàng)服務(wù)，而且還要求獲取最高的經(jīng)濟(jì)效益。于是問題就集中在免費(fèi)購物班車服務(wù)的路線選擇問題上。

（二）超市免費(fèi)班車選擇路線時(shí)必須滿足以下要求

路線必須經(jīng)過一定范圍內(nèi)（這個(gè)范圍必須是大于3至5公里）的所有大型居民點(diǎn)。

路線不能重復(fù)。

班車往返一次路線所需時(shí)間和行程最短。

（三）超市免費(fèi)班車最優(yōu)路線的數(shù)學(xué)模型

首先把社區(qū)、學(xué)校、換乘車站點(diǎn)抽象為點(diǎn)要素，并且作為頂點(diǎn)集N，這樣就滿足了大型超市選擇路線時(shí)的第一個(gè)要求，即必須經(jīng)過一定范圍內(nèi)（這個(gè)范圍必須大于3至5公里）的所有大型居民點(diǎn)，同時(shí)也把城市交通道路抽象為線要素，作為弧線集A。

其次是對(duì)弧線集A中的每條道路aij=（Ni，Nj）賦權(quán)值Cij。權(quán)值Cij是用來表示i與j節(jié)點(diǎn)之間的弧的費(fèi)用。根據(jù)采集到屬性數(shù)據(jù)，即消費(fèi)者購物的時(shí)間、頻率、品種，車輛的耗費(fèi)以及道路的車流量等來獲取的。如果道路通暢，車流量比較少，路程比較短，則我們賦與道路的權(quán)值Cij的值就比較小，即可以免費(fèi)班車行駛的時(shí)間就比較短。其數(shù)學(xué)模型如圖1。

其中：V為車輛數(shù)，N為0，1，2...n+1，共n+2個(gè)節(jié)點(diǎn)。0，n+1為超市；條件（2）表示每一個(gè)節(jié)點(diǎn)只能被訪問一次，當(dāng)?shù)趉輛車經(jīng)過ij弧時(shí)，Xijk的值為1，否則Xijk值為0；條件（3）表示每一條線路的節(jié)點(diǎn)需求和不能超過車的容量；條件（4）、（5）、（6）確保每輛車從中心離開，服務(wù)節(jié)點(diǎn)后離開，最后回到這個(gè)中心。

三、禁忌搜索算法

（一）算法描述及步驟

禁忌搜索算法的基本思想是：隨機(jī)給出一個(gè)初始解作為當(dāng)前解，在當(dāng)前解的鄰域中確定若干候選解；如果某一候選解對(duì)應(yīng)的目標(biāo)值滿足藐視規(guī)則，則忽略其禁忌特性，并用它替換當(dāng)前解和全局最優(yōu)狀態(tài)（best so far），然后將它加入禁忌表，同時(shí)更新禁忌表；如果不存在上述解，選擇候選解中的非禁忌的最佳狀態(tài)為當(dāng)前解，同樣將其相應(yīng)的對(duì)象加入禁忌表，并更新禁忌表；如此重復(fù)上述過程，直至滿足終止準(zhǔn)則。

禁忌搜索算法的步驟如下：

1、給定算法參數(shù)，隨機(jī)產(chǎn)生初始解x，將禁忌表置空；

2、判斷終止條件是否滿足？如滿足，結(jié)束算法并輸出最優(yōu)結(jié)果；

3、利用當(dāng)前解x的鄰域函數(shù)產(chǎn)生其鄰域解，從中確定候選解y；

4、判斷y是否滿足藐視規(guī)則？滿足則用此候選解y替代x成為當(dāng)前解，并將y進(jìn)禁忌表，同時(shí)替換“best so far”狀態(tài)，轉(zhuǎn)步驟2；否則：

5、判斷候選解的禁忌屬性，選擇候選解集中非禁忌對(duì)象對(duì)應(yīng)的最佳狀態(tài)為新的當(dāng)前解，同時(shí)將其相應(yīng)的禁忌對(duì)象進(jìn)禁忌表；

6、轉(zhuǎn)步驟2。

（二）算法設(shè)計(jì)

1、解的編碼。用一條路線所經(jīng)過節(jié)點(diǎn)的排列來表示一個(gè)解。例如可行解45236，則表示該路線依次經(jīng)過節(jié)點(diǎn)4，節(jié)點(diǎn)5，節(jié)點(diǎn)2，節(jié)點(diǎn)3，節(jié)點(diǎn)6。

2、初始解的選取。隨機(jī)選取從超市到某一節(jié)點(diǎn)的通路作為初始解。

3、鄰域的選擇。確定鄰域的搜索方法是禁忌搜索算法的一個(gè)重要步驟。本文采用互換法進(jìn)行鄰域操作，即隨機(jī)交換2個(gè)點(diǎn)的位置，這種互換法的每個(gè)狀態(tài)的鄰域解有C2m=m（m-1）/2個(gè)。因?yàn)樵诒疚闹凶罱K要回到始點(diǎn)，所以在實(shí)際隨機(jī)交換2個(gè)點(diǎn)時(shí)，不包括代表超市的初始點(diǎn)，即實(shí)際的鄰域解有Cm-12+1個(gè)。

4、禁忌對(duì)象的確定。禁忌對(duì)象是指那些被放置在禁忌表中的變化元素。禁忌的目的是為了盡量避免迂回搜索，本文將每次迭代的最優(yōu)解作為禁忌對(duì)象放入禁忌表中。

5、禁忌長(zhǎng)度和候選集的確定。禁忌長(zhǎng)度是禁忌對(duì)象在不考慮藐視準(zhǔn)則的情況下不能被選取的最大次數(shù)；候選集在當(dāng)前解的鄰域中選取。本文確定的禁忌長(zhǎng)度為sqrt（m），m為鄰域中解的個(gè)數(shù)；從鄰域中選取最優(yōu)的5個(gè)放入候選集中。

6、為簡(jiǎn)單起見，本文沒有使用藐視規(guī)則。如果在上一步中找到的解發(fā)現(xiàn)在禁忌表中，則重新開始找不同的備選解。

7、評(píng)價(jià)函數(shù)的設(shè)計(jì)。本文使用一條路線所經(jīng)過的節(jié)點(diǎn)之間的弧的權(quán)值的和函數(shù)最為憑借函數(shù)。

8、終止規(guī)則。為簡(jiǎn)單起見，本文采用的是確定迭代次數(shù)的終止規(guī)則。

結(jié)合以上幾點(diǎn)以及上一節(jié)中的禁忌搜索算法步驟，我們就可以得到使用緊急搜索算法解決超市免費(fèi)班車最優(yōu)路線的選擇問題。

四、數(shù)值試驗(yàn)及結(jié)果分析

實(shí)驗(yàn)由1個(gè)超市8個(gè)節(jié)點(diǎn)組成的路線。有2輛車用于接送客戶，每輛車的限載容量為8人，最大行駛距離為50km。已知各節(jié)點(diǎn)與超市中心、各節(jié)點(diǎn)之間的距離及各節(jié)點(diǎn)需求量，如表1所示（0表示超市中心）。要求合理安排車輛的行駛路線，使總運(yùn)行費(fèi)用最少，即總運(yùn)輸里程最小。問題的最優(yōu)解為：

總運(yùn)輸里程為67.5km.

五、結(jié)束語

通過實(shí)驗(yàn)結(jié)果可以看出，本文設(shè)計(jì)禁忌搜索算法找到解的質(zhì)量較高，是求解超市免費(fèi)班車最優(yōu)路線的選擇問題的一種可行的優(yōu)化算法。

參考文獻(xiàn)：

1、池潔，李莉.物流中配送區(qū)域與配送路線的網(wǎng)絡(luò)優(yōu)化法[J].運(yùn)籌與管理，2003(2).

2、Jean-Yves Potvin，Jean-MarcRousseau.A parallel route building algorithm for the vehicle routing and scheduling problem with time windows[J].European Journal of Operational Research.1993(66).

3、Tan K C，Lee H，Ou K.Hybrid genetic algorithms in solving vehicle routing problems with time window constraints[J].Asia-Pacific Journal of Operational Research，2001(1).

4、王細(xì)元.超市免費(fèi)班車最優(yōu)路線的選擇[J].技術(shù)與市場(chǎng)，2007(6).

5、王東平，李紹榮.禁忌搜索算法用于解決網(wǎng)絡(luò)路由問題[J].計(jì)算機(jī)科學(xué)，2003(6).

（作者簡(jiǎn)介：王新春，山東師范大學(xué)在讀博士，現(xiàn)任職于濟(jì)南職業(yè)學(xué)院計(jì)算機(jī)系；于曉萍，濟(jì)南職業(yè)學(xué)院計(jì)算機(jī)系主任、教授；姜玉帛，山東建筑大學(xué)副教授）

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”