带硬时间窗的车辆路径问题研究
随着经济的飞速发展,尤其是电商的快速崛起,物流配送行业以及生产制造企业的竞争愈加激烈,车辆路径问题作为其核心问题得到了广泛关注。随着客户对配送及时性要求越来越高,带时间窗的车辆路径问题,尤其是带硬时间窗的车辆路径问题成为了重点研究问题。
高效的车辆路径问题求解算法可以帮助运输以及配送企业降低运输成本,增加企业效益,并且为客户提供更满意的服务。带硬时间窗的车辆路径问题作为组合优化问题,自身存在复杂性,各约束条件之间相互制约,求解算法的研究成为了难点。
本文针对此问题进行了如下研究:(1)针对传统构造启发式算法容易产生冗余路径的缺点,设计了一种新的构造启发式算法。该算法包括三个主要阶段:初始路径构建阶段,插入阶段和交换操作阶段。
首先利用最少车辆数以及客户位置的凸包来确定用于构造初始路径的种子客户,而非传统构造算法中随机选择的方法。其次,不同于大多数的构造算法,此算法的插入阶段有两个插入过程:第一个过程中,未分配的客户被迭代地插入到初始路径中的最佳插入位置而不考虑约束,全部插入后再执行约束检验和调整操作;第二个插入过程中,通过考虑路径的空闲容量、客户的需求以及 ...