PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Reinforcement Learning for Electric Vehicle Routing Problem with Time Windows

Bo Lin, Bissan Ghaddar, Jatin Nathwani

arXiv:2010.02068v4cs.LGcs.AImath.OCstat.ML

TL;DR

The paper addresses the challenge of solving EVRPTW efficiently at large scale, where existing approaches become difficult to use. It develops an end-to-end RL framework combining a pointer-network attention model with graph embeddings and evaluates its ability to generate feasible solutions for large instances. The model solves instances that existing methods cannot solve and is presented as suitable for large-scale EV operations.

  • Problem

    EVRPTW requires routing capacitated electric vehicles to serve customer demands within time windows while minimizing fleet travel distance, but existing methods lose efficiency as instances grow.

  • Method

    The framework uses an attention model combining a pointer network and graph embedding, with EVRPTW-specific states, rewards, masking, and stochastic-sampling-based reinforcement learning.

  • Results

    The RL model efficiently generates good feasible solutions for very large instances unsolvable by existing methods; with 40 or more customers, it is the only tested algorithm solving EVRPTW within 15 minutes.

  • Takeaways & Limitations

    The approach could support large-scale real-time EV fleet operations and serve as an initialization or primal heuristic for other solution algorithms.

  • Takeaways & Limitations

    The current formulation assumes full charging, and the reward function has no theoretical guarantee that constraints will not be violated.

Abstract

from arXiv · show

The past decade has seen a rapid penetration of electric vehicles (EV) in the market, more and more logistics and transportation companies start to deploy EVs for service provision. In order to model the operations of a commercial EV fleet, we utilize the EV routing problem with time windows (EVRPTW). In this research, we propose an end-to-end deep reinforcement learning framework to solve the EVRPTW. In particular, we develop an attention model incorporating the pointer network and a graph embedding technique to parameterize a stochastic policy for solving the EVRPTW. The model is then trained using policy gradient with rollout baseline. Our numerical studies show that the proposed model is able to efficiently solve EVRPTW instances of large sizes that are not solvable with any existing approaches.

I. INTRODUCTION

EVRPTW is a computationally difficult routing problem whose existing exact and heuristic methods lose efficiency and generality as instances grow. The paper develops an RL approach that adapts a policy-based framework with graph embeddings to generate feasible solutions for very large instances and support large-scale operations.

  • Problem context: EVRPTW models capacitated electric-vehicle fleets serving regional customers under demand, routing, and time-window requirements.Customers have associated demands and time windows, while vehicles may visit charging stations during service.
  • Problem context: Existing VNS/TS and branch-and-price-and-cut methods produce high-quality solutions, but their solution quality and efficiency decrease as instance size increases.Their reliance on EVRPTW-specific structures and assumptions also makes generalization to other variants difficult.
  • Motivation: Reinforcement learning can solve combinatorial optimization without optimal labels by learning action sequences and adjusting parameters through reward signals.The paper positions RL as an alternative to supervised models trained on solutions from existing algorithms.
  • Approach: The proposed model redefines the state, reward, and masking mechanisms for EVRPTW and adds graph embedding to combine local vertex information with global graph information.It builds on the policy-based framework of Nazari et al. while addressing EVRPTW's need for global system information.
  • Contribution: The approach efficiently generates good feasible solutions for very large EVRPTW instances that existing methods cannot solve.The authors identify potential use in large-scale real-time fleet operations and as an initialization or primal heuristic for other solvers.

III. PROBLEM DEFINITION

EVRPTW models capacitated electric vehicles serving customers with demands and time windows while allowing depot returns and station recharging. The reinforcement-learning formulation generates routes sequentially, updates system state after each selected vertex, and uses rewards and penalties to favor short feasible solutions.

  • Problem setting: EVRPTW assigns capacitated EVs to serve regional customers with demands and time windows, while vehicles may recharge at stations during the planning horizon.Vehicles begin at a depot with full batteries and return routes to the depot.
  • Problem setting: A solution is a vertex sequence whose depot occurrences separate routes assigned to different EVs.For example, {0, 3, 2, 0, 4, 1, 0} represents two routes.
  • Reinforcement-learning formulation: At each decoding step, the agent selects a vertex, updates the system state, and repeats until all customer demands are satisfied.The state includes graph information, global variables, and the travel history used to estimate the next-vertex probability.
  • State transitions: System time advances according to customer service and travel, station charging and travel, or depot travel, depending on the current vertex type.Travel time, charging time, and the constant customer service time are included in the transition update.
  • Reward design: The reward favors short total distance while penalizing excessive vehicle use, station visits, and negative battery levels.Other constraints are handled through masking, and the reward uses negative constants for penalty terms.
  • Reward design: Experiments indicate that the reward guides constraint-respecting solutions, but it provides no theoretical guarantee against violations.A downstream local-search heuristic is suggested when violations occur.

A. The Attention Model

The proposed attention model parameterizes next-vertex probabilities for EVRPTW by combining state embeddings, attention-based probability estimation, and an LSTM decoder. Its distinguishing design choice is graph embedding that synthesizes local and global graph information.

  • Model architecture: The model estimates the probability of selecting the next vertex from the current EVRPTW state and travel history.It is presented as an attention model for the probability estimator in the sequential routing framework.
  • Model architecture: The architecture contains embedding, attention, and LSTM decoder components for representing state, estimating vertex probabilities, and restoring travel history.The model structure is illustrated in Figure 2.
  • Model architecture: Unlike the referenced model, the proposed architecture incorporates graph embedding to synthesize local and global information.This graph-level representation is the stated key difference from the earlier model.

1) Graph Embedding:

The graph-embedding component maps local vertex information and global state variables into vectors, then recursively propagates neighborhood and edge information. The resulting embeddings combine local and global context for each vertex.

  • Input embedding: Local vertex arrays are embedded with a shared one-dimensional convolution, while global variables are mapped to a ξ-dimensional vector.The global variables are time, battery level, and available-vehicle count.
  • Recursive graph embedding: Structure2Vec recursively updates each vertex representation for p rounds using graph and global information.After the recursion, each vertex receives a ξ-dimensional embedded vector.
  • Recursive graph embedding: The recursion propagates information through neighboring vertices and edges while aggregating global and location information.Neighborhood membership, edge travel time, trainable parameters, and ReLU define the update components.
  • Resulting representation: Each final vertex embedding contains both local and global information, providing a representation of the graph context.This is intended to represent the complicated EVRPTW graph context more effectively.

2) Attention Mechanism:

The attention mechanism forms a graph context from embedded vertices and uses it with decoder state information to estimate next-vertex probabilities. Masking assigns near-zero probability to actions that violate demand, battery, time, horizon, or termination conditions.

  • Context-based attention: The mechanism computes a context vector as a weighted sum of all embedded vertex vectors.The vertex weights are defined by the attention equations.
  • Context-based attention: Attention uses embedded vertex information and LSTM decoder state to calculate each vertex’s visiting probability.The formulation uses nonlinear transformations and softmax normalization before estimating next-step probabilities.
  • Feasibility masking: Masking excludes customers with no unsatisfied demand, excessive demand, insufficient battery feasibility, or violated earliest-arrival time windows.Masked logits receive a very large negative value, making the corresponding selection probability close to zero.
  • Feasibility masking: Masking also excludes moves that prevent returning to the depot before the planning horizon ends.When the vehicle is at the depot with no remaining customer cargo, only the depot remains unmasked.

4) LSTM Decoder:

The LSTM decoder updates a hidden state from the EV’s current position and prior memory, then uses attention-derived probabilities to construct EVRPTW solutions. It supports greedy decoding, stochastic sampling, and beam search, trading speed against exploration and solution quality.

  • LSTM state update: At decoding step t, the LSTM combines the EV’s current-position representation with the previous memory state to produce hidden state h_t.The hidden state retains trajectory information through step t and is passed to the attention model.
  • Probability-based decoding: Attention probabilities p_i^t over vertices enable the agent to decode an EVRPTW solution at each step.The decoder uses these probabilities to select or sample the next vertex.
  • Greedy decoding: Greedy decoding selects the highest-probability next vertex and generates one solution per instance.Its myopic selection can produce poor solutions because it lacks exploration of the solution space.
  • Stochastic sampling: Stochastic sampling draws the next vertex from the probability distribution and can generate multiple solutions, retaining the shortest-distance solution.Repeated sampling provides broader exploration than a single greedy trajectory.
  • Beam search: Beam search maintains multiple high-probability solutions and reports the best final solution, while greedy decoding remains the fastest strategy.Beam search evaluates solution probabilities rather than only individual transitions.

C. Policy Gradient

The policy-gradient method trains the EVRPTW solver from rewards assigned to its generated solutions rather than from solutions supplied by existing algorithms. A rollout baseline is used to reduce gradient-estimation variance and support faster learning.

  • Policy-gradient training: Policy gradient trains the model by evaluating rewards for solutions generated by its stochastic policy instead of using existing algorithmic solutions.The trainable parameters are denoted by θ, and π_θ represents the corresponding stochastic solution policy.
  • Baseline motivation: A good gradient baseline can reduce training variance and increase learning speed.This motivates the use of a rollout baseline in the training procedure.
  • Rollout baseline: The rollout baseline begins with an exponential moving average of rewards, then periodically evaluates and updates a baseline policy.The baseline policy is initialized at the Λth training step and updated only when the current policy satisfies the stated criterion.
  • Objective: The loss is the negative expected total reward of trajectories sampled using π_θ.Minimizing this objective trains the stochastic policy toward higher-reward solutions.
  • Gradient estimation: The gradient estimate uses a batch of N training examples, sampled solutions, the rollout baseline, and their policy probabilities.The probability chain rule obtains solution probabilities from model outputs at each decoding step.

3) Instance Generation:

Training instances are randomly generated under normalized spatial, demand, time-window, vehicle, and charging assumptions, with a small fleet-and-customer configuration used to improve generation efficiency. Algorithm 1 summarizes the resulting REINFORCE training loop.

  • Instance generation: Customer and station locations are generated within [0, 1]×[0, 1], while customer demands are sampled uniformly from four discrete values.The demand values are {0.05, 0.10, 0.15, 0.20}.
  • Training procedure: Each training step generates N random EVRPTW instances and processes them through the algorithm’s repeated training loop.The pseudocode initializes network weights and a test set before generating batches of instances.
  • Training procedure: The training loop advances each instance until termination, computes trajectory rewards, and applies the baseline update condition.The algorithm observes new states, increments the decoding step, and evaluates rewards for generated trajectories.
  • Fleet and charging assumptions: Training uses 3 EVs, 10 customers, and 3 charging stations, with a [0, 1] planning horizon and specified charging-time assumptions.Fully charging from zero requires 0.25 time units, while replenishing energy for one distance unit requires 0.15 time units.
  • Normalization and algorithm: Vehicle cargo and battery capacities are normalized to 1.0, and Algorithm 1 provides the pseudocode for REINFORCE with rollout baseline.The small training instance size is used to improve instance-generation efficiency without compromising reported model performance.

VI. NUMERICAL EXPERIMENT

The experiments implement the RL model in Python and TensorFlow on a specified CPU-only system, using adapted hyperparameters and three decoding strategies. Performance is evaluated through travel distance and solution time tables, with stochastic decoding sampling multiple solutions.

  • Experimental implementation: Experiments run on a 2018 MacBook Pro with four 2.3 GHz CPU processors and 16 GB RAM, using TensorFlow 2.2.0 and Python.The stated operating system is Mac OS 10.13.6.
  • Model configuration: The model uses separate one-dimensional convolutional embeddings, 128-dimensional representations, an LSTM state size of ξ = 128, and Adam step size 0.001.Training uses batch size N = 128 and clips gradient norms at 2.0.
  • Evaluation metrics: Table I compares average total travel distance across five approaches, while Table II compares their average solution time.These tables provide complementary quality and runtime measures for the tested approaches.
  • Decoding evaluation: Testing compares greedy decoding, stochastic decoding, and beam search, with 100 sampled solutions for stochastic decoding and three simultaneous solutions for beam search.The shortest-distance stochastic solution and highest-probability beam-search solution are reported.

B. Computational Result

The RL model produces feasible EVRPTW solutions quickly and scales better than CPLEX and VNS/TS on large instances, although it trails established methods on small-instance solution quality. Analysis indicates that the model uses location, time-window, graph, and battery information, but can miss advantageous early charging decisions.

  • Computational comparison: The stochastic RL implementation consistently provides the best solution quality among the three RL decoding approaches, although it requires more time than greedy decoding and beam search.The comparison includes CPLEX, VNS/TS, and the proposed RL model across seven scenario types.
  • Computational comparison: 8.58% and 11.81% are the stochastic RL optimality gaps for C5-S2-EV2 and C10-S3-EV3, while CPLEX and VNS/TS reach optimality in most cases.These results show weaker solution quality for the RL model on small instances.
  • Computational comparison: For scenarios with 40 or more customers, the RL model is the only method solving EVRPTW within 15 minutes, averaging around 1.8 minutes for 50-customer instances.VNS/TS has better solution quality on C20-S3-EV3 and C30-S4-EV4 but takes 7–10 times longer than RL.
  • Computational comparison: The RL model solves all 100 C30-S4-EV4 instances in around 40 minutes, whereas VNS/TS solves 12 in two hours; for C100-S12-EV12, RL averages 4 minutes per instance while VNS/TS solves none.For C50-S6-EV6, the RL agent solves 1300% more instances than VNS/TS.
  • Algorithm analysis: The RL agent selects routes using customer locations and time windows, sometimes reducing distance by serving a later-window customer before an earlier-window customer.It nevertheless misses the optimal order of customers 4 and 7 in the analyzed instance.
  • Algorithm analysis: The model can generate feasible solutions without exhausting battery energy, but its charging decisions are often driven by current battery level and may miss earlier charging opportunities.In one example, VNS/TS uses one EV after charging early, while RL requires two EVs; the reward guides feasibility but offers no theoretical guarantee against constraint violations.

VII. CONCLUSION

The paper presents an EVRPTW reinforcement learning framework that combines graph embedding with a pointer-network architecture to synthesize local and global graph information. It offers scalable, efficient feasible solutions for very large instances while identifying charging decisions and realistic charging assumptions as areas for improvement.

  • The algorithm scales to very large EVRPTW instances that existing methods cannot solve and quickly provides relatively good feasible solutions.
  • Its efficient solution process could support large-scale real-time EV operations and rapid adjustments when operational conditions change.
  • The framework combines graph embedding techniques with a pointer-network architecture to synthesize local and global graph information for EVRPTW.
  • Future work includes specialized charging-decision components, relaxing the full-charging assumption, hybridizing with other optimization methods, and training on real-world energy and charging data.
Loading 2010.02068v4…