论文部分内容阅读
小批量多批次配送已成为现代物流配送发展的一大趋势，而车辆路线问题是其关键问题。目前配送通常将正向物流和逆向物流单独配送，这样会导致较高的车辆空载率。为了节约资源，降低成本，本文将二者整合起来，研究正逆向物流一体化车辆路线问题。分别从确定性、模糊性和动态三方面研究了该类问题的模型和算法。论文的创新点主要体现在对车辆路线问题的拓展及相应有效算法的设计，具体包括以下几个方面：
(1)租赁条件下的第三方物流多车型硬时间窗车辆路线问题研究。建立了以车辆租赁费用和运行费用最小为目标的模型，并提出了结合模拟退火法的混合遗传算法。该算法以优先满足最小费用车型的策略来分配多车型车辆，并采用客户直接排列的方法以实现车辆数的变化。算例分析表明，该混合遗传算法具有较好的搜索能力和求解稳定性，按最小费用分配车辆策略可为第三方物流企业车辆的租赁决策提供重要依据。
(2)大规模同时集散货物路线问题的算法设计研究。首先应用分形理论中的空间填充曲线法求解初始解，接着将当前解分解成几个独立的路线子集合，再用新禁忌搜索算法求解每个路线子集合，最后将子集合求得的最好路线组成新的当前解，其中新禁忌搜索算法集成了大量的邻域搜索方法，并采用了重起和扰动策略。数据实验表明，该算法取得了新的最好解，为同时集散货物路线问题的求解提供了新思路。
(3)业务繁忙环境下带时间窗的同时集散货物路线问题研究。以车辆数、运输里程和完成运输任务总时间最小为目标建立了多目标模型，并提出了基于路线集合划分的分解迭代算法以解决大规模问题。数据实验表明，该算法能有效解决带时间窗的单向车辆路线问题和集散一体化的双向车辆路线问题，为物流配送提供了有力的决策依据。
(4)配送车辆数和车辆工作时间有限的多车次同时集散货物路线问题研究。以车辆数和运输里程最小为目标建立了多目标模型，提出了允许不可行解的搜索算法。该方法能同时解决路线安排和路线分配的问题，其中路线安排采用了4种邻域搜索方法和重起策略，路线分配采用了初次分配和二次调整策略。算例分析表明，该方法能有效地找到满意解，采用多车次安排路线比单车次安排路线更加经济合理。
(5)逆向需求模糊的同时集散货物路线问题研究。建立了基于模糊置信度理论的多目标模型，并提出了基于模拟的改进禁忌搜索算法来求解该模型。该算法用模拟的方法计算路线失败值，在路线搜索中采用路线内部改善和路线间改善两类邻域操作，而且采用了重起策略。算例表明，该算法优于传统的扫描算法，并且正逆向物流整合与分别运输相比其运输费用显著减少。
(6)逆向需求动态出现的混合集散货物路线问题研究。该问题中逆向需求出现的时刻、位置以及要求服务的时间和发货量事前是完全未知的，且具有时间窗约束。将问题的求解过程分为静态和动态两阶段，每阶段分别用改进记录更新算法求解：采用随机大邻域搜索法及重起和扰动策略来提高解的质量，并通过约束邻域搜索范围和设计常量可行性检查两种策略来减少计算时间。数据实验表明，该算法是快速有效的，将动态出现的逆向需求实时整合到已有路线中，比单独安排动态需求的配送更经济。