带硬时间窗的车辆路径问题研究.doc

带硬时间窗的车辆路径问题研究随着经济的飞速发展,尤其是电商的快速崛起,物流配送行业以及生产制造企业的竞争愈加激烈,车辆路径问题作为其核心问题得到了广泛关注。随着客户对配送及时性要求越来越高,带时间窗的车辆路径问题,尤其是带硬时间窗的车辆路径问题成为了重点研究问题。高效的车辆路径问题求解算法可以帮助运输以及配送企业降低运输成本,增加企业效益,并且为客户提供更满意的服务。带硬时间窗的车辆路径问题作为组合优化问题,自身存在复杂性,各约束条件之间相互制约,求解算法的研究成为了难点。本文针对此问题进行了如下研究:(1)针对传统构造启发式算法容易产生冗余路径的缺点,设计了一种新的构造启发式算法。该算法包括三个主要阶段:初始路径构建阶段,插入阶段和交换操作阶段。首先利用最少车辆数以及客户位置的凸包来确定用于构造初始路径的种子客户,而非传统构造算法中随机选择的方法。其次,不同于大多数的构造算法,此算法的插入阶段有两个插入过程:第一个过程中,未分配的客户被迭代地插入到初始路径中的最佳插入位置而不考虑约束,全部插入后再执行约束检验和调整操作;第二个插入过程中,通过考虑路径的空闲容量、客户的需求以及未分配客户与可行路径之间的距离来重新插入未安排客户。此外,对于不能插入到任何可行路径的客户,引入了交换算子的操作代替传统算法中直接创建新路径的操作。(2)针对本文提出的构造启发式算法在处理地理位置上集聚的客户以及具有宽松时间窗和较大车辆容量的问题时,得到的结果存在行驶距离较长的问题,本文利用烟花算法能够进行信息交互分配资源的优点,设计了一种基于改进型烟花算法的带时间窗的车辆路径问题优化技术。此算法首先通过本文提出的构造启发式算法(不执行交换操作)产生初始烟花,即车辆路径解决方案,然后根据每个烟花适应度值的不同差异化计算每个烟花爆炸能够产生的火花数量。此外,使用交叉重组的方式生成爆炸火花,以完成算法中的邻域搜索过程;且引入了变异火花来增强种群的多样性以提高算法的搜索效率。(3)分别对本文提出的新的构造启发式算法和基于改进型烟花算法的带时间窗车辆路径问题的优化技术使用Matlab仿真软件在Solomon100个客户的测数据集上进行实验验证,将获得的结果与网络公布最优结果进行比对分析,同时将两种算法的结果进行比较,以验证提出算法的有效性。(4)最后,用Flexsim仿真软件求解实际配送案例,并与提出算法的运行结果进行比较,以验证算法的可行性。