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

فصلنامه مدیریت راهبردی در سیستم های صنعتی (مدیریت صنعتی سابق)

مقاله 7، دوره 8، شماره 24، شهریور 1392، صفحه 99-112   

نوع مقاله: مقاله پژوهشی

نویسندگان

مجید یوسفی خوشبخت^{* 1}؛ حسن زارعی²؛ زهرا سعادتی اسکندری³؛ نرگس محمودی دارانی⁴؛ احمد محمود جانلو⁵

¹مربی، دانشگاه آزاد اسلامی، واحد همدان، باشگاه پژوهشگران جوان و نخبگان، همدان، ایران،

²دانشکده ریاضی، دانشگاه پیام نور، همدان، ایران

³کارشناس ارشد، دانشکده دانشگاه آزاد اسلامی، واحد فریدن، باشگاه پژوهشگران جوان و نخبگان، فریدن، ایران

⁴مربی، دانشگاه آزاد اسلامی، واحد رباط کریم، رباط کریم، ایران

⁵کارشناس ارشد، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر تهران

چکیده

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

کلیدواژه‌ها

الگوریتم نمونه مورچگان؛ مسائل –NP تام؛ مسئله مسیریابی وسیله نقلیه باز؛ الگوریتم درج؛ الگوریتم جابجایی

مراجع

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.