论文部分内容阅读
随着社会的进步,我国物流产业不断发展,已经成为国民经济的重要组成部分。但是我国物流发展存在成本高、效率低的问题。物流配送环节是物流行业的一个重要环节,优化物流配送路径是降低物流运输成本、促进物流发展的关键。带时间窗的车辆路径问题(the vehicle routing problem with time windows,VRPTW)是规划物流服务路线的重要问题,具有重要的现实意义和实用价值。研究VRPTW的求解算法,既能降低物流运输成本,又可以提升物流配送效率,推动行业发展和社会进步。本文首先对多目标VRPTW问题展开研究,在此基础上分别对多车型带时间窗的车辆路径问题(the fleet size and mix vehicle routing problem with time windows,FSMVRPTW)和动态带时间窗的车辆路径问题(the dynamic vehicle routing problem with time windows,DVRPTW)的求解算法展开研究。研究的主要内容如下:(1)针对现有混合蚁群算法(hybrid ant colony optimization,HACO)在求解大规模客户的VRPTW时目标单一、收敛速度慢等问题,提出了一种改进的混合蚁群算法(improved hybrid ant colony optimization,IHACO)。IHACO首先在采用周边选择策略提升蚁群的选择效率,并提出一种首节点选择策略来加速算法收敛;其次在信息素叠加公式上增加了和车辆数有关的惩罚函数,使算法在优化距离的同时优化车辆数;最后将一种插入算法与2-interchange混合来提高算法的搜索能力和车辆利用率。实验部分从Solomon数据集上选取6个问题对算法进行测试,平均结果表明IHACO与HACO相比总距离降低了25.0%,车辆数降低了28.4%。(2)针对IHACO在面对多车型问题时无法高效的选择车辆类型的缺点进一步进行研究,将IHACO与并行拆分-重构策略相结合,提出一种改进算法(fleet size and mix-ant colony optimization,FSM-ACO)。FSM-ACO以最大容量的车量类型为约束构建初始解,以此降低初始解的车辆数。然后以最高车辆利用率为原则,将部分路径拆分为车型成本更低、车辆利用率最高的线路和客户集合。接着使用并行插入启发式算法综合考虑时间窗宽度、行驶距离、车辆利用率、车辆成本等因素将拆分出来的客户插入其他路径,实现解的重构。实验部分选取了标准数据集上的12个问题进行测试。与改进前的算法相比,FSM-ACO平均降低了16.06%的配送成本,同时提升了算法的收敛速度。(3)本文在IHACO的基础上分别从求解策略和求解算法两方面对DVRPTW展开研究。在求解策略方面,分别采用紧急订单策略和目标客户策略来解决基本时间片法来解决DVRPTW时存在应对紧急需求客户能力差、调度方案在相邻时间片过渡不平稳的问题。在求解算法方面,针对IHACO在DVRPTW中效率低的缺点,采用了信息素保护策略用来保存每个阶段的优质序列信息,提高了算法效率。实验部分在Lackner标准数据集中选取的10个测试问题上进行实验。结果表明,本文算法相较于改进前的算法在平均配送距离上降低了27.4%。