Deep reinforcement learning for solving vehicle routing problems with backhauls

Publication Type

Journal Article

Publication Date

3-2024

Abstract

The vehicle routing problem with backhauls (VRPBs) is a challenging problem commonly studied in computer science and operations research. Featured by linehaul (or delivery) and backhaul (or pickup) customers, the VRPB has broad applications in real-world logistics. In this article, we propose a neural heuristic based on deep reinforcement learning (DRL) to solve the traditional and improved VRPB variants, with an encoder–decoder structured policy network trained to sequentially construct the routes for vehicles. Specifically, we first describe the VRPB based on a graph and cast the solution construction as a Markov decision process (MDP). Then, to identify the relationship among the nodes (i.e., linehaul and backhaul customers, and the depot), we design a two-stage attention-based encoder, including a self-attention and a heterogeneous attention for each stage, which could yield more informative representations of the nodes so as to deliver high-quality solutions. The evaluation on the two VRPB variants reveals that, our neural heuristic performs favorably against both the conventional and neural heuristic baselines on randomly generated instances and benchmark instances. Moreover, the trained policy network exhibits a desirable capability of generalization to various problem sizes and distributions.

Keywords

Deep reinforcement learning (DRL), logistics, neural heuristic, two-stage attention, vehicle routing problem (VRP)

Discipline

Databases and Information Systems | OS and Networks

Research Areas

Intelligent Systems and Optimization

Publication

IEEE Transactions on Neural Networks and Learning Systems

First Page

1

Last Page

15

ISSN

2162-237X

Identifier

10.1109/TNNLS.2024.3371781

Publisher

Institute of Electrical and Electronics Engineers

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TNNLS.2024.3371781

This document is currently not available here.

Share

COinS