有工作时限和时间窗约束的车辆调度问题研讨.pdf

第十七届中国过程控制会议论文集 有工作时限和时间窗约束的车辆调度问题研究 李桃迎 ，陈燕 （大连海事大学，经济与管理学院，辽宁 大连 116026） 摘要：本文对有工作时限和时间窗约束的配载车辆调度进行研究，利用多重旅行商问题的结构，对 C-K 节约算法进行改进，建立能够处理有工作时限和时间窗约束的启发式算法模型。通过求解实际情况下， 配载车辆调度问题的满意解，验证模型的可行性。 关键词：车辆调度；工作时限；时间窗约束；C-K 节约算法 0 引 言 车辆调度问题(VRP)可分为满载车辆调度和配载车辆调度两大类。满载车辆调度问题，就是每辆车 只给一个客户送货，并且目的地只有一个，通常最优路径就是能够满足广义费用的最短路，广义费用 通常是时间、费用和距离。对于满载车辆的调度，可以采用 Dijkstra 或 Floyd 算法求解。配载车辆调 度问题，就是一辆车给一个以上客户送货，货物的目的地有多个，需要多次卸货。调度人员不仅要指 派每辆车上所装载的货物，而且还要指派每辆车的行驶路线和停靠卸货顺序。因此求解过程比满载车 辆调度要复杂的多。 工作时限就是每辆车每天的最长工作时间，为了更好的体现工作时限，本文仅对一天内可以完成 配送的短途配载车辆调度问题进行研究。时间窗就是客户对货物送达时间的要求，通常用客户允许送 货车辆的最早到达和最迟到达的时间范围来描述。配载车辆调度问题,通常采用 Clarke 和 Write 提出 的 C-K 节约算法进行求解[1]。但是 C-K 节约算法无法处理工作时限、时间窗约束和车辆容量限制，本 文对 C-K 节约算法进行了改进，从而构造出处理配载车辆调度问题的启发式算法。 １ 配载车辆调度问题描述 配载车辆调度问题描述为：配送中心给 n 个客户送货，第 i 个客户的货物需求量为 g ，卸货时间 i 为 UT ，客户允许货物到达的最早时间为 ET ，最迟时间为 LT 。中心与客户、客户与客户两两间的运 i i i 输费用为 cij ，运输时间为 Tij （i,j=0,1,2,3,…,n, 其中，0 表示配送中心，1,2,3,…,n 为客户编号）。由于 每辆车都有容量 V （Vg ,i=1,2,3,…,n ）限制，每辆车不允许超载，而且必须在时间窗内把货物送到。 i 如果每辆车有工作时限 WTk （k=1,2,3,…,K ，K 表示配送车辆总数）。要求指派车并确定每辆车的配送 路线，使总的运输费用 Z 最低。 把配送中心和客户统一看作配送网络中的结点，并且每辆车的路径都是从配送中心（0 结点）出 发最终回到配送中心的闭环。假设在其中一条配送线路上，i 是j 前面并且相邻的结点，RT 、RT 分别 i j 是到达结点的时间，则它们之间的关系如下： RT RT +UT +T （1） j= i i ij 为了模型建立的需要，定义如下变量： 1 车 k 从点 i 行驶到点 j