时间窗变动的车辆调度干扰管理模型与算法

针对客户时间窗变动对原物流配送车辆调度方案造成干扰的问题,运用干扰管理思想,分析干扰事件对路径、成本和服务时间三个方面的影响,对其干扰程度加以度量;以该干扰事件对原方案造成的广义费用偏离最小为目标,建立客户时间窗变动的干扰管理模型,通过判断客户时间窗变动对原方案是否产生影响进行干扰辨识,并基于该干扰辨识结果,设计基于禁忌搜索新的调度算法;算例不仅验证了模型和算法的有效性,而且,敏感性分析也验证了其对各种不同价值货物的适用性。实验结果表明,本文提出的干扰管理模型可以全面地刻画干扰对原方案的影响,干扰处理方法优于全局重调度方法,且能够在更短时间内生成满意的物流配送车辆调度调整方案。

Disruption Management Model and Algorithm for Vehicle Scheduling with Time Window Changes

Vehicle scheduling problems(VSP)play a very important role in the area of urban logistics distribution. Traditionally, it assumes that customers’ time window remains unchanged during the execution of distribution plan for a VSP solution. In reality, however, there usually exist disruptions caused by the changing of customers’ time window, which make it difficult to conduct the predetermined distribution plan. In order to handle this problem, this paper measures the disruption degree by analyzing the impact of disturbance on path, cost and service time with the methodology of disruption management, and the disruption management model is established aiming at minimizing the generalized cost deviation to the current distribution plan. The disruptions are identified by means of judging whether customers’ time window changes can have an effect on the current plan. And a new dispatching method using tabu search algorithm in combination with the relocate operator to generate the neighborhood solution is designed based on the results of disruptions identification. The numerical example tests the effectiveness of the proposed model and algorithm, and moreover, the sensitivity analysis verifies the applicability of the proposed model to various values of goods. The experimental results show that the disruption management model can fully depict the disruption impacts on the current distribution plan, the proposed method is more practical than the global rescheduling method, and it can generate a satisfactory distribution vehicle scheduling plan in a shorter time.