题名

調適型導引螞蟻演算法求解時窗收卸貨問題之研究

并列篇名

Solve Pick up and Delivery Problem with Time Windows via a Guided Adaptive Ant Colony System

DOI

10.6402/TPJ.201003.0099

作者

李泰琳(Tai-Lin Li)；張靖(Ching Chang)

关键词

螞蟻演算法 ； 導引區域搜尋法 ； 時間窗收卸貨問題 ； Ant colony optimization ； Guided local search ； Pickup and delivery problem with time windows

期刊名称

運輸計劃季刊

卷期/出版年月

39卷1期（2010 / 03 / 30）

页次

99 - 132

内容语文

繁體中文
中文摘要

本研究主要結合導引區域搜尋技術(guided local search, GLS)與李泰琳等人提出的調適型螞蟻演算法(adaptive ant colony system, AACS)，設計調適型導引螞蟻演算法(guided adaptive ant colony system, GAACS)求解時窗收卸貨問題(pickup and delivery problem with time windows, PDPTW)。首先，引用李泰琳等人所提出之問題規模精簡策略與關連式旅行成本網絡結構，將PDPTW轉換為無時窗的近似收卸貨問題(similar pickup and delivery problem, SPDP)，其優點為在計算過程中不需要考慮時窗限制；其次，提出GAACS演算法整合的觀念。演算法績效測試為應用國際標準題庫VRPTW例題，配合Lau與Liang (2002)方法進行修改，產生具有標竿解之PDPTW例題18題進行測試，問題規模皆為100個作業，結果顯示GAACS可以在25.9分鐘平均時間，求得與標竿解平均差異僅1.8%之近似最佳解。
英文摘要

The Pick Up and Delivery Problem with Time Windows (PDPTW) was solved via the proposed Guided Adaptive Ant Colony System (GAACS), which was integrated by the Guided Local Search (GLS) and Adaptive Ant Colony System (AACS) proposed by Lee Tai-Lin, etc. However, in order to solve the PDPTW more efficiently and effectively, a PDPTW was transferred to be a new similar PDP (SPDP) without time window via the Time Window Partitioning and Discretization Strategy. In order to show the contribution of the GAACS, 18 Solomon benchmark VRP problems were transferred to be PDPTW problems via the method developed by Lau and Liang. According to the computation results, we obtained the average percentages of errors of the best published solutions among18 PDPTW test instances, with 1.80% and an average computation time of 25.9 minutes. This shows that our proposed GAACS method can solve PDPTW accurately in a reasonable time.
主题分类 工程學 > 交通運輸工程
社會科學 > 管理學
参考文献
  1. 李泰琳、張靖(2008)。應用時窗分割與整數化策略簡化時窗收卸貨問題之研究。運輸學刊，20(3)，313-350。
    連結：
  2. 李泰琳、張靖、卓裕仁(2007)。調適型螞蟻演算法應用於旅行推銷員問題之研究。運輸學刊，19(1)，89-120。
    連結：
  3. 林志鴻(2005)。宅配業車輛路線規劃問題之模式建立與求解。運輸學刊，17(1)，65-94。
    連結：
  4. 梅明德、謝浩明(2001)。時窗限制動態車輛路線問題之線上型路線建立啟發式解法。運輸學刊，13(2)，73-111。
    連結：
  5. 陳家和、丁慶榮(2005)。應用螞蟻演算法於時窗限制車輛途程問題之研究。運輸學刊，17(3)，261-280。
    連結：
  6. 韓復華、王國琛(2002)。巨集式解法在求解大規模旅行推銷員問題之應用。運輸學刊，14(2)，1-14。
    連結：
  7. Appelgren, L. H.(1969).A Column Generation Algorithm for a Ship Scheduling Problem.Transportation Science,3(1),53-68.
  8. Balas, E.,Vazacopoulos, A.(1998).A Guided Local Search with Shifting Bottleneck for Job Shop Scheduling.Management Science,44(2),262-275.
  9. Bent, R.,Van Hentenryck, P.(2006).A Two-Stage Hybrid Algorithm for Pickup and Delivery Vehicle Routing Problems with Time Windows.Computers and Operations Research,33(4),875-893.
  10. Bullnheimer, B.,Hartl, R. F.,Strauss, C.(1999).A New Rank Based Version of the Ant System-A Computational Study.Central European Journal for Operations Research and Economics,7(1),25-38.
  11. Davenport, A.(1997).Department of Computer Science, University of Essex.
  12. Desrosiers, J.,Dumas, Y.,Solomon, M. M.,Sournis, E.(1995).Time Constrained Routing and Scheduling.Handbooks in Operations Research and Management Science,8,35-139.
  13. Working Paper
  14. Dorigo, M.(1992).Italy,Dipartimento diElettronica e Informatica, Politecnico di Milano.
  15. Dorigo, M.,Gambardella, L. M.(1997).Ant Colonies for the Traveling Salesman Problem.BioSystems,43,73-81.
  16. Dorigo, M.,Gambardella, L. M.(1997).Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.IEEE Transactions on Evolutionary Computation,1(1),53-66.
  17. Dror, M.(1994).Note on the Complexity of the Shortest Path Models for Column Generations in the VRPTW.Operations Research,42(5),977-978.
  18. Dumas, Y.,Desrosiers J.,Soumis F.(1991).The Pickup and Delivery Problem with Time Windows.European Journal of Operational Research,54(1),7-22.
  19. Fabian, J.,Perez, L.(2005).A Meta-Heuristic Applied for a Topologic Pickup and Delivery Problem with Time Windows Constraints.Lecture Notes in Computer Science,3516,924-928.
  20. Faroe, O.,Pisinger, D.,Zachariasen, M.(2003).Guided Local Search for the Three-Dimensional Bin Packing Problem.INFORMS Journal on Computing,267-283.
  21. Gambardella, L. M.,Dorigo, M.(1996).Solving Symmetric and Asymmetric TSPs by Ant Colonies.In Proceedings of the IEEE International Conference on Evolutionary Computation,Japan:
  22. Gambardella, L. M.,Dorigo, M.(1995).Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem.In Proceedings of the Eleventh International Conference on Machine Learning,Morgan Kaufmann:
  23. Kilby, P.,Prosser, P.,Shaw, P.(1997).Guided Local Search for the Vehicle Routing Problem.2ND International Conference on Metaheuristics-MIC97,France:
  24. Kilby, P.,Prosser, P.,Shaw, P.(1999).META-HEURISTICS Advances and Trends in Local Search Paradigms for Optimization.Boston:Kluwer Academic.
  25. Kohl, N.(1995).Institute of Mathematical Modeling, Technical University of Denmark.
  26. Kolen, A. W. J.,Rinnooy Kan, A. G. H.,Trienekens, H. W. J. M.(1987).Vehicle Routing with Time Windows.Operations Research,35(2),266-273.
  27. Lau, H. C.,Liang, Z.(2002).Pickup and Delivery with Time Windows-Algorithms and Test Case Generation.International Journal on Artificial Intelligence Tools,11(3),455-472.
  28. Le Louarn, F. X.,Gendreau, M.,Potvin, J. Y.(2004).GENI Ants for the Traveling Salesman Problem.Annals of Operations Research,131,187-201.
  29. Lin, S.(1965).Computer Solutions for the Traveling Salesman Problem.Bell Systems Technology Journal,44,2245-2269.
  30. Lu, Q.,Dessouly, M.(2004).An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem.Transportation Science,38(4),503-514.
  31. Mester, D.,Bräysy, O.(2005).Active Guided Evolution Strategies for the Large Scale Vehicle Routing Problem with Time Windows.Computers & Operations Research,32,1593-1614.
  32. Mills, P.(2002).Department of Computer Science, University of Essex.
  33. Mitrovic-Minic, S.,Laporte, G.(2004).Waiting Strategies for The Dynamic Pickup and Delivery Problem with Time Windows.Transportation Research Part B,38,635-655.
  34. Mladenović N.,Hansen, P.(1997).Variable Neighborhood Search.Computers and Operations Research,24,1097-1100.
  35. Nanry, W. P.,Barnes, J. W.(2000).Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search.Transportation Research Part B,34,107-121.
  36. Psarafis, H.(1980).A Dynamic Programming Solution to the Single Vehicle Many to Many Immediate Request Dial-a-Ride Problem.Transportation Science,14(2),130-154.
  37. Psarafis, H.(1983).An Exact Algorithm for the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem.Transportation Science,17(4),351-361.
  38. Rochat, Y.,Taillard, E. D.(1995).Probabilistic Diversification and Intensification in Local Search for Vehicle Routing.Journal of Heuristics,1,147-167.
  39. Savelsbergh, M. W. P.(1988).Computer Aided Routing.Amsterdam:Centrum Voor Wiskunde en Informatica.
  40. Savelsbergh, M. W. P.,Solomon, M.(1995).The General Pickup and Delivery Problem.Transportation Science,29(1),17-29.
  41. Sexton, T. R.,Bodin, L. D.(1985).Optimizing Single Vehicle Many-to-Many Dial-a-Ride Problem with Desired Delivery Time: II Routing.Transportation Science,19(4),411-435.
  42. Sexton, T. R.,Bodin, L. D.(1985).Optimizing Single Vehicle Many-to-Many Dial-a-Ride Problem with Desired Delivery Time: I Scheduling.Transportation Science,19(4),378-410.
  43. Stützle, T.,Hoos, H. H.(1999).MAX-MIN Ant System and Local Search for Combinatorial Optimization Problems.Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization.
  44. Stützle, T.,Hoos, H. H.,Bäck, T. (editors),Michalewicz, Z. (editors),Yao, X. (editors)(1997).The MAX-MIN Ant System and Local Search for the Travelling Salesman Problem.Proceedings for the IEEE International Conference on Evolutionary Computation (ICEC'97),Piscataway, USA:
  45. Stützle, T.,Hoos, H. H.,R. F. Albrecht Q. D. Smith (editors),N. C. Steele (editors)(1998).Artificial Neural Network and Genetic Algorithms.New York:Springer Verlag.
  46. Taillard, É.,Badeau, P.,Gendreau, M.,Guertain, F.,Potvin, J. Y.(1995).Technical Report CRT-95-66Technical Report CRT-95-66,Centre de Recherche sur les Transports, University of Montreal.
  47. Tsang, E.,Voudouris, C.(1997).Fast Local Search Guided Local Search and Their Application to British Telecom's Workforce Scheduling Problem.Operations Research Letters,20(3),119-127.
  48. Voudouris, C.(1997).University of Essex.
  49. Voudouris, C.,Tsang, E.(1995).Technical Report CSM-247Technical Report CSM-247,Department of Computer Science, University of Essex.
  50. Voudouris, C.,Tsang, E.(1998).Solving the Radio Link Frequency Assignment Problem Using Guided Local Search.Proceedings of NATO Symposium on Radio Length Frequency Assignment, Sharing and Conservation Systems (Aerospace),Aalborg, Demark:
  51. Voudouris, C.,Tsang, E.(1995).Technical Report CSM-249Technical Report CSM-249,Department of Computer Science, University of Essex.
  52. Voudouris, C.,Tsang, E.(1998).Guided Local Search and Its Application to the Travelling Salesman Problem.European Journal of Operational Research,132(2),80-110.
  53. Voudouris, C.,Tsang, E.(1996).Partial Constraint Satisfaction Problems and Guided Local Search.Proceedings of 2nd International Conference on Practical Application of Constraint Technology (PACT'96),London:
  54. Voudouris, C.,Tsang, E.(1995).Technical Report CSM-250Technical Report CSM-250,Department of Computer Science, University of Essex.
  55. Voudouris, C.,Tsang, E.(1999).Theory and Methodology Guided Local Search and Its Application to the Traveling Salesman Problem.European Journal of Operational Reasearch,113,469-499.
  56. Voudouris, C.,Tsang, E. P. K.,F. Glover (ed.)(2003).Handbook of Metaheuristics.Kluwer, Springer.
  57. Wang, X.(2001).Civil Engineering, University of Calllifornia Irvine.
  58. Zhong, Y.,Cole, M. H.(2005).A Vehicle Routing Problem with Backhauls and Time Windows: A Guided Local Search Solution.Transportation Research Part E,41,131-144.
  59. 朱經武、劉曄、洪秀華(2004)。同時考慮以自有車輛收送或或委託貨運公司服務之啟發式演算法。海運學報，13，147-162。
  60. 彭冠儒、陳正芳(2002)。混合送貨、收貨的車輛途程問題。2002年產業電子化運籌管理學術暨實務研討會
  61. 黃信翔、王晉元(2005)。碩士論文(碩士論文)。國立交通大學運輸科技與管理學系。
  62. 韓復華、卓裕仁、陳國清(1999)。五種巨集啟發式解法在VRP問題上之應用與比較。中華民國第四屆運輸網路研討會論文集
print cancel