1مربی، دانشگاه آزاد اسلامی، واحد رباط کریم، رباط کریم، ایران
2مربی، دانشگاه آزاد اسلامی، واحد تهران شمال، باشگاه پژوهشگران جوان و نخبگان، تهران، ایران
3مربی، دانشگاه آزاد اسلامی، واحد همدان، باشگاه پژوهشگران جوان و نخبگان، همدان، ایران
تاریخ دریافت: 16 دی 1396،
تاریخ پذیرش: 16 دی 1396
چکیده
مسئله مسیریابی وسیله نقلیه (VRP) یکی از مهم‌‌ترین مسائل بهینه‌سازی ترکیباتی است که امروزه به علت کاربردهای وسیع که در مشکلات روزمره دارد بسیار مورد توجه قرار می‌گیرد. در این مسئله ناوگانی از وسایل نقلیه با ظرفیت Q از گره‌ای به نام انبار شروع به حرکت می‌کنند و بعد از سرویس‌دهی به مشتریان به آن باز می‌گردند به شرط آنکه هر کدام از مشتریان را فقط یک‌بار مورد ملاقات قرار دهند و در هیچ زمانی بیشتر از ظرفیت محدود Q بارگذاری نکنند. هدف در این مسئله کمینه‌کردن تعداد وسایل نقلیه به همراه مسیرهای پیموده شده توسط آن‌ها است. این مقاله نوعی روش ترکیبی جستجوی ممنوع را برای این مسئله پیشنهاد می‌کند. در این روش برای جستجوی همسایگی و حرکت از یک جواب به جواب دیگر از سه حرکت درج، جابجایی و الگوریتم جمعیت مورچگان استفاده می‌شود. برای آزمایش کارایی الگوریتم، چهارده مثال استاندارد کریستوفیدز در نظر گرفته شده و الگوریتم بر روی آن مورد اجرا قرار گرفته است. نتایج محاسباتی روی این مثال‌ها که دارای اندازه‌ای از 50 تا 199 می‌باشند نشان می‌دهد که الگوریتم پیشنهادی توانسته است که رقابت خوبی با الگوریتم‌های مشهور فراابتکاری از نظر کیفیت جواب‌ها داشته باشد. به علاوه جواب‌های نزدیک به بهترین جواب‌های تاکنون بدست آمده برای بیشتر مثال‌ها بدست آورده است به طوری که سه بهترین جواب توسط این الگوریتم به دست آمد.
1Lecturer, Robat karim Branch, Islamic Azad University, Robat karim, Iran
2Lecturer, Young Researchers & Elite Club, North Tehran Branch, Islamic Azad University, Tehran, Iran
3Assistant Professor, Young Researchers & Elite Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran
چکیده [English]
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
کلیدواژه‌ها [English]
Taboo Search, One-point Algorithm, NP-hard Problems, Vehicle Routing Problem
مراجع
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.
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.
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.
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.
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.
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.
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
ابتدای صفحه