多时空配送任务驱动的无人车队车辆数优化方法

• 作者: 郑李萍 王建强 张玉召 董祚帆
• 来源期刊: 计算机应用
• 关键词: 终端配送 无人配送车 最小车队 时空网络 路径覆盖问题 最大流问题
• 年，卷（期）: 2021,（5）
• 所属期刊栏目: 先进计算|Advanced computing
• 页码范围: 1406-1411
• 页数: 6页
• 分类号: TP242.6|U492
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2020081183

摘要

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