Vehicle Routing with Finite Time Horizon using Deep Reinforcement Learning with Improved Network Embedding

AI summary

Overview

Research area: Combinatorial optimization for vehicle routing, specifically the Vehicle Routing Problem with a Finite Time Horizon (VRP-FTH), solved with deep reinforcement learning and graph neural network embeddings.

Technical level: Intermediate — the paper assumes working familiarity with reinforcement learning (policy gradients) and graph neural networks (attention, embeddings), but the problem setting itself is easy to grasp.

Scope (one sentence): The paper proposes a graph-attention-based network embedding module, trained inside a policy-gradient reinforcement learning agent, to maximize the number of customers served within a fixed time horizon.

What This Paper Is About

In the Vehicle Routing Problem with a Finite Time Horizon, a single vehicle leaves a depot, serves as many customers as it can, and must return to the depot before a fixed time limit expires. Because not every customer can be reached in time, the goal is not to minimize distance but to maximize the count of customers actually served, with requests that are either fully known in advance (deterministic) or arriving during the trip (stochastic). The authors argue that existing reinforcement learning methods for this problem only build local node embeddings from raw node coordinates and Euclidean networks, so they fail to capture real road-network structure, and they never produce a context-aware global view of the routing graph.

Key Contributions

1. A routing network embedding module that produces both local node encoding vectors and a single context-aware global graph representation vector, built from Graph Attention Networks with edge features (GAT-Edge) plus a Cross-Attention mechanism.
2. Incorporation of the remaining finite time horizon into the graph embedding module, so the global graph representation reflects the current routing context rather than a static graph view.
3. A Markov Decision Process formulation for VRP-FTH whose state space includes node features, a sparse adjacency matrix (built from k-nearest neighbours) and edge features, unlike prior deep RL formulations that use only node coordinates.
4. A complete routing method, Policy Gradient with GAT-Edge (PG-GAT-Edge), which integrates the embedding module with a REINFORCE-based policy network and a compatibility-and-masking layer, evaluated on Euclidean, Eastern Massachusetts highway and Vienna city networks.

Main Findings

• Euclidean networks (EN-50, EN-100): PG-GAT-Edge achieved customer service rates of 75.2 and 48.0 on deterministic instances and 71.3 and 40.9 on stochastic instances, versus 56.8/24.8 and 52.4/26.2 for DRL-Transformer, 41.1/17.5 and 23.7/18.4 for DRL-S2V, 48.8/25.8 for the Genetic Algorithm and 37.8/19.9 for Variable Neighbourhood Search. The paper reports this as a 59.2% improvement on deterministic Euclidean instances and 46.0% on stochastic instances compared to the other methods (the conclusion restates a 52.6% improvement on Euclidean instances).
• EMA highway networks (EMA-50, EMA-100, EMA-150): PG-GAT-Edge dominated every instance — 86.6, 57.5 and 41.7 on deterministic instances and 94.5, 49.8 and 56.2 on stochastic instances, compared with 74.1/46.1/27.3 (deterministic) and 28.7/22.0/33.6 (stochastic) for DRL-Transformer. The conclusion summarizes the EMA gain as 57.7% over the other methods.
• Vienna city network (Vienna-160, Vienna-300, stochastic): PG-GAT-Edge reached 47.9 and 28.2, against 42.3/25.8 for DRL-Transformer, 27.4/12.5 for DRL-S2V and 27.7/13.9 for the Multiple Knapsack Approximation. This corresponds to 72.9% more customer service on Vienna-160 and 102.8% more on Vienna-300 than MKA; the conclusion reports an 11.2% improvement on Vienna networks overall.
• Solution time: PG-GAT-Edge required 0.45, 0.63 and 1.03 seconds on EMA-50, EMA-100 and EMA-150, and 0.78 and 1.85 seconds on Vienna-160 and Vienna-300. The Genetic Algorithm needed 6.79, 7.52 and 7.88 seconds on the EMA instances, while MKA needed 26.59 and 70.1 seconds on the Vienna instances. The conclusion states the solution time is 90.64% less than the genetic algorithm and 35.4% less than DRL-Transformer, and that the gap grows with network size.
• Time horizon sensitivity: On Vienna-160 and EN-50, PG-GAT-Edge consistently outperformed DRL-Transformer across all values of the finite horizon U; on EN-50 the performance gap widened as U increased.
• Ablation on EMA-50: Removing edge features dropped the service rate to 83.2 (a 4.1% improvement attributed to edge features); removing the global graph embedding module dropped it to 76.4 (11.8% lower than the proposed method); removing the finite horizon from the embedding dropped it to 78.2 (a 10.7% improvement attributed to including the horizon). The full method scored 86.6.

Methodology in Plain English

The routing task is framed as a sequence of decisions: at each step the agent looks at the current situation and picks the next node to visit. The state is deliberately rich — it includes, for the whole network, travel-time-based node features, a sparse adjacency matrix built from each node's k-nearest neighbours, and edge features defined as one minus the min-max normalized travel time. It also includes the vehicle's current location, the set of active customer requests, and the remaining time left in the horizon.

An embedding module turns this state into representations. Two Graph Attention Network layers with edge features attend over neighbouring nodes, with the attention scores scaled by the edge features, and residual connections combine the two layers into the final node embeddings. A Cross-Attention layer then asks "given the current vehicle state, which nodes matter right now?" — the vehicle state forms the query, and the node embeddings act as keys and values — producing a single global graph embedding vector. A separate vector sums the embeddings of the currently active customer requests. The remaining time horizon is projected and concatenated with the global graph embedding, the current node embedding and the active-customer embedding to form a context vector.

A compatibility layer then scores every candidate node against this context vector, and a masking step removes nodes that have already been visited or that cannot be reached and still allow a return to the depot within the remaining time. A softmax over the masked scores gives the probability of visiting each node. The agent gets +1 reward for serving a customer while time remains, a penalty equal to the total number of customers if it fails to finish within the horizon, and 0 otherwise. Training uses the REINFORCE policy gradient algorithm. The network uses two GAT-Edge layers with 4 attention heads, 64-dimensional embeddings, and a context vector projected to 256 dimensions. Baselines include a Genetic Algorithm (population size 100, 1000 generations, mutation rate 0.01), Variable Neighbourhood Search, Multiple Knapsack Approximation (only on Vienna), DRL-Transformer and DRL-S2V.

Why This Matters

The paper is a concrete argument that how you represent a routing network matters as much as which learning algorithm you use. Most deep RL routing work treats cities as flat sets of coordinates; this work shows that feeding the actual graph structure — adjacency, edge weights and travel time — into the agent yields both better service rates and faster decisions. The ablation results make the case explicitly: edge features account for a 4.1% gain, the global graph embedding for 11.8%, and embedding the remaining time horizon for 10.7%.

Real-world applications:

• Delivery and logistics routing, where a driver or vehicle has a fixed shift length and must choose which stops to serve.
• Same-day and on-demand delivery, where new requests arrive during the trip (the stochastic setting the paper evaluates).
• Urban planning and transportation analysis, using the highway-network experiments built from OpenStreetMap data.
• Fleet and service dispatch, which the authors name as the direction for future work.

Industry relevance: the reported solution times are sub-second to a few seconds (0.45 to 1.85 seconds for the proposed method across the tested networks), and the paper notes the time advantage over baselines widens as the network grows. That matters for operators who need routing decisions made during a trip rather than computed offline, and it makes real road-network inputs — rather than idealized straight-line distances — practical to use.

Future Directions

• Extending the framework from a single vehicle to vehicle fleet routing, which the authors explicitly identify as future work.
• Adapting the MDP to other VRP variants. The authors note that the smallest horizon at which the agent serves 100% of customers represents the minimum time needed to serve everyone, and that by modifying the MDP the method could support time-minimization VRP, distance-minimization VRP and VRP with time windows.
• Testing scalability beyond the largest tested instances (EMA-150 with 150 customers, Vienna-300 with 300 customers), particularly given the claim that the solution-time advantage grows with network size.
• Investigating the boundary conditions of the approach: the paper does not report how performance or solution time behaves for much larger graphs, nor how the fixed hyperparameters (2 GAT-Edge layers, 4 attention heads, 64-dimensional embeddings, 256-dimensional context projection) were selected or whether they transfer across network types.

Target Audience

This paper is most useful to researchers and graduate students working on combinatorial optimization, reinforcement learning for routing, and graph neural networks — particularly those interested in how graph embeddings can be conditioned on dynamic context. It also suits practitioners in logistics, delivery and transportation technology who are evaluating whether learned routing policies can beat classical heuristics on real road networks while remaining fast enough for operational use. Readers should be comfortable with policy gradient methods, attention mechanisms and standard VRP terminology to get the most out of the methodology sections.

Authors’ abstract

In this paper, we study the vehicle routing problem with a finite time horizon. In this routing problem, the objective is to maximize the number of customer requests served within a finite time horizon. We present a novel routing network embedding module which creates local node embedding vectors and a context-aware global graph representation. The proposed Markov decision process for the vehicle routing problem incorporates the node features, the network adjacency matrix and the edge features as components of the state space. We incorporate the remaining finite time horizon into the network embedding module to provide a proper routing context to the embedding module. We integrate our embedding module with a policy gradient-based deep Reinforcement Learning framework to solve the vehicle routing problem with finite time horizon. We trained and validated our proposed routing method on real-world routing networks, as well as synthetically generated Euclidean networks. Our experimental results show that our method achieves a higher customer service rate than the existing routing methods. Additionally, the solution time of our method is significantly lower than that of the existing methods.