图神经网络+强化学习

访问【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}$ 之间的序列就是一辆车的路线。

0.png

1.jpg

2.jpg

3.jpg

图神经网络+强化学习

推荐阅读更多精彩内容