物流车辆路径算法的优化与设计.doc

1、物流车辆路径算法的优化与设计【摘要】：随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的50左右，所以降低物流成本首先要从降低物流配送的运输成本开始。一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化，这正是本文要研究的课

2、题。【关键词】：物流配送；路径；车辆路径问题(VRP)；MATLAB1 前言1.1 课题研究背景 运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。因此，自从 1959 年 Danting 和Ramser 提出车辆路径问题 (Vehicle Routing Problem，VRP)以来，VRP 便成为近年来物流领域中的研究热点。VRP 一般定义为：对一系列发货点和或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如

3、货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标 (如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。本文围绕 VRP 展开了研究，共包括五章内容。首先，本文收集国内外关于 VRP 研究的文献资料并进行整理、分类，详细介绍了 VRP 园内外研究现状，尤其对经典 VRP、有时间窗的 VRP(VRPTW)、动态 VRP(DVRP)、带能力约束的 VRP(CVRP)国内外研究现状分别展开了介绍：然后通过介绍物流配送在整个物流过程中具有的重要意义及我国物流配送的现状，说明了解决 VRP 的必要性及现实意义：建立了物流配送中 VRP的两种数学模型：利用回路表

4、示的 VRP 模型和利用运输成本表示的 VRP 模型；通过表格详细讨论了 VRP 的基本算法；最后，本文使用自然数编码、构造表示可行线路的染色体、类 PMX 交叉等方法及对适值函数加入惩罚项对标准遗传算法加以改进，并用 MATLAB 编程实现了本文提出的算法，以一个 VRPTW 实例分析证明了该算法的有效性。1.2 车辆路径的概念 车辆路径问题(VRP)一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定问题的目标( 如路程最短、费用最少、时间尽量少、使用车辆数

5、尽量少等)。目前有关 VRP 的研究已经可以表示（如图 1）为：给定一个或多个中心点（中心仓库，central depot）、一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化。图 1 VRP 示意图2 车辆路径问题算法综述目前，求解车辆路径问题的方法非常多，基本上可以分为精确算法和启发式算法 2 大类。2.1 精确

6、算法 精确算法是指可求出其最优解的算法，主要运用线性规划、整数规划、非线性规划等数学规划技术来描述物流系统的数量关系，以便求得最优决策。精确算法主要有：分枝定界法(Branch and Bound Approach)割平面法(Cutting Planes Approach)网络流算法(Network Flow Approach)动态规划算法(Dynamic Programming Approach)总的说来，精确性算法基于严格的数学手段，在可以求解的情况下，其解通常要优于人工智能算法。但由于引入严格的数学方法，计算量一般随问题规模的增大呈指数增长，因而无法避开指数爆炸问题，从而使该类算法只能有

7、效求解中小规模的确定性 VRP，并且通常这些算法都是针对某一特定问题设计的,适用能力较差,因此在实际中其应用范围很有限。2.2 启发式算法 由于车辆路径优化问题是 NP 难题，高效的精确算法存在的可能性不大(除非 P=NP)，所以寻找近似算法是必要和现实的，为此专家主要把精力花在构造高质量的启发式算法上。启发式算法是在状态空间中的改进搜索算法，它对每一个搜索的位置进行评价，得到最好的位置，再从这个位置进行搜索直到目标。在启发式搜索中，对位置的估价十分重要，采用不同的估价可以有不同的效果。目前已提出的启发式算法较多，分类也相当多，按 Van Breedam 的分类法，主要的启发式算法有以下几类：

8、构造算法、两阶段法、智能化算法。2.2.1 构造算法(Constructive Algorithm) 这类方法的基本思想是：根据一些准则，每一次将一个不在线路上的点增加进线路，直到所有点都被安排进线路为止。该类算法的每一步把当前的线路构形(很可能是不可行的) 跟另外的构形(也可能是不可行的 )进行比较并加以改进，后者或是根据某个判别函数 (例如总费用)会产生最大限度的节约的构形，或是以最小代价把一个不在当前构形上的需求对象插入进来的构形，最后得到一个较好的可行构形。这类算法中中最著名的是 Clarke 和 Wright在 1964 年提出的节约算法。构造算法最早提出来解决旅行商问题，这些方法一

9、般速度快，也很灵活，但这类方法有时找到的解离最优解差得很远。2.2.2 两阶段法(Two-phase Algorithm) 学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进，为此提出了两阶段法。第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止。Gillet 和 Miller 于 1974 年提出的 sweep算法，Christofides、Mingozzi 和 Toth 的算法以及 Fisher 和 Jaikumar 的算法都属于两阶段法

10、。一般第一阶段常用构造算法，在第二阶段常用的改进技术有 2-opt(Lin,1965)，3-opt(Lin Kernighan,1973)和 Or-opt (Or,1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。一些基于数学规划的算法也属于两阶段法，把问题直接描述成一个数学规划问题，根据其模型的特殊构形，应用一定的技术(如分解) 进行划分，进而求解己被广泛研究过的子问题 (Fisher 和 Jaikumar,1981)。在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的

11、某种判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性。此方法是目前成果最丰富、应用最多的一类方法。每一种方法讨论的情况不尽一致，适用范围也不完全相同。2.2.3 智能化算法(Intelligent Algorithm) 这类算法以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间。总体来看，尽管启发式算法能够在有限的时间内求出质量较高的解，但由于其搜索解空间的能力有所限制，因此经常无法达到预期的要求。20 世纪 90 年代以来，由于人工智能方法在解决组合优化问题中的强大功能，不少学者开始将人工智能引入车辆路线问题的求解中，并构造了大量

12、的基于人工智能的启发式算法(智能化启发式算法) 。智能化启发式算法从本质上讲仍然属于启发式算法，其基本思想是从一初始解开始，通过对当前的解进行反复地局部扰乱(Perturbations)以达到较好的解。目前，最常见的智能化启发式算法包括模拟退火算法(Simulated Annealing)、禁忌搜索算法(Tabu Search)、遗传算法(Genetic Algorithm)、蚁群算法(Ant Colony)和神经网络(Neutral Networks)方法等。2.3 VRP 中常见的约束条件 在 VRP 中，最常见的约束条件有:(1) 容量约束：任意车辆路径的总重量不能超过该车辆的能力负荷。

13、引出带容量约束的车辆路径问题(CapacitatedVehicle Routing Problem，CVRP)。(2) 优先约束：引出优先约束车辆路径问题(VehicleRouting Problem with precedence Constraints，VRPPC)。(3) 车型约束：引出多车型车辆路径问题(Mixed/Heterogeneous Fleet Vehicle Routing Problem，MFVRP/ HFVRP)。(4) 时间窗约束：包括硬时间窗(Hard Time windows)和软时间窗 (Soft Time windows) 约束。引出带时间窗(包括硬时间窗和软

14、时间窗 )的车辆路径问题 (Vehicle Routing Problem withTime windows，VRPTW) 。(5) 相容性约束：引出相容性约束车辆路径问题(VehicleRouting Problem with Compatibility Constraints，VRPCC)。(6) 随机需求：引出随机需求车辆路径问题(VehicleRouting Problem with Stochastic Demand，VRPSD)。(7) 开路：引出开路车辆路径问题(Open Vehicle RoutingProblem)。(8) 多运输中心：引出多运输中心的车辆路径问题(Multi

15、-Depot Vehicle Routing Problem)。(9) 回程运输：引出带回程运输的车辆路径问题(VehicleRouting Problem with Backhauls)。(10) 最后时间期限：引出带最后时间期限的车辆路径问题(Vehicle Routing Problem with Time Deadlines)。(11) 车速随时间变化：引出车速随时间变化的车辆路径问题(Time-Dependent Vehicle Routing Problem)。2.4 CVRP 问题描述及其数学模型 CVRP 的描述：设某中心车场有 k 辆车，每辆配送车的最大载重量 Q，需要对 n

16、 个客户(节点)进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i 的货物需求量是 qi (i=1,2,n)，且 qiQ。记配送中心编号为 0，各客户编号为 i(i=1,2 ,n)， cij 表示客户 i 到客户 j 的距离。求满足车辆数最小，车辆行驶总路程最短的运送方案。定义变量如下:建立此问题的数学模型：minz = cijxijk (2.2)约束条件：yki =1 (i=0,1,n ) (2.3)xijk=ykj (j=0,1,n k=1,2,m) (2.4)xjik=ykj (j=0,1,n k=1,2,m) (2.5)qiyki Q (k=1,2,m) (

17、2.6)3 物流配送车辆路径优化的基本理论与方法物流配送车辆路径优化问题一般可描述为；有一个配送中心，拥有 m 辆车辆，现在有，项货物运输任务需要完成，以 1，2，f 表示，已知任务 i 的货运量为 g。(f-1,2，)，求满足货运需求的费用最小的车辆行驶路径。在日常生活和生产实际当中，许多类似的问题都可归结为这类问题。如在图 11 所示的配送体系下，有一个配送中心，需向几个顾客运送货物，每个顾客对货物有一定的需求，运送货物的车辆在配送中心装货后发出，送到各个顾客处，完成任务后返回配送中心，如何确定满足用户需求的费用最小的车辆行驶路径。又如，若干厂家生产一些产品，需要运到配送中心，车辆从配送中

18、心出发，到各厂家去装货，装满后返回配送中心，在满足厂家发货需求的情况下，按什么路径行驶，可使总费用最少。货物通过配送中心中转的配送体系这两个问题的实质是相同的，只有装货任务或只有卸货任务。在货物较少的情况下，用一辆车完成一项任务时，车辆不能满载，这样，车辆的利用率较低，因此可考虑用一辆车完成多项任务。图 1，2 表示了五条车辆的行驶路径(图中矩形表示配送中心，小圆圈表示货物的运输任务)。关于物流配送车辆路径问题的优化方法比较多，本章着重介绍几种比较典型的方法，节约矩阵法和分派启发式算法。配送路径图3.1 节约矩阵法 节约矩阵法自提出后，得到了普遍的认同，它简单、易于理解、灵活性好，可分析性和交

19、互式特性都较好，不少算法的局部或是全部应用了节约矩阵算法。本节以某一配送中心为例，来介绍节约矩阵算法。假设某配送中的 13 个客户提供配送服务。每一个顾客在网络模型中用一个点代表，位置以（Xi，Yi)表示，顾客的需求用 ai 表示，0 表示配送中心。如表 l-l 所示。各结点位置如下图所示。设配送中心共有 4 辆车，每一辆车的承载能力是 200 单位。显然，运输费用与车辆的运输总距离紧密相连，并且配送路径方案有多种组合，不同的组合的总距离不同，成本费用也不同。节约法的主要步骤如下：(1)建立距离矩阵；(2)建立节约矩阵；(3)分配车次和路线；(4)将顾客排序。运算中的前面三步主要是安排车次，第四步则安排路线顺序以使运输的总距离最短。