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

汪浩祥，楊彥歡，馮 英

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

（南京農業大學 工學院，江蘇 南京 210031）

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

0 引言

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

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

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

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

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

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

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

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

1.1 解決問題的基本思路

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

（j=1,2,3,…,nk-1）設第k個節點可以被服務的可能性為p，運用三角模糊表示為：

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

1.2 模型的建立

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

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

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

本文在文獻[6]所提出的配送車輛優化調度問題的禁忌搜索算法的基礎上，結合本文所建的模型進行算法改進，修改客戶可以被運輸的可能性要大于給定的P*，同時在單配送的禁忌算法基礎上改進適合本模型的為集送一體化的算法。

Step1：參數設置，輸入各個參數。選取一個常數來確定禁忌長度。對于候選集的確定，從當前解的領域中隨機選擇若干個領域。設置迭代步數。

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

Step3：采用客戶直接排列的方式，隨機產生初始解。

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

Step5：對于某個解，進行解的評價。具體步驟是：根據步驟3，對于超過配送中心提供的車輛的數目，設其為對應的配送路徑方案中的不可行路徑數M，給配送路徑方案的目標函數值為Z，并設對每條不可行路徑的懲罰權數為Pw。采用E=Z+M×Pw進行解的評價。

Step6：從當前解的領域中隨機選擇若干個領域。通過兩交換法實現領域的操作，將每次迭代的最好解作為禁忌對象放在禁忌表中。進行禁忌操作。選擇記錄最好解。

Step7：直到進行了指定步數的迭代，終止程序。步驟流程圖如圖1所示。

3 實驗計算及結果分析

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

表1 客戶信息表

根據本例的特點，采用了如下參數：對不可行路徑的懲罰pw取300km，每次迭代共搜索當前解的40個鄰居，禁忌長度取10，迭代步數取400，主觀臨界值P*取0.8。對實例6.1用禁忌算法隨機求解10次，得到的結果見表2、路徑迭代過程見圖2。

從表2中可以看，在主觀模糊需求下可提供服務臨界值0.8概率的情況下，用禁忌搜索算法對實例的10次求解過程中，得到了質量很高的解，其配送總里程的平均值為116.47km平均使用的車輛是3輛，與實例6.1中不考慮需求模糊性相比，運輸距離平均增加1.04km，也就是由于不確定性，導致運輸距離增加。其中第9次解的質量最高，配送里程112.9km，對應的配送方案為：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 計算結果統計表

4 結束語

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

[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] 侯玲娟，周泓，梁春華.不確定需求和旅行時間下的車輛路徑問題[J].計算機集成制造系統，2011,17(1):101-107.

[4] 邢占文.考慮不確定因素條件下帶回程取貨的車輛路徑問題研究[D].西安：長安大學（博士學位論文），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].長春理工大學學報，2006,29(1):84-85.

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

[8] 郎茂祥.配送車輛優化調度模型預算法[M].北京：電子工業出版社，2009.

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