论文部分内容阅读
车辆路径规划问题在很多领域包括物流行业运用广泛。随着各种辅助技术的成熟,比如卫星导航技术可以提供路线信息,计算机计算能力和存储能力的提高,高速信息网络的建成等都在促使车辆路径规划问题向更加智能更加高效方向发展。这样既能减少企业的物流成本同时能够提高顾客的体验。现实中顾客会随机提出送货需求,同时希望仓库能够在一个固定时间段将货物送达,此时间段是一个弹性区间,所以带软时间窗的动态车辆路径规划问题研究有现实意义。基于实际需求,本课题研究带软时间窗的动态车辆路径规划问题,针对问题中软时间窗和请求动态到达的约束条件设计了具体的解决方案。在软时间窗前一段到达会增加企业的时间成本,为此设计了一个线性惩罚函数;而在后一段到达会使顾客满意度降低,设计了一个指数惩罚函数。同时将车辆整个工作时间分解成一系列固定时间片来解决请求动态到达问题。本论文设计两个智能启发式算法:改进大领域搜索算法和混合粒子群算法。两个算法会对上个时间片到达的请求进行计算规划出路线,而将本时间片到达顾客点放在下一个时间片处理。改进大领域搜索算法针对软时间窗要求设计一个基于活动安排的贪心算法生成初始解,然后采用插入删除启发式策略进行优化。混合粒子群算法针对问题设计了针对性的粒子结构,并采用Grasp算法生成初始解,然后使用一个粒子速度位置启发式函数进行迭代求解,最后采用PathRelinking算法优化结果。本课题采用Solomon标准数据,该数据依据顾客点的分布分为六大类型,每个类型包含9到12个数据文件每个文件含有100个顾客信息。由于目前还没有研究相同问题的文献,所以将和一篇研究带硬时间窗的动态车辆路径规划问题文章进行对比。惩罚区间设定为20,同时计算六大类型数据平均结果。从结果来看废弃率很明显减少,能够服务的顾客数目增多。同时针对本论文提出两种算法分别在惩罚区间和废弃率,惩罚区间和路程,动态度和废弃率,动态度和路程四个方面进行分析。可以看到六大不同类型数据在几个变量之间的表现,进而得出变量之间的关系。为了直观的展示路径规划效果,本课题设计了基于百度地图的动态车辆路径规划系统。该系统分别采用百度地图API为平台,前端以JQuery技术为核心,后端以PHP和MySQL调用基于Python实现算法。前端可以采用顾客信息包括时间窗和需求等信息,经过处理之后会在前端展示规划好的路径,同时前端各个窗口也会实时显示整个路径,车辆以及司机的信息。