車輛數不確定的軟時間窗車輛路徑問題的改進遺傳算法

摘要：綜合考慮車輛數和行駛距離兩種優化目標，提出了VRPSTW的多目標優化模型，同時提出了解決VRPTW問題的一種改進遺傳算法。在算法中，通過適應度函數的變化，較好地解決了多目標優化的問題；通過對交叉算子改進，增加了算法的尋優能力，同時又克服了算法對群體多樣性的要求；針對遺傳算法局部搜索能力弱的問題，加入了2-opt局部搜索方法，很好地彌補了遺傳算法的不足。經過實驗，本方法能較好地解決VRPSTW問題，從而對運輸決策提供有力支持。

關鍵詞：車輛路徑問題；時間窗；遺傳算法（GA）；車輛數不確定

中圖分類號：TP18:U492.3+12文獻標識碼：A

文章編號：1002-3100(2008)02-0020-04

Abstract: Vehicle Routing Problem with Time Windows（VRPTW）is represented as a multi-objective optimization problem， both considering number of vehicles and total cost（distance）and simultaneously propose a improved genetic algorithm to resolve this problem. In the algorithm， we resolve the balance of the two objectives through fitness function; and by using the improved Cross-Over operation， we can not only increase search ability of the algorithm， but also get rid of the limit of diversity of population; adding 2-opt in the algorithm because of the lack of local search ability of Genetic Algorithm to increase the local search ability of the algorithm. The experiment result indicates that the algorithm is efficient for VRPSTW and can provide useful support to make decision.

Key words: vehicle routing problem; Time Window; Genetic Algorithm（GA）; uncertain number of vehicles

0引言

車輛路徑問題（Vehicle Routing Problem， VRP），是現代物流系統中的關鍵一環。帶時間窗約束的車輛路徑問題（Vehicle Routing Problem With Time Windows，VRPTW）是對VRP問題的進一步擴展，它是在VRP問題的基礎上增加了服務時間窗的限制，這里的服務時間窗是指車輛到達各客戶的時間范圍。在VRPTW問題中，軟時間窗約束的問題與實際的情況更加吻合，因此有著很強的實用背景和研究意義。

VRP問題屬于NP-完全問題，Solomon和Savelsbergh指出，帶時間約束的VRP問題即使在確定車輛數的情況下求解，仍要比基本VRP問題復雜許多。Savelsbergh同時指出在確定車輛數的情況下找出VRPTW的一個可行解，也屬于NP-完全問題[1]。

在日常配送中，多指派一輛運輸車輛的固定成本要遠遠大于增加已有車輛的行駛距離的行駛成本。所以在問題求解的時候，尋求能完成任務的最少車輛數是減少運營成本的有效方法。目前，人們對VRP相關問題的研究多數是優先考慮最小化車輛數，再考慮最小化總行車路程。但在現實中，有時候具有最少的車輛數解具有較長的行車路程，而某些具有較短的行車路程的解卻具有較多的車輛數，如果過分追求車輛數的最少反而可能使總費用更高?？梢?，合理地考慮這兩個目標而不是孤立地只考慮一個目標，將更有利于決策者做出正確的決策，減少總費用支出。

針對以上問題，綜合考慮車輛數和總行車路程這兩個目標，將VRPSTW描述成一個多目標最優化問題(multi-objective optimization， MOP)。在建立模型的基礎上，通過了一種改進的遺傳算法來解決VRPSTW問題。改進的算法通過新型的交叉算子以及對個體進行局部尋優操作，較好地解決了VRPSTW問題。

1VRPSTW問題描述與數學模型

目標函數（3）、（4）保證運輸成本最小、同時指派較少的車輛；約束（5）表示每個客戶只能由一輛車來服務；約束（6）表示每輛運輸車輛不能超過它的載重量；約束（7）、（8）和（9）是流量約束，它表明每輛離開中心倉庫一次，且僅當車輛服務客戶h的時候才離開客戶h回到中心倉庫；約束（10）表明如果車輛k由i運行到j，則它不能早于i到達j；約束（11）表明車輛必須滿足所有客戶的時間窗要求，e，l為早到和遲到的單位時間成本。如果e，l為0，則問題退化到無時間窗的車輛路徑規劃問題。

2算法設計

2.1染色體表示及初始群體的生成

染色體的表示采用自然數串編碼機制。染色體中，除第一個基因編號0代表中央倉庫固定不變的外，其余每個基因代表一個客戶節點。染色體中基因的順序體現了車輛服務客戶節點的次序。車輛路線的劃分依靠車輛載重的約束動態化分。如染色體0 1 2 3 4 5 6 ，客戶節點1 2 3的總需求小于一輛車的載重而節點1 2 3 4的總需求大于一輛車的載重，則節點1 2 3 在一條線路上；同理計算余下的基因，計算出路的線數也就表示了所需車輛數。初始群體個體初始化的方法是隨機生成n個自然數排列，然后把自然數串加到倉庫節點0的后面。

2.2改進的交叉算子

文獻[2]中的交叉算子對節點間的距離比較敏感，而未考慮到節點的時間窗約束問題。這里綜合考慮節點間距離與節點時間窗對上述交叉操作做了修改。修改后，交叉操作過程為：依據競賽選擇的方法選定群體中的兩個染色體A和B，在染色體A中隨機產生一基因段（即不包括倉庫節點0的子路徑），如3 4 5，如圖1所示。

在算法進行的過程中，每代交叉操作后生成的子代群體都與父代群體混合，然后根據計算出的個體適應度大小選擇保留或者淘汰的個體，直到個體數量滿足算法設定的群體數量。由于在適應度函數中加入了車輛的固定成本項，那么個體代表的可行解所指派的車輛就多，雖然可能使行駛路程縮短，但若不足以抵消增加指派車輛的固定成本，那么，適應度反而很低，被淘汰的機會就會越大，這樣就能使可行解向著總費用最小的個體進化。

2.4變異算子

染色體變異的可能性較小，在遺傳算法中只起到輔助作用。方法是在每代群體中隨機選取染色體上的兩點，然后將選定的兩點的基因碼進行交換，從而完成變異。

2.5局部尋優算法

為了加快算法的收斂速度，算法對每次交叉操作后新生的個體進行了局部尋優操作。方法為：隨機交換新生個體中任意兩個位置基因，如新生個體為0987345621，選中的兩個位置為基因8和5，那么交換后的個體為0957348621。尋優操作進行指定的次數后對尋優生成的所有個體與交叉操作得到的個體比較，適應度最優的個體進入子代群體中等待與父群體混合后進行優勝劣汰的選擇操作。這種尋優操作既包括線路內部的尋優，也包括線路間的尋優，更容易得到全局最優解。

3實例計算與分析

已知該實例在有時間窗約束時的最優解為3輛車，最優行駛路徑：0-3-1-2-0、0-6-4-0、0-8-5-7-0，路徑總長度910。

本文算法使用VC與GALib（一種開源遺傳算法開發包）結合實現。實驗時，群體數量設為40，迭代次數200代，交叉概率0.8，變異概率0.01，早到懲罰設為10單位/小時，遲到懲罰設為50單位/小時，車輛的固定成本設為500單位/小時。幾種情況的計算結果見表3。

由表3中的計算結果我們可以看出：

（1）采用改進交叉算子得到的優化結果中，有50%得到了最優解，明顯優于采用PMX 交叉算子時只有20%得到最優解的情況。這說明本文提出的改進交叉算子對VRPSTW問題很有效。

（2）改進的遺傳算法由于在交叉操作后對個體進行局部尋優操作，所以尋優能力得到進一步提升，在實驗過程中100%得到了最優解。通過進一步的觀察，加入局部尋優操作的改進遺傳算法一般在迭代到20代的時候就能得到最優解，圖2為算法平均適應度進化曲線?？梢?，改進的算法無論從解的質量或求解時間上都得到了提升。

（3）由于文本的適應度函數增加了對車輛固定成本的懲罰，所以本文實驗的三種方法都能對車輛數進行優化，在情況最壞的PMX實驗中也有60%達到了車輛數的最優。可見，通過在適應度函數中加入車輛固定成本的懲罰項，有利于得到總成本較小的解。

4結束語

本文從多目標優化的角度出發，綜合考慮了車輛數與總行駛里程兩種優化目標，建立了VRPSTW問題的多目標優化模型。提出了一種新的構造交叉算子的方法，此方法綜合考慮節點間的距離與時間窗的因素，與普通交叉算子相比，能有效解決VRPSTW問題。同時考慮到遺傳算法局部搜索能力比較弱，加入了局部尋優算法，較好地彌補了遺傳算法局部搜索能力不足的缺點。實驗證明，本文的改進遺傳算法能很好地解決VRPSTW問題。

參考文獻：

[1]Sam R. Thangiah. Vehicle routing problem with time windows using genetic algorithms[S]. Application Handbook of Genetic Algorithms: New Frontiers （Volume H）. Boca Raton: CRC Press， 1995:253-277.

[2]Pereira F B， Tavares J， Machado P， Costa E. GVR: a New Genetic Representation for the Vehicle Routing Problem[C] // In Proceedings of the 13th Irish Conference on Artificial Intelligence and Cognitive Science （AICS 2002）. Limerick， Ireland， September， 2002:12-13.

[3]Tan K C， Lee L H， Zhu Q L， Qu K. Heuristic methods for vehicle routing problem with time windows[J]. Artificial Intelligence in Engineering， 2001，15:281-295.

[4] 趙燕偉，吳斌，蔣麗，等. 車輛路徑問題的雙種群遺傳算法求解方法[J]. 計算機集成制造系統，2004，10(3):303-306.

[5] 張濤，張杰，王夢光. 不確定車輛數的車輛路徑問題模型和混合算法[J]. 系統工程理論方法應用，2002，11(2):121-130.

[6] 宋偉剛，張宏霞，佟玲. 有時間窗約束非滿載車輛調度問題的遺傳算法[J]. 系統仿真學報，2005，17(11):2593-2597.

[7]Solomon， Marius M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research， 1987，35(2):254-265.

[8]K Deb， A Pratap， S Agrawal et al. A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation， 2002，6(2):182-197.

[9]Fonseca C M， Fleming P J. Genetic algorithms for multi-objective optimization: formulation， discussion and generalization[C] // Proc. of the Fifth Int. conf. on genetic algorithms. Forrest: 1993:416-423.

[10]Kenny Q. Zhu. A Diversity-controlling Adaptive Genetic Algorithm for the Vehicle Routing Problem with Time Windows[C] // Proceedings of the 15th IEEE International Conference on Tools for Artificial Intelligence （ICTAI 2003）， 2003:176-183.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。