بهینه‌سازی در مسیریابی باز وسیله نقلیه با استفاده از یک الگوریتم کارای ترکیبی فراابتکاری

محورهای موضوعی : مدیریت صنعتی

Majid Yousefi khoshbakht ¹ , Hassan Zarie ² , Zahra Sadati Eskandari ³ , Narges Mahmmudi Daranie ⁴ , Ahmad Mahmmud Janlo ⁵

1 - Member of Faculty Staff and Member of Young Researchers Club, Islamic Azad University, Hamadan Branch, Hamadan, Iran
2 - Faculty of Mathematics, Payam Noor University, Hamadan, Hamadan, Iran
3 - M. A Graduated and Member of Young Researchers Club, Islamic Azad University, Faridan Branch,
4 - Member of Faculty Staff, Islamic Azad University, Robat Karim Branch, Robat Karim. Tehran
5 - M.A Graduated, Faculty of Mathematics and Computer Sciences, Amirkabir University of Technology, Tehran, Iran

تاریخ دریافت : 1396/10/18 تاریخ پذیرش : 1396/10/18 تاریخ انتشار : 1392/06/01

کلید واژه: Open Vehicle Routing Problem, الگوریتم نمونه مورچگان, مسائل –NP تام, مسئله مسیریابی وسیله نقلیه باز, الگوریتم درج, الگوریتم جابجایی, Elite Ant Colony, NP-Complete Problems, Mixed Meta-heuristic Algorithm,

چکیده مقاله :

مسئله مسیریابی وسیله نقلیه باز (OVRP) یکی از مسائل مورد علاقه در ریاضیات محاسباتی است که بسیار مورد توجه محققان و دانشمندان قرار می‌گیرد. در این مسئله هدف تعیین کمینه هزینه جابجایی چندین وسیله نقلیه است که به طور هم‌زمان از انبار کالا شروع به حرکت می‌کنند و تعدادی از مشتری‌ها را مورد ملاقات قرار می‌دهند. باید توجه کرد که برخلاف مسئله مسیریابی وسیله نقلیه (VRP)، در این مسئله وسائل نقلیه لازم نیست که به انبار کالا برگردند. این مقاله نوعی روش فراابتکاری که در فاز اول آن از روش اصلاحی نمونه مورچگان (EAS) برای یافتن جوا‌ب‌هایی زیر بهینه استفاده می‌کند و در فاز دوم الگوریتم‌های درج و جابجایی برای یافتن جواب‌های بهتر به کار گرفته می‌شود. این الگوریتم بر روی مجموعه‌ای از 15 مثال با 50-400 مشتری مورد آزمایش واقع گردید که معلوم شد که این الگوریتم قادر است که در 10 مثال به بهترین جواب تاکنون یافت شده دست یابد. به علاوه از نظر کیفیت جواب‌های بدست آمده، ثابت شد که الگوریتم پیشنهادی بسیار رقابت پذیر است و انحراف معیار الگوریتم در همه مثال‌ها در حدود 1 درصد قرار دارد. به طور کل می‌توان گفت که الگوریتم پیشنهادی در مقایسه با سایر روش‌های موجود برای حل مسئله OVRP از نظر کیفیت جواب‌‌ها نتایج بهتری را بدست آورده است.

چکیده انگلیسی:

The Open Vehicle Routing Problem (OVRP) is one of the most intensively studied problems in computational mathematics that nowadays and it has been receiving much attention by researchers and scientists. In this Problem, the objective is to define minimized distance traveled of the several vehicles that start to move simultaneously from the depot and visit some customers. It is noted that against to the Vehicle Routing Problem (VRP), it is not necessary that vehicles return to the depot after servicing the customers. This paper proposes a meta-heuristic algorithm in which at the first stage, a modified elite ant colony (EAS) is applied for finding a suboptimal solution, and at the second stage, the insert and swap local search algorithms are used for finding better solutions. Computational results on fifteen standard benchmark problem instances show that the proposed algorithm is comparable in terms of solution quality of other meta-heuristic algorithms.  

منابع و مأخذ:

1-      Bodin, L., Golden, B., Assad, A. & Ball, M. (1983). Routing and scheduling of vehicles and crews: the state of the art. Computers & Operations Research, 10, 63–211.

2-      Brandão, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157, 52–64.

3-      Chiang, W. C., Russell, R., Xu, X., & Zepeda, D. (2009). A simulation/metaheuristic approach to newspaper production and distribution supply chain problems. International Journal of Production Economics, 121(2), 752-767.

4-      Christofides, N., Mingozzi, A. & Toth, P. (1979). The vehicle routing problem, In: Christofides N, Mingozzi A, Toth P, Sandi C, editors. Combinatorial optimization. Chichester, UK: Wiley, 315-338.

5-      Dorigo, M., Maniezzo, V. & Colorni, A. (1996). The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26(1), 29–41.

6-      Fleszar, K., Osman, I. H. & Hindi, K. S. (2009). A variable neighborhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, 195(3), 803-809.

7-      Fu, Z., Eglese, R. & Li, L. (2005). A new tabu search heuristic for the open vehicle routing problem. Journal of the Operational Research Society, 56, 267–274.

8-      Levy, L. (2005). Private communication, in RouteSmart Technologies.

9-      Li, F., Golden, B. & Wasil, E. (2005). Very large-scale vehicle routing: new test problems, algorithms, and results. Computers & Operations Research, 32,  1165–1179.

10-  Li, F., Golden, B. &Wasil, E. (2007). The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers & Operations Research, 34(10), 2918-2930.

11-  Letchford, A. N., Lysgaard, J. & Eglese, R. W. (2007). A branch-and-cut algorithm for the capacitated open vehicle routing problem. Journal of the Operational Research Society, 58, 1642–1651.

12-  MirHassani, S. A. & Abolghasemi, N. (2011). A particle swarm optimization algorithm for open vehicle routing problem. Expert Systems with Applications, 38(9), 11547-11551.

13-  Pisinger, D. & Ropke, S. (2005). A general heuristic for vehicle routing problems. University of Copenhagen, Technical Report 05/01, DIKU.

14-  Repoussisa, P. P., Tarantilisa, C. D., Braysy, O. & Ioannoua, G. (2010). A hybrid evolution strategy for the open vehicle routing problem. Computers & Operations Research, 37, 443-455.

15-  Russell, R., Chiang, W. C. & David, Z. (2008). Integrating multi-product production and distribution in newspaper logistics. Computers & Operations Research, 35(5),  1576-1588.

16-  Saadati Eskandari, Z. & Yousefikhoshbakht, M. (2012). Solving the vehicle routing problem by using an effective reactive bone route algorithm. Transportation Research Journal, 1, 51-67.

17-  Salari, M., Toth, P. &Tramontani, A. (2010). An ILP improvement procedure for the Open Vehicle Routing Problem. Computers & Operations Research, 37(12), 2106-2120.

18-  Sariklis, D. & Powell, S. (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51, 64–73.

19-  Schrage, L. (1981). Formulation and structure of more complex/realistic routing and scheduling problems. Networks, 11, 229–232.

20-  Taillard, R. (1995). Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1(1), 147–167.

21-  Tarantilis, C., Diakoulaki, D. & Kiranoudis, C. (2004). Combination of geographical information system and efficient routing algorithms for real life distribution operations. European Journal of Operational Research, 152, 37–53.

22-  Tarantilis, C., Ioannou, G., Kiranoudis, C. & Prastacos, G. (2004). A threshold accepting approach to the open vehicle routing problem, RAIRO Operations Research, 38, 345–360.

23-  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.

24-  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

25-  Yousefikhoshbakht1, M. & Khorram, E. (2012). Solving the vehicle routing problem by a hybrid meta-heuristic algorithm. Journal of Industrial Engineering International, 8(11), 1-9.

26-  Yousefikhoshbakht, M. & Rahmati, R. (2011). An Improved Ant Colony System for Solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Transportation Research Journal, 8(2), 183-198.

27-  Yu, S., Ding, C. & Zhu, K. 2011. A hybrid GA–TS algorithm for open vehicle routing optimization of coal mines material. Expert Systems with Applications, 38(8), 10568-10573.

28-   Zafari, A., Tashakori , S. M. & Yousefikhoshbakht  M. (2010). A Hybrid Effective Genetic Algorithm for Solving the Vehicle Routing Problem. International Journal of Industrial Engineering and Production Management, 21 (2), 63-76.