【作者】 王旭坪；

【导师】 杨德礼；

【作者基本信息】 大连理工大学 ， 管理科学与工程， 2010， 博士

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

【Abstract】 Logistics distribution vehicle routing problem with time windows belongs to a typical NP-Hard problem. In addition, all kinds of disruptions occur in the actual logistic activities. These disruptions disturb the original optimal routing solution, impact on serving customers on time and make service quality and service efficiency decline. Therefore, it is very necessary and meaningful to quickly and efficiently handle disruptions which emerge during the logistics distribution vehicle routing problem.As a methodology of handling disruptions in real time, disruption management chiefly settles such kind of incidents that happens frequently. Based on the concept of disruption management, the recovery model and its algorithm are researched. The main researches in this paper are as follows:(1) After analyzed the differences and the settling demands in the sorts of vehicle routing problem with disruptions, three rescuing strategies, namely the same way rescue strategy, nearby rescue strategy and addition rescue strategy, are proposed to slove the disruption problem. Besides, according to the disruption management, the predigestion strategies are put forward to predigest the search space.(2) To tackle the disruption caused by the customer time window changes in the logistics, the disruption recovery solution is given based on the theory of disruption management. The transformation method for the disruption recovery of the vehicle routing problem is proposed based on multiple depots, and the disruption recovery strategies and the methods of deviation measurement are given, which is the basis of the disruption management modeling for the vehicle routing problem. For the disruption management of vehicle routing problem with the request changes of customers, the disruption is illustrated, the disruption management model is constructed, and the normalization processing for the model is given, making the model compatible with VRPTW. The chromosome code based on customer is ameliorated and the genetic algorithm is designed. A representative result and the analysis are given in this paper, and the experiment indicates the validity of the model and algorithm.(3) Demand changes in vehicle routing problem with backhaul are researched, such as new requests, requests of canceling service and increase/decrease in the quantity from backhauls. And based on disruption management thoughts, demand changes are analyzed, their impact on the original plan is measured, and a disruption recovery model for the problem is put forward. Then two strategies and heuristics algorithm are designed. Finally, benchmark data are used to test. And results show the effectiveness of the model and the algorithm.(4) From the disruption management point of view, the rescue requirements are analyzed, model for the problem with a broken-down vehicle in VRPTW with servicing distribution are proposed and the strategies are given. The algorithm founded on the strategies above is designed. Finally, the performance of these strategies are analyzed and compared.更多还原