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

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

نویسنده

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

چکیده

صورت کلاسیک مسأله «مسیریابی وسیله نقلیه» هزینه حمل‌ونقل را مربوط به کمان­ های شبکه می­ داند، در صورتی که هزینه­ های اولیه (ثابت) بکارگیری وسیله نقلیه و استخدام راننده جزء هزینه ­های اصلی حمل‌ونقل کالا به حساب می ­آیند. در این مقاله، مدلی برای مسأله «مسیریابی وسیله نقلیه» ارائه شده است، که در آن هزینه ­های اولیه بکارگیری وسیله به صورت مجزا و در کنار سایر هزینه ­ها کمینه می­ گردد. این مسأله یک مسأله با «پیچیدگی بالا» به حساب می ­آید، و نمی ­توان آن را در شبکه­ های درون­ شهری بزرگ به صورت دقیق و در مرتبه زمانی چندجمله ­ای حل کرد. بنابراین، برای حل مدل پیشنهادشده از الگوریتم «بهینه ­سازی اجتماع مورچگان» استفاده شده است. الگوریتم ­های قبلی بهینه ­سازی اجتماع مورچگان که برای حل مسیریابی وسیله نقلیه ارائه ­شده ­اند، قادر به در نظر گرفتن هزینه­ های اولیه بکارگیری وسیله به عنوان یک عامل هزینه در تابع هدف نیستند. یکی از نوآوری­ های این مقاله به اصلاح این الگوریتم برای منظور کردن هزینه­ های اولیه بکارگیری وسیله معطوف شده است. برای ارزیابی توان مدل پیشنهادشده، شبکه شهر مشهد با 253 ناحیه ترافیکی و یک دپو در منطقه مرکزی شهر، برای بکارگیری مدل روی شبکه واقعی انتخاب شده است. نتایج نشان می ­دهند که روش حل ارائه شده با سرعت قابل قبول (با زمانی کمتر از 2 ثانیه) به نتایج تقریبی مطلوب همگرا می­ شود. این در حالی است که حل مدل مذکور با استفاده از نرم ­افزارهای تجاری موجود ممکن نیست.

کلیدواژه‌ها


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

Capacitated Vehicle Routing Problem Considering Cost of Vehicle Deployment

نویسنده [English]

  • Mohsen Babaei
Assistant Professor, Civil Engineering Department, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran
چکیده [English]

This paper proposes an integer linear mathematical formulation for Vehicle Routing Problem (VRP), where the capital cost for deploying each vehicle is minimized together with other on-link transportation costs. The model has been formulated as a multi-commodity network flow model with capacity constraints. It is well known that the computational complexity to this type of problems is NP-hard. Thus, the ACO algorithm, which has been known to be a powerful meta-heuristic algorithm for solving VRPs in large networks, has been adapted to solve the problem. Although the ACO algorithm has repeatedly been used to solve the capacitated VRP, it has a drawback that cannot consider the capital cost of each vehicle along with other operational costs of the vehicles (associated with the total distance traveled within a day) in its initial form. More specifically, naturally it assumes that each vehicle returns to the depot if it becomes full or the demand finishes, each met first; this paper seeks to propose an adapted ACO algorithm in which this assumption is released. To assess the capability of the proposed model in large-scale networks, the case study of Mashhad city, consisting of 253 traffic analysis zones and over than 3800 links, has been considered. Results show that the proposed algorithm converges to near-to-optimal solutions within two seconds of cpu time, which is encouraging.

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

  • Vehicle Routing Problem
  • Capacity Constraint
  • Ant Colony Optimization (ACO)
  • Real-world Networks
  • Babaei, M., & Rajabi-Bahaabadi, M. (2019). "School bus routing and scheduling with stochastic time-dependent travel times considering on-time arrival reliability." Computers & Industrial Engineering, Vol. 138, 106125.

 

  • Bell, J. E., & McMullen, P. R. (2004). “Ant colony optimization techniques for the vehicle routing problem.” Advanced Engineering Informatics, Vol. 18, No. 1, PP. 41-48.

 

  • Bullnheimer, B., Hartl, R. F., & Strauss, C. (1997). “Applying the ant system to the vehicle routing problem.” Second Metaheuristics International Conference, MIC’97, Sophia-Antipolis, France.

 

  • Cordeau, J.-F., Laporte, G., Savelsbergh, M. W., & Vigo, D. (2007). “Vehicle routing.” Transportation, handbooks in operations research and management science, Vol. 14, PP. 367-428.

 

  • Dantzig, G. B., & Ramser, J. H. (1959). "The truck dispatching problem." Management science, Vol. 6, No. 1, PP. 80-91.

 

  • Eksioglu, B., Vural, A. V., & Reisman, A. (2009). “The vehicle routing problem: A taxonomic review.” Computers & Industrial Engineering, Vol. 57, No. 4, PP. 1472-1483.

 

  • Elshaer, R., & Awad, H. (2020). “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants.” Computers & Industrial Engineering, 140, 106242.

 

  • Gendreau, M., Hertz, A., & Laporte, G. (1994). “A tabu search heuristic for the vehicle routing problem.” Management science, Vol. 40, No. 10, PP. 1276-1290.

 

  • Gendreau, M., Potvin, J.-Y., Bräumlaysy, O., Hasle, G., & Løkketangen, A. (2008). “Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography.” Springer.

 

  • Golden, B. L., Raghavan, S., & Wasil, E. A. (2008). “The Vehicle Routing Problem: Latest Advances and New Challenges.” Springer.

 

  • Guo, N., Qian, B., Hu, R., Jin, H. P., & Xiang, F. H. (2020). “A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem.” Complexity.

 

  • Huang, S. H., Huang, Y. H., Blazquez, C. A., & Chen, C. Y. (2022). “Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm.” Advanced Engineering Informatics, Vol. 51, 101536.

 

  • Jia, Y. H., Mei, Y., & Zhang, M. (2021). “A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem.” IEEE Transactions on Cybernetics.

 

  • Laporte, G. (1992). “The vehicle routing problem: An overview of exact and approximate algorithms.” European Journal of Operational Research, Vol. 59, No. 3, PP. 345-358.

 

  • Laporte, G., Nobert, Y., & Desrochers, M. (1985). “Optimal routing under capacity and distance restrictions.” Operations research, Vol. 33, No. 5, PP. 1050-1073.

 

  • Leite, M. R., Bernardino, H. S., & Gonçalves, L. B. (2022). “A variable neighborhood descent with ant colony optimization to solve a bilevel problem with station location and vehicle routing.” Applied Intelligence, Vol. 52, No. 7, PP. 7070-7090.

 

  • Marinakis, Y., Marinaki, M., & Dounias, G. (2008). “Honey bees mating optimization algorithm for the vehicle routing problem Nature inspired cooperative strategies for optimization (NICSO 2007) (PP. 139-148): Springer.

 

  • Marinakis, Y., Marinaki, M., & Dounias, G. (2010). “A hybrid particle swarm optimization algorithm for the vehicle routing problem.” Engineering Applications of Artificial Intelligence, Vol. 23, No. 4, PP. 463-472.

 

  • Mutar, M., Burhanuddin, M., Hameed, A., Yusof, N., & Mutashar, H. (2020). “An efficient improvement of ant colony system algorithm for handling capacity vehicle routing problem.” International Journal of Industrial Engineering Computations, Vol. 11, No. 4, PP. 549-564.

 

  • Niu, Y., Yang, Z., Chen, P., & Xiao, J. (2018). "Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost." Journal of cleaner production, Vol. 171, PP. 962-971.

 

  • Osman, I. H. (1993). “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem.” Annals of operations research, Vol. 41, No. 4, PP. 421-451.

 

  • Potvin, J.-Y., Duhamel, C., & Guertin, F. (1996). “A genetic algorithm for vehicle routing with backhauling.” Applied Intelligence, Vol. 6, No. 4, PP. 345-355.

 

  • Rajabi-Bahaabadi, M., Shariat-Mohaymany, A., Babaei, M., & Vigo, D. (2021). "Reliable vehicle routing problem in stochastic networks with correlated travel times." Operational Research, Vol. 21, No. 1, PP. 299-330.

 

  • Taş, D., Dellaert, N., Van Woensel, T., & De Kok, T. (2013). "Vehicle routing problem with stochastic travel times including soft time windows and service costs." Computers & Operations Research, Vol. 40, No. 1, PP. 214-224.

 

  • Vidal, T., Laporte, G., & Matl, P. (2020). “A concise guide to existing and emerging vehicle routing problem variants.” European Journal of Operational Research, Vol. 286, No.2, PP. 401-416.

 

  • Wang, I. L. (2018). "Multicommodity network flows: A survey, Part I: Applications and Formulations." International Journal of Operations Research, Vol. 15, No. 4, PP. 145-153.

 

  • Wu, H., Gao, Y., Wang, W., & Zhang, Z. (2021). “A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows.” Complex & Intelligent Systems.

 

  • Xiang, X., Qiu, J., Xiao, J., & Zhang, X. (2020). “Demand coverage diversity based ant colony optimization for dynamic vehicle routing problems.” Engineering Applications of Artificial Intelligence, Vol. 91, 103582.

 

  • Zhao, P. X., Luo, W. H., & Han, X. (2019). "Time-dependent and bi-objective vehicle routing problem with time windows." Advances in Production Engineering & Management, Vol. 14, No. 2, PP. 201-212.