Conditional neural heuristic for multiobjective vehicle routing problems

Existing neural heuristics for multiobjective vehicle routing problems (MOVRPs) are primarily conditioned on instance context, which failed to appropriately exploit preference and problem size, thus holding back the performance. To thoroughly unleash the potential, we propose a novel conditional neu...

Full description

Saved in:
Bibliographic Details
Main Authors: FAN, Mingfeng, WU, Yaoxin, CAO, Zhiguang, SONG, Wen, SARTORETTI, Guillaume, LIU, Huan, WU, Guohua
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2024
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/8729
https://ink.library.smu.edu.sg/context/sis_research/article/9732/viewcontent/TNNLS2024_MOVRP_av.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-9732
record_format dspace
spelling sg-smu-ink.sis_research-97322024-04-18T07:31:59Z Conditional neural heuristic for multiobjective vehicle routing problems FAN, Mingfeng WU, Yaoxin CAO, Zhiguang SONG, Wen SARTORETTI, Guillaume LIU, Huan WU, Guohua Existing neural heuristics for multiobjective vehicle routing problems (MOVRPs) are primarily conditioned on instance context, which failed to appropriately exploit preference and problem size, thus holding back the performance. To thoroughly unleash the potential, we propose a novel conditional neural heuristic (CNH) that fully leverages the instance context, preference, and size with an encoder–decoder structured policy network. Particularly, in our CNH, we design a dual-attention-based encoder to relate preferences and instance contexts, so as to better capture their joint effect on approximating the exact Pareto front (PF). We also design a size-aware decoder based on the sinusoidal encoding to explicitly incorporate the problem size into the embedding, so that a single trained model could better solve instances of various scales. Besides, we customize the REINFORCE algorithm to train the neural heuristic by leveraging stochastic preferences (SPs), which further enhances the training performance. Extensive experimental results on random and benchmark instances reveal that our CNH could achieve favorable approximation to the whole PF with higher hypervolume (HV) and lower optimality gap (Gap) than those of the existing neural and conventional heuristics. More importantly, a single trained model of our CNH can outperform other neural heuristics that are exclusively trained on each size. In addition, the effectiveness of the key designs is also verified through ablation studies. 2024-03-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/8729 info:doi/10.1109/TNNLS.2024.3371706 https://ink.library.smu.edu.sg/context/sis_research/article/9732/viewcontent/TNNLS2024_MOVRP_av.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Context modeling Decoding Encoder-decoder Fans; multiobjective optimization neural heuristic Neural networks Pareto optimization Training Vehicle routing vehicle routing problems Artificial Intelligence and Robotics Theory and Algorithms Transportation
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Context modeling
Decoding
Encoder-decoder
Fans; multiobjective optimization
neural heuristic
Neural networks
Pareto optimization
Training
Vehicle routing
vehicle routing problems
Artificial Intelligence and Robotics
Theory and Algorithms
Transportation
spellingShingle Context modeling
Decoding
Encoder-decoder
Fans; multiobjective optimization
neural heuristic
Neural networks
Pareto optimization
Training
Vehicle routing
vehicle routing problems
Artificial Intelligence and Robotics
Theory and Algorithms
Transportation
FAN, Mingfeng
WU, Yaoxin
CAO, Zhiguang
SONG, Wen
SARTORETTI, Guillaume
LIU, Huan
WU, Guohua
Conditional neural heuristic for multiobjective vehicle routing problems
description Existing neural heuristics for multiobjective vehicle routing problems (MOVRPs) are primarily conditioned on instance context, which failed to appropriately exploit preference and problem size, thus holding back the performance. To thoroughly unleash the potential, we propose a novel conditional neural heuristic (CNH) that fully leverages the instance context, preference, and size with an encoder–decoder structured policy network. Particularly, in our CNH, we design a dual-attention-based encoder to relate preferences and instance contexts, so as to better capture their joint effect on approximating the exact Pareto front (PF). We also design a size-aware decoder based on the sinusoidal encoding to explicitly incorporate the problem size into the embedding, so that a single trained model could better solve instances of various scales. Besides, we customize the REINFORCE algorithm to train the neural heuristic by leveraging stochastic preferences (SPs), which further enhances the training performance. Extensive experimental results on random and benchmark instances reveal that our CNH could achieve favorable approximation to the whole PF with higher hypervolume (HV) and lower optimality gap (Gap) than those of the existing neural and conventional heuristics. More importantly, a single trained model of our CNH can outperform other neural heuristics that are exclusively trained on each size. In addition, the effectiveness of the key designs is also verified through ablation studies.
format text
author FAN, Mingfeng
WU, Yaoxin
CAO, Zhiguang
SONG, Wen
SARTORETTI, Guillaume
LIU, Huan
WU, Guohua
author_facet FAN, Mingfeng
WU, Yaoxin
CAO, Zhiguang
SONG, Wen
SARTORETTI, Guillaume
LIU, Huan
WU, Guohua
author_sort FAN, Mingfeng
title Conditional neural heuristic for multiobjective vehicle routing problems
title_short Conditional neural heuristic for multiobjective vehicle routing problems
title_full Conditional neural heuristic for multiobjective vehicle routing problems
title_fullStr Conditional neural heuristic for multiobjective vehicle routing problems
title_full_unstemmed Conditional neural heuristic for multiobjective vehicle routing problems
title_sort conditional neural heuristic for multiobjective vehicle routing problems
publisher Institutional Knowledge at Singapore Management University
publishDate 2024
url https://ink.library.smu.edu.sg/sis_research/8729
https://ink.library.smu.edu.sg/context/sis_research/article/9732/viewcontent/TNNLS2024_MOVRP_av.pdf
_version_ 1814047495745961984