Mathematical Modelling Approaches for Integrated Single Machine Scheduling and Electric Vehicle Routing Problem

Year 2024, , 48 - 59, 17.05.2024

İclal Bağcı , Hande Öztop , Zeynel Abidin Çil

https://doi.org/10.26650/JTL.2024.1414907

Abstract

In recent years, increasingCO2 emissions and resource utilization has adversely affected the environment. Sustainability efforts have been initiated to decrease these effects, including environmentally friendly electric vehicles in vehicle fleets used for transportation. The electric vehicle routing problem (EVRP) has emerged in the literature, and numerous studies have been conducted, considering specific constraints related to electric vehicles. Due to various charging feature constraints, EVRP diverges from the classical vehicle routing problem (VRP) and becomes more complex. In addition to the load capacity constraints of classical VRP, electric vehicles must deliver products to customers via an optimal vehicle route while considering battery capacity limitations. This study addresses the integrated single-machine scheduling and electric vehicle routing problem. After scheduling and processing customer product requests on a single machine, electric vehicle routes must be created to deliver these products to customers. To meet customer expectations, the objective function of the problem aims to minimize the costs associated with customer product delivery delays. Two mathematical models, i.e., mixed-integer linear programming (MILP) and constraint programming (CP) models, are presented to solve this problem. The results and performances of these models are compared on a set of instances. Numerical results indicate that the CP model has superior performance than the MILP model for the problem.

Keywords

Electric vehicle routing, single machine scheduling, mixed-integer linear programming, constraint programming, integrated scheduling and routing

References

• Berghman, L., Kergosien, Y., & Billaut, J. C. (2023). A review on integrated scheduling and outbound vehicle routing problems. European Journal of Operational Research. google scholar
• Booth, K. E., & Beck, J. C. (2019). A constraint programming approach to electric vehicle routing with time windows. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4-7, 2019, Proceedings 16 (pp. 129-145). Springer International Publishing. google scholar
• Bruglieri, M., Pezzella, F., Pisacane, O., & Suraci, S. (2015). A variable neighborhood search branching for the electric vehicle routing problem with time windows. Electronic Notes in Discrete Mathematics, 47, 221-228. google scholar
• Chen, H. K., Hsueh, C. F., & Chang, M. S. (2009). Production scheduling and vehicle routing with time windows for perishable food products. Computers & operations research, 36(7), 2311-2319. google scholar
• Dataset (2024). < https://l24.im/8KTgI> google scholar
• Devapriya, P., Ferrell, W., & Geismar, N. (2017). Integrated production and distribution scheduling with a perishable product. European Journal of Operational Research, 259(3), 906-916. google scholar
• Farahani, P., Grunow, M., & Günther, H. O. (2012). Integrated production and distribution planning for perishable food products. Flexible services and manufacturing journal, 24, 28-51. google scholar
• Felipe, Â., Ortuno, M. T., Righini, G., & Tirado, G. (2014). A heuristic approach for the green vehicle routing problem withmultiple technologies and partial recharges. Transportation Research Part E: Logistics and Transportation Review, 71, 111-128. google scholar
• Fu, L. L., Aloulou, M. A., & Triki, C. (2017). Integrated production scheduling and vehicle routing problem with job splitting and delivery time windows. International Journal of Production Research, 55(20), 5942-5957. google scholar
• Goeke, D. (2019). Granular tabu search for the pickup and delivery problem with time windows and electric vehicles. European Journal of Operational Research, 278(3), 821-836. google scholar
• Ha, M. H., Nguyen, T. D., Duy, T. N., Pham, H. G., Do, T., & Rousseau, L. M. (2020). A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints. Computers & Operations Research, 124, 105085. google scholar
• He, P., Li, K., & Kumar, P. R. (2022). An enhanced branch-and-price algorithm for the integrated production and transportation scheduling problem. International Journal of Production Research, 60(6), 1874-1889. google scholar
• Hojabri, H., Gendreau, M., Potvin, J. Y., & Rousseau, L. M. (2018). Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints. Computers & Operations Research, 92, 87-97. google scholar
• Jamili, N., Ranjbar, M., & Salari, M. (2016). A bi-objective model for integrated scheduling of production and distribution in a supply chain with order release date restrictions. Journal of Manufacturing Systems, 40, 105-118. google scholar
• Keskin, M., & Çatay, B. (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation research part C: emerging technologies, 65, 111-127. google scholar
• Koulamas, C. (2010). The single-machine total tardiness scheduling problem: Review and extensions. European Journal of Operational Research, 202(1), 1-7. google scholar
• Küçükoğlu, İ., & Öztürk, N. (2016). Heterojen Filoya Sahip Elektrikli Araçların Rota Optimizasyonu. Celal Bayar Üniversitesi Fen Bilimleri Dergisi, 12(3), 525-534. google scholar
• Kucukoglu, I., Dewil, R., & Cattrysse, D. (2021). The electric vehicle routing problem and its variations: A literature review. Computers & Industrial Engineering, 161, 107650. google scholar
• Lam, E., Desaulniers, G., & Stuckey, P. J. (2022). Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging, and capacitated recharging stations. Computers & Operations Research, 145, 105870. google scholar
• Li, K., Zhou, C., Leung, J. Y., & Ma, Y. (2016). Integrated production and delivery with single machine and multiple vehicles. Expert Systems with Applications, 57, 12-20. google scholar
• Liao, C. J., & Juan, H. C. (2007). An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Computers & operations research, 34(7), 1899-1909. google scholar
• Long, J., Pardalos, P. M., & Li, C. (2022). Level-based multi-objective particle swarm optimizer for integrated production scheduling and vehicle routing decision with inventory holding, delivery, and tardiness costs. International Journal of Production Research, 60(11), 3319-3338. google scholar
• Low, C., Chang, C. M., Li, R. K., & Huang, C. L. (2014). Coordination of production scheduling and delivery problems with heterogeneous fleet. International Journal of Production Economics, 153, 139-148. google scholar
• Luo, X., & Chu, F. (2006). A branch and bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing total tardiness. Applied Mathematics and Computation, 183(1), 575-588. google scholar
• Mohammadi, S., Al-e-Hashem, S. M., & Rekik, Y. (2020). An integrated production scheduling and delivery route planning with multi-purpose machines: A case study from a furniture manufacturing company. International Journal of Production Economics, 219, 347-359. google scholar
• Moons, S., Ramaekers, K., Caris, A., & Arda, Y. (2017). Integrating production scheduling and vehicle routing decisions at the operational decision level: a review and discussion. Computers & Industrial Engineering, 104, 224-245. google scholar
• Ozcelik, F., Ertem, M., & Saraç, T. (2022). A stochastic approach for the single-machine scheduling problem to minimize total expected cost with client-dependent tardiness costs. Engineering Optimization, 54(7), 1178-1192. google scholar
• Öztop, H. (2022, October). A Constraint Programming Model for the Open Vehicle Routing Problem with Heterogeneous Vehicle Fleet. In The International Symposium for Production Research (pp. 345-356). Cham: Springer International Publishing. google scholar
• Öztop, H., Kizilay, D., & Çil, Z. A. (2021). Mathematical models for the periodic vehicle routing problem with time windows and time spread constraints. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 11(1), 10-23. google scholar
• Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(4), 500-520. google scholar
• Tanaka, S., & Araki, M. (2013). An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Computers & Operations Research, 40(1), 344-352. google scholar
• Ullrich, C. A. (2013). Integrated machine scheduling and vehicle routing with time windows. European Journal of Operational Research, 227(1), 152-165. google scholar
• Wang, J., Yao, S., Sheng, J., & Yang, H. (2019). Minimizing total carbon emissions in an integrated machine scheduling and vehicle routing problem. Journal of Cleaner Production, 229, 1004-1017. google scholar
• Yüksel, D., Kizilay, D., Öztop, H., & Özkan, S. (2021). Mathematical models for milk dispatching problem. Journal of Transportation and Logistics, 6(2), 217-235. google scholar
• Zhao, M., & Lu, Y. (2019). A heuristic approach for a real-world electric vehicle routing problem. Algorithms, 12(2), 45. google scholar
• Zhao, Z., Li, X., & Zhou, X. (2020). Distribution route optimization for electric vehicles in urban cold chain logistics for fresh products under time-varying traffic conditions. Mathematical Problems in Engineering, 2020, 1-17. google scholar