带软时间窗约束的开放式车辆路径问题及其应用

摘要

车辆路径问题是运输组织优化中的核心问题之一。本文将首先对车辆路径问题的特点、分类以及求解算法的研究现状等进行综述。
　　 带软时间窗约束的开放式车辆路径问题在实践中广泛存在。它与基本的车辆路径问题的主要不同点，一是不要求车辆完成运输任务后返回原出发点，或者是若要求返回原出发点，则沿原去程路线返回，二是客户希望车辆在给定时间窗内进行服务，如果违背了时间窗，则须支付惩罚。本文对带软时间窗约束的开放式车辆路径问题从理论上进行了研究。通过利用所研究的问题的特点，设计了七种邻域结构、并在搜索过程中引入一种随机多样性等，从而构造了一个求解该问题的禁忌搜索算法。从用随机方式产生的初始解出发，用该禁忌搜索算法对56个标准测试问题进行求解。与相关文献中的结果进行了比较。通过比较，显示了本禁忌搜索算法的优势。
　　 在理论研究的基础上，本文运用禁忌搜索算法对长沙市市内邮政运输趟班数据进行了环形和辐射形两种邮路形式、共四种邮车路径规划方案的案例测试。通过比较各种规划方案的结果，显示出通用启发式算法对于依靠经验的传统手工编排趟班的明显优势，表明了在物流发达、经营点众多、分布范围较广、车辆行驶距离较长的大中城市，相对于环形邮路，辐射形邮路具有很大的优势。
　　 多车场车辆路径问题广泛存在于多个行业之中，对其研究不仅具有实际应用价值，更是研究供应链集成与协调的基础。多车场带软时间窗约束的开放式车辆路径问题则比单车场带软时间窗约束的开放式车辆路径问题求解更加复杂。本文以客户直接排列方法表示多车场带软时间窗约束的开放式车辆路径问题中的解；对于多车场的处理，则是随机从车场集合中选一个车场并从中派出一辆车，该车完成配送任务后再回到距离这条路径上的最后一个配送点最近的车场。如此循环，直到所有配送任务完成。这样，就从整体上对多车场带软时间窗约束的开放式车辆路径问题进行了求解。
　　 分析了农产品物流起点——农产品物流集货运输，将其归结为一类各车辆最后客户相同且确定的带软时间窗约束的不完全开放式车辆路径问题，并提出了一个遗传算法用于求解。通过对提供第三方物流服务的农村汽车货运企业的农产品物流集货运输问题进行模拟，构造了一个农产品物流集货运输路径问题算例，进行了算例测试，获得了满意的优化效果，表明了本遗传算法的优势。