Bi-level RL-Heuristic Optimization for Real-world Winter Road Maintenance

Yue Xie; Zizhen Xu; William Beazley; Fumiya Iida

cs.AIFeb 27, 2026

Bi-level RL-Heuristic Optimization for Real-world Winter Road Maintenance

Authors: Yue Xie, Zizhen Xu, William Beazley, Fumiya Iida

Organizations: School of Science, Loughborough University, UK · Department of Engineering, University of Cambridge, UK · National Highways, 199 Wharfside St, Birmingham B1 1RN, UK

Abstract

Winter road maintenance is critical for ensuring public safety and reducing environmental impacts, yet existing methods struggle to manage large-scale routing problems effectively and mostly reply on human decision. This study presents a novel, scalable bi-level optimization framework, validated on real operational data on UK strategic road networks (M25, M6, A1), including interconnected local road networks in surrounding areas for vehicle traversing, as part of the highway operator's efforts to solve existing planning challenges. At the upper level, a reinforcement learning (RL) agent strategically partitions the road network into manageable clusters and optimally allocates resources from multiple depots. At the lower level, a multi-objective vehicle routing problem (VRP) is solved within each cluster, minimizing the maximum vehicle travel time and total carbon emissions. Unlike existing approaches, our method handles large-scale, real-world networks efficiently, explicitly incorporating vehicle-specific constraints, depot capacities, and road segment requirements. Results demonstrate significant improvements, including balanced workloads, reduced maximum travel times below the targeted two-hour threshold, lower emissions, and substantial cost savings. This study illustrates how advanced AI-driven bi-level optimization can directly enhance operational decision-making in real-world transportation and logistics.

Figures & tables

Sets
$R_{C}$	Set of road segments requiring salt coverage $(R_{C}=\{1,2,\ldots,N\})$
$R_{NC}$	Set of road segments not requiring salt coverage, used only for connectivity
	$(R_{NC}=\{1,2,\ldots,M\})$
$R=R_{C}+R_{NC}$	Set of road segments
D	Set of depots (each depot associated with vehicle availability constraints)
V	Set of vehicles available for routing $(V=\{1,2,\ldots,K\})$

Table 1: Mathematical Notation

Figure 1: Overview of the bi-level optimization framework. The upper-level PPO agent assigns treatment-required road segments to depots. The lower-level routing module solves each subproblem under operational constraints and returns reward metrics (makespan and emissions) to guide policy updates

Method	$Z_{1}$ (min)	$Z_{2}$ (kg CO 2 )	NoV
KDTree+NN	122.14	3,386.63	20
KDTree-PPO+NN	118.81	3,220.95	28

Table 2: Raw results on the fixed network (no normalization).

Z_{1}

= makespan (h);

Z_{2}

= emissions (kg CO 2 e).

Figure 3: Objectives and fleet use across PPO–NN iterations.

Panel of Figure 4 — Figure 4: Treated edges by depot. Coloured polylines show vehicle trajectories from each depot (blue = Misterton, orange = Pytchley, green = Rothersthorpe) drawn over the full road network (grey). Arrowheads indicate driving direction.

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 135 papers

Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing
Jun 30, 2026Oguzhan Karaahmetoglu, Hyong KimLarge Language Model-Guided Optimization Combinatorial Optimization
Carnegie Mellon University · Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 15213 USA
Towards Autonomous Railway Operations: A Semi-Hierarchical Deep Reinforcement Learning Approach to the Vehicle Rescheduling Problem
May 11, 2026Alberto Castagna, Stefan Zahlner, Adrian Egli +4Multi-Agent Coordination Intelligent Transportation Systems
∗enliteAI, AT · †SBB CFF FFS, CH · ‡Flatland Association, CH
Graph-Based Inference and Topology-Aware Multi-Agent Reinforcement Learning for Large-Scale Railway Network Management
Sep 24, 2026Giacomo Arcieri, Gregory Duthé, Christophe Muller +3Predictive Maintenance Multi-Agent Reinforcement Learning
Department of Civil, Environmental and Geomatic Engineering, ETH Zürich, Zürich, 8093, Switzerland · Department of Statistics, University of Oxford, Oxford, United Kingdom · Dept. of Civil and Environmental Engineering, The Pennsylvania State University, University Park, PA, 16802, USA +1

Jun 30, 2026J/K move · Enter open · S save

Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing

Oguzhan Karaahmetoglu, Hyong Kim

Carnegie Mellon University · Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 15213 USA

Large Language Model-Guided Optimization Combinatorial Optimization Vehicle Routing

Open paper AskPDF arXiv

Large-scale capacitated vehicle routing problems (CVRPs) are commonly addressed using cluster-first route-second (CFRS) approaches that split a routing instance into smaller, computationally tractable subproblems. Existing splitting methods typically rely on fixed partitioning rules, predefined optimization objectives, or learned policies, which may perform inconsistently across instances exhibiting different spatial, demand, and operational characteristics. In this work, we propose an adaptive CFRS system that formulates a decomposition procedure as an iterative decision-making process. Motivated by the recent success of large language models (LLMs) in reasoning and tool selection, the system employs an LLM as a high-level decision maker that analyzes the evolving decomposition state and selectively applies further clustering, balancing, and refinement operators. The proposed algorithm jointly partitions customers and vehicles, enabling capacity-aware clustering while adapting partitioning decisions to the characteristics of each problem. We evaluate the approach on synthetic and benchmark-derived CVRP instances containing up to 500,000 customers. Experimental results demonstrate competitive performance on benchmark-scale instances while exhibiting improved scalability and robust routing quality on substantially larger problems. These results highlight the potential of adaptive, LLM-guided decision support as a practical approach for industrial-scale vehicle routing and large-scale logistics planning.

Abstract

Vehicle Routing

Explore similar work

Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing

Towards Autonomous Railway Operations: A Semi-Hierarchical Deep Reinforcement Learning Approach to the Vehicle Rescheduling Problem

Graph-Based Inference and Topology-Aware Multi-Agent Reinforcement Learning for Large-Scale Railway Network Management