“虹”学讲堂举办373讲数据驱动的车辆径路算法与应用

车辆路径规划问题既是经典的交通问题，又是运筹学的起源。在日常生活中，我们乘坐公交、骑行共享单车、使用网络地图导航、快递外卖配送等背后都蕴含车辆路径规划问题。接下来，让我们走进本期的“虹”学讲堂，学习数据驱动的车辆路径规划相关知识吧！

5月20日上午，由研究生院/研究生工作部主办、运输工程学院承办、校研究生科学技术协会协办的“虹”学讲堂第373讲以线上讲座形式顺利举办。北京化工大学经济管理学院李想教授作了题为“数据驱动的车辆径路算法与应用”的报告，相关学院共300余名师生参加讲座。

本次报告主要包括以下三个部分：

（1）车辆路径规划问题；

（2）车辆路径规划模型；

（3）车辆路径规划算法；

车辆路径规划问题（Vehicle Routing Problem)是由Dantzig和Ramser于1959年首次提出的问题模型，具体定义为：一定数量的客户各自拥有不同数量的货物需求，配送中心组织一个车队向客户提供货物，解决如何组织适当的行车路线使客户的需求得到满足的问题，并满足一定约束条件下成本最小、耗时最短等目标。

通过明确车辆路径规划问题含义，李想教授指出了车辆路径规划存在的问题，从公交场站调度员、城管部门、交通部门三方角度讲解了车辆路径规划的模型。

1. 调度员迫切需要时刻表与排班优化技术支持，提升效率。（1）决策变量：发车班次、停靠站点、发车时刻、排班计划；（2）目标函数：最小化成本、最大化客流；（3）约束条件：运力约束、工作时长；（4）模型参数：时空旅行时间、时空出行需求。

2. 城管部门迫切需要共享单车搬运调度技术支持，提升城市共享单车的治理水平。（1）决策变量：搬运车辆数量、搬运车辆路径、搬运任务指派；（2）目标函数：最小化搬运成本；（3）约束条件：容量约束、时间约束；（4）模型参数：时空旅行时间、围栏单车盈亏。

3. 交通部门迫切需要定制巴士临时组线技术支持，快速疏散交通枢纽的激增客流。（1）决策变量：定制巴士数量、定制巴士线路、订单指派；（2）目标函数：最快疏散客流、最大化收益；（3）约束条件：容量约束、运行时间、停站数量；（4）模型参数：时空旅行时间、时空出行需求。

此外，李想教授介绍了共享汽车与危化品运输的路径规划和订单指派问题：共享汽车路径规划与订单指派中，调度人员应针对空车的调运进行决策，包括其与非空车辆调度进行协同决策，并考虑异质车型的影响；危化品运输路径规划与订单指派的关键在于如何刻画时空运输网络中的事故概率、事故后果和运输风险，以及如何表征时空旅行时间。

李想教授指出，车辆路径规划模型主要解决的问题是：K辆车从场站出发，决定每辆车的出发时间与路径；经过N个站点，决定在每个站点的停车时间，总计P个订单。

该模型的约束条件为：（1）车辆路径约束：每辆车从虚拟起点出发，经过一系列中间站点，到达虚拟终点；（2）旅行时间约束：每辆车在相邻站点“到达时间、停站时间、旅行时间”关系约束；（3）停站数量约束；（4）工作时长约束；（5）任务指派约束：起点时间窗、终点时间窗；（6）车辆容量约束：断面容量、初始容量。

通过对车辆路径规划问题进行分析，李想教授提到，车辆路径规划算法主要分为三类：（1）小规模问题：分支定界法、列生成技术；（2）中规模问题：分布式+启发式+精确算法；（3）大规模问题：分治式+分布式+启发式。

报告结束后，李想教授耐心解答了同学们关于讲座内容的疑问，使同学们对数据驱动的车辆径路算法有了更加深入的认识。