(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111479361.5 (22)申请日 2021.12.0 6 (71)申请人 西安邮电大 学 地址 710121 陕西省西安市长安区西长安 街西安邮电大 学 (72)发明人 孙家泽　耿扬　 (51)Int.Cl. G06Q 10/04(2012.01) G06F 30/18(2020.01) G06F 111/04(2020.01) (54)发明名称 一种带软时间窗的多目标车辆路径规划方 法 (57)摘要 本发明针对多目标路径 规划问题， 公开了一 种带软时间窗的多目标车辆 路径规划方法， 属于 智能交通领域。 该方法首先读取车辆路径数据 集， 构建路网拓扑图； 设定路径长度和兼容乘客 数为目标， 求解初始种群中所有的非支配解， 并 添加软时间窗来更新当前最优解； 采用0 ‑1随机 数进行状态转移概率判断和添加惩罚值全局更 新人流量的方法， 选择满足约束条件的最优解 集。 本发明提供了一种有效且 稳定的带软时间窗 的多目标车辆路径规划方法， 有助于探索一条在 满足约束条件的情况下， 使得路径长度更短、 兼 容乘客数更多以及运送时间尽可能短， 具有良好 的应用前 景。 权利要求书2页 说明书7页 附图1页 CN 114118616 A 2022.03.01 CN 114118616 A 1.一种带 软时间窗的多目标 车辆路径规划方法， 其特 征在于， 包括以下步骤： 步骤一： 获取轨迹数据集， 并使用N＝{0,1,...,i,...,m}表示配送中心和客户点， 其中 i∈N,0≤i≤m， 且i＝0表示配送中心， i＝1,...,m表示m个客户点， 使用(xi,yi)表示配送中 心和客户点位置坐标， 在配送中心使用最多M辆具有相同型号和最大负载容量为R的车辆完 成所有客户点的运送任务， ci表示第i个客户点的货物需求量， 并满足maxci≤R， 表 示单条路径上的最大兼容乘客数， 并保证C≤R， 使用[Ei,Li]作为配送中心和客户点的时间 窗， 其中Ei表示最早服务客户点i的时间， Li表示最晚服务客户点i的时间， 首先采用佳点集 产生客户规模为S的初始路径集PT， 其中S的可取值为25、 50和100， 并根据配送 中心和客户 点位置坐标、 货物需求 量、 时间窗信息和车辆最大兼容乘客数等构建路网拓扑图； 步骤二： 使用所得解的路径长度及其该路径上兼容乘客数作为目标函数f1与f2， 其中f1 的定义域为路网中单条路径起点至终点的最短距离， f2的定义域为R， 且其值域均为实数， 当f1的值越小f2的值越大时， 说明当前解更加优良， 对于满足约束条件的不同解T1和T2， 且 T1,T2∈PT， 求解PT中所有满 足f1(T1)＞f1(T2)并且f2(T1)＞f2(T2)， 或者f1(T1)＜f1(T2)并且 f2(T1)＜f2(T2)帕累托支配关系的非支配解个体， 并将求解得到的所有非支配解保存在外 部非支配解 集PT_set， 构建多目标 车辆路径问题模型； 步骤三： 在多目标车辆路径问题模型基础上设置软时间窗， 即将未按照客户点时间窗 约束到达导致的等待时间和延迟时间作为目标函数f3与f4， 其中f3、 f4的定义域为PT， 值域 为实数， 此时要求f3与f4的值尽可能小， 且保证车辆返回配送中心的时间不超出时间窗约 束， 使得当前解更优， 对于满足软时间窗约束的不同解， 根据帕累托支配关系求解 非支配解 并将求解得到的所有非支配解保存在外部非支配解集PT_ set， 设定客户规模S、 固定参数α、 调节参数θ、 β 、 w1、 w2及最大迭代次数， 令迭代次数j＝1， 开始迭代； 步骤四： 在第j次迭代时， 从非支配解集PT_set中随机选取解进行下一状态的选择， 累 加计算状态 转移概率， 通过生 成0‑1随机数判断状态 转移概率是否大于 当前累加概率， 选择 下一可取客户点， 根据公式(1)计算状态转移概 率， 其中τuv为边(u,v)上的人流量， ηuv为一个启发值， Jk(u)是车辆k在点u处时未服务的客 户集合， tu是车辆到达客户点u时的时间， [Eu,Lu]是客户点u的时间窗， 再通过参数w1和w2综 合考虑目标， 其中w1+w2＝1， θ和β 参数用于平衡启发值和人流量， 数值越大占比越大， 的 作用是计算状态转移 概率， 其中由人流量和启发值组成的部分指向路径较短且兼容乘客数 最多的边， 计算时间窗和总体时间部分指向符合时间窗约束的边； 步骤五： 在第j次迭代时， 从非支配解集PT_set中随机选取解更新路径中人流量， 即通 过公式(2)和公式(3)更新人流 量， τuv＝ τuv*(1‑α )                   (2)权　利　要　求　书 1/2 页 2 CN 114118616 A 2公式(3)由每次派送最优车辆的总路程决定， 即当前最优解， 添加如公式(4)所示的惩 罚值 以此奖励超过全局最优解 的超级解， 同时在公式(3)中采用对称处理， 即处理当前 最优路径中当前客户点时， 同时处 理当前最优路径中的对称客户点， 减少求 解时间； 步骤六： 判断终止条件， 迭代条件为当前迭代次数大于最大迭代次数， 若迭代终止条件 成立， 此时外部非支配解集为带软时间窗多目标车辆路径规划问题的最优解集， 输出该最 优解集并停止迭代； 否则， 令迭代次数j＝j+1， 返回步骤三。权　利　要　求　书 2/2 页 3 CN 114118616 A 3