带软时间窗约束的车辆路径问题的混合算法研究及其应用.doc

带软时间窗约束的车辆路径问题的混合算法研究及其应用车辆路径问题(VehicleRoutingProblems,VRP)是一个NP难问题,是物流领域中具有重要理论和实际意义的问题。在现实生活中,有很多问题可以抽象为VRP问题,如银行押款车的行驶路线、快递分发包裹、工业垃圾回收、校车接送学生、餐馆送餐等。选择合理的物流配送方案,可以降低企业物流开支,节约成本,提高效率,加速货物的流通过程,赚取更多的利润,对于一个企业的成败具有关键性意义。在中国物流业快速发展的今天,对VRP问题的研究愈发重要。带时间窗约束的VRP问题(VehicleRoutingProblemswithTimeWindows,VRPTW)是在基本VRP问题的基础上衍生而来,有着很高的研究价值。本文致力于研究带重量约束和软时间窗约束的VRP问题(CapacitatedVehicleRoutingProblemswithSoftTimeWindows,CVRPSTW)。长期以来,国内外许多学者对这个问题进行了大量的研究和阐述,产生了许多优秀的算法。在他们工作的基础上,利用VRP问题的数学模型,本文提出了一种分布式的多阶段混合启发式算法,目标是在合理的时间内取得较好的结果。本文的主要工作包括:第一,实现单机版的多阶段混合启发式算法,包括使用模拟退火算法(SimulatedAnnealing,SA)对车辆数目进行优化,使用禁忌搜索算法(TabuSearch,TS)对违反时间窗代价和路线总行程距离进行优化。在求解过程中,使用了多种不同的邻域生成方法,包括对部分元素的交换和重置的小邻域生成法、基于摧毁和重建思想的大邻域生成法,以减少在局部最优附近的重复搜索。加入自适应存储(AdaptiveMemory,AM)算法,当搜索陷入瓶颈时,从AM中产生新的邻域搜索中心,开始新一轮迭代搜索,使得搜索及时跳出瓶颈并向着好的方向前进,保证搜索的有效性和多样性。第二,基于Spark分布式框架,实现算法的分布式版本,比较单机版本与分布式版本的解的质量和求解效率。第三,开发实现一个AndroidAPPdemo,将VRPSTW问题与当下活跃的外卖配送相结合,将算法理论与实际应用相结合。文中采用Solomon的benchmark数据集进行算法测试。实验结果表明,提出的SA算法和TS搜索算法有着不错的表现;分布式的混合算法取得了良好的效果,保证能在较短的可接受时间内取得不错的结果。APPdemo的开发,将理论研究与实际应用有机地结合在一起,在肯定理论研究重要性的同时,有效地解决实际问题。