论文部分内容阅读
车辆路径问题(Vehicle Routing Problem,简称VRP)是物流运输行业中的较实用的经典优化问题。随着我国物流行业的快速发展,问题优化难度随着问题规模的增加而增大,同时优化目标和场景变得更加复杂。本文针对我国押运行业的大规模车辆路径问题展开研究,结合实际的问题规模、目标及约束条件,建立有效的优化方法,提高相关行业的物流运作效率、降低运营成本并提高服务质量。大多数对车辆路径问题的研究都是基于经典的算例。经典算例都以最小化车辆数量和总行驶距离为优化目标;且只使用单一优化策略,无法满足复杂场景需求;默认行车速度在城市各个区域的恒定,忽略了行驶时间的优化;只限制晚到时间窗,而允许车辆早到,忽略了早到带来的运营成本。同时这些经典算例的规模相对较小,而押运行业的日常作业规模常接近300点。本文结合中国某押运公司的真实场景,对行业中的多种策略、多种目标和约束条件的大规模车辆路径问题进行建模,以最小化车辆数、总工作时间和总行驶距离为目标,同时考虑满足车容量、早到时间窗、晚到时间窗等约束。由于本文研究问题的规模较大且目标、约束复杂,导致求解难度较大,经典人工蜂群算法(ABC)和变邻域搜索算法(VNS)在优化结果和效率上都有一定的局限性。为了进一步提升相关元启发式算法的优化效果,本文创新性地设计了基于聚类算法与元启发式算法的混合算法。具体地,我们提出使用K-means算法的聚类结果为人工蜂群算法提供蜜源(初始解),而不是使用随机产生的蜜源。经典的Kmeans聚类算法只聚焦于地理位置上的相似性,不适用于带时间窗的车辆路径问题,所以本文针对性地对聚类算法进行改进。实验结果表明,该新型的人工蜂群算法在目标值和运算效率上都比传统的人工蜂群算法更优越。同样地,结合K-means聚类算法获得的初始解也能有效提高变邻域搜索算法的优化效果。最后,针对押运行业复杂的场景和多样的需求,本文提出三种不同的优化策略,分别是成本最小化策略、工作时间均衡策略、突发应对策略,分别在降低成本、降低被劫风险、应对突发事件上有很好的表现。