共计 1599 个字符，预计需要花费 4 分钟才能阅读完成。
拜访【WRITE-BUG 数字空间】_[内附残缺源码和文档]
车辆门路布局问题（VRP）是运筹优化畛域最经典的优化问题之一。在此问题中，有若干个客户对某种货物有一定量的需要，车辆能够从仓库取货之后配送到客户手中。客户点与仓库点组成了一个配送网络，车辆能够在此网络中挪动从而实现配送工作。在求解此问题过程中，须要优化的决策变量为每个客户的配送工作应该调配到哪一辆车上，以及每辆车实现客户配送工作的先后顺序，优化指标为最小化车辆总行驶间隔和应用的车辆数。
一、试验要求
复现以下论文的办法和后果：
Duan,L., Zhan,Y., Hu,H., Gong,Y., Wei,J., Zhang,X., Xu,Y.: Efficiently solving the practical vehicle routing problem: A novel joint learning approach. In: KDD. pp.3054–3063 (2020)
1．为了节省时间，训练用 10 个（或以上）的城市规模的算例。测试算例用 20 个（或者以上）规模。
2．显示出算法训练收敛过程，可视化最初的解。可能的状况下，比照 OR-Tools 的求解成果（前面详细描述）。
二、导言
车辆门路布局问题（VRP）是运筹优化畛域最经典的优化问题之一。在此问题中，有若干个客户对某种货物有一定量的需要，车辆能够从仓库取货之后配送到客户手中。客户点与仓库点组成了一个配送网络，车辆能够在此网络中挪动从而实现配送工作。在求解此问题过程中，须要优化的决策变量为每个客户的配送工作应该调配到哪一辆车上，以及每辆车实现客户配送工作的先后顺序，优化指标为最小化车辆总行驶间隔和应用的车辆数。
故外围优化的指标为车辆总的固定成本 + 运输成本，VRP 问题最简略的模式就是使车辆具备容量的束缚（装载量无限）。每辆车从给定的节点登程和返回，优化的指标就是车辆相干费用和配送间隔的函数。目前的钻研工作分为两个流派：一种是通过运筹学，另一种是深度学习。运筹学的办法是把 VRP 定义为数学优化问题，通过准确或启发式算法达到最优或者近似最优解，然而实在场景的数据量下须要破费的工夫很多。而对于深度学习，之前的钻研是在人工生成的数据集上，疏忽了真实世界的运输网络。在实在 VRP 问题数据集上，没有一个办法能比得上 OR-tools，于是便想着提出一种新的办法。
三、算法流程
这里次要是将论文中的算法联合我本人的了解再形容一遍
Problem Setup: Graph Optimization Perspective
首先从图优化的视角来形式化的形容以下 VRP 问题。一个 VRP 实例，能够看做一张图 $G=(V, E)$，其中顶点汇合: $V={0, \ldots, n}$, 其中 $i=0$ 示意 depot, $i=1, \ldots, n$ 示意客户，边汇合: $\quad E=\left{e_{i j}\right}, i, j \in V$。
depot 节点只有坐标特色 $x_{0}^{c}$，而其余客户节点有坐标特色和需求量特色，因而是一个二维特征向量 $x_{i}=\left{x_{i}^{c}, x_{i}^{d}\right}$，其中 $ x_{i}^{c}, x_{i}^{d}$ 别离是坐标特色和需求量特色。每条边关联两个节点之间的间隔为 $m_{i j}$。
假如有：VRP 是生成一个 tour 汇合，每个 tour 代表了一个车辆的门路，从节点 0 登程，在节点 0 完结，每个客户被服务一次且仅一次，每辆车的负载不超过它自身的容量，指标是最小化总体破费。
那么，模型的指标是生成一个客户的序列: $\pi=\left(\pi_{1}, \pi_{2}, \pi_{3}, \ldots, \pi_{T}\right)$ 其中, $\pi_{t} \in{0,1, \ldots, n}$, 并且 $\pi_{0}$ 能够呈现屡次，其余节点只能呈现一次。因而，每两个 $\pi_{0}$ 之间的序列就是一辆车的路线。
