مسئله مسیریابی وسایل نقلیه چند انباره با تحویل چندمرحله‌ای و محدودیت تردد: الگوریتم جستجوی همسایگی متغیر

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

نویسندگان

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

2 دانشیار گروه مهندسی صنایع ، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران

چکیده

هدف از حل مساله مسیریابی وسایل نقلیه، یافتن مسیری مناسب با در نظر گرفتن شرایط موجود در مساله حمل ‌و نقل است. در این مساله، در نظر گرفتن شرایط مسیریابی با چند انبار به همراه اعمال محدودیت تردد برخی وسایل نقلیه در برخی مسیرها، شرایطی کاملا واقعی و پیچیده را بوجود خواهد آورد. از طرفی در مواردی نیز لازم است با چندین بار ملاقات، تقاضای مشتریان تحویل داده شود. به این منظور در این تحقیق سعی شده با در نظر گرفتن همزمان شرایط چند انباره بودن، امکان تحویل چندمرحله‌ای و محدودیت تردد، سعی گردیده است تا شرایط مساله مسیریابی تا حد زیادی به مسائل دنیای واقعی نزدیک گردد. در این مقاله، پس از ارائه یک مدل ریاضی، مساله در ابعاد کوچک با استفاده از حل کننده سیپلکس حل شده است. در ادامه و از آنجائیکه مساله مورد بررسی در دسته مسائل NP-Hard می‌باشد، برای حل آن در ابعاد بزرگتر، الگوریتم جستجوی همسایگی متغیر پیشنهاد گردیده است. در پایان نیز برای اعتبار سنجی و بررسی کیفیت الگوریتم پیشنهادی، از الگوریتم شبیه‌سازی تبرید استفاده شده است. نتایج محاسباتی حاصل نشان می‌دهد که الگوریتم پیشنهادی از نظر زمان و کیفیت حل دارای عملکرد مناسبی است.

کلیدواژه‌ها


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

Multi-depot vehicle routing problem with split delivery and traffic restriction: Variable neighborhood search algorithm

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

  • Mostafa Hajikhani 1
  • Javad Behnamian 2
1 PhD student of industrial engineering, Bu-Ali Sina University, Hamedan, Iran
2 Associate Professor, Department of Industrial Engineering, Faculty of Engineering, Bu Ali Sina University, Hamadan
چکیده [English]

The purpose of solving the problem of vehicle routing is to find a suitable route taking into account the existing conditions in the transportation problem. In this case, considering the routing conditions with several depots along with imposing traffic restrictions on some vehicles on some routes, will create quite real and complex conditions. Furthermore, in some cases, it is necessary to deliver the customer demand by visiting several times. For this purpose, in this research, by simultaneous considering of multiple depots, split delivery and traffic restrictions, it has been tried to bring the conditions of the routing problem very close to real-world problems. In this paper, after presenting a mathematical model, the problem is solved in small-size instances using CPLEX solver. Then, due to NP-Hardness of considered problem, to solve it on a larger size instance, a variable neighborhood search algorithm is proposed. Finally, the simulated annealing algorithm is used to validate and evaluate the quality of the proposed algorithm. The computational results show that the proposed algorithm has good performance in terms of runtime and solution quality.

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

  • Vehicle Routing Problem
  • Multi-Depot
  • Split Delivery
  • Traffic Restriction
  • Variable Neighborhood Search
[1]     Tavakkoli-Moghaddam R, Omidi-Rekavandi M, Ghodratnama A. (2014) “Mathematical modeling for the forward and reverse logistics network design”, Management Research in Iran,17, 4, 43-63.
[2]     Brandão, J. (2020) "A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem", European Journal of Operational Research, 284, 559-571
[3]     Soeanu, A., Ray, S., Berger, J., Boukhtouta, A. and Debbabi, M. (2020) "Multi-depot vehicle routing problem with risk mitigation: Model and solution algorithm", Expert Systems with Applications, 145, 113099.
[4]      Crevier, B. Jean-François, C. and Gilbert, L. (2007) "The multi-depot vehicle routing problem with inter-depot routes", European journal of operational research, 176, 2, 756-773.
[5]     Montoya-Torres, J. R., Franco, J. L., Isaza, S.N., Jimenez, H. F. and Herazo-Padilla, N. (2015) "A literature review on the vehicle routing problem with multiple depots", Computers & Industrial Engineering, 79, 115-129.
[6]     Ray, S., Soeanu, A., Berger, J. and Debbabi, M. (2014) "The multi-depot split-delivery vehicle routing problem: Model and solution algorithm", Knowledge-Based Systems, 71 238-265.
[7]     Li, J., Li, T., Yu, Y., Zhang, Zh., M. Pardalos, P., Zhang, Y. and Ma,Y. (2019) "Discrete firefly algorithm with compound neighborhoods for asymmetric multi-depot vehicle routing problem in the maintenance of farm machinery", Applied Soft Computing, 81, 105460.
[8]     Tu, W., Fang, Zh., Li, Q., Shaw, Sh.-L. and Chen, B. (2014) "A bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem", Transportation Research Part E: Logistics and Transportation Review, 61, 84-97.
[9]     Bortfeldt, A. and Junmin Y. (2020) "The split delivery vehicle routing problem with three-dimensional loading constraints", European Journal of Operational Research, 282, 2, 545-558.
[10]  Casazza, M., Alberto C. and Wolfler Calvo, R. (2020) "A route decomposition approach for the single commodity Split Pickup and split delivery vehicle routing problem", European Journal of Operational Research, in press, DOI: 10.1016/j.ejor.2019.07.015.
[11]  Gulczynski, D. Bruce, G. and Edward, W. (2011) "The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results", Computers & Industrial Engineering, 61, 3, 794-804.
[12]  Wang, X.,Golden, B., Wasil, E. and Zhang, R. (2016). "The min–max split delivery multi-depot vehicle routing problem with minimum service time requirement", Computers & Operations Research, 71, 110-126.
[13]  Hosseini, S. and Hasani, A. (2018) “Modelling and solving the vehicle routing problem in distribution of a supply chain considering restriction on the movement of the vehicles”, Sharif Journal of Industrial Engineering & Management, 34.1(1.1), 147-155.
[14]  Salehi Sarbijan, M. and Behnamian, J. (2020) “Modeling and solving of bi-objective multi-product production routing problem with outsourcing and accident risk in transportation”, Modern Research in Decision Making, 5, 2, 137-163.
[15]  Behnamian, J. and Adabi, F. (2018). Competitive production routing problem: modeling, solving and valid inequalities”, Modern Research in Decision Making, 3(2), 55-79.
[16]  Tam, V. and Keng T. (2004) "Combining meta-heuristics to effectively solve the vehicle routing problems with time windows", Artificial Intelligence Review, 21. 2, 87-112.
[17]  Molanoori, H., Tavakkoli-Moghaddam, R., Sabouhi, F. and Hajiaghaiee Keshteli, M. (2018) “A two-stage, multi-commodity, step fixed-charge transportation model solving by a simulated annealing algorithm”, Quarterly Journal of Transportation Engineering, 10, 2, 399-413.
[18]   Hasanpur H, Norng A. and Nabizadeh M. (2014) “Robust Project Scheduling Model with Resources Constraint and Solving It by Simulated Annealing Algorithm (Part of the Project Activities of Gas Condensate Refinery in Bandar Abbas)”, Management Research in Iran, 18, 1, 1-24.