物流配送是整个物流体系中最基本的业务环节，如何为客户提供满意的配送服务是物流企业必须关注的问题。在实际的物流活动中，配送车辆经常会碰到大量干扰事件，如交通事故、车辆故障、道路堵塞及天气变化等。从而导致物流配送时间延迟甚至中断，影响企业物流的效率与效益。因此，如何有效地处理此类干扰事件，使其对整个物流配送系统的影响最小，已经成为物流配送管理中的难点问题。根据Yu和Qi[1]对干扰管理的定义可知，干扰管理正是处理这类问题的方法论，是近年来学术界前沿性的热点和难点研究课题。针对这一问题，本文研究了有顾客时间窗的物流配送干扰管理问题，主要针对行驶时间延迟的物流配送展开研究，建立了问题的干扰管理模型，及其求解算法，并用实验验证了算法的可行性。 二、文献综述 本文研究主要涉及两个关键词，即物流配送干扰管理和有顾客时间窗的车辆路径规划问题(Vehicle Routing Problem with Time Window，VRPTW)[2]。 对于第一个关键问题，现有研究主演集中在模型及算法上。Huisman等提出用于解决具有旅行时间延迟的多车场车辆调度问题的聚类-重排算法[3]；丁秋雷等针对物流配送过程中车辆受到干扰而发生配送延迟的问题，运用干扰管理思想，对系统扰动进行判定，并提出干扰管理两阶段决策方法[4]；Potvin等针对新增客户需求和旅行时间干扰的问题，建立了综合考虑车辆行驶时间、对客户的服务时间延迟和服务结束时间最小化三方面的模型，并用插入算法求解问题[5]；王旭平等针对顾客时间窗和发货量变化的车辆调度干扰管理问题，从配送路径、配送成本和客户满意度3个方面进行干扰辨识和度量，建立了模型和研究了求解的遗传算法[6]；胡祥培等分析了干扰管理的两大类模型-网络模型和数学模型，并评述了求解干扰管理模型的精确算法和启发式算法[7]；张育宏等对道路发生交通堵塞而导致日常调度计划不能按时完成的情况进行了建模，并采用启发式算法对模型进行求解[8]。上述这些方法极大地丰富了物流配送领域车辆调度和路径规划模型与算法的研究成果。但是现有的模型与算法都是针对特定问题提出的，问题若变化，模型及算法会变得不可行，不能满足干扰管理建模与求解的需求。 对于第二个关键VRPTW关键问题。现有研究主要集中在各中启发式算法上。谢秉磊等提出了有时间窗的非满载车辆调度问题的遗传算法，将货运量约束和时间窗约束转化为目标约束，设计了基于自然编码的可同时处理软、硬时间窗约束的遗传算法[9]；王明春等从VRPTW原始问题出发，针对干扰发生的所有车辆均在车场的情况，对增加和减少客户、时间窗、客户需求和路线可行性的扰动等问题，以干扰发生后的新计划与原计划偏差最小为目标建立了扰动恢复模型，并利用禁忌搜索算法对问题进行求解[10]；侯立文等研究了求解带时间窗的客户需求可分条件下的车辆路径问题，在考虑客户需求可分及客户方和配送中心时间窗限制的前提下，重新构造了问题模型，并用蚂蚁算法求解问题[11]；王征等提出了顾客时间窗变化的多车场车辆调度干扰管理研究模型，以顾客时间窗变化这类干扰事件发生时间的问题状态为基础，以系统整体扰动最小化问目标，建立问题的目标规划数学模型，并提出邻域搜索算法[12]。上述这些研究方法，为VRPW领域的进一步发展奠定基础。已有研究中，启发式方法(如禁忌搜索算法、模拟退火算法和遗传算法等)有其独特的运行机制，不是搜索到局部最优解等就停止搜索，而是具有引导算法跳出局部最优解而转向全局最优解的功能。 上述文献的算法研究存在一定的局限性，如干扰发生时不能及时处理；对于难以满足时间窗的客户点实施舍弃策略，而对其重新配送等。针对以上存在的问题，本文结合干扰管理思想，对有时间窗的物流配送延迟问题进行研究，干扰发生时，通过局部调整实现物流配送路径的优化。 三、问题描述及模型 (一)VRPTW问题概述 有时间窗车辆路径问题(Vehicle Routing Problems with Time Windows，VRPTW)，是近年来各学者研究的重点。其基本定义可以描述为下：有客户若干，他们各自有不同数量的货物需求，由配送中心提供货物，由一个车队负责分配货物，组织适当的行车路线，目标是使客户的需求得到满足，并能在一定的约束条件下，达到目标(路程最短、使用车辆数尽量少、费用最少、耗费时间最少等)。在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时间窗(Hard Time Window)，硬时间窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时间窗(Soft Time Window)，不一定要在时间窗内到达，但是在时间窗之外到达必须要处罚，以处罚替代等待与拒收是软时间窗与硬时间窗最大的不同。 (二)物流配送受延迟的干扰管理问题描述 1.问题描述及假设 (1)问题描述如下：有一定数量的客户配送中心负责向各客户运输货物，假设配送中心的编号为0，有N个客户，编号分别为1，2，3，…，N。第i个客户的货物需求量为qi，卸货时间为UTi，客户允许到达的最早时间、最迟时间分别为ETi、LTi。中心与客户、客户与客户两两之间的运输费用Cij，运输时间为Tij(i=1，2，3，…，n)。已知每辆车的载重量都有Q的限制(Q＞qi，i=1，2，3，…n)，每辆车不允许超载，而且必须在规定的时间内把货物送到。如果每辆车有工作时限WTk(k=1，2，3，…k，k表示配送车辆总数)，要求指派车并确定每辆车的配送路线，使总的运输费用最低或是运输路径最短。本文研究车辆未在规定时间内到达，即配送时间延迟，系统发生干扰，此时需要及时处理干扰事件对系统的影响，以尽量小的扰动恢复系统的正常运行。若延迟则必须要惩罚。 (2)前提及假设： 1)配送中心有充足、同质的货物，且停有k辆用于服务顾客的车辆，每辆车的容量和最长在途行驶时间分别为Qk和Dk。
