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

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

1. 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
2. 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
3. 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
4. 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
5. Dataset (2024). < https://l24.im/8KTgI> google scholar
6. 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
7. 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
8. 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

9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. Koulamas, C. (2010). The single-machine total tardiness scheduling problem: Review and extensions. European Journal of Operational Research, 202(1), 1-7. google scholar
17. 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
18. 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
19. 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
20. 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
21. 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
22. 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
23. 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
24. 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
25. 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
26. 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
27. 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
28. Ö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
29. Ö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
30. 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
31. 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
32. Ullrich, C. A. (2013). Integrated machine scheduling and vehicle routing with time windows. European Journal of Operational Research, 227(1), 152-165. google scholar
33. 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
34. 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
35. Zhao, M., & Lu, Y. (2019). A heuristic approach for a real-world electric vehicle routing problem. Algorithms, 12(2), 45. google scholar
36. 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