需求变动的带回程取货车辆路径问题研究

论文摘要

带时间窗的回程取货车辆路径问题(VRPB)是车辆路径问题的衍生问题。在实际生活中,带时间窗的回程取货车辆路径问题在物流配送路线中广泛存在,例如零售业、快件与货运和逆向物流等,是物流管理学科的前沿热点问题之一。另外,在实际的物流活动中,不可避免会出现各种干扰事件,它们打乱原有的初始行车方案,影响了取送货任务的按时完成,造成了服务效率和服务质量的下降。因此,对VRPB问题中出现的干扰事件进行快速有效的处理是十分必要和有意义的。本文针对带时间窗的回程取货车辆调度中的干扰问题,以干扰事件对系统的扰动最小为目标,基于干扰管理思想对需求变动的带时间窗的回程取货车辆路径问题(VRPBTW)进行研究。本文的主要研究工作如下:(1)定义了干扰发生前的静态VRPBTW问题及其模型,在此基础上分析了现实世界中的需求变动,辨识分析和度量了这些需求变动对系统产生的扰动,进一步建立了其扰动恢复模型。(2)先提出了求解原VRPBTW问题的混合禁忌搜索算法;针对需求变动问题的特点,设计了基于策略的启发式算法求解扰动恢复模型。(3)用标准测试数据实例验证求解原问题的混合禁忌搜索算法和求解干扰问题的基于策略的启发式算法,证明了所提出的干扰管理模型及算法的有效性。本文建立的需求变动的VRPBTW问题的扰动恢复模型,有效地降低了需求变动干扰事件对系统的行车计划的扰动,在很大程度上减少了对客户服务时间的延迟和物流服务提供商的成本损失,给实际的物流企业提供了一定的参考,也为今后研究其他类干扰的VRPBTW问题奠定了基础。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 问题的提出
• 1.1.1 研究背景
• 1.1.2 研究对象的界定
• 1.2 国内外研究现状
• 1.2.1 带回程取货车辆路径问题国内外研究现状
• 1.2.2 干扰管理及其模型与算法国内外研究进展
• 1.2.3 带回程取货车辆路径问题的干扰管理研究进展
• 1.2.4 国内外同类研究总结
• 1.3 本文的主要工作和结构
• 2 需求变动的VRPBTW问题的扰动恢复模型
• 2.1 原问题描述及其数学模型
• 2.1.1 原问题描述
• 2.1.2 原问题的数学模型
• 2.2 需求变动的VRPBTW问题的扰动辨识与度量
• 2.2.1 问题分析
• 2.2.2 系统扰动度量定性分析
• 2.2.3 系统扰动度量定量分析
• 2.3 驶离车场的车辆复位转化
• 2.4 需求变动的VRPBTW的扰动恢复模型
• 3 需求变动的VRPBTW扰动恢复模型的求解算法
• 3.1 路线构造法
• 3.2 路线改进——禁忌算法
• 3.2.1 禁忌搜索算法的要素
• 3.2.2 算法流程
• 3.3 需求变动的VRPBTW启发式算法
• 3.3.1 策略设计
• 3.3.2 算法流程
• 4 数据实验及结果分析
• 4.1 实验数据的选择
• 4.2 生成初始最优方案
• 4.3 处理干扰问题实现
• 结论
• 参考文献
• 附录 算法实现代码
• 攻读硕士学位期间发表学术论文情况
• 致谢