[物流车辆路径算法的优化与设计]

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

【摘要】：随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的50％左右，所以降低物流成本首先要从降低物流配送的运输成本开始。

一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化，这正是本文要研究的课题。

【关键词】：物流配送；路径；车辆路径问题(VRP)；MATLAB

1 前言

1.1 课题研究背景

运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。因此，自从1959年Danting 和Rams er 提出车辆路径问题(Vehicle Routing Problem ，VRP) 以来，VRP 便成为近年来物流领域中的研究热点。

VRP 一般定义为：对一系列发货点和／或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等) 。本文围绕VRP 展开了研究，共包括五章内容。首先，本文收集国内外关于

VRP 研究的文献资料并进行整理、分类，详细介绍了VRP 园内外研究现状，尤其对经典V RP 、有时间窗的VRP(VRPTW)、动态VRP(DVRP)、带能力约束的VRP(CVRP)国内外研究现状分别展开了介绍：然后通过介绍物流配送在整个物流过程中具有的重要意义及我国物流配送的现状，说明了解决VRP 的必要性及现实意义：建立了物流配送中VRP 的两种数学模型：利用回路表示的VRP 模型和利用运输成本表示的VRP 模型；通过表格详细讨论了VR P 的基本算法；最后，本文使用自然数编码、构造表示可行线路的染色体、类PMX 交叉等方法及对适值函数加入惩罚项对标准遗传算法加以改进，并用MATLAB 编程实现了本文提出的算法，以一个VRPTW 实例分析证明了该算法的有效性。

1.2 车辆路径的概念

车辆路径问题(VRP)一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定问题的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等) 。

目前有关VRP 的研究已经可以表示（如图1）为：给定一个或多个中心点（中心仓库，cen tral depot ）、一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化。

图1 VRP 示意图

2 车辆路径问题算法综述

目前，求解车辆路径问题的方法非常多，基本上可以分为精确算法和启发式算法2大类。

2.1 精确算法

精确算法是指可求出其最优解的算法，主要运用线性规划、整数规划、非线性规划等数学规划技术来描述物流系统的数量关系，以便求得最优决策。精确算法主要有：

分枝定界法(Branch and Bound Approach)

割平面法(Cutting Planes Approach)

网络流算法(Network Flow Approach)

动态规划算法(Dynamic Programming Approach)

总的说来，精确性算法基于严格的数学手段，在可以求解的情况下，其解通常要优于人工智能算法。但由于引入严格的数学方法，计算量一般随问题规模的增大呈指数增长，因而无法避开指数爆炸问题，从而使该类算法只能有效求解中小规模的确定性VRP ，并且通常这些算法都是针对某一特定问题设计的, 适用能力较差, 因此在实际中其应用范围很有限。

2.2 启发式算法

由于车辆路径优化问题是NP 难题，高效的精确算法存在的可能性不大(除非P=NP)，所以寻找近似算法是必要和现实的，为此专家主要把精力花在构造高质量的启发式算法上。启发式算法是在状态空间中的改进搜索算法，它对每一个搜索的位置进行评价，得到最好的位置，再从这个位置进行搜索直到目标。在启发式搜索中，对位置的估价十分重要，采用不同的估价可以有不同的效果。目前已提出的启发式算法较多，分类也相当多，按Van Breedam 的分类法，主要的启发式算法有以下几类：构造算法、两阶段法、智能化算法。

2.2.1 构造算法(Constructive Algorithm)

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

构造算法最早提出来解决旅行商问题，这些方法一般速度快，也很灵活，但这类方法有时找到的解离最优解差得很远。

2.2.2 两阶段法(Two-phase Algorithm)

学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进，为此提出了两阶段法。第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止。Gillet 和Miller 于1974年提出的sweep 算法，Chr istofides 、Mingozzi 和Toth 的算法以及Fisher 和Jaikumar 的算法都属于两阶段法。一般第一阶段常用构造算法，在第二阶段常用的改进技术有2-opt(Lin,1965)，3-opt(Lin Kernighan,19

73) 和Or-opt (Or,1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。

一些基于数学规划的算法也属于两阶段法，把问题直接描述成一个数学规划问题，根据其模型的特殊构形，应用一定的技术(如分解) 进行划分，进而求解己被广泛研究过的子问题(Fisher 和Jaikumar,1981) 。

在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性。 此方法是目前成果最丰富、应用最多的一类方法。每一种方法讨论的情况不尽一致，适用范围也不完全相同。

2.2.3 智能化算法(Intelligent Algorithm)

这类算法以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间。

总体来看，尽管启发式算法能够在有限的时间内求出质量较高的解，但由于其搜索解空间的能力有所限制，因此经常无法达到预期的要求。20世纪90年代以来，由于人工智能方法在解决组合优化问题中的强大功能，不少学者开始将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法(智能化启发式算法) 。智能化启发式算法从本质上讲仍然属于启发式算法，其基本思想是从一初始解开始，通过对当前的解进行反复地局部扰乱(Perturbations)以达到较好的解。目前，最常见的智能化启发式算法包括模拟退火算法(Simulated Annealing) 、禁忌搜索算法(Tabu Search) 、遗传算法(Genetic Algorithm) 、蚁群算法(Ant Colony) 和神经网络(Neutral Networks) 方法等。

2.3 VRP 中常见的约束条件

在VRP 中，最常见的约束条件有:

(1) 容量约束：任意车辆路径的总重量不能超过该车辆的能力负荷。引出带容量约束的车辆路径问题(CapacitatedVehicle Routing Problem ，CVRP) 。

(2) 优先约束：引出优先约束车辆路径问题(VehicleRouting Problem with precedence Constr aints ，VRPPC) 。

(3) 车型约束：引出多车型车辆路径问题(Mixed/Heterogeneous Fleet Vehicle Routing Probl em ，MFVRP/ HFVRP) 。

(4) 时间窗约束：包括硬时间窗(Hard Time windows) 和软时间窗(Soft Time windows) 约束。引出带时间窗(包括硬时间窗和软时间窗) 的车辆路径问题(Vehicle Routing Problem wit hTime windows ，VRPTW) 。

(5) 相容性约束：引出相容性约束车辆路径问题(VehicleRouting Problem with Compatibility Constraints ，VRPCC) 。

(6) 随机需求：引出随机需求车辆路径问题(VehicleRouting Problem with Stochastic Deman d ，VRPSD) 。

(7) 开路：引出开路车辆路径问题(Open Vehicle RoutingProblem) 。

(8) 多运输中心：引出多运输中心的车辆路径问题(Multi-Depot Vehicle Routing Problem) 。

(9) 回程运输：引出带回程运输的车辆路径问题(VehicleRouting Problem with Backhauls) 。

(10) 最后时间期限：引出带最后时间期限的车辆路径问题(Vehicle Routing Problem wit h Time Deadlines) 。

(11) 车速随时间变化：引出车速随时间变化的车辆路径问题(Time-Dependent Vehicle Routi ng Problem) 。

2.4 CVRP 问题描述及其数学模型

CVRP 的描述：设某中心车场有k 辆车，每辆配送车的最大载重量Q ，需要对n 个客户(节点) 进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i 的货物需求量是q i (i=1,2,…,n)，且q i

:

建立此问题的数学模型：

约束条件：

minz = cij x ijk (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)

qi y ki Q (k=1,2,…,m) (2.6)

3 物流配送车辆路径优化的基本理论与方法

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

货物通过配送中心中转的配送体系

这两个问题的实质是相同的，只有装货任务或只有卸货任务。在货物较少的情况下，用一辆车完成一项任务时，车辆不能满载，这样，车辆的利用率较低，因此可考虑用一辆车完成多

项任务。图1，2表示了五条车辆的行驶路径(图中矩形表示配送中心，小圆圈表示货物的运输任务) 。

关于物流配送车辆路径问题的优化方法比较多，本章着重介绍几种比较典型的方法，节约矩阵法和分派启发式算法。

配送路径图

3.1 节约矩阵法

节约矩阵法自提出后，得到了普遍的认同，它简单、易于理解、灵活性好，可分析性和交互式特性都较好，不少算法的局部或是全部应用了节约矩阵算法。

本节以某一配送中心为例，来介绍节约矩阵算法。

假设某配送中的13个客户提供配送服务。每一个顾客在网络模型中用一个点代表，位置以（Xi ，Yi) 表示，顾客的需求用ai 表示，0表示配送中心。如表l-l 所示。各结

点位置如下图所示。

设配送中心共有4辆车，每一辆车的承载能力是200单位。显然，运输费用与车辆的运输总距离紧密相连，并且配送路径方案有多种组合，不同的组合的总距离不同，成

本费用也不同。节约法的主要步骤如下：

(1)建立距离矩阵；

(2)建立节约矩阵；

(3)分配车次和路线；

(4)将顾客排序。

运算中的前面三步主要是安排车次，第四步则安排路线顺序以使运输的总距离最短。

各结点位置图示

3.2 安排车次和路线

距离矩阵和节约矩阵求出后，不同的车次和路线的组合安排会发生不同的费用，这里主要阐述优化各种路径的方法，以求出合理的车次安排。

这罩有一个反复循环的过程，首先每个顾客被安排在不同的路线，如果两条路线的载重量不超过车的载重量，我们就可以将两条路线合并起来，如若合并第三条路线时，也没有超过车的载重量时，将第三条路线与刚才的合并路线重新合并成新的路线，如此反复

下去，直至不能合并为止，或超过了车的载重量。由节约矩阵得到如表1-4所示的修正路线。

4 物流配送中VRP 的数学模型及其求解算法

4.1 物流配送中VRP 的提出

考虑这样一类问题：假定有一个配送中心，需向几个顾客运送货物，每个用户对货物有一定需求．运送货物的车辆在配送中心配装发车后，把货物送到各用户处，如何确定费用最小的车辆行使路线? 又如，零售商将若干生产商生产的产品运到其配送中心，车辆从配送中心出发，到各个厂家去装货，装满后运到配送中心。在满足厂家发货要求的情况下，按什么路线行使，可使总费用最小? 这两个问题的实质是相同的，如果货物量大，车辆为完成任务需满载运行，则按最短路行驶即可。若货物量较少，用一辆车完成任务时，车辆不能满载，利用

率较低，则可考虑用一辆车完成多项任务。这种将各分散用户组织起来、联合送货的方式就是配送运输的基本特点。笔者利用Clarke —Wright 节约法“三角形的一边必定小于另外两边之和”的思想说明，在配送运输方式下，通过将多个用户联合在一条路线上，并为车辆选择优化的绕行次序，可以降低成本，提高效率。

假定有许多需要同样货物的需求点，配送中心P 派若干货车去送货，每个需求点去一次。其中，每条路线受到时间、货物量限制。设i 、j 是这些需求点中的任意两点。若每个点都有一辆车从P 出发去送货，然后回到仓库(如图3．1所示) 。假设两点之间往返距离相同，则到i ，j 行走的总距离D 为

如果连接i ，j ，让一辆车去送货(如图3．2所示) ，则到i ，j 行走的总距离L 为到仓库(如图

3．1所示) 。假设两点之间往返距离相同，则到i ，f 行走的总距离D 为

配送方式下节约的里程为

-

研究VRP 一般存在以下几个前提条件：

①被配送的是可混装的物资：

②各个用户的所在地和需求均己知；．

③从配送中心到各个用户间的运输距离已知：

④配送中心有足够的资源以供配送，并且拥有足够的运输能力。

VRP 方案则明确规定符合约束条件时应派出的车辆数、车型和各车辆的具体行车路线。实施VRP 运输方案，可以保证按时、按量完成当日的运输任务，又可以使总行程最少。图3．3与图3．4将传统运输方式和配送运输方式下车辆行驶路线的效果进行了对比。

4.2 物流配送中VRP 的数学模型 4.2.1 物流配送中VRP 描述

某配送中心对一定地域范围内的客户(需求点) 进行物流配送服务，每个需求点所需货物量均较小(小于车辆容量) ，且每个需求点距配送中心以及各需求点间的距离为已知。若配送中心的货物量都能满足客户的需求，且配送中心可以通过自有或租用或与运输公司合作的方式有足够的运力可供调配，要求每辆送货车的一次载重量不自}超过其额定载重量，且每辆车的总运行距离有一定上限。为了提高车辆的利用率，如何安排车辆路线和进行车辆调度既能满足配送任务，又使车辆运行总里程最短。也就是说，为了完成运输任务，配送中心需派若干辆车，全部送货路线为几条大的路线(回路) 组成：每辆送货车从配送中心出发后．沿一条覆盖若干用户的大路线(回路) 送货，然后返回配送中心。此时，VRP 方案应包括两个相关的环节：

a ．哪些客户要被分配到一条回路上（即哪些客户的货物应该安排在同一辆车上) ； b ，每条路线上客户的绕行次序。

4.2.2 物流配送中VRP 数学模型

一个典型的VRP 模型可以用回路表示，也可以把时间、路程、花费等转化成运输成本来表示，其基本原理都是相同的：

(1)利用回路表示：

a ．基本条件

现有m 辆相同的车辆停在一个共同的源点(或物流中心)P, 它需要给n 个顾客提供货物，顾客为V1，V2，…，Vn, 。并且源点和客户的坐标已知。

b ．模型目标

确定所需要的车辆的数目N, 并指派这些车辆到一个回路中, 同时包括回路内的路径安排和调度，使得运输总距离S 最小。

C ．约束条件

(2)车辆完成任务之后都要回到源点V 0。

(3)车辆不能超过最大载重量Wi 和最大行驶长度Li 的限制。

d ．数学模型

假设d i(j-1)i，表示第i 辆车对应的路线中顺序排列的第j-1个客户和第j 个客户之间的距离；d i(li)(0)表示第i 辆车对应的路线中第I i 个客户与源点V 0之间的距离。由此可以建立如下的数学模型：

模型中：

(3-la)为目标函数，即：使车辆在完成配送任务时的总运行距离最短；

(3-2a)为车辆的能力约束，即每个子回路中客户的需求总量不超过车辆的最大载重量，保证某台车所访问的全部客户的需求量不能超过车辆本身的载重量：

(3-3a)表示每个子回路中车辆的运行长度不超过其最大行驶早程：

(3-4a)表示每辆车对应的客户数不超过总的客户数；

(3-5a)表示所有参与运行的车，其所服务的客户总数与实际的客户数相等，即保证每个客户都得到服务；

(3-6a)表示每辆车服务的对应客户集合；

(3 7a) 表示每个客户在同一时刻只能由一辆车来进行服务；

(3-8a)表示第，辆车是否参与服务：

(3-9a)表示不超过所提供的最大车辆数的限制。

(2)利用运输成本表示：

设某配送中心可用车辆集合为qk(k=1，…m)，q k 为车辆的载重量，用户为j ，j=1，…n(为了与后文自然数编码保持一致，本文假定配送中心的代码为0) ，gi 为用户j 的货运量。由于是可混装的运输，因此有magi

为构造数学模型，定义变量：

得到配送调度模型如下：

4.3 物流配送中VRP 的基本算法

正如绪论的介绍，VRP 具有多种变化型态。事实上，根据研究重点的不同，VRP 存在多种分类方式，但总的来说，在VRP 中．最常见的附加条件有：

(1)能力约束。与每个客户或城市对应的需求是个非负的值，任意车辆路径的总重量不能超过该车辆的能力负荷。

(2)任意路径所含城市数的上界为q 。

(3)总时间约束。任意路径的长度不能超过预先给定的界c ：该长度由车辆在城市间的旅行时间t 和在该路径里的每个城市的停留时间所构成。

(4)时间窗口。必须在时间区间里访问城市i ，并允许在城市i 等待。

(5)多个城市间存在优先级关系．必须在访问城市i 之前访问城市j 。

5 遗传算法在VRP 中的应用

5.1 遗传算法简介 5.1.1 遗传算法的引入

遗传算法(GenetiC Algorithm ，GA) 是一种有效地解决最优化问题的方法。它最先是由John Holland 于1975年提出来的，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。其思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。GA 以一种群体中的所有个体为对象，并利用随机化技术指导一个被编码的参数空间进行高度搜索。其中，选择、交叉和变异构成了遗产算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等五个要素组成了GA 的核心内容。

GA 从一个随机产生的称为“种群(population)”的初始解开始搜索过程，种群中每个个体使问题的一个解，称为“染色体(chromosome)”。染色体是一串符号，比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“适值(fitness)”来衡量染色体的好坏，生成的下一代染色体称为后代(offspring)。后代是由前一代染色体通过交叉(crossover)或者变异(mutution)运算形成的。在新一代形成过程中，根据适度的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适值高的染色体被选中的概率较高。这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或者次优解。

GA 的基本执行过程如下：

①编码：GA 在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串数据， 这些串结构的不同组合便构成了不同的点。

②初始群体的生成：随机产生N 个初始串结构，每个串结构称为一个个体(或叫染色体) ，N 个个体构成了一个群体，群体内个体的数量N 就是群体规模。群体内每个染色体必须以某种编码形式表示，编码的内容可以表示染色体的某些特征。随着求解问题的不同，它所表示的内容也是不同。通常染色体表示被优化的参数，每个初始个体就表示着问题的初始解。

③适应性值评估检测：适应值函数表明个体或解的优劣性。对于不同的问题，适应值函数定义的方式也不同。

④选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。按照一定的选择策略选择合适的个体，选择实现了达尔文的适者生存原则。根据群体中每个个体的适应值，从中选择具有最好的个体作为父代重新繁殖下一代群体。

⑤交叉：杂交或交叉是两个染色体之间随机交换信息的一种机制。以事先给定的杂交概率愚在选择出的个体中任意选择两个个体进行杂交运算或重组运算，产生两个新的个体，重复此过程直到所有要求杂交的个体杂交完毕。交叉操作是GA 中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体结合了其父辈个体的特性。交叉体现了信息交换的思想。 ⑥变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机的改变串结构数据中某个串的值。同生物界一样，GA 中发生变异的概率很低，通常取值在0．00l--0．0l 之间。变异为新个体的产生提供了机会。根据需要可以以事先给定的变异概率Pm 在最好的个体中选择若干个体，并按一定的策略对选中的个体进行变异运算。

变异运算增加了GA 找到最优解的能力。

⑦检验停机条件，若满足收敛条件或固定迭代次数则停机；若不满足条件则转③重新进行进化过程。每一次进化过程就产生新一代的群体。群体内个体所表示的解通过进化最终达到最优解。

实际上，GA 中有遗传(交叉和变异) 和进化(选择) 两类运算。其计算流程图如下图所示：

GA 的计算过程流程图

5.1.2 GA的3个算子

(1)选择算子

从群体中选择优质的个体，淘汰劣质个体的操作叫选择。选择的目的是把优化的个体(或解) 直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种：适应度比例方法、最佳个体保存方法、期望值方法、排序选择法、联赛选择方法、排挤方法等等。

(2)杂交(交叉) 算子

杂交是两个个体之州随机交换信息的一种操作。当两个个体之间进行杂交操作时，由于杂交通过个体传播可以发生模式的破坏作用，因此研究杂交技术对减少杂交的破坏作用具有重要意义。常用的杂交技术有：一点杂交、二点杂交、均匀杂交、多点杂交、启发式杂交、顺序杂交、混合杂交等。

(3)变异算子

变异是随机改变某个个体遗传信息的一种操作。GA 中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。GA 通过交叉和变异这一对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。常用的变异算子有： ①基本变异算子：是指对群体中的个体编码串随机挑选一个或多个基因座并对这些基因座的基因值做变化(以变异概率P 。做变动) 。

②逆转算子：其基本操作内容是，在个体串中随机挑选二个逆转点，然后将两个逆转点问的基因值以逆转概率P 。逆向排序。

③自适应变异算子：该算子与基本变异算子的操作内容类似，唯一不同的是变异概率P 。不是固定不变而是随群体中个体的多样性程度进行自适应调整。

5.1.3 GA的改进策略

GA 是基于自然的选择和遗传机制的搜索算法，具有以下特点：以编码形式工作，可以并行搜索多个峰值而不是一个点；把问题的参数表示成个体，并以编码的形式运行，而不是对参数本身进行求解：用概率传递规则代替确定性规则；只使用目标函数信息，而不使用推导过程或其他辅助知识。GA 具有运算并行性，可以在复杂的搜索空间内同时评价多个点，这样有利于在多值空间寻找全局最优解。GA 关心每次进化群体中个体的质量，即解的质量。这不同于许多优化方法需要递推信息或需要知道问题结构和参数的全部知识。因此，GA 尤其适合不确定问题或非线性复杂问题的求解。

由于对染色体GA 运算通常获得不可行的后代，为了解决如何满足约束的问题，近年来提出了一些GA 的改进策略，主要分为以下几类：

(1)拒绝策略

拒绝策略抛弃进化过程中产生的不可行的染色体，这是GA 中普遍的做法。当可行的搜索空间是凸的且为整个搜索空间的适当的一部分时，这种做法是有效的，然而这样的条件也是比较苛刻的。例如对许多约束优化条件初始种群可能是由非可行染色体构成的，这就需要对他们进行修补。对于某些系统，允许跨过不可性染色体使用修复往往更能达到最优解。

(2)修复策略

修复染色体是对不可性染色体采用修复程序使之变为可行的。对于许多组合优化问题，构造修复程序比较容易。已经证明，对于一个有多个不连通可行集的约束优化问题，修复策略在速度和计算性能上都远胜于其他策略。但是该方法的缺点是它对问题本身的依赖性，对于每个具体问题必须涉及专门的修复程序，而对于某些问题，修复过程本身比原问题的求解更复杂。

(3)改进遗传子策略

解决可行性问题的一个合理办法是涉及针对问题的表达式，以及专门的遗传算子来维持染色体的可行性。许多领域的实际工作者采用专门的问题表达方式和遗传算子构成了非常成功的GA ，这是一个非常普遍的趋势。但是该方法遗传搜索受到了可行域的限制。

(4)惩罚策略

上面的三种策略的共同优点是不会产生不可行解，缺点是无法考虑可行域外的点。

对于约束严格问题，不可解在种群中占的比例很大，这样将搜索限制在可行域内就很难找到可行届。惩罚策略就是在遗传搜索中考虑不可行解的技术。

构造带有惩罚项的适值函数一般有两种，一种是采用加法形式：

其中，x 代表染色体，f(X)是问题的目标函数；D(x)是惩罚项。对于极大化问题

:

对于极小化问题，则取：

另一种是乘法形式：

此时，对于极大化问题，则取：

对于极小化问题，则取：

6 结束语

本文在对物流配送业务进行详细研究的基础上，针对物流配送中对成本影响较大的车辆路线优化问题(VRP)进行了集中的研究，从而建立现代物流配送路线问题的数学模型，利用遗传算法，借助MATLAB 计算机编程，获得求解VRP 的一个较好方案。

车辆路径问题(Vehicle Routing Problem ，VRP) 是物流管理研究中的一项重要内容。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客了对物流环节的满意度，降低服务商运作成本。自从1959年Danting 和Ramser 提出VRP 之后，很快引起了运筹学、管理学、计算机应用、组合数学、图论等学科的专家学者的高度重视。他们对此问题进行了大量的理论研究和实验分析，取得了很大的研究进展。

目前，VRP 在国外己广泛应用于实际生活中，如邮局的邮件递送业务、超级市场的商品供应、牛奶站的牛奶送达业务、工业产品的运输、运输公司的任务安排、乘务员计划的安排等等，并取得了极大的效益。

7 参考文献

【1】王焰．对国内外物流市场发展的研究与思考[J]．物流技术，2000(6)：36-38

【2】宋伟刚．物流T 程及其应用[M]．北京：机械工业出版社，2003

【3】杨家其．现代物流与运输[砌．北京：人民交通出版社，2003

【4】丁立言，张铎．物流配送[M]．北京：清华人学出版社，2002

【5】谢秉磊，郭耀煌，郭强．动态车辆路径问题[J]．系统工程理论与实践，2002，11(2)：116--120

【6】祝崇隽，刘民，吴澄．供应链中车辆路径问题的研究进展及前景[J】．计算机集成制造系统，2001，7(11)：1．6

【7】Assad A ．A ．Medeling and Implementation Issues in VehiCle Routing ：Method and

【8】Studies[J]．StudiesinManagementScience andSystems ，1988，16：7-45

【9】Bal 1 M ．0，Golden B ．L ．，Assad A ．A ．，Bodin L ．D ．P1annJng For Truck F1eet Size in Presence of a Common Carrier 0ption[J]．Decision Science ，1983，14：103—120

【10】郭耀煌，李军．满载问题的车辆路线安排[J]．系统工程学报，1995，10(2)：106-118

【11】郭耀煌，李军．车辆优化调度问题的研究现状述评哪．茜南交通人学学报，1995，30(4)：376—382

【12】李军．车辆调度问题的分派启发式算法[J]．系统工程理论与实践，1999，19(1)：27-33

【13】王小平，曹立明．遗传算法——理论、应片j 与软件实现[M】．西安：西安交通大学出版社，2002

【14】王万良，宋毅，吴启迪．求解作业车问调度问题的双倍体遗传算法与软件实现[J]．计算机集成制造系统，2001，10(1)：65．69

【15]郊朝晖，张焱，裘聿皇．一种基于复数编码的遗传算法[J]．控制理论与应用，2003，20(1)：97—100

【16】黎明，熊晓峰，马聪．一种基于有性繁殖的遗传算法[J]．中国图像图形学报，2003，8(5)：509—515

【17】张建，马光文，杨东方等．双倍体遗传算法求解龙溪河梯级电站长期优化调度问题．四川水利，2002．5：33—35

【18】陈森发．网络模型及其优化[M]．东南入学出版社。1992