基于禁忌算法的帶模糊需求集送一體化路徑優(yōu)化

汪浩祥，楊彥歡，馮 英

WANG Hao-xiang,YANG Yan-huan,FENG Ying

（南京農(nóng)業(yè)大學(xué) 工學(xué)院，江蘇 南京 210031）

(College of Engineering,Nanjing Agricultural University,Nanjing 210031,China)

0 引言

車輛路徑問題（Vehicle Routing Problem，VRP） 最早是在1959年由Dantzig和Ramser[1]首先提出。是指對(duì)一系列客戶的需求點(diǎn)，設(shè)計(jì)一組開始和結(jié)束于一個(gè)中心出發(fā)點(diǎn)的最小費(fèi)用路徑。每個(gè)顧客只能被服務(wù)一次，而且一個(gè)車輛服務(wù)的顧客數(shù)不能超過它的能力。針對(duì)VRP問題的提出，國(guó)內(nèi)外學(xué)者們對(duì)不同背景的VRP問題做了大量的研究工作。針對(duì)物流配送，常見的車輛路徑問題有以下幾種類型：帶容量約束的車輛路徑問題；多車型車輛路徑問題；帶時(shí)間窗的車輛路徑問題；帶回程運(yùn)輸?shù)能囕v路徑問題；相容性約束車輛路徑問題和不確定性車輛路徑問題等。對(duì)應(yīng)于不同類型的配送問題，國(guó)內(nèi)外很多的科學(xué)家、工程師和管理學(xué)者都對(duì)這一問題進(jìn)行了探討。先后涌現(xiàn)了大量的解決VRP問題的啟發(fā)式、亞啟發(fā)式算法。如Clark和Wright在1964提出的節(jié)約算法；Lin在1965年提出的2-opt和3-opt交換算法；Gillett和Miller在1974年提出的Sweep算法等，以及近年來出現(xiàn)的亞啟發(fā)式算法，如遺傳算法（Genetic Algorithm）、模擬退火算法（Simulated Annealing）、禁忌搜索算法（Tabu Search）、神經(jīng)網(wǎng)絡(luò)（Neutral Network） 等。

然而，在以往的絕大多數(shù)VRP問題中，人們一般在假定構(gòu)造路徑之前，所有的信息（包括顧客信息，車輛信息）都是確定的，而在實(shí)際應(yīng)用的過程中，由于客觀世界存在的不確定因素，以及人類主觀因素的影響，車輛路徑問題的某些參數(shù)可能是不確定的。近幾年，不確定性路徑問題引起各界學(xué)者的注意。Teodorovicc[2]等學(xué)者針對(duì)顧客需求不確定的車輛路徑問題開展研究，其假設(shè)各個(gè)客戶的需求是模糊的，并采用三角型模糊數(shù)來描述這一模糊的客戶需求。侯玲娟[3]等學(xué)者針對(duì)一類不確定需求和旅行時(shí)間下的隨機(jī)車輛路徑問題，建立了一個(gè)隨機(jī)規(guī)劃模型，提出了一種帶有自適應(yīng)機(jī)制的改進(jìn)遺傳算法。邢占文[4]在前人的研究基礎(chǔ)上，綜合各種不確定因素，包括需求不確定，車輛不確定等。引入“假設(shè)客戶”的概念，將動(dòng)態(tài)問題轉(zhuǎn)化為靜態(tài)問題，并提出基于非精確距離矩陣的共軛優(yōu)化算法進(jìn)行優(yōu)化。

在隨機(jī)需求車輛路徑問題（Vehicle Routing Problem with Stochastic Demands,VRPSD）提出以來，許多專家學(xué)者提出了有關(guān)求解本類問題的求解算法。其中D.Teodorovic和Pavkovic運(yùn)用Gilett和Miller[5]提出的sweeping算法，甘勤濤，陽平華，童鐘靈[6]提出禁忌搜索算法求解本問題。張建勇，李軍[7]通過引入決策者主觀偏好值的概念，提出了求解具有模糊特征的車輛路徑問題的模糊機(jī)會(huì)規(guī)劃模型問題的一種基于模糊模擬的混合遺傳算法。

本文研究的集送貨一體化車輛路徑問題（Vehicle Routing Problem with Pick-up and Delivery,VRPPD）是允許同時(shí)集貨和送貨的混合作業(yè)，此類問題是假設(shè)某一顧客需求點(diǎn)同時(shí)存在集貨需求和送貨需求時(shí)，允許在該顧客點(diǎn)同時(shí)進(jìn)行集貨作業(yè)和配貨作業(yè)問題的一個(gè)分類。郎茂祥[8-9]對(duì)具有多種類型車輛、具有行駛里程限制、同時(shí)考慮集貨及送貨過程的VRP問題，給出了基于貨量參數(shù)的雙下標(biāo)數(shù)學(xué)模型。本文基于雙下標(biāo)集散一體化模型，結(jié)合模糊車輛路徑問題（Fuzzy Vehicle Routing Problem，F(xiàn)VRP）引入三角模糊需求數(shù)。提出一種適合實(shí)際情況的車輛路徑問題，并基于禁忌算法進(jìn)行求解。

1 問題的描述及模型的建立

結(jié)合文獻(xiàn)[7]建立帶有模糊需求的集散一體化模型，將適用于本論文的模型描述如下：設(shè)配送中心有K輛車，其中車輛的載重量為（ k=1,2,3,…,K），其一次配送的最大行駛距離，需要向L個(gè)客戶送貨和取貨。其中客戶i的需求量為。供應(yīng)量為ui（ i=1,2,3,…,L ）。客戶i到客戶j的距離為sij。配送中心到每個(gè)客戶的距離為soj（ i,j=1,2,…,L ）設(shè)nk為第K臺(tái)車輛配送的客戶數(shù)（nk=0表示未使用第k個(gè)車輛），用Rk表示第k條路徑，其中的元素rki表示客戶rki在路程k中的順序?yàn)閕（不包括配送中心），令rki=0表示配送中心。本文考慮的目標(biāo)是行駛距離最小化。

本文通過引用Zadeh[8]提出的模糊集的概念來建立適合本文的模型。模糊集即給定論域X上的一個(gè)模糊集，是指對(duì)任何x∈R，都有一個(gè)數(shù)μ（x）∈［0,1］與之對(duì)應(yīng)。u（x）稱為模糊集u的隸屬函數(shù)，或稱u（x）為x對(duì)模糊集u的隸屬度。

設(shè)s和u分別為模糊數(shù)的下限和上限，m為可能性最大的值，那么模糊效用（s、m、u）表示。其隸屬函數(shù)為：

1.1 解決問題的基本思路

任意給定的一個(gè)客戶，都具有三個(gè)重要的屬性，即自身的地理位置、需求量和供應(yīng)量。就一個(gè)配送問題來說，隨著某一車輛服務(wù)的節(jié)點(diǎn)數(shù)增加，由于該問題中需求量是模糊的，導(dǎo)致車的剩余裝載能力也是模糊的。正是由于這種模糊性存在，很難確定在該車輛完成前k-1個(gè)節(jié)點(diǎn)的服務(wù)之后，是否還有能力繼續(xù)服務(wù)第k個(gè)節(jié)點(diǎn)，只是能確定，當(dāng)車輛的剩余運(yùn)輸能力越大，而第k個(gè)節(jié)點(diǎn)的供貨量越大，需求量越小，該車能夠服務(wù)第k個(gè)節(jié)點(diǎn)的機(jī)會(huì)就越大。為了解決這種模糊需求條件下的集收送一體化配送問題，本文引入三角模糊數(shù)來概率化服務(wù)第k個(gè)節(jié)點(diǎn)的可能性。對(duì)于給定節(jié)點(diǎn)的需求模糊數(shù)是~d=d1,d2,d3（ ），設(shè)某車輛服務(wù)完第k個(gè)節(jié)點(diǎn)之后，已裝載的貨物的貨物量為：

（j=1,2,3,…,nk-1）設(shè)第k個(gè)節(jié)點(diǎn)可以被服務(wù)的可能性為p，運(yùn)用三角模糊表示為：

很明顯，P越大，該車能夠服務(wù)第k個(gè)節(jié)點(diǎn)的可能性就越大，在此，設(shè)P*（P*∈ ［0,1］）表示決策者根據(jù)歷史數(shù)據(jù)得到的，需求變動(dòng)條件下給出的關(guān)于P的主觀臨界值。對(duì)于給定的P*值，若P≥P*，則可以服務(wù)k點(diǎn)，否則，派新車完成這一任務(wù)。重復(fù)以上過程，直到所有的客戶都安排完畢。

1.2 模型的建立

綜上所述，該模糊車輛調(diào)度問題的模型建立如下：

在此模型中，目標(biāo)（1）表示最小化運(yùn)行距離。約束（2）、（3）、（4） 表示配送過程中其載貨量不超過其載重量。其中約束（3）表示模糊需求條件下，可以運(yùn)載第K個(gè)客戶的可能性大于給定的主觀臨界值。約束（5）表示配送過程中行駛距離不超過最大允許的行駛距離。約束（6）、（7）、（9）、（10）表示L個(gè)客戶全部被服務(wù)，且每個(gè)客戶只能由一輛車來服務(wù)。

2 基于模糊需求的禁忌搜索算法

本文在文獻(xiàn)[6]所提出的配送車輛優(yōu)化調(diào)度問題的禁忌搜索算法的基礎(chǔ)上，結(jié)合本文所建的模型進(jìn)行算法改進(jìn)，修改客戶可以被運(yùn)輸?shù)目赡苄砸笥诮o定的P*，同時(shí)在單配送的禁忌算法基礎(chǔ)上改進(jìn)適合本模型的為集送一體化的算法。

Step1：參數(shù)設(shè)置，輸入各個(gè)參數(shù)。選取一個(gè)常數(shù)來確定禁忌長(zhǎng)度。對(duì)于候選集的確定，從當(dāng)前解的領(lǐng)域中隨機(jī)選擇若干個(gè)領(lǐng)域。設(shè)置迭代步數(shù)。

Step2：生成模糊需求。根據(jù)提供的歷史數(shù)據(jù)，得到隸屬度為1確定需求量，即d2。采用隨機(jī)數(shù)的方式產(chǎn)生d1和d3。具體步驟是：隨機(jī)生成一個(gè)［0,1］范圍內(nèi)和［1,2］范圍內(nèi)的數(shù)，根據(jù)實(shí)際歷史數(shù)據(jù)，可以確定范圍。重復(fù)上述步驟，直至生成所有的顧客的模糊需求量。

Step3：采用客戶直接排列的方式，隨機(jī)產(chǎn)生初始解。

Step4：對(duì)于某個(gè)解，按其排列方式進(jìn)行約束檢驗(yàn)。具體步驟是：先將第k個(gè)點(diǎn)加入到路線中，計(jì)算出加入k點(diǎn)之后的P值，與給定的主觀臨界值P*比較，如果滿足條件再進(jìn)行其他約束條件的檢驗(yàn)。如果滿足，就加入第k點(diǎn)，如果不滿足，就將K點(diǎn)加入一臺(tái)新的車輛。直至所有的客戶點(diǎn)均被安排。

Step5：對(duì)于某個(gè)解，進(jìn)行解的評(píng)價(jià)。具體步驟是：根據(jù)步驟3，對(duì)于超過配送中心提供的車輛的數(shù)目，設(shè)其為對(duì)應(yīng)的配送路徑方案中的不可行路徑數(shù)M，給配送路徑方案的目標(biāo)函數(shù)值為Z，并設(shè)對(duì)每條不可行路徑的懲罰權(quán)數(shù)為Pw。采用E=Z+M×Pw進(jìn)行解的評(píng)價(jià)。

Step6：從當(dāng)前解的領(lǐng)域中隨機(jī)選擇若干個(gè)領(lǐng)域。通過兩交換法實(shí)現(xiàn)領(lǐng)域的操作，將每次迭代的最好解作為禁忌對(duì)象放在禁忌表中。進(jìn)行禁忌操作。選擇記錄最好解。

Step7：直到進(jìn)行了指定步數(shù)的迭代，終止程序。步驟流程圖如圖1所示。

3 實(shí)驗(yàn)計(jì)算及結(jié)果分析

本文采用文獻(xiàn)[8]一書中的例6.1進(jìn)行實(shí)驗(yàn)計(jì)算。設(shè)配送中心和20個(gè)客戶分布在一個(gè)邊長(zhǎng)為20km的正方形區(qū)域內(nèi)，每個(gè)客戶的需求量與供應(yīng)量以及客戶在2t以下，配送有10臺(tái)車，最大載重量為8t，車輛一次配送最大行駛距離為50km。作者用計(jì)算機(jī)隨機(jī)產(chǎn)生的配送中心和20個(gè)客戶位置坐標(biāo)以及客戶的貨物需求量和供應(yīng)量如表1。（配送中心的坐標(biāo)為（3.2km，14.1km）X表示橫坐標(biāo)，Y表示縱坐標(biāo)，Q表示隸屬度為1需求量，U表示供應(yīng)量）。

表1 客戶信息表

根據(jù)本例的特點(diǎn)，采用了如下參數(shù)：對(duì)不可行路徑的懲罰pw取300km，每次迭代共搜索當(dāng)前解的40個(gè)鄰居，禁忌長(zhǎng)度取10，迭代步數(shù)取400，主觀臨界值P*取0.8。對(duì)實(shí)例6.1用禁忌算法隨機(jī)求解10次，得到的結(jié)果見表2、路徑迭代過程見圖2。

從表2中可以看，在主觀模糊需求下可提供服務(wù)臨界值0.8概率的情況下，用禁忌搜索算法對(duì)實(shí)例的10次求解過程中，得到了質(zhì)量很高的解，其配送總里程的平均值為116.47km平均使用的車輛是3輛，與實(shí)例6.1中不考慮需求模糊性相比，運(yùn)輸距離平均增加1.04km，也就是由于不確定性，導(dǎo)致運(yùn)輸距離增加。其中第9次解的質(zhì)量最高，配送里程112.9km，對(duì)應(yīng)的配送方案為：0-4-14-5-12-2-9-15-1-0,0-7-8-19-16-13-6-11-20-3-10-18-0,0-17-0。

表2 計(jì)算結(jié)果統(tǒng)計(jì)表

4 結(jié)束語

本文在對(duì)集收送一體化配送問題進(jìn)行簡(jiǎn)單描述的基礎(chǔ)上，結(jié)合實(shí)際終端配送過程中的實(shí)際需求不確定性，通過引入模糊數(shù)的概念，建立了具有模糊特征的集收送一體化路徑問題的規(guī)劃模型。給出了解決這一類終端配送問題的基本解題思路，提出了一種求解帶有模糊需求的集散一體化的這類問題的禁忌搜索算法，并且通過實(shí)例驗(yàn)證這種算法的可行性。

[1] Bodin L,Golden B,Assad A,et al.Routing and scheduling of vehicles and crews:the st ate of the art[J].Computer and Operation Research,1983(10):62.

[2] Teodorovic D,Pavkovic G..The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J].Fuzzy Set and System,1996,82(3):307-317.

[3] 侯玲娟，周泓，梁春華.不確定需求和旅行時(shí)間下的車輛路徑問題[J].計(jì)算機(jī)集成制造系統(tǒng)，2011,17(1):101-107.

[4] 邢占文.考慮不確定因素條件下帶回程取貨的車輛路徑問題研究[D].西安：長(zhǎng)安大學(xué)（博士學(xué)位論文），2011.

[5] Gillett B,Miller L.A heuristic algorithms for the vehicle routing dispatch problem[J].Operational Reserarch,1974,22(22):340-349.

[6] 甘勤濤，陽平華，童鐘靈.模糊需求車輛路徑問題的禁忌搜索算法研究[J].長(zhǎng)春理工大學(xué)學(xué)報(bào)，2006,29(1):84-85.

[7] 張建勇，李軍.模糊車輛路徑問題的一種混合遺傳算法[J].管理工程學(xué)報(bào)，2005(2):23-26.

[8] 郎茂祥.配送車輛優(yōu)化調(diào)度模型預(yù)算法[M].北京：電子工業(yè)出版社，2009.

[9] 郎茂祥.裝卸混合車輛路徑問題的模擬退火算法研究[J].系統(tǒng)工程學(xué)報(bào)，2005(5):41-47.