论文部分内容阅读
在互联网以及电子商务飞速发展的时代,加快发展现代物流行业逐渐成为提高经济效益的重要手段。如何优化运输过程、最大可能的利用车辆装载空间,对降低运输成本、提高运输效率有着至关重要的作用。因此,车辆路径问题和装箱问题是物流行业关心的重点问题,一直以来受到国内外学者的关注,二者的结合问题更是具有重要的实践价值。目前大部分的研究主要集中在带三维装载约束的车辆路径问题(Vehicle Routing Problem with Three-dimensional Loading Constraints,3L-CVRP),而对于其他形式的车辆与装箱一体化问题,相关课题的研究涉及较少。本文主要研究带三维装载约束的取送货车辆路径问题(Pickup and Delivery Problem with Three-dimensional Loading Constraints,3L-PDP),这一问题属于3L-CVRP的延伸,满足现实生活中的多种运输场景,具有重要的研究意义。本文针对3L-PDP问题,提出混合启发式算法:对于路径部分,主要采用基于模拟退火框架的大邻域搜索算法进行优化,并结合禁忌策略增加搜索的多样性;对于装箱部分,采用基于块结合的基础启发式算法寻找可行装载方案。装载可行性判断作为一个约束条件被集成到路径优化过程中。实验结果表明了算法在路径优化方面的有效性,部分解的质量能够优于目前最新的研究成果。本文同时还对混合启发式算法进行改进,构建并行多邻域合作的大邻域搜索算法,并将算法在Spark分布式平台上实现。多个大邻域搜索过程分散在不同的Spark集群节点中独立运行,有效增加搜索范围。集群控制节点通过解的集合(Solution Pool)收集并更新各个节点获得的最优解,保证算法的收敛性。结果表明并行化的算法具有更好的稳定性与高效性,能够有效提升整体解的质量。