论文部分内容阅读
带时间窗的车辆路径规划问题(VRPTW)是一个NP难题,求解十分困难。更为不幸的是,在物流配送过程中还经常发生对正常物流配送产生干扰和不良影响的事件。如何快速处理这些干扰事件,最大限度的减少干扰事件对企业整体物流配送工作的影响,就成了物流企业和学术界共同关注亟待解决的热点问题。本文基于干扰管理思想,以第三方物流配送应对经常受到干扰事件影响的管理问题为研究对象,重点探讨物流配送的干扰管理理论及方法,提出并建立干扰管理模型并研究相应的快速求解算法。本文的主要工作如下:(1)分析了对此类干扰事件进行多车互救的救援需求,从实际配送系统的运行特点出发,提出了多车互救策略,即“同路”、“邻近”和“增派”救援策略,简化了模型的求解。根据不同类型的配送系统车辆调度干扰管理问题的特点,提出了针对车辆调度干扰管理问题中备选车辆的搜索空间范围的简化策略,使搜索空间得到简化,并针对不同的需求对搜索空间进行分组,以简化问题的求解。(2)针对客户时间窗变动问题,提出基于干扰管理思想构建扰动恢复策略和方案。应用虚拟多车场实现车辆调度扰动恢复问题转化,提出车辆调度扰动恢复策略和扰动度量方法,以作为车辆调度干扰管理建模的基础;分析顾客时间窗和发货量变化造成的扰动并进行辨识,建立干扰管理模型,提出归一化处理办法对原始问题进行有效兼容;结合干扰管理模型的特点,改进基于顾客的编码表示方法,可以反映出车辆调度扰动恢复策略;根据干扰管理思想,设计遗传算法对干扰管理模型进行求解。给出了一个具有代表性的算例试验结果,算例结果及其分析表明干扰管理模型和遗传算法的有效性。(3)针对带回程取货车辆路径问题中客户需求变动问题,如出现新的服务请求、客户点减少及其货物量增加或减少等,基于干扰管理的思想,从定性和定量两个方面对这些干扰事件进行分析和度量,提出了车辆调度的扰动恢复模型;设计了基于邻近策略和增派策略的启发式算法对模型进行求解;并用实例数据进行了验证。(4)分析了带时间窗服务型车辆路径问题中物流配送运力受扰的救援需求,基于干扰管理思想建立了服务型车辆路径问题扰动恢复模型;对车辆受损的带时间窗服务型车辆路径问题提出了救援策略,并设计了混合使用以上救援策略的启发式算法;最后对实施这救援策略的效果进行了分析和比较。