臺灣博碩士論文加值系統

蟻群最佳化演算法於時窗限制之車輛途程問題的研究
學生：高秀梅 指導教授：梁韵嘉 博士
元智大學工業工程與管理研究所
摘要
物流配送系統中，物流中心必須在最適當的時間內將正確數量的產品運送到正確的地點以滿足顧客的需求。但隨著客製化需求愈來愈受重視，顧客對於貨品交期時間之要求也愈嚴苛，因此在車輛途程問題中導入時窗因子，即VRPTW(Vehicle Routing Problem with Time Window)，將使得車輛途程問題之應用更符合實際需要。
車輛途程問題之求解複雜度很高，屬於NP-Hard問題，以傳統數學模式求解時，須花費冗長的運算時間，因此為了于合理計算時間內獲得理想的解，啟發式方法便成為一較可行之途徑。基於此特性，本研究針對硬性時窗之VRPTW問題，建構蟻群最佳化演算法(ACO)為解題架構，將影響演算成效的因子作測試與分析，例如費洛蒙起始濃度( τ0 )、螞蟻數( N )、局部啟發式函數( η )、區域改善、區域更新、全域更新、以及ACO參數，其中又包括規則決定參數 (q0)、費洛蒙殘留比例(ρ)、及參數α與β等，並透過Solomon(1987)標準題庫的六類題型進行測試與驗證，測試50及100個顧客點之測試結果，以C類的表現為最好，其中在50個顧客點的題型中，又以R112及RC104的表現最佳，與文獻最佳解的距離誤差僅有0.04﹪及0.00﹪；而100個顧客點的題型中，則以R211及RC202的表現較文獻最佳解好，改善率達9.22﹪及5.5﹪。
關鍵字：時窗限制車輛途程問題、蟻群最佳化演算法

A Study of Ant Colony Optimization on Vehicle Routing Problem with Time Window
Student： Hsiu-Mei Kao Advisors：Dr. Yun-Chia Liang
Department of Industrial Engineering and Management
YUAN-ZE University
ABSTRACT
In a logistic distribution system, the right amount of products has to be shipped to the right place from the depot to meet customers’ needs. With customized requirement being valued more, customers are more demanding on merchandise’s on-time delivery. Thus, in order to meet practical needs, time window constraint is considered in this research and, therefore, the focus of this research is VRPTW (Vehicle Routing Problem with Time Window).
Solving vehicle routing problems involves with high complexity. Since the VRPTW is a NP-Hard problem, traditional mathematical programming approach needs lengthy computational time to find the optimal solution. In order to obtain good solutions within acceptable computing time in practice, metaheuristics becomes a better option. In this research, we employ one of metaheuristics - Ant Colony Optimization (ACO) — for VRPTW problem. To investigate the characteristic of ACO on VRPTW, a thorough parameter design are conducted, and then the optimal parameter and algorithm structure is suggested. Based on 56 benchmark problems by Solomon, we test and verify all six categories and test different customer sizes including 50 and 100. The result shows that in C category problem ACO performs the best. In addition, in two of 50-customer problems, R112 and RC104, the proposed algorithm provides the best percentage deviation from the best solution in the literature that is 0.04% and 0.00%, respectively. In two of 100-customer problems, R211 and RC202, ACO improves the known best results in the literature by 9.22% and 5.5%, respectively.
Keywords: Vehicle Routing Problem with Time Window, Ant Colony Optimization.

目 錄
中文摘要 I
英文摘要 II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
一、 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍 4
1.4 研究流程 5
二、 文獻探討 7
2.1 車輛途程問題之定義 7
2.2 時間窗 10
2.3 VRP與VRPTW的求解方法 11
2.3.1 初始解法 14
2.3.2 萬用啟發式演算法 16
2.3.3 傳統交換改善法 18
2.4 相關文獻探討 26
2.4.1 具時窗限制之車輛途程問題相關文獻 26
2.4.2 蟻群最佳化演算法之相關文獻 33
三、 研究方法 38
3.1 VRPTW之問題描述與基本假設 38
3.1.1 問題描述 38
3.1.2 假設條件與限制條件 40
3.2 VRPTW之數學模式建立 41
3.2.1 符號說明 41
3.2.2 VRPTW之數學模式 41
3.3 ACO演算法之架構 45
3.3.1 起源 45
3.3.2 步驟流程 47
3.4 路徑改善程序 54
四、 參數設計與實驗設計 58
4.1 測試題庫與最佳解 58
4.2 ACO演算法之最佳化設計 59
4.2.1 確立演算法之架構 62
4.2.2 ACO參數設定 67
4.2.3費洛蒙初始濃度之設定 71
4.3 例題測試與比較分析 73
五、 結論與建議 81
5.1 結論 81
5.2 未來研究方向 82
參考文獻 83
附錄1 VRPTW標準題庫之題型屬性一覽表(50個顧客點) 94
附錄2 Solomon題庫100個顧客點之最佳解相關資料 95
附錄3 Solomon題庫50個顧客點之最佳解相關資料 97
附錄4 實驗測試數據資料 99

參考文獻
王正宇，「台灣物流業」，清華大學工業工程與管理系物流管理。[Online]. Available:http://cimlab.ie.nthu.edu.tw/logistics/project/center/P2.htm (Dec. 10, 2002)
「物流與產業發展關係」，環緯簡訊網頁，第25期。[Online]. Available: http://www.roundsway.com.tw/25-1.html (Dec. 10, 2002)
Jorge Tavares. Vehicle Routing Problem-The Evolutionary Way. [Online]. Available: http://eden.dei.uc.pt/~jast/vrp/ (June 2003)
李玉雯，「軟性時窗限制下醫院運輸部門車輛途程問題之研究」，成功大學工業工程與管理研究所，碩士論文，2000.
李洪鑫，「含時間窗車輛途程問題各演算法適用範圍之探討」，東海大學工業工程研究所，碩士論文，2000.
吳亮瑩，「單一物流中心配送車輛途程問題之研究-以遺傳演算法求解」，成功大學工業管理研究所，碩士論文，1999.
林修竹，「包容性啟發式解法在VRPTW問題上之應用」，交通大學運輸工程與管理研究所，碩士論文，1999.
陳百傑，「以啟發式演算法求解時窗限制車輛途程問題」，中原大學工業工程研究所，碩士論文，2002.
陳契伸，「硬性/軟性時窗限制之車輛途程問題研究」，中原大學工業工程研究所，碩士論文，2001.
陳夏祥，「蟻族系統求解相依整備時間之單機總延遲問題」，台灣科技大學工業管理研究所，碩士論文，2002.
陳坤賓，「模擬退火演算法應用於車輛途程規劃問題之研究」，元智大學工業工程與管理研究所，碩士論文，1998.
曾維豪，「軟性時間與回程撿收之車輛途程問題」，元智大學工業工程與管理研究所，碩士論文，2000.
敖君瑋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，元智大學工業工程與管理研究所，碩士論文，1999.
曾國維，「現代化儲運系統-理論與實務應用」，鴻儒堂出版社，1983.
黃珈昇，「物流體系中貨櫃運送車輛途程規劃問題之探討」，中原大學工業工程研究所，碩士論文，1996.
楊智凱，「以門檻接受法改善TSP及VRP路網成本之研究」，交通大學士木工程研究所，碩士論文，1995.
廖亮富，「含時窗限制多部車車輛途程問題解算之研究」，元智大學工業工程與管理研究所，碩士論文，1998.
廖韋翔，「應用門檻值接受法之多目標車輛路徑規劃」，雲林科技大學工業工程與管理技術研究所，碩士論文，1998.
熊碩成，「以實驗設計改善時窗限制下物流中心車輛途程問題之研究」，國防管理學院資訊研究所，碩士論文，2001.
鄭超元，「考慮時窗限制之多車種零擔貨運車輛途程問題」，海洋大學航運管理研究所，碩士論文，2002.
蕭宗勝，「螞蟻族群演算法應用在組合問題之研究」，銘傳大學資訊管理研究所，碩士論文，2002.
韓復華、楊智凱、卓裕仁，「應用門檻接受法求解車輛路線問題之研究」，運輸計劃季刊，第26卷，第二期，253-280，1998.
顏成佑，「基因演算法解算軟性時窗車輛途程問題之研究」，元智大學工業工程研究所，碩士論文，2000.
魏宗徹，「整合時窗限制與回程撿收之多車種車輛途程問題」，元智大學工業工程與管理研究所，碩士論文，2001.
藍坤銘，「應用資料挖掘之順序樣式法於螞蟻理論之改善」，台北科技大學生產系統工程與管理研究所，碩士論文，2002.
蘇伯達，「以螞蟻系統探索關聯性規則」，清華大學工業工程與管理研究所，碩士論文，2002.
Badeau, P., F. Guertin, M. Gendreau, J. Y. Potvin, and E. Taillard, “A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows,” Transportation Research, Vol. 5, pp. 109-122, 1997.
Bean, J. C., “Genetic Algorithms and Random Keys for Sequencing and Optimization,” ORSA Journal on Computing, Vol. 6, pp. 154-160, 1994.
Blanton, J. L. and R. L. Wainwright, “Multiple Vehicle Routing with Time and Capacity Constraints using Genetic Algorithms,” Proceedings of the 5th International Conference on Genetic Algorithm, pp. 452-459, Morgan Kaufmann, San Mateo, CA, 1993.
Bodin, L., B. Golden, A. Assad, and D. Bull, “Routing and Scheduling of Vehicle and Crews: The State of the Art,” Computers & Operations Research, Vol. 10, pp. 63-211, 1983.
Bonimi, E. and J. Lutton, “The N-city Traveling Salesman Problem: Statistical Mechanics Algorithm and the Metropolis Algorithm,” SIAM Review, Vol. 26, pp. 551-568, 1984.
Braun, H., “On Solving Traveling Salesman Problems by Genetic Algorithms,” Parallel Problem-Solving from Nature, pp. 129-133, Springer-Verlag, Berlin, 1991.
Bräysy, O. and Gendreau M., “Metaheuristics for the Vehicle Routing Problem with Time Windows,” Internal report STF42 A01021, SINTEF Applied Mathematics, Department of Optimisation, Norway, 2001.
Bulinski, M. and R. Quandt, “On an Integer Program for a Delivery Problem,” Operations Research, Vol. 12, pp. 300-304, 1964.
Bullnheimer, B., R. F. Hartl, and C. Strauss, “A New Rank Based Version of the Ant System－A Computational Study,” Central European Journal for Operations Research and Economics, Vol. 7, pp. 25-38, 1999.
Bullnheimer, B., R. F. Hartl, and C. Strauss, “Applying the Ant System to the Vehicle Routing Problem,” In S. Martellom I. H. Osman, and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 285-296, Kluwer, 1999.
Bullnheimer, B., R. F. Hartl, and C. Strauss, “An Improved Ant System Algorithm for the Vehicle Routing Problem,” Annals of Operations Research, Vol. 89, pp. 319-328, 1999.
Carlton, W. B., “A Tabu Search Approach to the General Vehicle Routing Problem,” Ph.D. Thesis, The University of Texas at Austin, TX, 1995.
Chabrier, A., “Vehicle Routing Problem with Elementary Shortest Path Based Column Generation,” Working Paper, ILOG, Madrid, Spain, 2002.
Chen, X., W. Wan, and X. Xu, “Modeling Rolling Batch Planning as Vehicle Routing Problem with Time Windows,” Computers and Operations Research, Vol. 25, pp. 390-400, 1998.
Chiang, W.-C. and R. A. Russell, “A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows,” INFORMS Journal on Computing, Vol. 9, pp. 417-430, 1997.
Christofides, N., A. Mingozzi, and P. Toth, “The Vehicle Routing Problem,” In N. Christofides, A. Mingozzi, P. Toth and C. Sandi (eds.), Combinatorial Optimization, pp. 315-338, Wiley, 1979.
Christofides, N., A. Mingozzi, and P. Toth, “State space Relaxation Procedures for the Computation of Bounds to Routing Problems,” Networks, Vol. 11, pp. 145-164, 1981.
Clarke, G. and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, pp. 568-581, 1964.
Comellas, F. and J. Ozón, “An Ant Algorithm for the Graph Colouring Problem,” First International Workshop on Ant Colony Optimization: From Ant Colonis to Artificial Ants, Brussels, Belgium, pp. , 1998.
Cook, T. and J. L. Rich, “A Parallel Cutting Plane Algorithm for the Vehicle Routing Problem with Time Windows,” Technical Report, Computational and Applied Mathematics, Rice University, Houstom, TX, 1999.
Colorni, A., M. Dorigo, V. Maniezzo, and M. Trubian, “Ant System for Job-shop Scheduling,” Belgian Journal of Operations Research, Statistics and Computer Science, Vol. 34, pp. 39-53, 1994.
Cordeau, J.-F., G. Laporte, and A. Mercier, “A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows,” Journal of the Operational Research Society, Vol. 52, pp. 928-936, 2001.
Davis, L., Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991.
Di Caro, G. and M. Dorigo, “Ant Colonies for Adaptive Routing in Packer-Switched Communication Networks,” Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSN V), Amsterdam, The Netherlands, pp. 673-682, September 1998.
Dorigo, M., V. Maniezzo, and A. Colorni, “Positive Feedback as a Search Strategy,” Technical Report No. 91-016 Revised, Politecnico di Mlano, Italy, 1991.
Dorigo, M., “Optimization, Learning and Natural Algorithms,” Ph.D. Thesis, Politecnico di Mlano, Italy, 1992.
Dorigo, M., V. Maniezzo, and A. Colorni, “The Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man and Cybernetics- Part B, Vol. 26, pp. 29-41, 1996.
Dorigo, M. and L. M. Gambardella, “Ant Colonies for the Traveling Salesman Problem,” BioSystems, Vol. 43, pp. 73-81, 1997.
Dorigo, M. and L. M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, pp. 53-66, 1997.
Dorigo, M., G. Di Caro, and L. M. Gamburdella, “Ant Algorithms for Distributed Discrete Optimization,” Artificial Life, Vol. 5, pp. 137-172, 1999.
Eilon, S., C. D. T. Watson-Gandy, and N. Christofides, “Distribution Management: Mathematical Modelling and Practical Analysis,” Griffin, London, 1971.
Fleurent, C. and J. A. Ferland, “Genetic and Hybrid Algorithms for Graph Colouring,” Metaheuristics in Combinatorial Optimization, Annals of Operations Research, Vol .63, pp. 437-461, 1996.
Gambardella, L. M., E. Taillard, and G. Agazzi, “MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, “ In D. Corne, M. Dorigo and F. Glover (eds.) New Ideas in Optimization, MoGraw Hill, London, 1999.
Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP Completeness, W. H. Freeman & Co., New York, 1979.
Garcia, B. L., J. Y. Potvin, and J. M. Rousseau, “A Parallel Implementation of the Tabu Search Heuristic for Vehicle Routing Problems with Time Window Constraints,” Computers & Operations Research, Vol. 21, pp. 1025-1033, 1994.
Gendreau, M., A. Hertz, and G. Laporte, “A Tabu Search Heuristic for the Vehicle Routing Problem,” Management Science, Vol. 40, pp. 1276-1290, 1994.
Gillett, B. and L. Miller, “A Heuristic Algorithm for the Vehicle Dispatching Problem,” Operation Research, Vol. 22, pp. 340-349, 1974.
Glover, F., “Tabu Search-Part I,” ORSA Journal on Computing, Vol.1, pp. 190-206, 1989.
Glover, F., “Tabu Search-Part II,” ORSA Journal on Computing, Vol. 2, pp. 4-32, 1990.
Golden, B., T. Magnanti and H. Nguyen, “Implementing Vehicle Routing Algorithm,” Networks, Vol. 7, pp. 113-148, 1977.
Golden, B. L., G. Laporte, and E. D. Taillard, “An Adaptive Memory Heuristic for a Class of Vehicle Routing Problems with MinMax Objective,” Computers and Operations Research, Vol. 24, pp. 445-452, 1997.
Golden, B. L. and C. C. Skiscim, “Optimization by Simulated Annealing: A Preliminary Computational Study for the TSP,” Proceedings of the 1983 Winter Simulated Annealing Conference, Washington, D. C., 1983.
Guntsch, M. and M. Middendorf, “Pheromone Modification Strategies for Ant Algorithms Applied to Dynamic TSP,” Applications of Evolutionary Computing: Proceedings of EvoWorkshops 2001, LNCS 2037, Lake Como, Italy, pp. 213-222, 2001.
Halse, K., “Modelling and Solving Complex Vehicle Routing Problem,” Ph.D. Thesis, Institute of Mathematical Modelling, Technical University of Denmark, Lungy, Denmark, 1992.
Hertz, A., E. Taillard, and D. de Warra, “Tabu Search,” In E. Aarts and J. K. Lenstra (eds.), Local Search in Combinatorial Optimization, pp.121-136, John Wiley & Sons, Chichester, 1997.
Holland, J. H., Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, MI, 1975
Kallehauge, B., J. Larsen, and O.B.G. Madsen, “Lagrangeam Duality and Non-differentiable Optimization Applied on Routing with Time Windows-Experimental Results,” Internal Report IMM-REP-2000-8, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 2000.
Kirkpatrick, S., C. D. Gelatt, and P. M. Vecchi, “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680, 1983.
Kohl, N., J. Desrosiers, O.B.G. Madsen, M. M. Solomon, and F. Soumis, “2-Path Cuts for the Vehicle Routing Problem with Time Windows,” Transportation Science, Vol. 33, pp. 101-116, 1999.
Kolen, A. W. J., A. H. G. Rinnooy Kaan, and H. W. J. M. Trienekens, “Vehicle Routing with Time Windows,” Operation Research, Vol. 35, pp. 266-273, 1987.
Krolak, P., W. Felts, and G. Marble, “A Man-Machine Approach toward Solving the Traveling Saleman Problem,” Communications of the ACM, Vol. 14, pp.307-334, 1971.
Krolak, P., W. Felts, and J.Nelson, “A Man-Machine Approach toward Solving the Generalized Truck Dispatching Problem,” Transportation Science, Vol. 6, pp.149-170, 1972.
Lin, S., “Computer Solutions of the Traveling Salesman Problem,” The Bell System Technical Journal, Dec., pp. 2245-2269, 1965.
Louis, S. J., X. Yin, and Z. Y. Yuan, “Multiple Vehicle Routing with Time Windows Using Genetic Algorithms,” IEEE Proceedings of the 1999 Congress on Evolutionary Computation, Vol. 3, pp. 1804-1808, 1999.
Malmborg, C. J., “A Genetic Algorithm for Service Level Based Vehicle Routing Scheduling,” European Journal of Operation Research, Vol. 93, pp. 131-134, 1996.
Maniezzo, V. and A. Carbonaro, “An ANTS Heuristic for the Frequency Assignment Problem,” Future Generation Computer System, Vol. 16, pp. 927-935, 2000.
Maniezzo, V. and A. Colorni, “The Ant System Applied to the Quadratic Assignment Problem,” IEEE Transactions on Knowledge and Data Engineering, Vol. 11, pp. 769-778, 1999.
McMullen, P. R., “An Ant Colony Optimization Approach to Addressing a JIT Sequencing Problem with Multiple Objective,” Artificial Intelligence in Engineering, Vol. 15, pp. 309-317, 2001.
Mole, R. and S. Jameson, “A Sequential Route-Building Algorithm Employing a Generalized Savings Criterion,” Operational Research Quarterly, Vol. 22, pp. 503-511, 1976.
Nanry, W. P. and J. W. Barnes, “Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search,” Transportation Research Part B, Vol. 34, pp. 107-121, 2000.
Newton, R. and W. Thomas, “Design of School Bus Routes by Computer,” Socio-Economic Planning Science, pp. 75-85, 1969.
Or, I., “Traveling Salesman-type Combinatorial Problem and Their Relation to the Logistics of Regional Blood Banking,” Ph.D. Dissertation, Northwestern University, 1976.
Osman, I. H., “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem,” Annals of Operations Research, Vol. 41, pp. 421-451, 1993.
Potvin, J.-Y. and J.-M. Rousseau, “A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows,” European Journal of Operational Research, Vol. 66, pp. 331-340, 1993.
Potvin, J.-Y., T. Kervahut, B. L. Garcia, and J.-M. Rousseau, “The Vehicle Routing Problem with Time Windows Part I: Tabu Search,” INFORMS Journal on Computing, Vol. 8, pp. 158-164, 1996.
Potvin, J.-Y. and S. Bengio, “The Vehicle Routing Problem with Time Windows Part II: Genetic Search,” INFORMS Journal on Computing, Vol. 8, pp. 165-172, 1996.
Pureaz, V. M. and P. M. França, “Vehicle Routing Problem via Tabu Search Metaheuristic,” Technical Report CRT-347, Centre for Research on Transportation, Montreal, 1991.
Rego C. and C. Roucairol, “A Parallel Tabu Search Algorithm using Ejection Chains for the Vehicle Routing Problem,” In I. H. Osman and J. P. Kelly (eds.), Meta-Heuristics: Theory and Applications, pp. 661-675, Kluwer, Boston, 1996.
Reimann, M., S. Shtovba, and E. Nepomuceno, “A Hybrid ACO-GA Approach to Solve Vehicle Routing Problems,” DOM Working Paper 08/2001, University of Vienna, Vienna, Austria, 2001.
Robusté, F., C. F. Daganzo, and R. Souleyrette II, “Implementing Vehicle Routing Models,” Transportation Research, Vol. 24, pp. 263-286, 1990.
Schulze, J. and T. Fahle, “A Parallel Algorithm for the Vehicle Routing Problem with Time Window Constraints,” Annals of Operations Research, Vol. 86, pp. 585-607, 1999.
Schmitt, L. J., “An Evaluation of a Genetic Algorithmic Approach to the Vehicle Routing Problem,” Working Paper, Department of Information Technology Management, Christian Brothers University, Memphis, 1995.
Solomon, M., “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operations Research, Vol. 35, No. 2, pp. 254-265, 1987.
Stützle, T., “An Ant Approach to the Flow Shop Problem,” Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT’98), Vol. 3, pp. 1560-1564, Verlag Mainz, Aachen, 1997.
Stützle, T. and M. Dorigo, “ACO Algorithms for the Traveling Salesman Problem,” In K. Miettinen, M. Makela, P. Neittaanmaki and J. Periaux (eds.), Evolutionary Algorithms in Engineering and Computer Science, pp. 163-183, John Wiley & Sons, 1999.
Stützle, T. and H. Hoos, “The Max-Min Ant System and Local Search for Combinatorial Optimization Problems,” In S. Martellom I. H. Osman, and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 313-329, Kluwer, 1999.
Taillard, É. D, “Parallel Iterative Search Methods for Vehicle Routing Problem,” Networks, Vol. 23, pp. 661-673, 1993.
Taillard, É. D., P. Badeau, M. Gendreau, F. Guertin, and J. Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Science, Vol. 31, pp. 170-186, 1997.
Tan, K. C., L. H. Lee, and K. Ou, “Artificial Intelligence Heuristics in Solving Vehicle Routing Problems with Time Window Constraints,” Engineering Applications of Artificial Intelligence, Vol. 14, pp. 825-837, 2001.
Tan, K. C., L. H. Lee, K.Q. Zhu and K. Ou, “Heuristic Methods for Vehicle Routing Problem with Time Windows,” Artificial Intelligence in Engineering, Vol. 15, pp. 281-295, 2001.
Thangiah, S. R., I. H. Osman, and T. Sun, “Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Window,” Technical Report UKC/OR94/4, Institute of Mathematics & Statistics, University of Kent, CanterBury, UK, 1994.
Ulder, N. L. J., E. H. L. Aarts, H. J. Bandelt, P. J. M. van Laarhoven, and E. Pesch, “Genetic Local Search Algorithms for the Traveling Salesman Problem,” Parallel Problem-Solving from Nature, pp. 109-116, Springer-Verlag, Berlin, 1991.
Van Breedam, A., “Improvement Heuristics for the Vehicle Routing Problem Based on Simulated Annealing,” European Journal of Operational Research, Vol. 86, pp. 480-490, 1995.
Wade, A. and S. Salhi, “An Ant System Algorithm for the Vehicle Routing Problem with Backhauls,” Proceedings of the 4th Metaheuristics International Conference (MIC2001), pp. 199-203, The University of Birmingham, U.K., 2001.
Xu, J. and J. Kelly, “A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem,” Transportation Science, Vol. 30, pp. 379-393, 1996.
Zhu, K. Q., “A New Genetic Algorithm for VRPTW,” Proceedings of the 4th International Conference on Genetic Algorithm, Las Vegas, U.S.A., 2000