帶軟時間窗約束的多車場車輛路徑問題及其禁忌搜索算法研究

何小年

（湖南涉外經濟學院信息與機電工程學院 湖南 長沙 410205）

0 引言

車輛路徑優化是物流配送中的核心問題，對提高配送活動的效率和效益至關重要。自DANTAIG等[1]于1959年首次提出車輛路徑問題（vehicle routing problem，VRP）以來，對該問題的研究不僅成果豐碩，而且熱度一直不減，究其原因，一是該問題的NP-難性質足以吸引科研人員，二是該問題及其更復雜的各類延伸問題的廣泛應用性。多車場問題即屬于這一類極為復雜的延伸問題。本文研究一種VRP的復雜的延伸問題——帶軟時間窗約束的多車場車輛路徑問題（multi-depot VRP with soft time windows, MDVRPSTW）。MDVRPSTW研究的是有多個車場可以同時對若干個有一定貨物需求量的客戶進行服務，要求在滿足各客戶貨物需求和時間約束的前提下，對各車場車輛和行駛路線進行適當安排，使總配送費用最低。我國城市規模人口和面積一般都較大，交通擁擠，單車場很難實現配送的及時性并且可能會導致配送成本增大，多車場能有效解決此問題，現實中也有許多物流企業采用多車場調度方案。

對于多車場車輛調度問題的求解，從現有研究文獻來看，有的采用多車場整體優化法還有的采用通用啟發式算法優化算法。整體優化法是設定一個虛擬車場，將所有車場假設成一個整體來求解路徑問題，LI等[2]采用整體法法把各個車場都考慮進來進行整體優化，得到最小的費用。但這種方法把多個發車點統一到一個發車點，對于不同發車點的車輛數限制、發貨量限制、時間限制都比較難處理。徐東洋等[3]、胡蓉等[4]、周鮮成等[5]、王新玉等[6]在其著作中采用通用啟發式優化算法的研究重點集中在如何合理地縮小搜索空間和簡化求解步驟上，本文采用現代啟發式算法把多車場車輛路徑問題看作一個復雜的組合優化問題進行研究。

1 MDVRPSTW問題描述與數學模型

MDVRPSTW可以描述為：有M個車場（編號分別為N+1,N+2,...,N+M），每個車場擁有容量為Q的車輛Km臺（m∈﹛N+1，N+2，…，N+M﹜），負責對N（客戶編號為1,2...,N）個客戶配送貨物，假設客戶點i的貨物需求量為di（i∈﹛1，2，…，N﹜）且di≤Q，每個客戶由任意一個車場的車輛服務但只能由一輛車服務一次。車輛早于客戶規定的時間窗到達則在此等待，需要支付一定的等待費用，車輛晚于客戶規定的時間窗到達則需支付一定的懲罰費用。完成任務后，各車輛直接返回各自原屬車場。為構造數學模型，定義變量如下：

根據各客戶的需求量和車輛載重量可估計出所需車輛數的下限：

其中，[*]表示向下取整。

符號說明：K—需要的車輛數；L—車輛最大行駛距離；Q—車輛最大載重量；i,j—待服務的客戶點和車場；dij—從客戶點i到客戶點j的直接的距離，距離矩陣視為對稱，即dij=dji；di—客戶點i的貨物需求量；l—每輛車每公里的配送費用；c—車輛固定費用；ai—客戶點i的最早服務時間；bi—客戶點i的最晚服務時間；ti—車輛到達客戶點i的時間；tij—從客戶點i到客戶點j所需要的時間；p1—早于ai到達客戶點i等待時每分鐘的損失費用；v—平均車速；p2—晚于bi到達客戶點i并服務的延遲懲罰費用。客戶點i和客戶點j在同一路線且客戶點j恰好在客戶點i之后服務，則車輛到達客戶點j的時間為：tj=ti+tij。

因此，MDVRPSTW數學模型可以描述為：

滿足：

模型中，式（2）表示第一個優化目標，最小化所需車輛數；式（3）表示第二個優化目標，最小化總的配送費用（包括車輛行駛費用，車輛固定使用費用以及時間窗偏離懲罰費用；式（4）表示每條路線的行駛距離限制；式（5）表示車輛受到載重量的限制；式（6）表示每個客戶點只能由一輛車服務且所有客戶點都要得到服務；式（7）表示K條路線都從車場出發，最后又回到原車場；式（8）表示不能從車場到車場；式（9）表示車場m的車輛k是否從客戶點i到客戶點j；式（10）表示客戶點i的貨物運輸任務是否由車場m的車輛k來完成的。

2 求解MDVRPSTW問題的禁忌搜索算法

禁忌搜索（tabu search，TS）算法是一種全局性鄰域搜索算法，模擬人類具有記憶功能的逐步尋優特征。它通過局部鄰域搜索機制和相應的禁忌準則來避免迂回搜索，并通過藐視準則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效搜索，最終實現全局優化。

2.1 禁忌搜索算法初始解的產生

在算法中需要一個初始解開始搜索過程。本文采用自然數編碼，以隨機方式產生初始解序列。

2.2 鄰域結構

禁忌搜索算法優化過程中一個很重要的組成部分就是鄰域結構，其作用就是如何由一個解來產生一個新的解。本算法使用了四種鄰域結構，即頂點重新指派、頂點交換“尾”交換和頂點2-Opt，以隨機的方式選擇其中一種領域結構應用于當前解。

2.3 算法的禁忌對象和禁忌長度

禁忌搜索算法的禁忌對象就是指禁忌表中被禁的那些局部最優解。本文將每次迭代得到的最好解，作為禁忌對象放人禁忌表中。算法的禁忌長度的長短決定解的選取，禁忌長度越短，獲得優良解的可能性就相應增大，但是同時增加了迂回搜索，難以探索其他有效的搜索途徑。本文的禁忌長度是在5到10之間隨機選取。

2.4 特赦規則

本文采用基于適配值的藐視準則，即如果候選集中所有的解都為禁忌解，則解禁候選集中的最好解。

2.5 終止準則

本文采用事先限定算法的迭代次數為終止準則，該準則是指給定最大的迭代步數，使總的迭代步數不超過這個數，事先限定算法的迭代步數能有效控制算法的運行時間。

2.6 多車場的處理

本文將多配車場中心車輛調度問題看作一個復雜的組合優化問題來進行研究。假定每個車場可以派出車輛數所限制的前提下，本算法在帶軟時間窗約束的多車場車輛路徑問題中多車場的處理方法是：從車場集合中隨機地選取一個車場，配送車從被選中的車場出發，到各個客戶點去完成配送任務，直到車輛足夠滿為止，在完成最后一個客戶點的任務后，返回原車場的一條路線。如果所有的客戶點還沒有服務完，又從車場集合中隨機選取一個車場，配送車從被選中車場出發，然后完成剩余的客戶點的配送任務，直到車輛足夠滿為止，在完成最后一個客戶點的任務后，返回原車場，一直循環，直到所有的客戶點的配送任務都服務完畢。

3 MDVRPSTW案例測試

本算法已經在Pentium-Ⅳ2.67 GHZ微機上使用Delphi語言編程實現。為了測試算法的計算效果，本文使用兩個案例進行計算，兩個案例客戶點坐標與載重量和時間窗數據見表1。兩個案例數據都包含30個客戶和4個車場，其中31、32、33、34為車場。假定車輛載重量為450，車速為1個單位，每一距離單位行駛費用為2.5，派車固定費用為100，車輛最大行駛距離為240，提前到達等待費用為0.2，延遲到達懲罰費用為2，忽略客戶點的服務時間。本文按照兩個案例數據分別進行計算，案例1的具體結果如表2所示、配送路徑圖如圖1所示；案例2的具體結果如表3所示、配送路徑圖如圖2所示。

表1 兩個案例的客戶點和各車場數據表

本文計算案例1的結果如表2所示，配送路徑如圖1所示：最優路徑總長度551.1，行駛費用為1 377.78，程序運行時間0.05，時間窗內的客戶點數29，等待與懲罰費用66.07，派車固定費用600，總費用為2 043.85。計算案例2的結果如表3所示，配送路徑如圖2所示：最優路徑總長度628.34，行駛費用為1 570.85，程序運行時間0.05，時間窗內的客戶點數28，等待與懲罰費用90.02，派車固定費用600，總費用為2 260.87。

表2 本文按照案例1的數據測試的結果

表3 本文按照案例2的數據測試的結果

圖1 本文按案例1數據測試結果的車輛配送線路圖

圖2 本文按案例2數據測試結果的車輛配送線路圖

4 結論

本文對帶軟時間窗約束的多車場車輛路徑問題進行了研究，建立了相應的數學模型。通過隨機選擇車場，然后從被選中的車場里隨機派車執行配送任務，車輛執行完配送任務后返回原車場，一直循環到所有的客戶點都被服務完畢，將帶軟時間窗約束的多車場車輛路徑問題的求解作為一個復雜的組合優化問題來研究，拓展了此類問題的求解算法。通過案例測試，得出了兩個案例最少的車輛數和最優的路徑優化解，能在較短的時間內得到滿意的結果，等待與懲罰費用也在合理的范圍內。這表明用本文設計的禁忌搜索算法能得到比較好的計算結果，計算效率也較高。