论文标题
Neuro Cross Exchange：学习交叉交换以解决现实的车辆路线问题
Neuro CROSS exchange: Learning to CROSS exchange to solve realistic vehicle routing problems
论文作者
论文摘要
解决各种车辆路由问题（VRP）的元式墨西哥交叉交换（CE）通过交换车辆的子旅程来改善VRP的解决方案。在CE的启发下，我们提出了Meala-Heuristic的基本运营商Neuro CE（NCE），以解决各种VRP，同时克服CE的局限性（即昂贵的$ \ Mathcal {O}（o}（n^4）$搜索成本）。 NCE采用图形神经网络来预测成本范围（即CE搜索结果），并利用预测的成本指导作为搜索指导，以将搜索成本降低至$ \ Mathcal {o}（o}（n^2）$。由于NCE的学习目标是预测成本指导，因此可以简单地以有监督的方式进行培训，其培训样本可以毫不费力地准备。尽管NCE的简单性，但数值结果表明，经过灵活的多源VRP（FMDVRP）训练的NCE胜过元位基准基准。更重要的是，在解决FMDVRP（例如MDVRP，MTSP，CVRP）的独特特殊案例时，它在没有额外的培训的情况下，它显着胜过神经基准。
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.
