{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T23:21:02Z","timestamp":1782256862336,"version":"3.54.5"},"reference-count":44,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T00:00:00Z","timestamp":1755820800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["72171032"],"award-info":[{"award-number":["72171032"]}]},{"name":"National Natural Science Foundation of China","award":["72172023"],"award-info":[{"award-number":["72172023"]}]},{"name":"National Natural Science Foundation of China","award":["21YJA630048"],"award-info":[{"award-number":["21YJA630048"]}]},{"name":"National Natural Science Foundation of China","award":["21YJAZH070"],"award-info":[{"award-number":["21YJAZH070"]}]},{"name":"Humanities and Social Sciences Fund of Chinese Ministry of Education","award":["72171032"],"award-info":[{"award-number":["72171032"]}]},{"name":"Humanities and Social Sciences Fund of Chinese Ministry of Education","award":["72172023"],"award-info":[{"award-number":["72172023"]}]},{"name":"Humanities and Social Sciences Fund of Chinese Ministry of Education","award":["21YJA630048"],"award-info":[{"award-number":["21YJA630048"]}]},{"name":"Humanities and Social Sciences Fund of Chinese Ministry of Education","award":["21YJAZH070"],"award-info":[{"award-number":["21YJAZH070"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Urban logistics face complexity due to traffic congestion, fleet heterogeneity, warehouse constraints, and driver workload balancing, especially in the Heterogeneous Multi-Trip Vehicle Routing Problem with Time Windows and Time-Varying Networks (HMTVRPTW-TVN). We develop a mixed-integer linear programming (MILP) model with dual-peak time discretization and exact linearization for heterogeneous fleet coordination. Given the NP-hard nature, we propose a Hyper-Heuristic based on Cumulative Reward Q-Learning (HHCRQL), integrating reinforcement learning with heuristic operators in a Markov Decision Process (MDP). The algorithm dynamically selects operators using a four-dimensional state space and a cumulative reward function combining timestep and fitness. Experiments show that, for small instances, HHCRQL achieves solutions within 3% of Gurobi\u2019s optimum when customer nodes exceed 15, outperforming Large Neighborhood Search (LNS) and LNS with Simulated Annealing (LNSSA) with stable, shorter runtime. For large-scale instances, HHCRQL reduces gaps by up to 9.17% versus Iterated Local Search (ILS), 6.74% versus LNS, and 5.95% versus LNSSA, while maintaining relatively stable runtime. Real-world validation using Shanghai logistics data reduces waiting times by 35.36% and total transportation times by 24.68%, confirming HHCRQL\u2019s effectiveness, robustness, and scalability.<\/jats:p>","DOI":"10.3390\/a18090536","type":"journal-article","created":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:47:49Z","timestamp":1755870469000},"page":"536","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Reinforcement Learning Hyper-Heuristic with Cumulative Rewards for Dual-Peak Time-Varying Network Optimization in Heterogeneous Multi-Trip Vehicle Routing"],"prefix":"10.3390","volume":"18","author":[{"given":"Xiaochuan","family":"Wang","sequence":"first","affiliation":[{"name":"College of Transportation Engineering, Dalian Maritime University, Dalian 116026, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Na","family":"Li","sequence":"additional","affiliation":[{"name":"College of Transportation Engineering, Dalian Maritime University, Dalian 116026, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xingchen","family":"Jin","sequence":"additional","affiliation":[{"name":"College of Transportation Engineering, Dalian Maritime University, Dalian 116026, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,8,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"106375","DOI":"10.1016\/j.cie.2020.106375","article-title":"Dynamic coordinated scheduling for supply chain under uncertain production time to empower smart production for Industry 3.5","volume":"142","author":"Jamrus","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_2","first-page":"2232044","article-title":"Quality of service measurement for electric vehicle fast charging stations: A new evaluation model under uncertainties","volume":"21","author":"Zhao","year":"2025","journal-title":"Transp. A Transp. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"108597","DOI":"10.1016\/j.cie.2022.108597","article-title":"Modeling and solving a multi-trip multi-distribution center vehicle routing problem with lower-bound capacity constraints","volume":"172","author":"Nguyen","year":"2022","journal-title":"Comput. Ind. Eng."},{"key":"ref_4","first-page":"251","article-title":"Improved approximations for capacitated vehicle routing with unsplittable client demands","volume":"Volume 13265","author":"Friggstad","year":"2020","journal-title":"Integer Programming and Combinatorial Optimization, Proceedings of the 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, 27\u201329 June 2022"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/j.ins.2022.06.056","article-title":"QMOEA: A Q-learning-based multiobjective evolutionary algorithm for solving time-dependent green vehicle routing problems with time windows","volume":"608","author":"Qi","year":"2022","journal-title":"Inf. Sci."},{"key":"ref_6","first-page":"1","article-title":"A learning and searching integration approach for same-day delivery problem with heterogeneous fleets considering uncertainty","volume":"44","author":"Li","year":"2024","journal-title":"Transp. A Transp. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"106714","DOI":"10.1016\/j.cor.2024.106714","article-title":"Estimating optimal split delivery vehicle routing problem solution values","volume":"168","author":"Kou","year":"2024","journal-title":"Comput. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1016\/j.ejor.2016.04.065","article-title":"Large neighborhood search for multi-trip vehicle routing","volume":"255","author":"Arda","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"100139","DOI":"10.1016\/j.dajour.2022.100139","article-title":"A genetic algorithm model for optimizing vehicle routing problems with perishable products under time-window and quality requirements","volume":"5","author":"Agrawal","year":"2022","journal-title":"Decis. Anal. J."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.ins.2019.03.070","article-title":"A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows","volume":"490","author":"Zhang","year":"2019","journal-title":"Inf. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/j.aej.2022.09.008","article-title":"An improved tabu search algorithm for solving heterogeneous fixed fleet open vehicle routing problem with time windows","volume":"64","author":"Ahmed","year":"2023","journal-title":"Alex. Eng. J."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"106293","DOI":"10.1016\/j.cor.2023.106293","article-title":"An iterated local search algorithm for latency vehicle routing problems with multiple depots","volume":"158","author":"Escobar","year":"2023","journal-title":"Comput. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"120009","DOI":"10.1016\/j.eswa.2023.120009","article-title":"Application of improved multi-objective particle swarm optimization algorithm to solve disruption for the two-stage vehicle routing problem with time windows","volume":"225","author":"Kuo","year":"2023","journal-title":"Expert Syst. Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"102831","DOI":"10.1016\/j.trb.2023.102831","article-title":"An exact algorithm for the pickup and delivery problem with crowdsourced bids and transshipment","volume":"177","author":"Su","year":"2023","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1016\/j.trb.2023.01.002","article-title":"An exact algorithm for the two-echelon vehicle routing problem with drones","volume":"168","author":"Zhou","year":"2023","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.ejor.2020.09.022","article-title":"Multi-trip time-dependent vehicle routing problem with time windows","volume":"291","author":"Pan","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","first-page":"501","article-title":"The location-routing problem with multi-compartment and multi-trip: Formulation and heuristic approaches","volume":"16","author":"Moon","year":"2020","journal-title":"Transp. A Transp. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"111482","DOI":"10.1016\/j.asoc.2024.111482","article-title":"An adaptive large neighborhood search for the multi-vehicle profitable tour problem with flexible compartments and mandatory customers","volume":"156","author":"Yu","year":"2024","journal-title":"Appl. Soft Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"103138","DOI":"10.1016\/j.tre.2023.103138","article-title":"An exact algorithm for the multi-trip container drayage problem with truck platooning","volume":"175","author":"You","year":"2023","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"106571","DOI":"10.1016\/j.cie.2020.106571","article-title":"Hybrid differential evolution algorithm and genetic operator for multi-trip vehicle routing problem with backhauls and heterogeneous fleet in the beverage logistics industry","volume":"146","author":"Sethanan","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"106399","DOI":"10.1016\/j.cie.2020.106399","article-title":"New compact integer programming formulations for the multi-trip vehicle routing problem with time windows","volume":"144","author":"Neira","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"107113","DOI":"10.1016\/j.engappai.2023.107113","article-title":"A double-adaptive general variable neighborhood search for an unmanned electric vehicle routing and scheduling problem in green manufacturing systems","volume":"126","author":"Liu","year":"2023","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"107252","DOI":"10.1016\/j.cie.2021.107252","article-title":"A novel reinforcement learning-based hyper-heuristic for heterogeneous vehicle routing problem","volume":"156","author":"Qin","year":"2021","journal-title":"Comput. Ind. Eng."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"107695","DOI":"10.1016\/j.cie.2021.107695","article-title":"Integrated scheduling optimization of U-shaped automated container terminal under loading and unloading mode","volume":"162","author":"Xu","year":"2021","journal-title":"Comput. Ind. Eng."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"106817","DOI":"10.1016\/j.cor.2024.106817","article-title":"Tri-objective lot-streaming scheduling optimization for hybrid flow shops with uncertainties in machine breakdowns and job arrivals using an enhanced genetic programming hyper-heuristic","volume":"172","author":"Duan","year":"2024","journal-title":"Comput. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"121050","DOI":"10.1016\/j.eswa.2023.121050","article-title":"A Q-learning-based hyper-heuristic evolutionary algorithm for the distributed flexible job-shop scheduling problem with crane transportation","volume":"234","author":"Zhang","year":"2023","journal-title":"Expert Syst. Appl."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"123854","DOI":"10.1016\/j.eswa.2024.123854","article-title":"A multi-surrogate genetic programming hyper-heuristic algorithm for the manufacturing project scheduling problem with setup times under dynamic and interference environments","volume":"250","author":"Li","year":"2024","journal-title":"Expert Syst. Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"13572","DOI":"10.1109\/TCYB.2021.3111082","article-title":"Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem","volume":"52","author":"Li","year":"2022","journal-title":"IEEE Trans. Cybern."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2034","DOI":"10.1049\/itr2.12394","article-title":"Coordinated multi-agent hierarchical deep reinforcement learning to solve multi-trip vehicle routing problems with soft time windows","volume":"17","author":"Zhang","year":"2023","journal-title":"IET Intell. Transp. Syst."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"105954","DOI":"10.1016\/j.engappai.2023.105954","article-title":"Green location routing problem with flexible multi-compartment for source-separated waste: A Q-learning and multi-strategy-based hyper-heuristic algorithm","volume":"121","author":"Shang","year":"2023","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"111138","DOI":"10.1016\/j.cie.2025.111138","article-title":"Enhancing column generation by reinforcement learning-based hyper-heuristic for vehicle routing and scheduling problems","volume":"206","author":"Xu","year":"2025","journal-title":"Comput. Ind. Eng."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"106338","DOI":"10.1016\/j.cor.2023.106338","article-title":"Off-line approximate dynamic programming for the vehicle routing problem with a highly variable customer basis and stochastic demands","volume":"159","author":"Dastpak","year":"2023","journal-title":"Comput. Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"112173","DOI":"10.1016\/j.knosys.2024.112173","article-title":"Token-based deep reinforcement learning for Heterogeneous VRP with Service Time Constraints","volume":"300","author":"Wang","year":"2024","journal-title":"Knowl. Based Syst."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"102370","DOI":"10.1016\/j.tre.2021.102370","article-title":"The multi-trip vehicle routing problem with time windows and unloading queue at depot","volume":"152","author":"Huang","year":"2021","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1016\/j.ejor.2024.04.013","article-title":"An accelerated benders decomposition algorithm for the solution of the multi-trip time-dependent vehicle routing problem with time windows","volume":"317","author":"Fragkogios","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"100848","DOI":"10.1016\/j.disopt.2024.100848","article-title":"Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks","volume":"53","author":"Blauth","year":"2024","journal-title":"Discret. Optim."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"103847","DOI":"10.1016\/j.tre.2024.103847","article-title":"Optimizing first-and-last-mile ridesharing services with a heterogeneous vehicle fleet and time-dependent travel times","volume":"193","author":"Sun","year":"2025","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"100133","DOI":"10.1016\/j.ejtl.2024.100133","article-title":"A Two-echelon Vehicle Routing Problem with time-dependent travel times in the city logistics context","volume":"13","author":"Gutierrez","year":"2024","journal-title":"EURO J. Transp. Logist."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.trb.2022.10.011","article-title":"Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation","volume":"166","author":"Lu","year":"2022","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/j.ejor.2015.09.047","article-title":"An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints","volume":"250","author":"Coelho","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1016\/j.ejor.2024.04.011","article-title":"A hybrid genetic search and dynamic programming-based split algorithm for the multi-trip time-dependent vehicle routing problem","volume":"317","author":"Zhao","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"103069","DOI":"10.1016\/j.tre.2023.103069","article-title":"Optimization of a rural bus service integrated with e-commerce deliveries guided by a new sustainable policy in China","volume":"172","author":"He","year":"2023","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"106189","DOI":"10.1016\/j.cor.2023.106189","article-title":"Metaheuristics with variable diversity control and neighborhood search for the Heterogeneous Site-Dependent Multi-depot Multi-trip Periodic Vehicle Routing Problem","volume":"153","author":"Vieira","year":"2023","journal-title":"Comput. Oper. Res."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"103518","DOI":"10.1016\/j.tre.2024.103518","article-title":"A reinforcement learning-based hyper-heuristic for AGV task assignment and route planning in parts-to-picker warehouses","volume":"185","author":"Li","year":"2024","journal-title":"Transp. Res. Part E Logist. Transp. Rev."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/9\/536\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:34:04Z","timestamp":1760034844000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/9\/536"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,22]]},"references-count":44,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2025,9]]}},"alternative-id":["a18090536"],"URL":"https:\/\/doi.org\/10.3390\/a18090536","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,22]]}}}