Optimization of the Low-Carbon Vehicle Routing Problem with Soft Time Windows: A Hybrid Genetic Algorithm HGA-SIH_Vol. 4 No. 3 (JES 2026)_Journal of Engineering System (ISSN: 2959-0604)

Home > Journal of Engineering System (ISSN: 2959-0604) > Vol. 4 No. 3 (JES 2026) >

Optimization of the Low-Carbon Vehicle Routing Problem with Soft Time Windows: A Hybrid Genetic Algorithm HGA-SIH

Download PDF

DOI: https://doi.org/10.62517/jes.202602322

Author(s)

Zhilin Zeng

Affiliation(s)

International College, Hunan University of Arts and Science, Changde, China

Abstract

To address the optimization challenge arising from carbon emission constraints and elastic time-sensitive demand in urban last-mile delivery, this paper studies the low-carbon vehicle routing problem with soft time windows (LCVRPTW). A mixed-integer linear programming model is formulated to minimize total system cost, integrating vehicle fixed activation costs, load-dependent fuel consumption and carbon emission costs, and soft time window penalty costs. The problem is proven to be strongly NP-hard. To overcome the limitations of standard genetic algorithms in medium- and large-scale scenarios, a hybrid genetic algorithm (HGA-SIH) is proposed, integrating the sequential insertion heuristic (SIH) with the simulated annealing Metropolis criterion. This paper derives the SIH marginal insertion cost decomposition formula, provides a set-theoretic description of the OX crossover operator, elucidates the statistical mechanics origin of the Metropolis criterion, and establishes temperature schedule convergence conditions. Based on the Markov chain framework, HGA-SIH is proven to converge to the global optimum with probability 1. Time complexity analysis shows per-generation computational complexity of O(N·n·K).

Keywords

Low-Carbon Vehicle Routing Problem; Soft Time Windows; Hybrid Genetic Algorithm; Sequential Insertion Heuristic; Simulated Annealing; Convergence Analysis

References

[1]Yin, N. (2023). Multiobjective Optimization for Vehicle Routing Optimization Problem in Low-Carbon Intelligent Transportation. IEEE Transactions on Intelligent Transportation Systems, 24(11), 13161-13170. [2]Liu, Y., Yu, Y., Baldacci, R., Tang, J., & Sun, W. (2025). Optimizing carbon emissions in green logistics for time-dependent routing. Transportation Research Part B-Methodological, 192, 103155. [3]Boz, E., Calik, A., & Sahin, Y. (2024). Solution approaches for the green vehicle routing problem with time window and simultaneous pickup and delivery. Journal of the Faculty of Engineering and Architecture of Gazi University, 39(2), 757-770. [4]Gao, J., Zheng, X., Gao, F., Tong, X., & Han, Q. (2022). Heterogeneous Multitype Fleet Green Vehicle Path Planning of Automated Guided Vehicle with Time Windows in Flexible Manufacturing System. Machines, 10(3), 197. [5]Wang, D. L., Ding, A., Chen, G. L., & Zhang, L. (2023). A combined genetic algorithm and A search algorithm for the electric vehicle routing problem with time windows. Advances in Production Engineering & Management, 18(4), 403-416. [6]Lai, D., Costa, Y., Demir, E., Florio, A. M., & Van Woensel, T. (2024). The pollution-routing problem with speed optimization and uneven topography. Computers & Operations Research, 164, 106557. [7]Li, W., Sun, Q., Guo, S., & Ma, H. (2025). Vehicle route and speed optimization with carbon emission control in fragile goods transportation. International Journal of General Systems. [8]Zhu, J. (2022). Solving Capacitated Vehicle Routing Problem by an Improved Genetic Algorithm with Fuzzy C-Means Clustering. Scientific Programming, 2022, 8514660. [9]Zhang, W., Li, H., Yang, W., Zhang, G., & Gen, M. (2022). Hybrid multiobjective evolutionary algorithm considering combination timing for multi-type vehicle routing problem with time windows. Computers & Industrial Engineering, 171. [10]Zhou, L., Zhang, H., & Fu, J. (2025). Green vehicle routing optimization based on dynamic constraint selection co-evolutionary algorithm. Scientific Reports, 15(1), 17688. [11]Jie, K.-W., Liu, S.-Y., & Sun, X.-J. (2022). A hybrid algorithm for time-dependent vehicle routing problem with soft time windows and stochastic factors. Engineering Applications of Artificial Intelligence, 109, 104606. [12]He Meiling, Yang Mei, Wu Xiaohui. Research on the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Soft Time Windows from a Low-Carbon Perspective. Journal of Jiangsu University (Natural Science Edition), 2026, 47(3): 283–291. [13]Ge Xianlong, Zhu Ziqiang. Electric Vehicle Routing Optimization Problem with Soft Time Windows. Industrial Engineering and Management, 2019, 24(4): 96–104+112. [14]Xie Yong, Hu Rong, Qian Bin, Chen Shaofeng, Zhang Guilian, Zhang Xiaodi. An Improved Population-Based Incremental Learning Algorithm for Solving the Vehicle Routing Optimization Problem with Soft Time Windows. Journal of Nanjing University of Science and Technology, 2016, 40(1): 110–116. [15]Yang Jin, Ma Liang. Application of Bee Colony Optimization Algorithm in Vehicle Routing Problem with Soft Time Windows. Forecasting, 2010, 29(6): 67–70+61. [16]Ren, T., Luo, T., Jia, B., Yang, B., Wang, L., & Xing, L. (2023). Improved ant colony optimization for the vehicle routing problem with split pickup and split delivery. Swarm and Evolutionary Computation, 77, 101228. [17]Fang, W., Guan, Z., Yue, L., Zhang, Z., Wang, H., & Meng, L. (2022). Heterogeneous-vehicle distribution logistics planning for assembly line station materials with multiple time windows and multiple visits. International Journal of Industrial Engineering Computations, 13(4), 473-490. [18]Hien, V. Q., Dao, T. C., & Binh, H. T. T. (2023). A greedy search based evolutionary algorithm for electric vehicle routing problem. Applied Intelligence, 53(3), 2908-2922. [19]Liu, L., Gu, R., Huo, J., & Zhou, Y. (2023). Origin-Oriented Shuffled Frog Leaping Vehicle Routing Multiobjective Optimization Algorithm. Journal of Database Management, 34(3). [20]Dong, Y., Wang, S., & Liu, X. (2025). Flow Shop Scheduling with Limited Buffers by an Improved Discrete Pathfinder Algorithm with Multi-Neighborhood Local Search. Processes, 13(8), 2325. [21]Niu, Y., Yu, F., Yao, H., & Yang, Y. (2022). Multi-equipment coordinated scheduling strategy of U-shaped automated container terminal considering energy consumption. Computers & Industrial Engineering, 174, 108804. [22]Zeng, Z., Ding, J. (2025). Design of an Intelligent Courier Vehicle System Based on STM32 and Free RTOS. Electronic Making, 2025, 33(15): 7-12. [23]Zhu, Y., Li, C., & Lee, K. Y. (2022). The NR-EGA for the EVRP Problem with the Electric Energy Consumption Model. Energies, 15(10), 3681. [24]Yue, B., Ma, J., Shi, J., & Yang, J. (2024). A Deep Reinforcement Learning-Based Adaptive Search for Solving Time-Dependent Green Vehicle Routing Problem. Ieee Access, 12, 33400-33419.