计算机应用

作者：郑李萍, 王建强, 张玉召, 董祚帆

单位：兰州交通大学 交通运输学院, 兰州 730070

关键词：终端配送,无人配送车,最小车队,时空网络,路径覆盖问题,最大流问题

基金：国家自然科学基金资助项目（71761025）；教育部“春晖计划”合作科研项目；甘肃省高等学校科研资助项目（2018A-023）。

为解决快递终端配送多时空任务驱动下的最小无人车队车辆数配置问题，提出一种随机优化方法。首先，分析服务时长和等待时长对无人车队行驶路线规划的影响，从而构建最短路径模型；然后，基于二维时空网络构造服务序列网络；其次，通过网络转换将最小无人车队车辆数配置问题转化为网络最大流问题，并建立以车队车辆数最小为目标的最小车队模型；最后，针对模型特征设计一种融合Dijkstra算法和Dinic算法的Dijkstra-Dinic算法来对最小无人车队车辆数配置问题进行求解。在四种不同规模的服务网络中进行仿真实验，实验结果表明：在不同成功服务率下，最小无人车队车辆数与服务网络规模呈正相关，但随等待时长的增加而减少并趋向于稳定；所提算法中所引入的One-stop算子大大提高了搜索效率，所提模型和算法适用于大规模服务网络中的最小车队计算。

来源：2021年第5期

《计算机应用》期刊编辑部

查看计算机应用杂志2021年第5期