Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Kết hợp Các Phương Pháp Meta-Heuristic Để Giải Quyết Hiệu Quả Vấn Đề Lập Lịch Xe Có Cửa Sổ Thời Gian
Tóm tắt
Các vấn đề lập lịch xe với cửa sổ thời gian là những bài toán giao hàng đầy thách thức, trong đó các trường hợp liên quan đến 100 khách hàng hoặc hơn có thể khó giải quyết. Đã có nhiều phương phápheuristics thú vị được đề xuất để xử lý những vấn đề này một cách hiệu quả. Trong bài báo này, chúng tôi đã xem xét hai phương pháp meta-heuristic nổi tiếng và kết hợp một cách cẩn thận cơ chế trí nhớ ngắn hạn và dài hạn của cả hai phương pháp để đạt được kết quả tốt hơn. Nguyên mẫu của chúng tôi đã cho thấy được sự so sánh tích cực đối với các phương pháp tìm kiếm gốc và các tổ hợp tìm kiếm liên quan khác trên các bài kiểm tra của Solomon. Quan trọng hơn, đề xuất tích hợp của chúng tôi mở ra nhiều hướng nghiên cứu thú vị cho các cuộc điều tra tiếp theo.
Từ khóa
#Vấn đề lập lịch xe #cửa sổ thời gian #phương pháp heuristic #phương pháp meta-heuristic #trí nhớ ngắn hạn #trí nhớ dài hạn.Tài liệu tham khảo
De Backer, B., Furnon, V., Kilby, P., Prosser, P. & Shaw, P. (1997). Solving Vehicle Routing Problems Using Constraint Programming and Met Heuristics. In Journal of Heuristics, Vol. 1–16. Kluwer Academic Publishers.
Gendreau, M., Hertz, A. & Laporte, G. (1994). A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science 40(10): 1276–1290.
Hoel, P. G. (1976). Elementary Statistics, 4th edn. John Wiley & Sons.
Jee, J. C. (2000). Solving Vehicle Routing Problems with Time Windows Using Micro-Genetic Algorithms. Proceedings of the 6th National Ungergraduate Research Opportunities Programme Congress 2000. Faculty of Engineering, NUS, September 7–8.
Kilby, P., Prosser, P. & Shaw, P. (1997). Guided Local Search for the Vehicle Routing Problems. In Proceedings of 2nd International Conference on Metaheuristics (MIC97), 1–10. Sophia-Antiplois, France, July 21–24.
Lin, S. (1965). Computer Solutions for the Traveling Salesman Problem. Bell Systems Technology Journal 44: 2245–2269.
Ma, K. T. (2001). Using Hybrid Search Methods to Solve A.I. Search and Optimization Problems. Hons Thesis, The National University of Singapore.
Osman, I. H. (1993). Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Ann. Oper. Res. 41: 421–451.
Prosser, P. & Shaw, P. (1997). Study of Greedy Search with Multiple Improvement Heuristics for Vehicle Routing Problems. Technical Report RR/96/201, Department of Computer Science, Univeristy of Strathclyde, Glasgow.
Rochat, Y. & Taillard, E. D. (1995). Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Technical Report CRT–95–13, Centre de recherche sur les transports, Université de Montréal, Montréal.
Savelsbergh, M.W. P. (1988). Computer Aided Routing. Amsterdam: Centrum voor Wiskunde en Informatica.
Seah, D. (1999). Ant Colonoy Optimization On Vehicle Routing Problems. Thesis for the Master of Computer Science, National University of Singapore.
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problem with Time Windows. Oper. Res. 35: 254–265.
Spears, W. M. (1993). Simulated Annealing for Hard Satisfiability Problems. NCARAI Tech. Report AIC 93–015. AI Center, Naval Research Laboratory, Washington D.C.
Tsang, E., Wang, C. J., Davenport, A., Voudouris, C. & Tung, L. L. (1999). A Family of Stochastic Methods for Constraint Satisfaction and Optimisation. The First International Conference on the Practical Application of Constraint Technologies and Logic Programming. London.
Voudouris, C. & Tsang, E. (1995). Technical Report CSM-247. Department of Computer Science, Univeristy of Essex.
Wah, B. & Chen, Y. X. (2000). Constrained Genetic Algorithms and Their Applications in Nonlinear Constrained Optimization. Proceedings of IEEE ICTAI. Vancouver, Canada.