ارائه و حل مدل مسیریابی وسیله نقلیه در مسافت طولانی با درنظر گرفتن الزامات راننده و فعالیت‌های نگهداری و تعمیرات

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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها


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

A new long haul vehicle routing model considering driver requirements and maintenance activities

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

  • Sahar Anbari 1
  • seyed farid Ghannadpour 2
1 Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
2 Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
چکیده [English]

In this research, a new model for long-haul vehicle routing problem considering driver requirements and preventive maintenance activities is presented. The aim of this study is routing optimizaton with delays in servicing minimization and scheduling by allocating a number of drivers to the routes and paying attention to driving requirements and long-distance drivers' rest and meeting the operational limitations of the transportation system. Due to the NP-Hard nature of the problem, the hybrid meta-heuristic algorithm is proposed to solve the model in large scale. The proposed development algorithm is an adaptive large neighborhood search algorithm that is reinforced using simulated annealing algorithm and optimized routes by considering the limitations of driving requirements and by allocating one or two drivers to the route as well as considering times for preventive maintenance activities to reduce distribution costs.

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

  • Vehicle routing
  • Long haul
  • driver schedule
  • maintenance activity
- قنادپور، سید فرید؛ زندیه، فاطمه (1398) "مسئله مسیریابی وسایل نقلیه مبتنی بر نظریه بازی با هدف کاهش ریسک حمل کالای ارزشمند"، فصلنامه مهندسی حمل و نقل، دوره 11، شماره 1، پاییز، ص. 71-98.
 
- روشنخواه؛ شیدا، سیدابریشمی؛ سید احسان، جوانشیر، حسن (1399) "ارائه مدل مسیریابی وسایل نقلیه امدادی در شبکه‌های کوچک و متوسط"، فصلنامه مهندسی حمل و نقل، دوره 12، شماره 1، پاییز، ص. 139-161.
 
- صالحیان؛ فرهاد، توکلی مقدم؛ رضا، نوروزی، نرگش (1398) "حل مساله مسیریابی وسایط نقلیه با در نظر گرفتن رضایت‌مندی مشتریان و کاهش انرژی مصرفی با الگوریتم زنبور عسل"، فصلنامه مهندسی حمل و نقل، دوره 11، شماره 2، زمستان، ص. 299-311.
 
- Dantzig, George B., and John H. Ramser. (1959). "The truck dispatching problem." Management science Vol. 6, No. 1, pp. 80-91.
 
- Bodin, L., Assad, A., Ball, M. and Golden, B. (1983) "Routing and scheduling of vehicles and crews", Computers and Operations Research, Vol. 10, No. 2, pp. 63-211.
 
- Ghoseiri, K., & Ghannadpour, S. F. (2010). "Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm". Applied Soft Computing, Vol. 10, No. 4, pp. 1096-1107.
 
- López-Santana, E., Akhavan-Tabatabaei, R., Dieulle, L., Labadie, N., & Medaglia, A. L. (2016). "On the combined maintenance and routing optimization problem". Reliability Engineering & System Safety, Vol. 145, pp. 199-214.
 
- Bektaş, Tolga, and Gilbert Laporte. (2011). "The pollution-routing problem." Transportation Research Part B: Methodological, Vol. 45, No. 8, pp. 1232-1250.
 
- Dekker, Rommert, Moritz Fleischmann, Karl Inderfurth, and Luk N. van Wassenhove, eds. Reverse logistics: quantitative models for closed-loop supply chains. Springer Science & Business Media, 2013.
 
- Naderipour, Mansoureh, and Mahdi Alinaghian. (2016). "Measurement, evaluation and minimization of CO2, NOx, and CO emissions in the open time dependent vehicle routing problem." Measurement, Vol. 90, pp. 443-452.
 
- Demir, Emrah, Tolga Bektaş, and Gilbert Laporte. (2014). "A review of recent research on green road freight transportation." European Journal of Operational Research, Vol. 237, No. 3, pp. 775-793.
 
- Çatay, Bülent. (2010). "A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery." Expert Systems with Applications, Vol. 37, No. 10, pp. 6809-6817.
 
- Wassan, Niaz A., and Gábor Nagy. (2014). "Vehicle routing problem with deliveries and pickups: Modelling issues and meta-heuristics solution approaches." International Journal of Transportation, Vol. 2, No. 1, pp. 95-110.
 
- Royo, B., Sicilia, J. A., Oliveros, M. J., & Larrodé, E. (2015). "Solving a long-distance routing problem using ant colony optimization". Appl. Math, Vol. 9, No. 2, pp. 415-421.
 
- Xu, H., Chen, Z. L., Rajagopal, S., & Arunapuram, S. (2003). "Solving a practical pickup and delivery problem". Transportation science, vol. 37, No. 3, pp.347-364
 
- Wang, Hsiao-Fan, and Ying-Yen Chen. (2012). "A genetic algorithm for the simultaneous delivery and pickup problems with time window." Computers & Industrial Engineering, Vol.62, No. 1, pp. 84-95.
 
- Goel, A., & Kok, L. (2012). "Truck driver scheduling in the United States". Transportation science, Vol. 46, No. 3, pp. 317-326.
 
- Demir, Emrah, Tolga Bektaş, and Gilbert Laporte. (2012). "An adaptive large neighborhood search heuristic for the pollution-routing problem." European Journal of Operational Research,Vol. 223, No. 2, pp. 346-359.
 
- Koç, C., Jabali, O., & Laporte, G. (2018). "Long-haul vehicle routing and scheduling with idling options". Journal of the Operational Research Society, Vol. 69, No. 2, pp. 235-246.
 
- Medina, J., Hewitt, M., Lehuédé, F., & Péton, O. (2019). "Integrating long-haul and local transportation planning: The Service Network Design and Routing Problem". EURO Journal on Transportation and Logistics, vol. 8, No. 2, pp. 119-145.
 
- Goel, A., Vidal, T., & Kok, A. L. (2020). "To team up or not–Single versus team driving in European road freight transport". Flexible services and manufacturing journal, DOI: https://doi.org/10.1007/s10696-020-09398-0.
 
- Heggen, H., Molenbruch, Y., Caris, A., & Braekers, K. (2019). "Intermodal Container Routing: Integrating Long-Haul Routing and Local Drayage Decisions". Sustainability, Vol. 11, No. 6, pp. 1634.
 
- Dai, L., Stålhane, M., & Utne, I. B. (2015)." Routing and scheduling of maintenance fleet for offshore wind farms". Wind Engineering, Vol. 39, No. 1, pp. 15–30.
 
- Zamorano.E, Stollez.R. (2017). "Brach and Price Approaches for the Multi-period Technician Routing and Scheduling Problem". European Journal of operational Research, Vol. 257, pp. 55-68.
 
- Rashidnejad, M., Ebrahimnejad, S., & Safari, J. (2018). "A bi-objective model of preventive maintenance planning in distributed systems considering vehicle routing problem". Computers & Industrial Engineering, Vol. 120, pp. 360-381.
 
- Goyal, S. K., & Gunasekaran, A. (1992). "Determining economic maintenance frequency of a transport fleet". International Journal of Systems Science, Vol. 23, No. 4, pp. 655-659.
 
- Jia-Yen Huang and Ming-Jong Yao, (2008). "On the coordination of maintenance scheduling for transportation fleets of many branches of a logistic service provider". Computers and Mathematics with Applications, Vol. 56, pp. 1303–1313.
 
- Bouvard, K., Artus, S., Bérenguer, C. and Cocquempot, V. (2011). "Condition-based dynamic maintenance operations planning and grouping. Application to commercial heavy vehicles". Reliability Engineering and System Safety, Vol. 96, pp. 601–610.
 
- Eduyn López-Santana, RahaAkhavan-Tabatabaei, Laurence Dieulle, Nacima Labadie and AndrésL. Medaglia, (2016). "On the combined maintenance and routing optimization problem". Reliability Engineering and System Safety Vol. 145, pp. 199–214.
 
- Chandra Ade Irawan, Djamila Ouelhadj, Dylan Jones, Magnus Stålhane and Iver Bakken Sperstad, (2016). "Optimisation of maintenance routing and scheduling for offshore wind farms". European Journal of Operational Research Vol. 256, pp. 76-89.
 
- Dhahri, Amine, Kamel Zidi and Khaled Ghedira. (2015). "A variable neighborhood search for the vehicle routing problem with time windows and preventive maintenance activities". Electronic Notes in Discrete Mathematics, Vol. 47, pp. 229-236.
 
- Dhahri, Amine, Anis Mjirda, Kamel Zidi and Khaled Ghedira. (2016). "A VNS-based Heuristic for Solving the Vehicle Routing Problem with Time Windows and Vehicle Preventive Maintenance Constraints." Procedia Computer Science, Vol. 80, pp. 1212-1222.
 
- Troudi A., Dellagi S., Addouche S. An optimal maintenance policy for transport vehicles in a supply chain under infrastructure/environment constraints. 45th International Conference on Computers & Industrial Engineering (CIE45), Metz, France, 28-30 October 2015.
 
- Jbili, S., Chelbi, A., Radhoui, M., & Kessentini, M. (2018). "Integrated strategy of vehicle routing and maintenance". Reliability Engineering & System Safety, Vol. 170, pp.202-214.
 
- Santosa, B., & Lathifah, A. (2015). "A viral system to solve generalized orienteering problem". Procedia Computer Science, Vol. 72, pp.337-344.
 
- Ropke, Stefan, and David Pisinger. (2006). "A unified heuristic for a large class of vehicle routing problems with backhauls." European Journal of Operational Research, Vol. 171, No. 3, pp. 750-775.
 
- Hemmelmayr, Vera C., Jean-François Cordeau, and Teodor Gabriel Crainic. (2012). "An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics." Computers & operations research, Vol. 39, No. 12, pp. 3215-3228.
 
- Clarke, Geoff, and John W. Wright. (1964). "Scheduling of vehicles from a central depot to a number of delivery points." Operations research, Vol. 12, No. 4, pp. 568-581.
 
- Pisinger, David, and Stefan Ropke. (2007). "A general heuristic for vehicle routing problems." Computers & operations research, Vol. 34, No. 8, pp.2403-2435.
 
- Shaw, Paul. "Using constraint programming and local search methods to solve vehicle routing problems." In International conference on principles and practice of constraint programming, pp. 417-431. Springer, Berlin, Heidelberg, 1998.
 
- Solomon, M. M. (1987). "Algorithms for the vehicle routing and scheduling problems with time window constraints". Operations research, Vol.35, No.2. pp.254–265.
https://www.sintef.no/projectweb/top/vrptw/solomon-benchmark/
 
- Chen, B., Qu, R., Bai, R., & Ishibuchi, H. (2016). "A variable neighborhood search algorithm with compound neighborhoods for VRPTW". RIRO Operations Research, Vol. 54, No. 5, pp.1467-1494.
 
- SINTEF (2015). Best known solution values for Solomon benchmark. http:// www.sintef.no/Projectweb/TOP/VRPTW/Solomonbenchmark/ 100-customers/
 
- Konstantakopoulos, G. D., Gayialis, S. P., Kechagias, E. P., Papadopoulos, G. A., & Tatsiopoulos, I. P. (2020). "A Multiobjective Large neighborhood search metaheuristic for the vehicle routing problem with time windows". Algorithms, Vol. 13, No. 10, pp.243.
 
- Chen, X., Zhou, Y., Tang, Z., & Luo, Q. (2017). "A hybrid algorithm combining glowworm swarm optimization and complete 2-opt algorithm for spherical travelling salesman problems". Applied Soft Computing, Vol.58, pp.104-114.
 
- Küçükoğlu, İ., & Öztürk, N. (2015). "An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows". Computers & Industrial Engineering, Vol. 86, pp.60-68.
 
- Ghannadpour, S. F., & Zandiyeh, F. (2020). "A new game-theoretical multi-objective evolutionary approach for cash-in-transit vehicle routing problem with time windows (A Real life Case)". Applied Soft Computing, Vol. 93, pp. 106378.
 
- Rochat, Y., & Taillard, É. D. (1995). "Probabilistic diversification and intensification in local search for vehicle routing". Journal of heuristics, Vol. 1, No. 1, pp. 147-167.
 
- Cook, W., & Rich, J. L. (1999). "A parallel cutting-plane algorithm for the vehicle routing problem with time windows". DOI: https://hdl.handle.net/1911/101910
 
- Desrochers, M., Desrosiers, J., & Solomon, M. (1992). "A new optimization algorithm for the vehicle routing problem with time windows". Operations research, Vol. 40, No. 2, pp.342-354.
 
- Tan, K. C., Chew, Y. H., & Lee, L. H. (2006). "A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows". Computational Optimization and Applications, Vol. 34, No. 1, pp.115.
 
- Kallehauge, B., Larsen, J., & Madsen, O. B. (2006). "Lagrangian duality applied to the vehicle routing problem with time windows". Computers & Operations Research, Vol. 33, No. 5, pp.1464-1487.
 
- Chiang, W. C., & Russell, R. A. (1997). "A reactive tabu search metaheuristic for the vehicle routing problem with time windows". INFORMS Journal on computing, Vol. 9, No. 4, pp. 417-430.
 
- Alvarenga, G. B., Mateus, G. R., & De Tomi, G. (2007). "A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows". Computers & Operations Research, Vol. 34, No. 6, pp.1561-1584.
 
- Zhang, D., Cai, S., Ye, F., Si, Y. W., & Nguyen, T. T. (2017). "A hybrid algorithm for a vehicle routing problem with realistic constraints". Information Sciences, Vol. 394, pp. 167-182.
 
- Qi, Y., Hou, Z., Li, H., Huang, J., & Li, X. (2015). "A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows". Computers & Operations Research, Vol. 62, pp. 61-77.
 
- Ombuki, B., Ross, B. J., & Hanshar, F. (2006). "Multi-objective genetic algorithms for vehicle routing problem with time windows". Applied Intelligence, Vol. 24, No. 1, pp. 17-30.
 
- Thangiah, S. R., Osman, I. H., & Sun, T. (1994). "Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows". Computer Science Department, Slippery Rock University, Technical Report SRU CpSc-TR-94-27, 69.
 
- Kohl, N., Desrosiers, J., Madsen, O. B., Solomon, M. M., & Soumis, F. (1999). "2-path cuts for the vehicle routing problem with time windows". Transportation Science, Vol. 33, No. 1, pp.101-116.
 
- Mayerle, S. F., Chiroli, D.M.G., Figueiredo, J.N., Rodrigues, H.F. (2020). "The long-haul full-load vehicle routing and truck driver scheduling problem with intermediate stops: An economic impact evaluation of Brazilian policy". Transportation Research Part A: Plicy and Practice, Vol. 140, pp. 36-51.
 
- Haftor, D.M., Climent, R.C. (2021). "CO2 reduction through digital transformation in long-haul transportation: institutional entrepreneurship to unlock product service system innovation". Industrial Marketing Management, Vol. 94, pp. 115-127.
 
- Wolfinger, D., Tricoire, F., Doerner, K.F. (2019). "A metaheuristic for a multimodal long-haul routing problem". EURO Journal on Transportation and Logistics, Vol. 8, No. 4, pp.397-433.