车辆调度问题优化算法研究

2007-12-11 14:36:36|  分类： 学习 |举报 |字号 订阅

车辆优化调度问题是现代物流系统优化中关键的一环，也是开展电子商务活动中不可缺少的内容。对车辆优化调度理论与方法进行系统研究是构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。

车辆优化调度问题最早是由Danzig和Ramser于1959年提出的，由于这一问题的理论涉及多学科，很多实际问题都可以归于这一类问题，应用前景广阔，所以一直成为运筹学与组合优化领域的研究热点问题。最近几十年来，对车辆优化调度问题的研究取得了很多有意义的成果，已经广泛用于生产、生活的各个方面，如报纸或货物投递、出租车调度和包裹快递等。............

关键词：车辆调度优化算法，PDPTW问题，独占性，动态，多目标，禁忌搜索算法，遗传算法，滚动时域调度算法

Optimal Algorithm Research of Vehicle Scheduling Problem

Abstract

Vehicle optimal scheduling problem is the key part of modern logistics system, and also the indispensable portion of the e-business activities. To study the theory and method of vehicle optimal scheduling problem is the basis of constructing the integrated logistics system, establishing modern scheduling system, developing the intelligent transportation system and developing the e-business.

Vehicle optimal scheduling problem was firstly proposed by Danzig and Ramser in 1959. For the theory of this problem is involved in many disciplines and many practical problems can be induced into it, the problem has been always being the hot problem in operations research and component optimal domains. In the last several decades, many significant achievements on this problem have been achieved and used extensively in many aspects in real life and production, such as the newspaper or good delivery, taxi scheduling and parcel delivery courier, and so on.

Key words: vehicle scheduling optimal algorithm, PDPTW, exclusive, dynamic, multi-objective, tabu search algorithm, genetic algorithm, rolling horizon scheduling algorithm

第一章   绪  论

现代物流系统是由运输、存储、包装、配送、装卸、搬运等若干个相互依赖、相互制约的子系统集合而成的具有特定功能的有机整体。其中车辆运输系统是物流中一个重要的直接与消费者相连的环节，对运输车辆进行优化调度，可以提高物流经济效益、实现物流科学化，可以说，对车辆调度问题的理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。

1.1 车辆运输调度问题概述

车辆运输调度问题是最早由Dantzig和Ramser于1959年首次提出的，由于这一问题涉及多学科，很多实际问题的理论抽象都可以归结于这一问题，应用前景广阔，所以一直成为运筹学与组合优化领域的研究热点。最近几十年来，对车辆运输调度问题的研究取得了很多有意义的成果，已经广泛用于生产、生活的各个方面，如报纸或货物投递、出租车调度和包裹快递等。

车辆运输调度问题一般定义为[李军01]：对一系列装货点和（或）卸货点，规划适当的行车路线，使车辆有序地通过它们，满足一定的约束条件（如时间窗口约束、车辆容量限制、车辆行驶里程限制、司机最大工作时间限制等），达到一定的目标（如车辆行驶路程最短、运输费用最少、使用车辆数最少，服务质量最高等）。

自从车辆运输调度问题于1959年提出后，[Bodin81]、[Bodin83] 、[Assad88] 和[Desrocherg90]等许多学者对车辆运输调度问题从不同角度按不同标准进行了多种分类：

按任务特征分，有纯装货问题和纯卸货问题（车辆在所有任务点只装货或卸货，即集货和卸货问题）及装卸货混合问题（每个客户有不同的装货点和卸货点，即集货、送货一体化问题）。

按任务性质分，有对弧服务问题（如邮递员问题）和对点服务问题（旅行商问题）以及混和服务问题（如交通车辆路线安排问题）。

按车辆载货状况分，有满载问题（货运量不小于车辆容量，完成一项任务需要不只一辆车）和非满载问题（货运量小于车辆容量，多项任务合用一辆车）。

按车库数目分，有单车库问题和多车库问题。

按车辆类型分，有单车辆类型问题（所有车辆容量相同，类型相同）和多车辆类型问题（执行任务车辆的容量和类型不完全相同）。

按车辆对车库的所属关系，分为车辆开放问题（车辆可以不返回其出发车库）和车辆封闭问题（车辆必须返回其出发车库）。

按优化目标问题来分，有单目标问题和多目标问题。

按不同的数学模型，分为TSP问题（Traveling Salesman Problem, 旅行商问题，以下简称TSP问题），VRP问题（Vehicle Routing Problem, 车辆路由问题，以下简称VRP问题）和PDP问题（Pickup and Delivery Problem, 装卸货问题，以下简称PDP问题）。

1.2 车辆运输调度系统中的两个热点问题模型

1.2.1 VRP问题模型

VRP问题（车辆路由问题）是车辆运输调度中最常见的问题之一，是一个经典的运筹学问题，在交通、物流和资源配置等方面有着广泛的现实意义。该问题是组合优化领域中比较复杂的热点问题，是著名的TSP问题（旅行商问题）的一个特例，因而也是NP-hard问题。

VRP问题是用来为一些有容量限制的车辆确定其访问客户的最优路径，每个客户必须被访问一次且只能访问一次。我们可以这样理解VRP问题：现有一个（或多个）仓库和多个客户，仓库有车队（车辆数量确定或不确定），车辆有容量限制，每个客户有一定量的货物要送到仓库，问仓库怎样派车才能使运输成本最小。VRP问题就是为了设计最优路线来满足从一个或多个仓库向许多地理位置分散的客户提供运输服务，同时必须满足一系列的约束，包括车辆容量约束、货物类型约束、总服务时间窗约束等。

假设描述VRP问题的数学符号如下：

VRP问题的上述模型中，式（1-1）是VRP问题的目标函数，式（1-2）规定了从仓库出发的路径的最大数目是 ，式（1-3）限定了每条路径的起点和终点都必须是仓库，式（1-4）和式（1-5）规定了每个客户都被访问了一次而且只被访问了一次，式（1-6）是车辆的容量约束。

VRP问题的目标函数一般为总运输成本最小，常用的目标函数有以下几种：

1. 最小使用的车辆数目

2. 最小总服务时间

3. 最小车辆总运输距离

4. 最小客户不满意度

其中，客户不满意度通常是其等待时间和超出正常服务时间的线性函数，其中超出正常服务时间是指实际运输时间和客户要求运输时间的差。

1.2.2 PDPTW问题模型

PDPTW问题是VRP问题的一个很有用的扩展，近段时期引起越来越多的研究者的注意，许多新的优化思想和优化方法被引入到此问题中，并产生了一定的影响。

PDPTW问题（Pickup and Delivery Problem with Time Windows，带时间窗口的装卸货问题）是为一个车队寻找最优的运输路径来满足所有客户的运输需求。车队的每一辆车从车库出发，沿优化的路径为客户服务并最终返回车库。每一辆车都给定最大容量和出发、返回车库。每个运输需求指定一个装货点、一个卸货点和运输货物量。装货点、卸货点以及车库都有时间窗口。车辆必须在规定的时间窗内访问装、卸货点。也就是说，在运输网络中，已知待服务的装、卸货点和车库的位置和时间窗口、车辆的最大容量以及运输货物量的前提下，设计车辆运输路径，使运输成本最小化。

PDPTW的解是路径的集合，每一辆车对应一条路径，包括以下方面：

需要用到的车辆数目；即，有多少条路径

每辆车访问每一个点的顺序以及时刻

假设每辆车的类型相同，以下给出PDPTW问题的数学描述[Dumas91]：设 是所有客户的集合， 是集合 中所有客户的数目。每一个客户都指定一个装货点和一个卸货点，因此装、卸货点的个数都为 。不妨设客户 的装货地点为点 ，其对应的卸货地点则为点 ，设点0和点 表示车库。因此，  = 是装货点集合， = 是卸货点集合。 是除了车库点以外所有点的集合。 = 是包括车库在内的所有点的集合。对每个客户 ，要求将重量为 的货物从装货点 运到卸货点 。设点 的时间窗口为 ， 和 分别是该点的最早和最晚服务时间，即点 只能在此时间窗口内接受服务。 是车库的时间窗口，它表示车辆离开车库的最早时间和返回车库的最晚时间。 是车辆 的集合， 是集合 中的车辆数目。 是车的最大容量。对于不同的两个点 ， 和 分别代表从点 到点 的运输时间和运输代价。设点 的服务时间为 ，由于 可以很容易的并入到运输时间 中[William00]，所以本文将不考虑客户的服务时间。

PDPTW问题的数学模型中用到三个变量：二进制变量 ， ；时间变量 ；以及货物变量 。如果车辆 从点 行驶到点 ，二进制变量 为1，否则为0。时间变量 为车辆 在点 的服务开始时间。货物变量 为车辆 在服务了点 后的所装载的货物量。

PDPTW问题中，要求满足的约束条件主要有以下几种：

1) 时间窗口约束：车辆必须在规定的时间窗内服务装货点或卸货点。如果车辆在 之前到达点 ，必须在点 等待到 才能开始装卸货。车辆在 时刻之后到达点 ，则无法按时完成该点的装卸货任务，因而是不允许的。

2） 访问约束：车辆到客户指定的装货点装货，然后运输到相应的卸货点卸货。每一个点都必须被一辆车服务且只能服务一次。

3） 车库约束：车辆必须从车库出发到某一装货点，最后从某一卸货点返回车库。车辆返回车库后不允许再次出发。

4） 成对约束：一个客户需求的装货点 和其对应的卸货点 必须被同一辆车访问。

5） 次序约束：客户需求的装货点 必须在对应的卸货点 之前被访问。

6） 容量约束：任何时刻车辆所装货物量之和不能超过车辆的最大容量。

上述约束是PDPTW问题中常见的几种约束条件。另外还会根据实际情况的要求增加一些附加约束，如车辆类型与货物类型之间的类型匹配约束，司机的最大工作时间约束等。

PDPTW问题的优化目标也是总运输成本最小。一般来说，与总运输成本有关的费用包括：

车辆的固定代价，是运输代价中最重要的部分，要最大可能的减少使用的车辆数。

与车辆行驶距离有关的代价

PDPTW问题优化的目标函数就是这两个费用的加权和。设单位车辆的固定成本为 ，单位运输距离的成本为 （一般说来， ），则PDPTW问题的优化目标为：

(1-18)

因此，要使目标函数较小，就要尽可能的减少使用的车辆数，以及减少每辆车行驶的距离。

1.3 车辆运输调度问题的求解算法

车辆运输调度问题的求解算法有很多种，但究其本质来讲，基本分为最优化算法和启发式算法两大类。

1.3.1 最优化算法

最优化算法，也称之为精确算法，就是指能够通过有限的计算和推理得到优化问题的最优解的算法。在车辆运输调度问题中，所谓最优化算法就是找到一组路径集合，使得其目标函数值比其它任何一组可行路径集合的目标函数值更好。

常用的最优化算法主要有：分枝定界算法、动态规划算法和整数规划。通常情况下，NP-hard问题的精确解法的计算量较大，而且随着问题规模的增大计算量会呈爆炸式的增长，因此在实际问题中最优化算法的应用范围有限。

1.3.2 启发式算法

启发式算法是通过对过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观推断或试探的方法。启发式方法要求分析人员必须运用自己的感知和洞察力，从与研究问题有关而比较具体的模型及算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径。

用启发式方法求解问题时强调“满意”。常常是得到满意解，决策者就认为可以了，而不去追求最优解。之所以这样是因为：

(1) 很多问题不存在严格的最优解（如目标之间存在矛盾的多目标问题），此时对目标的满意性比最优性更能描述人们的选择行为。

(2) 得到某些问题最优解的成本太大。

(3) 从实际出发，有时探求问题的最优解没有意义。

对于NP-Hard问题，人们自然会想到启发式的算法。启发式的算法就是根据某种启发式的信息对已知的可行解进行改善，通过若干次的迭代获得相对满意的解。和精确算法相比，启发式的算法不能保证得到全局最优解，但是实现起来相对简单。

由于车辆运输调度问题是NP-hard问题，而现实中该问题规模一般很大，因此想以能够接受的运算速度找到最优解是不可能的。而启发式算法可以在相对短时间内找到“满意”解，为此研究人员把精力主要放在构造高质量的启发式算法上[James99]。目前已提出的求解车辆运输调度问题的启发式算法很多，主要分为经典启发式算法和现代启发式算法两类。

1. 经典启发式方法

经典启发式方法，如路径构造算法、路径改进算法等，能给出大规模问题的可行解，但解的质量依赖问题的特征。

1). 路径构造算法

根据一些准则，每次将一个未服务的客户插入到现有路径中去，直到所有客户都被安排进路径中为止[Desrochers 91]。常用的插入准则是根据某个判别函数（如车辆行驶距离或者运输成本等），以最小代价把一个不在当前路径上的客户插入到当前路径，最后得到一个较好的可行路径。

插入算法是最早提出来解决TSP问题和VRP问题的路径构造算法，该方法的特点是速度快和灵活，但有时找到的解离最优解的距离较远。

2). 路径改进算法

通过对路径构造算法的研究，认为由其求得的运输路径还可以被进一步改进，为此提出了路径改进算法。在路径改进算法中，第一阶段得到一个初始可行解，第二阶段通过对客户的调整，在始终保持解的可行性的情况下力图向最优解*近，每一步都产生另一个可行解以代替原来的解，使目标函数值得到改进，直到目标函数不能改进为止[Christofides93] 、[Renauld96]。一般来说，第一阶段常用路径构造算法构造一个初始可行解，第二阶段常用的改进技术有 交换、 交换和 交换法[Jun94]、[Lin73]，以改进第一阶段得到的初始解。

在改进求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断能力，并且根据经验，把主观的估计加到优化模型中去。

2. 现代启发式算法

现代启发式算法包括禁忌搜索算法（Tabu Search）[Glover 89] 、[Glover90] 、[Battiti94] 、[Barnes 95] 、[Carlton95] 、[Carlton96] 、[Christophe97] 、[William00]、[Cordeau03a]等，模拟退火算法（Simulated Annealing）[Osman93]，遗传算法（Genetic Algorithm）[Goldberg89] 、[Schaffer85]、[Horn94] 、[Cieniawski95]、[Murata96] 、[Ishibuchi98]、[Jeffery03]等，和神经网络（Neural Network）方法[Wilson88]。禁忌搜索和模拟退火在求解VRP问题和PDPTW问题中已经取得了较好的效果，而神经网络和遗传算法在TSP问题中应用较多。

1.4 本文问题涉及的一些数学概念

1.4.1 组合优化问题

本文研究的车辆运输调度问题是著名的组合最优化(Combinatorial optimization)问题，具有 - 共性。

组合最优化问题可以用数学模型表示为[邢文训99]：

其中， 为目标函数， 为约束函数， 为决策变量， 表示有限个点的集合。

一个组合最优化问题可用三参数( )表示，其中 表示决策变量的定义域， 表示可行解区域 = , 中的任何一个元素称为该问题的可行解， 表示目标函数。满足 = 的可行解 称为该问题的最优解。组合优化问题的特点是可行解集合为有限点集。由直观可知，只要将 中有限个点逐一判别是否满足 的约束和比较目标值的大小，该问题的最优解一定存在并可以得到。

现实生活中大量优化问题是从有限个状态中选取最好的一个，因而是组合优化问题，其中不少问题随着规模的增加，计算量呈指数增长，它们属于NP-hard问题。

1.4.2 NP-hard问题

一个求解实例 的算法的基本计算总次数 同实例 的计算机二进制输入长度 的关系常用符号 = = 表示，它的含义是：求解实例 的算法的基本计算总次数 是实例输入长度 的一个函数，这个函数被另一个函数 控制，即存在一个函数 和一个常数 ，使得

(1-18)

式(1-18)表示算法在求解实例 时，所用的基本计算总次数可以被一个函数值 控制。 的函数特性决定了基本计算总次数的性能。

1) 多项式算法

假设问题和解决该问题的一个算法已经给定，若给定该问题的一个实例 ，存在多项式函数 ，使得(1.1)成立, 称该算法对实例 是多项式时间算法；若存在 为多项式函数且对该问题任意的一个实例 ，都有(1.1)成立，则称该算法为解决该问题的多项式时间算法。特别对优化问题，当一个算法为求解该优化问题最优解的多项式时间算法，则称为该优化问题的多项式时间最优算法。

2) 多项式问题

对于给定的一个优化问题, 若存在一个求解该问题最优解的算法、一个多项式函数 和常数 ，使得(1.1)对给定优化问题的任何一个实例成立，则称给定的优化问题是多项式时间可解问题，或称多项式问题，所有多项式问题集记为 (polynomial)。

3) NP问题

如果一个问题的每一个实例只有“是”或“否”两种答案，则称这个问题为判定问题。称有肯定答案的实例为“是”实例，称答案为否的实例为“否”实例或非“是”实例。

若存在一个多项式时间函数 和一个验证算法 ，对一类判定问题 的任何一个“是”的判定实例 ，都存在一个字符串 是 的“是”答案，满足其输入长度 不超过 ，其中 为 的输入长度，且算法 验证 为实例 的“是”答案的计算时间 不超过 ，则称判定问题 是非多项式确定的，简记为 （nondeterministic polynomial）。在不混淆的情况下，用 表示所有非多项式确定问题的集合。

4) NP-hard问题

已知判定问题 和 ，若存在多项式函数 和 ，使得对 的任何实例 ，在多项式时间内构造 的一个实例，其输入长度不超过 ，并对 的任何一个算法 ，都存在问题 的一个算法 ，使得 算法调用 算法并使得计算时间   ，其中 和 分别表示算法 和 的计算时间与实例输入长度 之间的关系，则称问题 多项式归约（reduction）为 问题。

若 中的任何一个问题可在多项式时间归约为判定问题 ，则称 为 难或 - 。

判定问题  （ - ），其定义为   且 中的任何一个问题可在多项式时间内归约为 。于是有   - 。

对于一个新的组合优化问题，当找不到解它的有效算法时，就可以把注意力转向设法证明它是NP-hard问题，这样就避免了浪费精力去找有效算法，而采取另外可供选择的途径。

1.5 本文的工作和结构安排

前面简要介绍了车辆运输调度系统的一些相关问题， 近期对这些问题的研究十分活跃，许多新的优化思想和优化方法都被用来求解该类问题，并产生了一定的影响。但是国内对这些领域的研究还较少，要能够在实际问题应用还需要艰苦的工作。但是这些研究给未来车辆运输的优化调度奠定了基础。

在已有研究工作的基础上，本文主要研究了一类车辆运输调度问题：PDPTW问题及扩展问题的优化调度算法，分析了此类问题的性质并分别提出了其静态问题和动态问题的启发式求解算法；本文最后对多目标车辆运输调度问题进行了研究，提出了多目标混合遗传算法来求解多目标车辆运输调度问题。