یوسفی خوشبخت, مجید, زارعی, حسن, سعادتی اسکندری, زهرا, محمودی دارانی, نرگس, محمود جانلو, احمد. (1392). بهینه‌سازی در مسیریابی باز وسیله نقلیه با استفاده از یک الگوریتم کارای ترکیبی فراابتکاری. فصلنامه مدیریت صنعتی, 8(24), 99-112.
مجید یوسفی خوشبخت; حسن زارعی; زهرا سعادتی اسکندری; نرگس محمودی دارانی; احمد محمود جانلو. "بهینه‌سازی در مسیریابی باز وسیله نقلیه با استفاده از یک الگوریتم کارای ترکیبی فراابتکاری". فصلنامه مدیریت صنعتی, 8, 24, 1392, 99-112.
یوسفی خوشبخت, مجید, زارعی, حسن, سعادتی اسکندری, زهرا, محمودی دارانی, نرگس, محمود جانلو, احمد. (1392). 'بهینه‌سازی در مسیریابی باز وسیله نقلیه با استفاده از یک الگوریتم کارای ترکیبی فراابتکاری', فصلنامه مدیریت صنعتی, 8(24), pp. 99-112.
یوسفی خوشبخت, مجید, زارعی, حسن, سعادتی اسکندری, زهرا, محمودی دارانی, نرگس, محمود جانلو, احمد. بهینه‌سازی در مسیریابی باز وسیله نقلیه با استفاده از یک الگوریتم کارای ترکیبی فراابتکاری. فصلنامه مدیریت صنعتی, 1392; 8(24): 99-112.
بهینه‌سازی در مسیریابی باز وسیله نقلیه با استفاده از یک الگوریتم کارای ترکیبی فراابتکاری
1مربی، دانشگاه آزاد اسلامی، واحد همدان، باشگاه پژوهشگران جوان و نخبگان، همدان، ایران،
2دانشکده ریاضی، دانشگاه پیام نور، همدان، ایران
3کارشناس ارشد، دانشکده دانشگاه آزاد اسلامی، واحد فریدن، باشگاه پژوهشگران جوان و نخبگان، فریدن، ایران
4مربی، دانشگاه آزاد اسلامی، واحد رباط کریم، رباط کریم، ایران
5کارشناس ارشد، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر تهران
تاریخ دریافت: 18 دی 1396،
تاریخ پذیرش: 18 دی 1396
چکیده
مسئله مسیریابی وسیله نقلیه باز (OVRP) یکی از مسائل مورد علاقه در ریاضیات محاسباتی است که بسیار مورد توجه محققان و دانشمندان قرار می‌گیرد. در این مسئله هدف تعیین کمینه هزینه جابجایی چندین وسیله نقلیه است که به طور هم‌زمان از انبار کالا شروع به حرکت می‌کنند و تعدادی از مشتری‌ها را مورد ملاقات قرار می‌دهند. باید توجه کرد که برخلاف مسئله مسیریابی وسیله نقلیه (VRP)، در این مسئله وسائل نقلیه لازم نیست که به انبار کالا برگردند. این مقاله نوعی روش فراابتکاری که در فاز اول آن از روش اصلاحی نمونه مورچگان (EAS) برای یافتن جوا‌ب‌هایی زیر بهینه استفاده می‌کند و در فاز دوم الگوریتم‌های درج و جابجایی برای یافتن جواب‌های بهتر به کار گرفته می‌شود. این الگوریتم بر روی مجموعه‌ای از 15 مثال با 50-400 مشتری مورد آزمایش واقع گردید که معلوم شد که این الگوریتم قادر است که در 10 مثال به بهترین جواب تاکنون یافت شده دست یابد. به علاوه از نظر کیفیت جواب‌های بدست آمده، ثابت شد که الگوریتم پیشنهادی بسیار رقابت پذیر است و انحراف معیار الگوریتم در همه مثال‌ها در حدود 1 درصد قرار دارد. به طور کل می‌توان گفت که الگوریتم پیشنهادی در مقایسه با سایر روش‌های موجود برای حل مسئله OVRP از نظر کیفیت جواب‌‌ها نتایج بهتری را بدست آورده است.
1Member of Faculty Staff and Member of Young Researchers Club, Islamic Azad University, Hamadan Branch, Hamadan, Iran
2Faculty of Mathematics, Payam Noor University, Hamadan, Hamadan, Iran
3M. A Graduated and Member of Young Researchers Club, Islamic Azad University, Faridan Branch,
4Member of Faculty Staff, Islamic Azad University, Robat Karim Branch, Robat Karim. Tehran
5M.A Graduated, Faculty of Mathematics and Computer Sciences, Amirkabir University of Technology, Tehran, Iran
چکیده [English]
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.
کلیدواژه‌ها [English]
Elite Ant Colony, NP-Complete Problems, Open Vehicle Routing Problem, Mixed Meta-heuristic Algorithm
مراجع
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.
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.
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.
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.
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.
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.
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.
ابتدای صفحه