论文部分内容阅读
动态车辆路径问题(Dynamic Vehicle Routing Problem,DVRP)普遍应用于生活中的方方面面,例如快递配送、生鲜配送等;同时该问题对智慧交通和智慧城市的建设方面也起到极其重要的作用。作为在线控制的有效方法,滚动时域控制(Receding Horizon Control,RHC)策略可用于DVRP问题的求解。RHC策略通常采用均匀时间的窗口划分方式,无法根据模型的数据特征合理地划分时间窗口;且RHC只能对当前时间窗口内的客户进行服务,无法根据窗口结束时间附近的客户信息进行综合考虑配送方案。基于此,本文提出了两种不确定性滚动时域(Uncertain Receding Horizon Control,URHC)策略:(1)引入模糊集合中的隶属度函数,提出一种模糊滚动时域控制(Fuzzy Receding Horizon Control,FRHC)策略;(2)利用定积分求概率的性质,提出一种基于定积分的动态滚动时域控制(Dynamic Receding Horizon Control,DRHC)策略。第一步研究了一种基于模糊滚动时域控制策略优化动态车辆路径问题。针对RHC策略只能服务当前时间窗口内的客户这一规则,FRHC定义了客户与时间窗口的隶属度函数,用于重新表示客户与时间窗口的所属关系,并通过模糊阈值划分模糊时间窗口,采用遗传算法(Genetic Algorithm,GA)对时间窗口内的客户进行路径规划,并对国际标准测试集中的10个测试算例进行仿真实验。讨论了RHC与5组模糊阈值的求解效果,并找出FRHC策略的最佳模糊阈值。最后将RHC和FRHC分别与遗传算法(Genetic Algorithm,GA)、先到先得(First Come First Served,FCFS)、距离最近邻(NN)、按服务时间排序(FAST)、目标函数最近邻(NNF)5种算法相结合,讨论FRHC-GA与RHC-GA、FRHC-FCFS、RHC-FCFS……共10种DVRP求解方法的求解效果。实验结果表明,FRHC策略增加了时间窗口之间的信息交流,提高了时间窗口的邻域搜索能力;且FRHC-GA算法求解DVRP问题的配送方案最合理。第二步研究了一种基于定积分的动态滚动时域控制策略(Dynamic Receding Horizon Control,DRHC),以其优化预期服务时间服从正态分布的动态车辆路径问题(Dynamic Vehicle Routing Problem with Expected Service Time obeying Normal Distribution,DVRP-ESTND)。基于对生活中人们午餐习惯时间的考虑,提出了一种预期服务时间服从正态分布的动态车辆路径问题模型,即DVRP-ESTND模型。RHC策略常采用均匀窗口的划分方式,即平均滚动时域控制策略(Average Receding Horizon Control,ARHC),也有部分采用随机划分窗口的方式,即随机滚动时域控制策略(Random Receding Horizon Control,RRHC)。针对ARHC和RRHC策略在DVRP-ESTND模型下各时间窗口内的客户数量存在较大差异,容易造成车辆利用率低和客户等待时间长等问题,提出基于定积分的DRHC策略。该策略利用定积分求正态分布概率的特性,先求出系统时间内总概率值及时间窗口的平均概率值,再利用平均概率值计算出每个时间窗口的大小。通过统计分析三种策略的时间窗口内的客户数量,分析了DRHC策略的合理性。最后将DRHC、ARHC、RRHC策略分别与GA、FCFS、FAST、NN、NNF共5种算法相结合,对5组不同正态分布测试算例的仿真,实验结果表明:同等条件下,DRHC策略的解均优于其他两种策略的解,且DRHC-GA方法用于求解DVRP问题最合理有效。