Neuro CROSS exchange: Learning to CROSS exchange to solve realistic vehicle routing problems
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.