基于最大化无延时概率的路径规划问题的研究

As the number of global vehicles grows drastically, road networks become increasingly congested, and more and more vehicles are suffering traffic delay. Traffic delay often causes huge economic losses and serious environmental pollution.This project aims to solve the route planning problem, which maximizes the probability of no delay, and improve the existing solutions in three aspects: 1) multi-objective optimization model for probability of punctual arrival and delay duration is constructed, based on vehicle routing algorithm for maximal probability of punctual arrival. Cost function and weight coefficient involved in the model are defined. And the final model helps to decrease delay risk; 2) Indicator matrix of traffic network is designed to describe road segment relation and mathematical expression for straight route is studied, based on which the optimization algorithm can be constructed for traveler’s preference of straight route; 3) Combination of probability maximization for punctual arrival and distributed multi-agent approach is explored, in which the intentions of vehicles and estimated link travel times are collected, to enhance dynamic response of route planning in traffic network. The proposed solution is finally verified via traffic simulation software and practical navigation testing. The project will not only facilitate the theoretical development of routing planning for maximal probability of no delay, but will also provide explicit and effective methods for the deployment of practical vehicle routing.

随着全球汽车数量的增多，交通网络变得日益拥挤，越来越多的车辆正在经历着交通延时。交通延时往往会造成巨大的经济损失和严重的环境污染。本项目以最大化无延时概率的路径规划问题为研究目标，对现有的解决方案进行三方面的改进：1) 建立无延时概率与延时时间的多目标优化模型，确立代价函数与权重系数的构造方法，减小车辆延误风险；2) 构造描述路段关系的交通网络指示矩阵，研究路线直行程度的数学表达方式，据此设计优化算法以满足出行群体对于直行路线的喜好；3) 深入研究最大化无延时概率路径规划与分布式多智能体的结合方法，实时更新车辆行使意图及其预计通行时间，增强路径规划在随机交通网络中的动态响应。本项目所提的改进方案最终通过交通仿真软件以及实际车载导航进行验证，不仅能完善最大化无延时概率路径规划的理论体系，同时也能为路径规划算法的设计提供明确有效的研究方法。

路径规划是智能交通和智慧物流中一个广泛研究的问题。该问题通过优化路径来最大化或者最小化用户的某种目标(函数)，往往能够降低车辆的运行成本和减少对环境的污染，本质上为离散优化或者组合优化问题。本项目通过提出新的智能优化算法，分别求解交通中基于最大化不迟到概率的路径规划问题，和物流中基于最小化行驶路程(或时间)的路径规划问题。关于前者，分别提出了Q-learning和动态神经网络相结合的方法，以及Sub-gradient和多智能体相结合的方法，求解了单(辆)车和多(辆)车协作情况下最大化不迟到概率的路径规划问题，在北京和广州等城市路网上的测试表现出了优于已有方法的性能。关于后者，在深度强化学习的基础上，分别提出了用dual-aspect transformer自动为2-opt选定节点对，为LKH自动选定边的初始候选集，和multi-decoder相结合来提升解的多样性等方法优化物流中车辆对客户的服务或访问顺序，在仿真和公开数据集上展示出优于传统启发式算法的性能。此外，还将提出的深度强化学习方法推广到了与路径规划相类似的组合优化问题，如车间调度问题等。项目研究过程在智能优化这一方向上取得了一系列引人关注的成果，尤其是在用深度强化学习求解组合优化问题上。共完成相关学术论文21篇，其中SCI期刊论文15篇, CCF A类会议5篇(人工智能方向)，智能交通系统旗舰会议1篇。同时申请发明专利2项，培养研究生5名，获得中国机器人大赛助老服务机器人组冠军和救援机器人组季军。实际应用方面，所提的方法在真实交通路网和真实数据集上进行了测试。