刘虹庆 王世民

(北京工商大学计算机与信息工程学院 北京 100048)

0 引 言

车辆路径规划问题(Vehicle Routing Problem, VRP)于1959年由Dantzig等[1]提出。该问题定义在一定约束条件下(车载容量、客户需求量、运输过程等)寻求车辆的最优化行车路线，使得运输成本最低或运输距离最短。VRP问题是NP难问题[2]，也是运筹学和组合优化领域的研究热点之一[3]。近年来，启发式算法在求解大规模VRP问题中得到广泛的应用和探索。在启发式算法已得到成熟应用的背景下，本文从机器学习的全新角度出发，通过强化学习对车辆路径规划问题进行建模和求解值得探索。本文主要贡献如下：

(1) 为求解小规模的车辆路径规划问题设计了时间差分模型。为减小状态空间过大造成的存储和计算消耗，采用了动态表更新的方法，设计贪婪奖惩机制以加快算法收敛速度，使用Sarsa和Q-learning两个算法进行优化。

(2) 为求解大规模车辆路径规划问题设计了蒙特卡洛模型。借鉴启发式算法的思想，设计了能够有效模仿代理与环境交互的环境模型。使用环境模型采样和蒙特卡洛更新优化代理策略和值函数。

(3) 在小规模算例和大规模算例上分别进行实验，在小规模数据集上对时间差分模型的实验结果及性能进行了分析和对比。同时在大规模数据集上将蒙特卡洛模型和传统启发式算法进行了实验比较和分析。

1 相关工作

求解VRP问题的算法大致可分为精确算法和启发式算法(包括元启发式算法)两类。其中精确算法能得到最优解，但计算复杂高，不适合用于求解大规模的VRP问题。……