مدل‏سازی ریاضی برای مسأله مسیریابی وسایل نقلیه با حمل برگشتی و حل آن با الگوریتم کلونی مورچه چندگانه

نوع مقاله : مقاله پژوهشی- فارسی

نویسندگان

1 استادیار گروه مهندسی صنایع، دانشگاه علم و فرهنگ، تهران، ایران

2 استاد دانشکده مهندسی صنایع، پردیس دانشکدهﻫای فنی، دانشگاه تهران، تهران، ایران

3 دانشجوی دکترای مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه یزد، یزد، ایران

4 دانشجوی دکترای مهندسی صنایع، پردیس دانشکدهﻫای فنی، دانشگاه تهران، تهران، ایران

چکیده

در این مقاله، مسأله مسیریابی وسایل نقلیه با حمل برگشتی همراه با یک­سری محدودیت­های عملیاتی بررسی می شود. مشتریان به دو گروه مشتریان خط رفت که تحویل کالا به آن­ها صورت می­گیرد و مشتریان خط برگشت که کالا از آن­ها دریافت می­شود، تقسیم می­شوند. همچنین، اولویت خدمت­رسانی با مشتریان خط رفت است. نکته حائز اهمیت در این تحقیق آنکه، امکان تقسیم تقاضا برای مشتریانی که تقاضای آن­ها از بزرگترین وسیله نقلیه موجود بیشتر است و همچنین، محدودیت عملیاتی جدید عدم دسترسی به بعضی از وسایل نقلیه برای تعدادی از مشتریان، به صورت توأمان در نظر گرفته می­شود. دپوی مرکزی شامل ناوگانی از وسایل نقلیه با ظرفیت­های مختلف و به تعداد نامحدود بوده و تقاضای مشتریان به صورت پویا است و در هر دوره قابل تغییر است. این مسأله از نوع چند جمله­ای نامعین سخت (NP-hard) است و با توجه به ساختار خاص آن و بررسی ادبیات موضوع، یک الگوریتم کلونی مورچه چندگانه جدید(NM-ACO) برای حل آن پیشنهاد  می­شود. در این مقاله، پس از آشنایی با کلیات و بیشینه تحقیق، مدل ریاضی جدیدی برای مسأله مورد نظر ارایه می­شود و در ادامه الگوریتم کلونی مورچه چندگانه پیشنهادی که شامل دو فاز تخصیص و مسیریابی است، تشریح  می­گردد. در پایان، به تحلیل نتایج عددی حاصل از این الگوریتم برای مسایل آزمون طراحی شده پرداخته می­شود.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Mathematical Modeling for a Vehicle Routing Problem with Backhaul Solved by a New Multi-Ant Colony Optimization Algorithm

نویسندگان [English]

  • Azizollah Jafari 1
  • Reza Tavakkoli-Moghaddam 2
  • Mohsen Forghani 3
  • Rahmat Arab 4
1 Assistant Professor , Industrial Engineering University of Science and Culture, Tehran, Iran
2 Prof Industrial Engineering, University of Tehran, Tehran, Iran
3 PhD Industrial Engineering, University of Yazd, Yazd, Iran
4 PhD Industrial Engineering University of Tehran, Tehran, Iran
چکیده [English]

This paper considers the vehicle routing problem with backhaul (VRPB) and some applicable constraints, in which a set of costumers are divided into two subsets of linehaul and backhaul costumers. Each linehaul costumer requires its demands to be delivered from the depot. In addition, a specified quantity of products should be picked up from the backhaul nodes to the depot. The main point in this study is that the customer demands, which are over than the maximum of available vehicles, can be divided to different customers. In addition, there is limited vehicle access availability for some costumers. The central depot includes a fleet of vehicles with different capacities, in which the number of vehicles of each type is not limited and customer demands are dynamic and can change in each period. This problem is a well-known NP-hard one; therefore, a new multi-ant colony optimization algorithm is proposed to solve the given problem. This proposed algorithm contains two phases, namely clustering and routing. Finally, the numerical results of designed test problems have been discussed and analyzed.

کلیدواژه‌ها [English]

  • Vehicle Routing Problem with backhaul
  • Heterogeneous fleet of vehicles
  • Split service
  • Ant colony system
  • Local search

مراجع

Anily, S., 1996. The vehicle-routing problem with delivery and back-haul options. Naval Research Logistics 43, 415–434.
Anbuudayasankar, S.P., Ganesh, K., Lenny Koh, S.C., Ducq, Y. (2012). Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls. Expert Systems with Applications 39(3), 2296–2305.
Brandao, J., 2006. A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research 173, 540–555.
Bullnheimer, B., Hartl, R.F., Strauss, C., 1999. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research 89, 319–328.
Barnhart, C. and Laporte, G. (Eds.), 2007, Handbook in OR & MS, Chapter 6 -Vehicle Routing Vol. 14.
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, 29–41.
Duhamel, C., Potvin, J.Y., Rousseau, J.M., 1997. A tabu search heuristic for the vehicle routing problem with backhauls and time windows. Transportation Science 31, 49–59.
Gambardella, L.M., Taillard, E., Agazzi, G., 1999. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: Corne, D., Dorigo, M., Glover, F. (Eds.), New Ideas in Optimization. McGraw-Hill, pp. 63–76.
Gajpal, Y., Abad, P.L., 2009, Multi-ant colony system (MACS) for a vehicle routing problem  with backhauls, European Journal of Operational Research 196(1), 102–117.
Goetschalckx, M., Jacobsblecha, C., 1989. The vehicle-routing problem with backhauls. European Journal of Operational Research 42, 39–51.
Goetschalckx, M., Jacobsblecha, C., 1993. The vehicle routing problem with backhauls: Properties and solution algorithms. Georgia Institute of Technology, Technical Report, MHRC-TR-88-13.
Liu. S. C., Chung. C. H., 2009, “A heuristic method for the vehicle routing problem with backhauls and inventory”, Journal of Intelligent Manufacturing 20(1), 29–42.
Osman, I.H., Wassan, N.A., 2002. A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. Journal of Scheduling 5, 263–285.
Potvin, J.-Y., Duhamel, C., Guertin, F., 1996. A genetic algorithm for vehicle routing with backhauling. Applied Intelligence 6, 345–355.
Reimann, M., Doerner, K., Hartl, R.F., 2002. Insertion based ants for vehicle routing problems with backhauls and time windows. Lecture Notes in Computer Science, 135–148.
Reimann, M., Doerner, K., Hartl, R.F., Ants, D., 2004. Savings based ants divide and conquer the vehicle routing problem. Computers and Operations Research 31, 563–591.
Salhi, S., Wassan, N., Hajarat, M. (2013). The fleet size and mix vehicle routing problem with backhauls: formulation and set partitioning-based heuristics. Transportation Research - Part E: Logistics and Transportation Review, 56, 22–35.
Tavakkoli-Moghaddam, R., Saremi, A.R., Ziaee M.S., 2006, “A memetic algorithm for a vehicle routing problem with backhauls”. Applied Mathematics and Computation 181, 1049–1060.
Thangiah, S., Potvin, J., Sun, T. 1996. “Heuristic approaches to vehicle routing with backhauls and time windows” International Journal of Computers and operations Research 23(11), 1043–1057.
Thangiah, S.R., Potvin, J.Y., Sun, T., 1996. Heuristic approaches to vehicle routing with backhauls and time windows. Computers and Operations Research 23, 1043–1058.
Toth, P., Vigo, D., 1996. A heuristic algorithm for the vehicle routing problem with backhauls. In: Bianco, L., Toth, P. (Eds.), In: Advanced Method in Transportation Analysis. Springer-Verlag, Berlin, pp. 585–608.
Toth, P., Vigo, D., 1997. An exact algorithm for the vehicle routing problem with backhauls. Transportation Science 31, 372–385.
Toth, P., Vigo, D., 1999. A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. European Journal of Operational Research 113, 528–543.
Tütüncü, G. Y. (2010). An interactive GRAMPS algorithm for the heterogeneous fixed fleet vehicle routing problem with and without backhauls. European Journal of Operational Research 201(2), 593–600.
Wade, A.C., Salhi, S., 2002. An investigation into a new class of vehicle routing problem with backhauls. Omega 30, 479–487.
Wade, A.C., Salhi, S., 2004. An ant system algorithm for the mixed vehicle routing problem with backhauls. Metaheuristics: Computer Decision-making. Kluwer Academic Publishers, pp. 699–719.
Wassan, N., 2004. Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls Canterbury Business School, University of Kent, Working Paper No. 56.
Yano, C., Chan, T., Richter, L., Cutler, T., Murty, K., McGettigan, D., 1987. Vehicle routing at quality stores. Interfaces 17, 52–63.
Zachariadis, E.E., Kiranoudis, C.T. (2012). An effective local search approach for the vehicle routing problem with backhauls. Expert Systems with Applications 39(3), 3174-3184.
Wang, Z., Wang, Z., 2009, “A novel two-phase heuristic method for vehicle routing problem with backhauls”, Computers & Mathematics with Applications 57 (11-12), 1923–1928.
Zhen, T., Zhu, Y., Zhang, Q., 2008. “A hybrid ant colony algorithm for the capacitated vehicle routing problem”, Proceedings of IEEE International Symposium on IT in Medicine and Education, pp. 935–939.
 
پژوهش در مدیریت تولید و عملیات
دوره 7، شماره 1 - شماره پیاپی 12
فروردین 1395
صفحه 215-234

فایل ها

هم رسانی

ارجاع به این مقاله

آمار