爱华网1引言 随着信息技术的发展，物流已从传统的运输服务发展成为以信息技术和管理为核心的综合物流系统。据统计，物流成本占产品销售价格的75%左右。其中，运输成本在整个物流成本中占有相当大的比例。因此，对物流配送车辆调度进行优化成为企业尤为关注的焦点。
以往对物流配送和车辆调度的研究当中，传统的做法依据静态配送车辆优化调度理论。但客观世界存在着大量的不确定性，需要一种可以求解动态车辆路径优化问题的方法。 2 动态车辆路径问题的相关理论 动态车辆路径问题的提出。车辆路径问题是物流管理当中最为典型的问题，1959年由Dantzig 和 Ramser[2]提出之后立即引起了很大反响。理论上讲，车辆路径问题属于组合优化问题，其对应的优化目标是在满足基本约束条件的前提下，使得配送货物的车辆的行驶总里程、使用的配送车辆数量、行驶时间的组合达到最小。 动态车辆路径问题的定义。静态车辆路径问题中，在对物流配送路径进行优化之前的相关信息（客户、车辆、客户请求、调度及其他相关信息等）是已知且固定的；而动态车辆路径优化问题中的很多信息都是不确定且不可预知的，可能还会有部分信息是模糊的、随机的，在进行路径规划时要根据实时信息对车辆路径进行实时的规划调整和优化。 3 动态车辆路径问题模型 动态需求特征分析。车辆在配送的路程当中存在着大量的不确定性：如拥堵、恶劣天气、车辆故障、客户信息改变等，这都将直接影响配送车辆行驶时间或者速度的变化，导致等待甚至改变路线，进而造成车辆的调度成本的增加。这些不确定使优化调度变得复杂，但当信息一旦明确已知，就可以把动态车辆调度问题转化为静态车辆调度问题来求解。 为了充分研究动态车辆调度问题的动态性特性，这里引入两个概念：关键点和时刻表。关键点是指在某个特定的时刻正在客户点进行服务或者正在前往客户需求点服务的配送车辆，每条配送行驶路线最多只有一个关键点。对已经服务过的客户需求点暂不考虑，而关键点之后的未服务的客户需求点称为未分配点，在接收到新的请求信息，或者配送车辆路况发生改变时，应该首先及时、明确地知道当前关键点以及未分配点的信息。 通过一个简单的实例清晰地展示了动态车辆路径问题的相关特性。 按照车辆的位置状态，可以将所有客户需求点的信息大致分为四类：预先安排已经完成服务的、正在进行服务或正在前往服务的路上，预先安排未进行服务的以及新的客户请求。对于预先安排并已经完成服务的客户点我们不再考虑。如图1所示，时刻1的点1、2、4、5为正在进行服务的客户需求点或者车辆正在前往服务客户需求点的路上，这些点就是所谓的关键点，此时，车辆处于工作状态中，该资源已经被占用。在时刻2，图1右边的点3、6为关键点。此时，新的需求点7也是我们考虑的。 基于时刻表的动态车辆路径问题模型。动态车辆路径问题的模型是建立在规定的工作时间内（即调度周期）的,而该模型选择以每天的工作时间为时刻表，新的客户请求产生的时刻，动态车辆路径问题都会面对一个新的情况，当新的请求信息明确时，动态的调度问题即转变为静态。 式（3-7）配送服务的车辆从配送中心的出发时间必须在配送中心工作时间窗开始后； 式（3-8）最晚的配送车辆须在配送中心关闭前返回，该车辆可以晚于时间窗到达各客户需求点； 式（3-9）、（3-10）为0、1决策变量。 工作时间内，不同时刻的新客户请求的加入，可以在时刻表的基础上建立动态车辆调度问题模型，其中初始时刻的模型和传统静态模型一样，配送中心是关键点，而所有初始需求构成了未完成任务集合，此时的解是初始调度解。 4 总结 出于对实际应用中各种不确定性的考虑，本文讨论了在调度决策执行过程中新的客户需求不断产生的环境下的动态车辆路径问题，对预先的客户请求进行预先安排和优化，并对新的客户请求进行实时处理，把接收到的动态信息在信息明确的情况下转化为静态车辆路径优化问题，并在传统静态车辆调度问题的基础上，以成本最小化为最终目标，建立了基于时刻表的动态车辆调度模型。 可以应用到商品货物以及邮件的速运、公交车以及出租车的服务、零售业的配送、生产计划以及紧急服务等各个领域。因其广泛的应用价值，动态车辆路径问题必然是今后物流配送企业发展的方向。
