Deep reinforcement learning for solving vehicle routing problems with backhauls
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 neur...
Saved in:
Main Authors: | , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2024
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/9337 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-10337 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-103372024-09-26T07:06:03Z Deep reinforcement learning for solving vehicle routing problems with backhauls WANG, Conghui CAO, Zhiguang WU, Yaoxin TENG, Long WU, Guohua 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. 2024-03-29T07:00:00Z text https://ink.library.smu.edu.sg/sis_research/9337 info:doi/10.1109/TNNLS.2024.3371781 Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Deep reinforcement learning (DRL) logistics neural heuristic two-stage attention vehicle routing problem (VRP) Databases and Information Systems OS and Networks |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Deep reinforcement learning (DRL) logistics neural heuristic two-stage attention vehicle routing problem (VRP) Databases and Information Systems OS and Networks |
spellingShingle |
Deep reinforcement learning (DRL) logistics neural heuristic two-stage attention vehicle routing problem (VRP) Databases and Information Systems OS and Networks WANG, Conghui CAO, Zhiguang WU, Yaoxin TENG, Long WU, Guohua Deep reinforcement learning for solving vehicle routing problems with backhauls |
description |
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. |
format |
text |
author |
WANG, Conghui CAO, Zhiguang WU, Yaoxin TENG, Long WU, Guohua |
author_facet |
WANG, Conghui CAO, Zhiguang WU, Yaoxin TENG, Long WU, Guohua |
author_sort |
WANG, Conghui |
title |
Deep reinforcement learning for solving vehicle routing problems with backhauls |
title_short |
Deep reinforcement learning for solving vehicle routing problems with backhauls |
title_full |
Deep reinforcement learning for solving vehicle routing problems with backhauls |
title_fullStr |
Deep reinforcement learning for solving vehicle routing problems with backhauls |
title_full_unstemmed |
Deep reinforcement learning for solving vehicle routing problems with backhauls |
title_sort |
deep reinforcement learning for solving vehicle routing problems with backhauls |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2024 |
url |
https://ink.library.smu.edu.sg/sis_research/9337 |
_version_ |
1814047913658023936 |