基于协作的车辆路径问题研究

论文摘要

车辆路径问题(VRP)是根据需求约束条件和物流系统的设备、设施条件,对一系列有服务需求的顾客点,安排费用最小(时间、里程等)的车辆配送线路,是物流配送的关键内容之一。由于合理的路径规划能减少物流服务成本,提高服务质量,从而提高自身竞争力,因此VRP的研究得到了研究人员和物流企业的高度重视。已有的VRP文献中,绝大部分采用的是车辆不协作的路径策略,即车辆在运输时,都是独立运输,车辆之间没有协作。当物流配送的顾客和道路信息为不确定信息时,不协作的路径策略可能会带来巨大的资源浪费,而车辆相互协作运输不但能充分利用途中车辆的运输能力,还能缩短顾客的服务时间,从而减少运输成本,提高服务质量。随着通讯技术和优化技术的发展,车辆实时调度成为未来的发展趋势,基于协作的VRP也将成为研究趋势之一。本文以不确定信息下的物流配送问题为研究对象,提出了若干车辆协作的路径策略,对这些策略进行了理论分析和计算试验,证明了这些策略的有效性。全文主要内容如下:提出了一系列基于车辆协作的路径策略,包括基于两辆车、基于三辆车、基于四辆车的路径策略,并给出了策略的路径里程、装卸载次数和运输时间的数学分析。用仿真实验的方法对策略的使用效果进行了对比分析。探讨了大规模车辆路径问题的改进的SWEEP协作路径策略,提出了策略的车辆任务分配目标规划模型和启发式解法,采用模拟的方法对不协作策略和改进SWEEP策略的车辆数量、路径里程进行了对比分析。提出了大规模车辆路径问题的全局协作策略,策略分为两阶段,第一阶段用SWEEP算法分组,并在组内协作;第二阶段不同组之间进行协作。理论分析和计算结果显示了该策略的有效性。探讨了交通线路可能被毁坏情况下的路径决策问题,提出了基于不协作和基于协作的两阶段优化模型,给出了不同决策准则下的决策方法。鉴于车辆路径问题求解的复杂性,有针对性地研究了基于协作的车辆路径问题的启发式算法,设计了不同策略下的禁忌搜索算法、遗传算法,并对算法的适用性进行了比较分析。通过全文研究发现:与不协作策略比较,车辆协作的路径策略能不同程度地减少车辆行驶里程、车辆装载次数和路途行驶时间,是减少大规模物流配送

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 研究存在的问题
• 1.4 问题的提出
• 1.5 本文的研究内容和创新
• 1.6 主要创新点
• 第二章 SVRP 的模型及路径策略
• 2.1 SVRP 的性质
• 2.2 SVRP 的机会约束模型（CCP）
• 2.3 路径调整模型（SPR）
• 2.4 动态规划模型
• 2.5 多辆车协作的 SVRP 的路径策略
• 2.6 小结
• 第三章 基于协作的 SVRP
• 3.1 协作的概念及相关数学分析
• 3.2 两辆车的协作策略
• 3.3 三辆车的协作策略
• 3.4 四辆车的协作策略
• 3.5 本章小结
• 第四章 大规模物流系统的车辆协作策略
• 4.1 大规模物流问题研究现状
• 4.2 改进的 SWEEP 策略
• 4.3 分区协作策略
• 4.4 大规模问题的简化
• 4.5 小结
• 第五章 完全不确定信息下的 VRP
• 5.1 决策准则
• 5.2 完全不确定信息下的 VRP 决策过程
• 5.3 考虑路网可靠性的 VRP 多阶段规划模型
• 5.4 线路方案的效用评价值
• 5.5 乐观准则下的简化定理
• 5.6 悲观准则下的简化定理
• 5.7 协作 VRP 问题的简化
• 5.8 禁忌搜索算法
• 5.9 示例
• 5.10 小结
• 第六章 协作车辆路径问题的算法
• 6.1 遗传算法
• 6.2 禁忌搜索算法
• 6.3 遗传-禁忌混合搜索算法
• 6.4 大规模车辆路径问题的启发式算法
• 6.5 本章小节
• 第七章 总结与展望
• 7.1 主要的工作
• 7.2 主要创新点及结论
• 7.3 需要进一步研究的问题
• 参考文献
• 发表论文及参与科研情况说明
• 致谢