Neuro CROSS exchange: Learning to CROSS exchange to solve realistic vehicle routing problems
This addresses efficiency issues in solving realistic vehicle routing problems for logistics and transportation, though it is incremental as it builds on an existing meta-heuristic.
The paper tackles the high computational cost of the CROSS exchange meta-heuristic for vehicle routing problems by proposing Neuro CROSS exchange, which uses a graph neural network to predict cost-decrements, reducing search cost from O(n^4) to O(n^2). Numerical results show it outperforms meta-heuristic and neural baselines on various VRP variants without additional training.
CROSS exchange (CE), a meta-heuristic that solves various vehicle routing problems (VRPs), improves the solutions of VRPs by swapping the sub-tours of the vehicles. Inspired by CE, we propose Neuro CE (NCE), a fundamental operator of learned meta-heuristic, to solve various VRPs while overcoming the limitations of CE (i.e., the expensive $\mathcal{O}(n^4)$ search cost). NCE employs a graph neural network to predict the cost-decrements (i.e., results of CE searches) and utilizes the predicted cost-decrements as guidance for search to decrease the search cost to $\mathcal{O}(n^2)$. As the learning objective of NCE is to predict the cost-decrement, the training can be simply done in a supervised fashion, whose training samples can be prepared effortlessly. Despite the simplicity of NCE, numerical results show that the NCE trained with flexible multi-depot VRP (FMDVRP) outperforms the meta-heuristic baselines. More importantly, it significantly outperforms the neural baselines when solving distinctive special cases of FMDVRP (e.g., MDVRP, mTSP, CVRP) without additional training.