ترکیب الگوریتم‌های جستجوی ممنوع و جمعیت مورچگان برای مسئله مسیریابی وسیله نقلیه
محورهای موضوعی : مدیریت صنعتیNarges Mahmoodi Darani 1 , Azam Dolatnejad 2 , Majid Yousefikhoshbakht 3
1 - Lecturer, Robat karim Branch, Islamic Azad University, Robat karim, Iran
2 - Lecturer, Young Researchers & Elite Club, North Tehran Branch, Islamic Azad University, Tehran, Iran
3 - Assistant Professor, Young Researchers & Elite Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran
کلید واژه: NP-hard Problems, Vehicle Routing Problem, جستجوی ممنوع, جمعیت مورچگان, مسیریابی وسیله نقلیه, ترکیب الگوریتم‌ها, Taboo Search, One-point Algorithm,
چکیده مقاله :
مسئله مسیریابی وسیله نقلیه (VRP) یکی از مهم‌‌ترین مسائل بهینه‌سازی ترکیباتی است که امروزه به علت کاربردهای وسیع که در مشکلات روزمره دارد بسیار مورد توجه قرار می‌گیرد. در این مسئله ناوگانی از وسایل نقلیه با ظرفیت Q از گره‌ای به نام انبار شروع به حرکت می‌کنند و بعد از سرویس‌دهی به مشتریان به آن باز می‌گردند به شرط آنکه هر کدام از مشتریان را فقط یک‌بار مورد ملاقات قرار دهند و در هیچ زمانی بیشتر از ظرفیت محدود Q بارگذاری نکنند. هدف در این مسئله کمینه‌کردن تعداد وسایل نقلیه به همراه مسیرهای پیموده شده توسط آن‌ها است. این مقاله نوعی روش ترکیبی جستجوی ممنوع را برای این مسئله پیشنهاد می‌کند. در این روش برای جستجوی همسایگی و حرکت از یک جواب به جواب دیگر از سه حرکت درج، جابجایی و الگوریتم جمعیت مورچگان استفاده می‌شود. برای آزمایش کارایی الگوریتم، چهارده مثال استاندارد کریستوفیدز در نظر گرفته شده و الگوریتم بر روی آن مورد اجرا قرار گرفته است. نتایج محاسباتی روی این مثال‌ها که دارای اندازه‌ای از 50 تا 199 می‌باشند نشان می‌دهد که الگوریتم پیشنهادی توانسته است که رقابت خوبی با الگوریتم‌های مشهور فراابتکاری از نظر کیفیت جواب‌ها داشته باشد. به علاوه جواب‌های نزدیک به بهترین جواب‌های تاکنون بدست آمده برای بیشتر مثال‌ها بدست آورده است به طوری که سه بهترین جواب توسط این الگوریتمبه دست آمد.
The Vehicle Routing Problem (VRP) is one of the most important combinational optimization problems that is received much attention because of wide applications in routing problems. In this problem, fleet vehicles with Q capacity start to move from the depot and return after servicing to customers in which visit only ones each customer and load more than its capacity not at all. The objective is to minimize the number of used vehicles and total distance traversed. This paper proposes a hybrid tabu search for the VRP. In this algorithm, three types of neighborhood moves including insert, swap and ant colony system are used for searching the neighborhood and moving from current solution to next solution. Computational experience with the benchmark test instances involving from 50 to 199 confirms that proposed algorithm is competitive in compared to the famous meta-heuristic algorithms in terms of the quality of generated solutions. In addition, this algorithm finds closely the best-known solutions (BKS) for most of the instances in which three best-known solutions are also found
1- Ai, T. J. & Kachitvichyanukul, V. (2009). A Particle Swarm Optimization for the Heterogeneous Fleet Vehicle Routing Problem. International Journal of Logistics and SCM Systems, 3(1), 32-39.
2- Anily S. & Mosheiov G. (1994). The traveling salesman problem with delivery and backhauls. Operations Research Letters, 16, 11-18.
3- Berger, J. & Barkaoui, M. (2003). A hybrid genetic algorithm for the capacitated vehicle routing problem. in: Proceedings of the International Genetic and Evolutionary Computation Conference – GECCO03, LNCS 2723, 646–656.
4- Chen, P., Huang, H. K. & Dong, X. Y. (2010). Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem. Expert Systems with Applications, 37(2), 1620-1627.
5- Christofides, N. (1985). Vehicle routing, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, (eds.), The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 431-448.
6- Clarke, G. & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568-581.
7- Cordeau, J. F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52, 928–936.
8- Dantzig, G. B., Fulketson, D.R. & Johnson, S.M. (1954). Solution of a large-scale traveling-salesman problem. Operations Research, 2, 393-410.
9- Dethloff, J. (2001). Vehicle routing & reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. Operations Research Spectrum, 23, 79-96.
10- Dorigo, M. & Ganbardella, L. (1997) .Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE trans. Evolutionary Computing, 53-66.
11- Du, L. & He, R. (2012). Combining Nearest Neighbor Search with Tabu Search for Large-Scale Vehicle Routing Problem. Physics Procedia, 25, 1536-1546.
12- Eilon, S., Watson-Gandy, C. D. T. & Christofides, N. (1971). Distribution Management: Mathematical Modelling & Practical Analysis, Griffin, London.
13- Fisher, M.L., & Jaikumar, R. (1978). A decomposition algorithm for large-scale vehicle routing. Working Paper 78-11-05, Department of Decision Sciences, University of Pennsylvania.
14- Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP completeness. W.H. Freeman & Co., New York.
15- Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research, 13, 533-549.
16- Golden, B. L., & Assad, A. A. (1988). Vehicle Routing: Methods and Studies. North-Holland, Amsterdam.
17- Halskau, K. & Lokketangen, A. (1998). Analyse av distribusjonsopplegget ved Sylte Mineralvannfabrikk A/S, Research Report M9812. More Research, Molde (in Norwegian).
18- Hansen, P. (1986). The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming, capri, Italy: Presented at the Congress on Numerical Methods in Combinatorial Optimization.
19- Hemmelmayr, V. C., Cordeau, J. F. & Crainic, T. G. (2012.) An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics. Computers & Operations Research, 39(12), 3215-3228.
20- Imran, A., Salhi, S. & Wassan, N. A. (2009). A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem, European Journal of Operational Research. 197(2), 509-518.
21- Jaszkiewicz, A. & Kominek, P. (2003). Genetic local search with distance preserving recombination operator for a vehicle routing problem. European Journal of Operational Research, 151, 352-364.
22- Laporte, G., Louveaux, F. & Mercure, H. (1992). The vehicle routing problem with stochastic travel times. Transportation Science, 26(3), 161-170.
23- Marinakis, Y. & Marinaki, M. (2010). A hybrid genetic – Particle Swarm Optimization Algorithm for the vehicle routing problem. Expert Systems with Applications, 37(2), 1446-1455.
24- Martello, S. & Toth, P. (1990). Generalized assignment problem, in: S. Martello and P. Toth (eds.), Knapsack Problems. Algorithms and Computer Implementations, Wiley, Chichester, . 189-220.
25- Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research A 23A, . 377-386.
26- Osman, L. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annal Operations Research, 41, 421–451.
27- Prins, C. (2009). Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence, 22, 916–928.
28- Prive, J., Renaud, J., Boctor, F.F. & Laporte, G. (2006). Solving a vehicle routing problem arising in soft drink distribution. Journal of the Operational Research Society, 57(9), 1045-1052.
29- Santos, L., Coutinho-Rodrigues, J. & Current, J. R. (2010). An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transportation Research Part B: Methodological, 44(2), 246-266.
30- Stewart, W.R. & Golden, B.L. (1983). Stochastic vehicle routing: A comprehensive approach. European Journal of Operational Research, 14, 371-385.
31- Tang, F.A. & Galvao, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33, 595-619.
32- Tang, J., Zhang, J. & Pan, Z. (2010). A scatter search algorithm for solving vehicle routing problem with loading cost. Expert Systems with Applications, 37(6), 4073–4083.
33- Toth, P. & Vigo, D. (2002). The Vehicle Routing Problem, SIAM monographs on discrete mathematics and applications.
34- Wasner, M. & Zaphel, G. (2004). An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics, 90, 403-419.
35- Werra, D. & Hertz, A. (1989). Tabu Search Techniques: A tutorial and an application to neural networks. OR Spektrum, 131-141.
36- Yousefikhoshbakht, M., Didehvar, F., Rahmati, R. & Saadati Eskandari, Z. (2012). A hybrid ant colony system for the heterogeneous fixed fleet vehicle routing problem. Transportation Research Journal, 9(2), 191-207.
37- Yousefikhoshbakht, M., Didehvar, F., Rahmati, R. & Sedighpour, M. (2012). An effective imperialist competitive algorithm for solving the open vehicle routing problem. Transportation Research Journal, 9(1), 83-95
38- Yurtkuran, A. & Emel, E. (2010). A new Hybrid Electromagnetism-like Algorithm for capacitated vehicle routing problems. Expert Systems with Applications, 37(4), 3427-3433.
39- Zachariadis, E. E., Tarantilis, C. D. & Kiranoudis, C. T. (2009). A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints. European Journal of Operational Research, 195(3), 729-743.
40- Zhang, X. & Tang, L. (2009). A new hybrid ant colony optimization algorithm for the vehicle routing problem. Pattern Recognition Letters, 30(9), 848-855.
_||_1- Ai, T. J. & Kachitvichyanukul, V. (2009). A Particle Swarm Optimization for the Heterogeneous Fleet Vehicle Routing Problem. International Journal of Logistics and SCM Systems, 3(1), 32-39.
2- Anily S. & Mosheiov G. (1994). The traveling salesman problem with delivery and backhauls. Operations Research Letters, 16, 11-18.
3- Berger, J. & Barkaoui, M. (2003). A hybrid genetic algorithm for the capacitated vehicle routing problem. in: Proceedings of the International Genetic and Evolutionary Computation Conference – GECCO03, LNCS 2723, 646–656.
4- Chen, P., Huang, H. K. & Dong, X. Y. (2010). Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem. Expert Systems with Applications, 37(2), 1620-1627.
5- Christofides, N. (1985). Vehicle routing, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, (eds.), The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 431-448.
6- Clarke, G. & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568-581.
7- Cordeau, J. F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52, 928–936.
8- Dantzig, G. B., Fulketson, D.R. & Johnson, S.M. (1954). Solution of a large-scale traveling-salesman problem. Operations Research, 2, 393-410.
9- Dethloff, J. (2001). Vehicle routing & reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. Operations Research Spectrum, 23, 79-96.
10- Dorigo, M. & Ganbardella, L. (1997) .Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE trans. Evolutionary Computing, 53-66.
11- Du, L. & He, R. (2012). Combining Nearest Neighbor Search with Tabu Search for Large-Scale Vehicle Routing Problem. Physics Procedia, 25, 1536-1546.
12- Eilon, S., Watson-Gandy, C. D. T. & Christofides, N. (1971). Distribution Management: Mathematical Modelling & Practical Analysis, Griffin, London.
13- Fisher, M.L., & Jaikumar, R. (1978). A decomposition algorithm for large-scale vehicle routing. Working Paper 78-11-05, Department of Decision Sciences, University of Pennsylvania.
14- Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP completeness. W.H. Freeman & Co., New York.
15- Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research, 13, 533-549.
16- Golden, B. L., & Assad, A. A. (1988). Vehicle Routing: Methods and Studies. North-Holland, Amsterdam.
17- Halskau, K. & Lokketangen, A. (1998). Analyse av distribusjonsopplegget ved Sylte Mineralvannfabrikk A/S, Research Report M9812. More Research, Molde (in Norwegian).
18- Hansen, P. (1986). The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming, capri, Italy: Presented at the Congress on Numerical Methods in Combinatorial Optimization.
19- Hemmelmayr, V. C., Cordeau, J. F. & Crainic, T. G. (2012.) An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics. Computers & Operations Research, 39(12), 3215-3228.
20- Imran, A., Salhi, S. & Wassan, N. A. (2009). A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem, European Journal of Operational Research. 197(2), 509-518.
21- Jaszkiewicz, A. & Kominek, P. (2003). Genetic local search with distance preserving recombination operator for a vehicle routing problem. European Journal of Operational Research, 151, 352-364.
22- Laporte, G., Louveaux, F. & Mercure, H. (1992). The vehicle routing problem with stochastic travel times. Transportation Science, 26(3), 161-170.
23- Marinakis, Y. & Marinaki, M. (2010). A hybrid genetic – Particle Swarm Optimization Algorithm for the vehicle routing problem. Expert Systems with Applications, 37(2), 1446-1455.
24- Martello, S. & Toth, P. (1990). Generalized assignment problem, in: S. Martello and P. Toth (eds.), Knapsack Problems. Algorithms and Computer Implementations, Wiley, Chichester, . 189-220.
25- Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research A 23A, . 377-386.
26- Osman, L. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annal Operations Research, 41, 421–451.
27- Prins, C. (2009). Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence, 22, 916–928.
28- Prive, J., Renaud, J., Boctor, F.F. & Laporte, G. (2006). Solving a vehicle routing problem arising in soft drink distribution. Journal of the Operational Research Society, 57(9), 1045-1052.
29- Santos, L., Coutinho-Rodrigues, J. & Current, J. R. (2010). An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transportation Research Part B: Methodological, 44(2), 246-266.
30- Stewart, W.R. & Golden, B.L. (1983). Stochastic vehicle routing: A comprehensive approach. European Journal of Operational Research, 14, 371-385.
31- Tang, F.A. & Galvao, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33, 595-619.
32- Tang, J., Zhang, J. & Pan, Z. (2010). A scatter search algorithm for solving vehicle routing problem with loading cost. Expert Systems with Applications, 37(6), 4073–4083.
33- Toth, P. & Vigo, D. (2002). The Vehicle Routing Problem, SIAM monographs on discrete mathematics and applications.
34- Wasner, M. & Zaphel, G. (2004). An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics, 90, 403-419.
35- Werra, D. & Hertz, A. (1989). Tabu Search Techniques: A tutorial and an application to neural networks. OR Spektrum, 131-141.
36- Yousefikhoshbakht, M., Didehvar, F., Rahmati, R. & Saadati Eskandari, Z. (2012). A hybrid ant colony system for the heterogeneous fixed fleet vehicle routing problem. Transportation Research Journal, 9(2), 191-207.
37- Yousefikhoshbakht, M., Didehvar, F., Rahmati, R. & Sedighpour, M. (2012). An effective imperialist competitive algorithm for solving the open vehicle routing problem. Transportation Research Journal, 9(1), 83-95
38- Yurtkuran, A. & Emel, E. (2010). A new Hybrid Electromagnetism-like Algorithm for capacitated vehicle routing problems. Expert Systems with Applications, 37(4), 3427-3433.
39- Zachariadis, E. E., Tarantilis, C. D. & Kiranoudis, C. T. (2009). A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints. European Journal of Operational Research, 195(3), 729-743.
40- Zhang, X. & Tang, L. (2009). A new hybrid ant colony optimization algorithm for the vehicle routing problem. Pattern Recognition Letters, 30(9), 848-855.