物流车辆路径算法的优化与设计
物流车辆路径算法的优化与设计
【摘要】：随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的50％左右，所以降低物流成本首先要从降低物流配送的运输成本开始。
一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化，这正是本文要研究的课题。
【关键词】：物流配送；路径；车辆路径问题(VRP)；MATLAB
1 前言
1.1 课题研究背景
运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。因此，自从1959年Danting和Ramse r提出车辆路径问题(Vehicle Routing Problem，VRP)以来，VRP便成为近年来物流领域中的研究热点。
VRP一般定义为：对一系列发货点和／或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。本文围绕VRP展开了研究，共包括五章内容。首先，本文收集国内外关于VR P研究的文献资料并进行整理、分类，详细介绍了VRP园内外研究现状，尤其对经典VRP、有时间窗的VRP(VRPTW)、动态VRP(DVRP)、带能力约束的VRP(CVRP)国内外研究现状分别展开了介绍：然后通过介绍物流配送在整个物流过程中具有的重要意义及我国物流配送的现状，说明了解决VRP的必要性及现实意义：建立了物流配送中VRP的两种数学模型：利用回路表示的VRP模型和利用运输成本表示的VRP模型；通过表格详细讨论了VRP的基本算法；最后，本文使用自然数编码、构造表示可行线路的染色体、类PMX交叉等方法及对适值函数加入惩罚项对标准遗传算法加以改进，并用MATLAB编程实现了本文提出的算法，以一个VR PTW实例分析证明了该算法的有效性。
1.2 车辆路径的概念
车辆路径问题(VRP)一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定问题的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。
目前有关VRP的研究已经可以表示（如图1）为：给定一个或多个中心点（中心仓库，cent ral 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在196 4年提出的节约算法。
构造算法最早提出来解决旅行商问题，这些方法一般速度快，也很灵活，但这类方法有时找到的解离最优解差得很远。
2.2.2 两阶段法(Two-phase Algorithm)
学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进，为此提出了两阶段法。第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止。Gillet和Miller于1974年提出的sweep算法，Ch ristofides、Mingozzi和Toth的算法以及Fisher和Jaikumar的算法都属于两阶段法。一般第一阶段常用构造算法，在第二阶段常用的改进技术有2-opt(Lin,1965)，3-opt(Lin Ke rnighan,1973)和Or-opt (Or,1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。
一些基于数学规划的算法也属于两阶段法，把问题直接描述成一个数学规划问题，根据其模型的特殊构形，应用一定的技术(如分解)进行划分，进而求解己被广泛研究过的子问题(Fi sher和Jaikumar,1981)。
在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性。此方法是目前成果最丰富、应用最多的一类方法。每一种方法讨论的情况不尽一致，适用范围也不完全相同。
2.2.3 智能化算法(Intelligent Algorithm)
这类算法以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间。
总体来看，尽管启发式算法能够在有限的时间内求出质量较高的解，但由于其搜索解空间的能力有所限制，因此经常无法达到预期的要求。20世纪90年代以来，由于人工智能方法在解决组合优化问题中的强大功能，不少学者开始将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法(智能化启发式算法)。智能化启发式算法从本质上讲仍然属于启发式算法，其基本思想是从一初始解开始，通过对当前的解进行反复地局部扰乱(Perturbations)以达到较好的解。目前，最常见的智能化启发式算法包括模拟退火算法(S imulated Annealing)、禁忌搜索算法(Tabu Search)、遗传算法(Genetic Algorithm)、蚁群算法(Ant Colony)和神经网络(Neutral Networks)方法等。
2.3 VRP中常见的约束条件
在VRP中，最常见的约束条件有:
(1) 容量约束：任意车辆路径的总重量不能超过该车辆的能力负荷。引出带容量约束的车辆
路径问题(CapacitatedVehicle Routing Problem，CVRP)。
(2) 优先约束：引出优先约束车辆路径问题(VehicleRouting Problem with precedence C onstraints，VRPPC)。
(3) 车型约束：引出多车型车辆路径问题(Mixed/Heterogeneous Fleet Vehicle Routing Problem，MFVRP/ HFVRP)。
(4) 时间窗约束：包括硬时间窗(Hard Time windows)和软时间窗(Soft Time windows) 约束。引出带时间窗(包括硬时间窗和软时间窗)的车辆路径问题(Vehicle Routing Problem withTime windows，VRPTW)。
(5) 相容性约束：引出相容性约束车辆路径问题(VehicleRouting Problem with Compatib ility Constraints，VRPCC)。
(6) 随机需求：引出随机需求车辆路径问题(VehicleRouting Problem with Stochastic D emand，VRPSD)。
(7) 开路：引出开路车辆路径问题(Open Vehicle RoutingProblem)。
(8) 多运输中心：引出多运输中心的车辆路径问题(Multi-Depot Vehicle Routing Proble m)。
(9) 回程运输：引出带回程运输的车辆路径问题(VehicleRouting Problem with Backhaul s)。
(10) 最后时间期限：引出带最后时间期限的车辆路径问题(Vehicle Routing Problem with Time Deadlines)。
(11) 车速随时间变化：引出车速随时间变化的车辆路径问题(Time-Dependent Vehicle Ro uting Problem)。
2.4 CVRP问题描述及其数学模型
CVRP的描述：设某中心车场有k辆车，每辆配送车的最大载重量Q，需要对n个客户(节点)进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i
的货物需求量是q i (i=1,2,…,n)，且q i 建立此问题的数学模型： minz = c ij x ijk (2. 2) 约束条件： y ki =1 (i=0,1,…,n ) (2.3) x ijk=y kj(j=0,1,…,n k=1,2,…,m) (2.4) x jik=y kj(j=0,1,…,n k=1,2,…,m) (2.5) q i 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个客户提供配送服务。每一个顾客在网络模型中用一个点代表，位置以（X i，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)车辆完成任务之后都要回到源点V0。 (3)车辆不能超过最大载重量Wi和最大行驶长度Li的限制。 d．数学模型 假设d i(j-1)i，表示第i辆车对应的路线中顺序排列的第j-1个客户和第j个客户之间的距离； d i(li)(0)表示第i辆车对应的路线中第I i个客户与源点V0之间的距离。由此可以建立如下的数学模型： 模型中： (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．0 l之间。变异为新个体的产生提供了机会。根据需要可以以事先给定的变异概率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 F1ee t Size in Presence of a Common Carrier 0ption[J]．Decision Science，1983，14：1 03—120 【10】郭耀煌，李军．满载问题的车辆路线安排[J]．系统工程学报，1995，10(2)：106-1 18 【11】郭耀煌，李军．车辆优化调度问题的研究现状述评哪．茜南交通人学学报，1995，3 0(4)：376—382 【12】李军．车辆调度问题的分派启发式算法[J]．系统工程理论与实践，1999，19(1)：2 7-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 !""#$%%%&%%’( )#$$&***+,#清华大学学报-自然科学版. /012345678329-":2;0<:5.= *%%>年第(>卷第$$期 *%%>=?@A B(>=#@B$$ +C,+C $C(’&$C(D 车辆路径优化问题的均衡性 但正刚=蔡临宁=杜丽丽=郑力 -清华大学工业工程系=北京$%%%D(. 收稿日期E*%%’&%>&%F 基金项目E国家自然科学基金资助项目-F%*%$%%D. 作者简介E但正刚-$C F D&.=男-汉.=重庆=博士研究生G 通讯联系人E蔡临宁=副教授=H&I72A E:72A3J K1234567B 捕食搜索算法 动物学家在研究动物的捕食行为时发现，尽管由于动物物种的不同而造成 的身体结构的千差万别，但它们的捕食行为却惊人地相似.动物捕食时，在没有 发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物.一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物或者有 猎物迹象的附近区域进行集中的区域搜索，以找到史多的猎物.在搜寻一段时间 没有找到猎物后，捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻 找猎物。 模拟动物的这种捕食策略，Alexandre于1998提出了一种新的仿生计算方法，即捕食搜索算法(predatory search algorithm, PSA)。基本思想如下：捕食 搜索寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解;然后在较 优解附近的区域(邻域)进行集中搜索，直到搜索很多次也没有找到史优解，从 而放弃局域搜索;然后再在整个搜索空间进行全局搜索.如此循环，直到找到最优解(或近似最优解)为止，捕食搜索这种策略很好地协调了局部搜索和全局搜索 之间的转换.目前该算法己成功应用于组合优化领域的旅行商问题(traveling salesm an problem )和超大规模集成电路设计问题(very large scale integrated layout)。 捕食搜索算法设计 (1)解的表达 采用顺序编码，将无向图中的，n一1个配送中心和n个顾客一起进行编码.例如，3个配送中心，10个顾客，则编码可为:1一2一3一4一0一5一 6一7一0一8一9一10其中0表示配送中心，上述编码表示配送中心1负 贡顾客1,2,3,4的配送，配送中心2负贡顾客5,6,7的配送，配送中心3负贡顾 客8,9,10的配送.然后对于每个配送中心根据顾客编码中的顺序进行车辆的分配，这里主要考虑车辆的容量约束。依此编码方案，随机产生初始解。 (2)邻域定义 4 仿真结果与比较分析(Simulation results and comparison analysis) 设某B2C电子商务企业在某时段由3个配送中心为17个顾客配送3类商品，配送网络如图2所示。 摘要：经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去其最优性。本文提出的局内最短路问题，就是在已知条件不断变化的条件下，如何来快速的计算出此时的最优路径，文章设计了解决该问题的一个逆向标号算法，将它与传统算法进行了比较和分析，并针对实际中的物流配送管理中路径优化问题，按照不同的算法分别进行了详细的阐述与分析。 一、引言 现实生活中的许多论文发表经济现象通常都具有非常强的动态特征，人们对于这些现象一般是先进行数学上的抽象，然后用静态或统计的方法来加以研究和处理。从优化的理论和方法上看，经典的优化理论大多是站在旁观者的立场上看问题，即首先确定已知条件，然后在假设这些已知条件不变的基础上给出最优方案（即最优解）。条件一旦发生变化，这种方法所给出的最优方案就会失去其最优性。在变化的不确定因素对所考虑的问题影响很大的时候，经典的优化方法有：一是将可变化的因素随机化，寻求平均意义上的最优方案，二是考虑可变化因素的最坏情形，寻求最坏情形达到最优的方案。这两种处理方法对变化因素的一个特例都可能给出离实际最优解相距甚远的解，这显然是难以满足实际的要求的。那么是否存在一种方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢？ 近年来兴起的局内问题与竞争算法的研究结果在一定意义上给如上问题一个肯定的答案。其实本文所提出的逆向标号算法就是对应局内最短路问题的一个竞争算法，从本质上来说它是一种贪婪算法，在不知将来情况的条件下，求出当前状态下的最优解。[1]本文所考虑问题的实际背景是一个物流配送公司对其运输车辆的调度。假设物流公司需要用货车把货物从初始点O(Origin)运送到目的点D(Destination)。从日常来看，物流公司完全可以通过将整个城市交通网络看成一个平面图来进行运算，找到一条从O到D的最短路径以减少运输费用和节省运输时间。现考虑如下一个问题：如果当运输车辆沿着最短路径行驶到最短路径上的一点A，发现前方路径上的B点由于车辆拥塞而不能通过，车辆必须改道行驶，而此时物流配送公司应如何应对来保证其花费最低。问题推展开去，如果不是单个堵塞点，而是一个堵塞点序列，那物流配送公司又将如何来设计其最短路算法来在最短的时间内求出已知条件发生变化后的最优路径，从而有效的调度其运输车。本文首先建立了物流配送公司动态最短路的数学模型，相比较给出了求本文所提出的动态最短路问题的传统算法和作者提出的逆向标号算法，并分析了各自的算法复杂度。 二、数学模型假设城市交通网络是一个平面图，记为G，各个交通路口对应于图G上的各个顶点，令G=(G，V)为一边加权无向图，其中V为顶点的集合，E为边的集合，|G|=n，对于一般平面图上的三点之间，一定满足三角不等式，即任意三角形的两边之和一定不小于另外一边。对于本文要讨论的城市交通网络来说，即，任意三个结点之间的距离一定满足三角不等式。我们用O来表示运输的起始点，D表示运输的目的点。SP表示在没有路口堵塞情况下的最短路径，W(SP)表示沿着最短路径所要花费的运输费用。以下的讨论都是基于如下的基本假设：第一，去掉堵塞点后图G仍是连通的。第二，只有当运输车走到前一点后，才能发现后面的一点发生堵塞而不能通过。 三、算法分析 对于本文的上述问题，有两种算法一(传统算法)和二(逆向标号算法)可以满足要求，但两种算法在求动态最短路的过程中都将会用到Dijkstra算法[2]，通过对Dijkstra算法的分析我们知道，Dijkstra算法采用了两个集合这样的数据结构来安排图的顶点，集合S表示已 配送是指对局域范围内的客户进行多客户、多品种、按时联合送货活动。 配送活动是指根据一定区域范围内各个客户所需要的各个品种要求，对配送中心 的库存物品进行拣选、加工、包装、分割、组配、分装上车，并按一定路线循环 依次送达各个用户的物流活动。物流配送是供应链网络中一个重要的直接与消费 者相连的环节，是货物从物流节点送达收货人的过程。配送是在集货、配货基础上，按货物种类、品种搭配、数量、时间等要求所进行的运送，是“配”和“送”的有机结合。配送的实质是现代送货，是以低成本、优质服务为宗旨，是一种先进 的物流形式。 供应链网络的物流配送过程主要包括：从生产工厂进货并集结的集货作业； 根据各个用户的不同需求，在配送中心将所需要的货物挑选出来的配货作业；考虑配送货物的质量和体积，充分利用车辆的载重和容积的车载货物的配装及路线 的确定。随着供应链管理系统的集约化、一体化的发展，常将配送的各环节综合 起来，核心部分为配送车辆的集货、货物装配及送货过程。进行配送系统优化， 主要是配送车辆优化调度，包括集货线路优化、货物配装及送货线路优化，以及集货、货物配装和送货一体化优化。物流配送车辆优化调度，是供应链系统优化 中关键的一环，也是电子商务活动不可缺少的内容。对配送车辆进行优化调度， 可以提高供应链管理的经济效益、实现供应链管理科学化。 配送车辆优化调度实际上也就是车辆路径问题（V ehicle Routing Problem，简称VRP），是Dantzig和Ramse]80[于1959年提出来的，该问题被提出来之后， 很快就引起了运筹学、应用数学、组合数学、图论、网络分析、物流学、管理学、 以及计算机科学等学科专家和运输计划制订者的极大重视，成为了运筹学和组合 优化领域的前沿和研究热点问题。各学科专家对该问题进行了大量的理论研究及 实验分析，取得了很大的进展。 车辆路径问题是径旅行商问题（Travel Salesman Problem，简称TSP）衍生 而出的多路TSP问题，即为K-TSP。VRP的一般定义为]81[：对一系列送货点和 （或取货点），组织适当的行车路线，使车辆有序地通过它们，在满足一定的约 束条件下（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、 时间限制等），达到一定的目标（如路程最短、费用最少、使用车辆数最少等）。见图1。 系 统 管理学报 第１９卷 不同，文献［６］中１００，本文３０；③文献［６］中没有给出２０次求解中有多少次求得最优解，本文算法在软硬２种时间窗下，求得最优解的概率分别为９０％和７５％。由此可以看出本文算法具有较快的收敛速度和较高的稳定性。 表２实例ｌ。软时间窗下算法运行结果 第２个实例［６］，该问题有８个客户，顾客的装货或卸货的时间为Ｔｉ，一般将ｔ作为车辆的行驶时间的一部分计算费用，ｇｆ和［ｎ，，６ｉ］的含义同前，具体数据见表４。这些任务由仓库发出的容量为８ｔ的车辆来完成，车辆行驶速度为５０，仓库以及各个顾客之间的距离见表５。 ６），达到最优解的概率为８０％，其最终结果与文献［６］中相同最优解其费用值为９１０，对应的子路径 为（Ｏ一３一ｌ一２—０）、（Ｏ一６—４一Ｏ）、（Ｏ一８—５—７一Ｏ）。然而，文献 ［６］是在ｍａｘｇｅｎ＝５０、ｐｏｐｓｉｚｅ一２０的情况下，达到最优解的概率为６７％。这又说明了本文算法的有 效性。 表６实例２的算法运行结果 ４ 结语 尽管用带有子路径分隔符的自然数编码作为遗传算法解决ＶＲＰＴＷ问题的编码方式有其优点，但缺陷也是显而易见的，为了弥补该缺陷，本文去掉了 子路径中的分隔符，并采用Ｓｐｌｉｔ作为解码方式，就此设计了求解ＶＲＰＴＷ的遗传算法，并进行了数值试验的对比分析，试验结果表明，该算法是十分有 效的。参考文献 ＤａｎｔｚｉｑＧ，Ｒａｍｓｅｒ Ｊ．Ｔｈｅｔｒｕｃｋｄｉｓｐａｔｃｈｉｎｇｐｒｏｂｌｅｍ ［Ｊ］．Ｍａｎａｇｅｍｅｎｔ ｓｃｉｅｎｃｅ，１９５９，１３（６）８０一９１． 谢秉磊，李军，郭耀煌．有时间窗的非满载车辆调 度问题的遗传算法［Ｊ］．系统工程学报，２０００，１５ （３）２９０一２９４． 宋伟刚，张宏霞，佟玲．有时间窗约束非满载车辆调度问题的遗传算法［Ｊ］．系统仿真学报，２００５，１７ （１１）２５９３—２５９７． 刘诚，陈治亚，封全喜．带软时间窗物流配送车辆路径问题的并行遗传算法 》本文对在GIS（地理信息系统）环境下求解动态路径优化算法及相关技术 进行了研究。最短路径问题是网络分析中的基本的问题，它作为许多领域中选择 最优值的一个基本却又是一个十分重要的问题。特别是在交通诱导系统中占有重 要地位。本文分析了GIS环境下动态路径优化算法的特点，对GIS环境下城市 路网的最优路径选择问题的关键技术进行了研究和验证。 》考虑现实世界中随着城市路网规模的日益增大和复杂程度不断增加的情况，充分利用GIS 的特点，探讨了通过限制搜索区域求解最短路径的策略，大大减少了搜索的时间。 》另一方面，计算机技术的进步，地理信息系统(GIS)得到了飞速的发展。地理信息系统是采集、存储、管理、检索、分析和描述整个或部分地球表面与空间地理分布数据的空间信息系统。它是一种能把图形管理系统和数据管理系统有机地结合起来的信息技术，既管理对象的位置又管理对象的其它属性，而且位置和其它属性是自动关联的。它最基本的功能是将分散收集到的各种空间、非空间信息输入到计算机中，建立起有相互联系的数据库。当外界情况发生变化时，只要更改局部的数据，就可维持数据库的有效性和现实性[3][4]，GIS为动态路径优化问题的研究提供了良好的环境。目前GIS带动的产业急剧膨胀，已经应用到各个方面。网络分析作为地理信息系统最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用[5]。文献[6][7]说明了GIS 在城市道路网中的应用情况。而路网分析中基本问题之一是动态路径优化问题。所谓动态路径，不仅仅指一般地理意义上的距离最短，还可以应用到其他的参数，如时间、费用、流量等。相应的，动态路径问题就成为最快路径问题、最低费用问题等。 》GIS因为其强大的数据分析功能、空间分析功能,已被广泛应用于各种系统中与空间信息有密切关系的各个方面.各种在实际中的系统如电力系统，光缆系统涉及到最佳、最短抢修等问题都可以折合到交通网络中来进行分析，故而交通网络中最短路径算法就可以广泛的应用于其它很多的最佳、最短抢修或者报警系统中去[5]。最短路径问题是GIS网络分析功能的应用。最短路径问题可分为单源最短路径问题及所有节点间最短路径问题，其中单源最短路径更具有普遍意义[9]。 》2.1地理信息系统的概念 地理信息系统（Geographical Information System,简称GIS）是一种将空间位置信息和属性数据结合在一起的系统，是一种为了获取、存储、检索、分析和显示空间定位数据而建立的计算机化的数据库管理系统（1998年，美国国家地理信息与分析中心定义）[4]。这里的空间定位数据是指采用不同方式的遥感和非遥感手段所获得的数据，它有多种数据类型，包括地图、遥感、统计数据等，它们的共同特点都有确定的空间位置。地理信息系统的处理对象是空间实体，其处理过程正是依据空间实体的空间位置和空间关系进行的[25]。地理信息系统的外在表现为计算机软硬件系统，其内涵却是由计算机程序和地理数据组织而成的地理空间信息模型。当具有一定地理学知识的用户使用地理空间分析非空间分析等处理工具输入输出GIS数据库信息系统时，他所面对的数据不再是毫无意义的，而是把客观世界抽象为模型化的空间数据。用户可以按照应用的目的观测这个现实世界模型的各个方面的内容，取得自然过程的分析和预测的信息，用于管理和决策，这就是地理信息系统的意义。一个逻辑缩小的、高度信息化的地理系统，从视觉、计量和逻辑上对地理系统在功能上进行模拟，信息流动以及信息流动的结果，完全由计算机程序的运行和数据的变换来仿真。地理学家可以在地理信息系统支持下提取地理系统各个不同侧面、不同层次的空间和时间特征，也可以快速地模拟自然过程演变成思维过程的结果，取得地理预测或“实验”的结果，选择优化方案，用于管理与决策[26]。 一个完整的GIS主要有四个部分构成，即计算机硬件系统、计算机软件系统、地理数据（或空间数据）和系统管理操作人员。其核心部分是计算机系统（硬件和软件），地理数据反映 带时间窗物流配送车辆路径问题 摘要 本题是一个带有时间窗的车辆路径安排问题（VRPTW 问题）。根据题目条件，本文建立了一个求解最小派送费用的VRPTW 优化模型，采用遗传算法，给出了该模型的求解方法。然后，对一个实际问题进行求解，给出了一个比较好的路线安排方式。 模型一（见，在需求量、接货时间段、各种费用消耗已知的情况下，决定采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失。 模型一的求解采用遗传算法（见，对题目给出的实际问题进行求解，得到3 首先按照需求期望根据模型一得到一个比较好的方案，然后按照这一方案进行送货，在送货过程中，如果出现需求量过大的情况，允许车辆返回仓库进行补充。 模型一的思路清晰，考虑条件全面。但最优解解决起来困难，遗传算法只是一种相对好的解决方法，可以找出最优解的近似解。模型二的想法比较合理，易于实施，但还有待改进。 关键词：规划 时间窗 物流 车辆路径 遗传算法 一、 问题重述 一个中心仓库，拥有一定数量容量为Q 的车辆，负责对N 个客户进行货物派送工作，客户i 的货物需求量为i q ，且i q Q <，车辆必须在一定的时间范围[],i i a b 内到达，早于i a 到达将产生等待损失，迟于i b 到达将处以一定的惩罚，请解决如下问题： （1）给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。并具 体求解以下算例： q（单位：客户总数N=8,每辆车的容量Q=8（吨/辆）, 各项任务的货运量 i s（单位：小时）以及要求每项任务开始执行的时间吨）、装货（或卸货）时间 i a b由附录1给出，车场0与各任务点以及各任务点间的距离（单位：公 , 范围[] i i 里）由附件二给出，这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短； q为随机参数时的数学模型及处理方（2）进一步请讨论当客户i的货物需求量 i 法。 二、问题分析 本题主要在两种不同情况下，研究使派送费用最小的车辆行驶路径问题。车辆行驶派送的费用主要包括运输成本、车辆在客户要求到达时间之前到达产生的等待损失和车辆在客户要求到达时间之后到达所受惩罚等等。为满足派送费用最小的需求，即要使所选行车路径产生的总费用最小，从而确定出最佳的车辆派送方案。 q固定时，首先，我们根据题意，取若干辆车进行送当客户i的货物需求量 i 货，然后，主要考虑每辆车各负责哪些客户的送货任务，我们可以给出满足题中限制条件的很多参考方案供选用，并考虑以所选行车路径产生的总费用最小为目标的情况下，建立最优化模型确定最佳的车辆派送方案。 q为随机参数时，我们首先可以简化随进一步讨论，当客户i的货物需求量 i 机模型，根据客户i的货物需求量的期望与方差，确定每天应该运送给客户i的q，再根据第一题，确定最佳的车辆派送方案。 货物量，即 i 但考虑到客户的储存能力有限及货物在客户处的储存费用，客户不需要将一天的货物一次性接收完，只要满足缺货的情况出现的概率很低，客户可以让配送中心一天几次送货，这样可以得到很多满足约束的方案，考虑以单位时间的储存费用最小为目标，建立最优化模型，确定配送中心给每位客户每次的配送量、配送周期与最有车辆行驶路径。 三、模型假设 （1）每个客户的需求只能由一辆配送车满足； （2）每辆车送货时行驶的路程不超过它所能行驶的最远路程； （3）中心仓库的车辆总数大于或等于当派送费用最小时所需的车辆数；（4）从配送中心到各个用户、各个用户之间的运输距离已知； （5）配送中心有足够的资源以供配送。 四、符号说明 车辆路径问题优化算法 美国物流管理学会(Council of Logistics Management，CLM)对物流所作的定义为：“为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息，从其起运点至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制过程。” 而有关资料显示，物流配送过程(包含仓储、分拣、运输等)的成本构成中，运输成本占到52%之多。因此，如何在满足客户适当满意度的前提下，将配送的运输成本合理地降低，成为一个紧迫而重要的研究课题，车辆路径问题正是基于这一需求而产生的。 2.1车辆路径问题的定义 车辆路径问题可以描述为：给定一组有容量限制的车辆的集合、一个物流中心（或供货地）、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所有的客户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、行驶里程限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。[4] 因此研究车辆的路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。车辆路径问题已被证明是NP-Hard问题，因此求解比较困难。然而，由于其在现实生活中应用非常广泛，使得它无论在理论上还是在实践上都有极大的研究价值。 Penousal Machado等人[5]指出车辆路径问题(vehicle routing problem，简称VRP)是一个复杂的组合优化问题，是古老的旅行商问题和背包问题的综合。实际上，车辆路径问题通常可被分解或转化成一个或几个已经研究过的基本问题，再采用相应比较成熟的基本理论和方法，以得到最优解或满意解。 这些与车辆路径问题相关的常用基本问题有；旅行商问题、运输问题、背包问题、最短路问题、最小费用最大流问题、中国邮路问题、指派问题等。 旅行商问题可被描述为：一个推销员欲到n个城市推销商品，每2个城市之间的距离是已知的。如何选择一条路径使推销员依次又不重复地走遍每个城市后，回到起点且所走的路径最短。 运输问题关心的是（确实的或是比喻的）以最低的总配送成本把供应中心（称为出发地，sources）的任何产品运送到每一个接受中心（称为目的地，destinations）。运输问题需要的数据仅仅是供应量、需求量和单位成本。 背包问题是指有一只固定容量的背包和若干体积、重量不等的物品，背包的容量不允许装下这所有的物品，那么如何选择适当的物品装入背包，使得背包的装载量（所装物品的重量之和）最大。 最短路径问题解决的是在一个网络中，如何寻找两点之间的最短路径。这两点之间通常没有直接的通路可达，但可经由若干中间结点相通。 最小费用流问题主要解决如何以最小成本在一个配送网络中运输货物。最小费用流问题又称为网络配送问题。 最大流问题和最小费用流问题一样，也与网络中的流有关。但是它们的目标不同，最大流问题不是使得流的成本最小化，而是寻找一个流的方案，使得通过网络的流量最大。 中国邮路问题是由我国管梅谷同志在1962年首先提出的，它可描述为：一个邮递员负责某一个地区的信件投递。每天要从邮局出发，走遍该地区所有的街道再返回邮局，问应该怎样安排送信路线可以使所走的路程最短。 指派问题解决将n件工作安排给m个人完成的问题。已知不同人完成不同工作的效率（或成本）不同，指派问题要求以最高的效率（或最小的人工成本）完成工作的安排。 2.2车辆路径问题的分类 一、车辆路径问题描述和建模 1. 车辆路径问题 车辆路径问题（Vehicle Routing Problem, VRP ）,主要研究满足约束条件的最优车辆使用方案以及最优化车辆路径方案。 定义：设G={V,E}是一个完备的无向图，其中V={0,1,2…n}为节点集，其中0表示车场。V ,={1,2,…n}表示顾客点集。A={(i,j),I,j ∈V,i ≠j}为边集。一对具有相同装载能力Q 的车辆从车场点对顾客点进行配送服务。每个顾客点有一个固定的需求q i 和固定的服务时间δi 。每条边（i,j ）赋有一个权重，表示旅行距离或者旅行费用c ij 。 标准车辆路径问题的优化目标为：确定一个具有最小车辆数和对应的最小旅行距离或者费用的路线集，其满足下列约束条件： ⑴每一条车辆路线开始于车场点，并且于车场点约束； ⑵每个顾客点仅能被一辆车服务一次 ⑶每一条车辆路线总的顾客点的需求不超过车辆的装载能力Q ⑷每一条车辆路线满足一定的边约束，比如持续时间约束和时间窗约束等。 2.标准车辆路径的数学模型: 对于车辆路径问题定义如下的符号： c ij ：表示顾客点或者顾客点和车场之间的旅行费用等 d ij ：车辆路径问题中，两个节点间的空间距离。 Q ：车辆的最大装载能力 d i ：顾客点i 的需求。 δi ：顾客点i 的车辆服务时间 m:服务车辆数，标准车辆路径问题中假设所有的车辆都是同型的。 R ：车辆集，R={1,2….，m} R i :车辆路线，R i ={0，i 1,…i m ,0},i 1,…i m ?V ,,i ?R 。 一般车辆路径问题具有层次目标函数，最小化车辆数和最小化车辆旅行费用，在文献中一般以车辆数作为首要优化目标函数，在此基础上使得对应的车辆旅行费用最小，下面给出标准车辆路径问题的数学模型。 下面给出标准车辆路径问题的数学模型。 对于每一条弧（I,j ）,定义如下变量: x ijv = 1 若车辆v 从顾客i 行驶到顾客点j 0 否则 y iv = 1 顾客点i 的需求由车辆v 来完成0 否则 车辆路径问题的数学模型可以表述为： minF x =M x 0iv m i=1n i=1+ x ijv m v=1n j=0n i=0.c ij (2.1) x ijv n i=0m v=1≥1 ?j ∈V , (2.2) 摘要 供货小车的路径优化是企业降低成本,提高经济效益的有效手段,供货小车路径优化问题可以看成是一类车辆路径优化问题。 本文对供货小车路径优化问题进行研究，提出了一种解决带单行道约束的车辆路径优化问题的方法。首先，建立了供货小车路径优化问题的数学模型，介绍了图论中最短路径的算法—Floyd算法，并考虑单行道的约束，利用该算法求得任意两点间最短距离以及到达路径，从而将问题转化为TSP问题，利用遗传算法得到带单行道约束下的优化送货路线，并且以柳州市某区域道路为实验，然后仿真，结果表明该方法能得到较好的优化效果。最后对基本遗传算法采用优先策略进行改进，再对同一个供货小车路径网进行实验仿真，分析仿真结果，表明改进遗传算法比基本遗传算法能比较快地得到令人满意的优化效果。 关键字:路径优化遗传算法 Floyd算法 Abstract The Path Optimization of Goods Supply Car is the effective way to reduce business costs and enhance economic efficiency.The problem of the Path Optimization of Goods Supply Car can be seen as Vehicle routing proble. This paper presents a solution to Vehicle routing proble with Single direction road by Researching the Way of Path Optimization of Goods Supply Car. First, This paper Establish the mathematics model of Vehicle routing proble and introduced the shortest path algorithm-Floyd algorithm, then taking the Single direction road into account at the same time. Seeking the shortest distance between any two points and landing path by this algorithm,then turn this problem in to TSP. Solving this problem can get the Optimize delivery routes which with Single direction road by GA,then take some district in the state City of LiuZhou road as an example start experiment.The Imitate the true result showed that this method can be better optimize results. Finally improving the basic GA with a priority strategy,then proceed to imitate the true experiment to the same Path diagram. The result expresses the improvement the heredity calculate way ratio the basic heredity calculate way can get quickly give satisfaction of excellent turn the result. Keyword: Path Optimization genetic algorithm Floyd algorithm 万方数据 万方数据 万方数据 万方数据 万方数据 物流配送车辆路线求解算法 作者：牛永亮， 王金妹， Niu Yong-liang， Wang Jin-mei 作者单位：牛永亮,Niu Yong-liang(东南大学,交通学院,江苏,南京,210096)， 王金妹,Wang Jin-mei(福州大学,公共管理学院,福建,福州,350002) 刊名： 交通运输工程学报 英文刊名：JOURNAL OF TRAFFIC AND TRANSPORTATION ENGINEERING 年，卷(期)：2006,6(2) 被引用次数：12次 参考文献(8条) 1.胡大伟;宣登殿公路快速客运网络系统规划方法[期刊论文]-长安大学学报(自然科学版) 2004(02) 2.Min H;Jayaraman V;Srivastava R Combined location-routing problem:a systhesis and future research directions[外文期刊] 1998(1) 3.张波;叶家玮;胡郁葱模拟退火算法在路径优化问题中的应用[期刊论文]-中国公路学报 2004(01) 4.Wu Tai-his;Low C;BaiJiunn-wei Heuristic solutions to multi-depot location-routing problems[外文期刊] 2002 5.丁浩;李电生城市物流配送中心选址方法的研究[期刊论文]-华中科技大学学报(城市科学版) 2004(01) 6.张潜;高立群;胡祥培集成化物流中的定位配给问题的启发式算法[期刊论文]-东北大学学报(自然科学版) 2004(07) 7.赵建有;闫旺;胡大伟配送网络规划蚁群算法[期刊论文]-交通运输工程学报 2004(03) 8.Paolo T;Daniele V Models relaxations and exact approaches for the capacitated vehicle routing problem 2002(1-3) 引证文献(12条) 1.孙有望.宋华骏以均衡为目标的车辆调度问题研究[期刊论文]-物流科技 2010(6) 2.郝勇.朱倩.张海婷.蔡诚物流配送问题的研究文献统计与综述[期刊论文]-物流科技 2010(6) 3.陈洁.任斌基于GPS的智能物流管理系统设计[期刊论文]-科学技术与工程 2008(20) 4.赵建有.吴利清.刘大学带时间窗车辆路径问题的启发式遗传算法[期刊论文]-交通运输工程学报 2008(1) 5.徐红梅.杨兆升.闫长文.王彦新基于蚁群算法求解物流订单派送问题[期刊论文]-长安大学学报（自然科学版）2007(6) 6.赵宁.王琦璐面向共同配送的建模仿真研究[期刊论文]-系统仿真技术 2007(3) 7.徐莹.李军蚁群算法在物流配送路径优化问题上的应用[期刊论文]-价值工程 2007(11) 8.胡大伟.陈诚.王来军带硬时间窗车辆路线问题的混合遗传启发式算法[期刊论文]-交通运输工程学报 2007(5) 9.李芬.徐国虎基于遗传算法的配送中心选址问题求解[期刊论文]-商品储运与养护 2007(3) 10.赵忠杰.丁恒.田梅公路隧道交通疏散策略[期刊论文]-长安大学学报（自然科学版） 2007(1) 11.贺竹磬.孙林岩动态交通下车辆路径选择模型及算法[期刊论文]-交通运输工程学报 2007(1) 12.王生辉物流流体理论体系及应用研究[学位论文]硕士 2007 本文链接：https://www.doczj.com/doc/b33712295.html,/Periodical_jtysgcxb200602019.aspx 粒子群优化算法 计算车辆路径问题 摘要 粒子群优化算法中,粒子群由多个粒子组成,每个粒子的位置代表优化问题在D 维搜索空间中潜在的解。根据各自的位置,每个粒子用一个速度来决定其飞行的方向和距离,然后通过优化函数计算出一个适应度函数值(fitness)。粒子是根据如下三条原则来更新自身的状态:(1)在飞行过程中始终保持自身的惯性;(2)按自身的最优位置来改变状态;(3)按群体的最优位置来改变状态。本文主要运用运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题 由Dan tzig 和Ram ser 于1959年首次提出的, 它是指对一系列发货点(或收货点) , 组成适当的行车路径, 使车辆有序地通过它们, 在满足一定约束条件的情况下, 达到一定的目标(诸如路程最短、费用最小, 耗费时间尽量少等) , 属于完全N P 问题, 在运筹、计算机、物流、管理等学科均有重要意义。粒子群算法是最近出现的一种模拟鸟群飞行的仿生算法, 有着个体数目少、计算简单、鲁棒性好等优点, 在各类多维连续空间优化问题上均取得非常好的效果。本文将PSO 应用于车辆路径问题求解中, 取得了很好的效果。 针对本题，一个中心仓库、7个需求点、中心有3辆车，容量均为1，由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。 1233,1,7. k q q q l =====货物需求 量12345670.89,0.14,0.28,0.33,0.21,0.41,0.57g g g g g g g =======， 且 m a x i k g q ≤。利用matlab 编程，求出需求点和中心仓库、需求点之间的各 个距离，用ij c 表示。求满足需求的最小的车辆行驶路径，就是求 m i n i j i j k i j k Z c x = ∑∑∑ 。经过初始化粒子群，将初始的适应值作为每个粒子的个 ——第6届全国青年管理科学与系统科学学术会议论文集 2001年·大连 437 物流系统优化中的定位—运输路线安排问题 （ＬＲＰ）研究评述* 林岩 胡祥培** （大连理工大学系统工程研究所, 116023） 摘要 本文概述了物流优化问题中的定位—运输路线安排问题 （Location-Routing Problems, LRP ）的发展历程，并对LRP 的分类和解决方 法加以评述，最后就这一问题的发展方向进行简单地探讨。 关键词 LRP 物流 系统优化 运筹学 1 引言 新技术的迅速发展，特别是电子商务的风起云涌，为我国经济的快速发展提供了契机。目前我国电子商务得到政府和民众的支持，发展势头强劲，但是，由于它是一套全新的技术，同时还是一种全新的管理理念，所以其发展过程中必然存在一些难题。在电子商务“三流”（信息流、物流、资金流）中，随着网络基础设施建设的成熟、电子商务网站的蓬勃发展以及有效利用网络资源观念的普及，信息流的发展已经比较成熟了；而随着各大银行纷纷开展网上业务，以及支付网关的建立和加密技术的成熟，网上支付已经在许多网站上成为现实；然而，我国传统的物流体系是在计划经济环境下建立、发展起来的，与目前的电子商务环境已经无法相容。现今物流体系的落后现状已经成为我国社会经济快速发展的重要制约因素之 一。所以对物流系统优化的研究将会具有很大的现实意义。 国外许多学者在电子商务出现之前就已经研究物流系统优化的问题了，为各类实际问题构建了优化模型，并形成了许多解决问题的算法。依据实际问题的不同，可以对物流系统优化问题进行分类，比如，运输车辆路线安排问题（VRP ）、定位—配给问题（LA ）、定位—运输路线安排问题（LRP ）等等，其中LRP 更贴近目前的物流系统复杂的实际特征，所以对它的研究是十分有意义的。 本文先从VRP 和LA 的集成来探讨LRP 的由来，然后讨论LRP 的分类，同时探讨LRP 的研究现状，并对LRP 的解决方法进行概述，最后就LRP 的未来发展方向作简要的讨论。 2 从VRP 、LA 到LRP ——物流系统的集成 依据实际问题的不同，可以对物流系统优化问题进行分类，比如确定设施（指的是物品流动的出发点和终到点，如配送中心、仓库、生产工厂、垃圾回收中心等）位置、运输路线 * 国家自然科学基金重点项目(70031020) ** 林岩, 硕士研究生, 1972年出生, 主要研究方向: 电子商务, 信息系统工程。 胡祥培, 1962年出生, 教授,博导, 主要研究方向: 电子商务, 智能运筹学, 信息系统集成。 车辆路径优化及算法综述 袁建清 （黑龙江东方学院计算机科学与电气工程学部，黑龙江哈尔滨１５００８６ ）摘 要：阐述了ＶＲＰ的主要求解算法， 在参阅大量文献基础之上以禁忌搜索算法、遗传算法、蚂蚁算法三种主要的算法为划分总结了ＶＲＰ的研究现状以及三种算法的改良与应用情况，最后对车辆调度问题进行了展望，提出了进一步发展动向。 关键词：车辆路径问题；ＶＲＰ； 算法中图分类号：ＴＰ３１２ 文献标识码：Ａ 文章编号：１６７２－７８００（２０１１）０７－００６０－ ０２作者简介：袁建清（１９７９－） ，女，黑龙江穆棱人，硕士，黑龙江东方学院讲师，研究方向为信息管理。０ 引言 车辆路径问题（Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ，ＶＲＰ）是指在客户需求和位置已知的情况下， 确定车辆在各个客户间的行驶路线，使得运输路线最短或运输成本最低。对运输车辆进行优化调度，通过选择车辆的最佳运输路径，合理安排车辆调度顺序， 可以有效减少车辆的空驶率和行驶距离。它是物流系统优化环节中关键的一环。已经典型应用到牛奶配送、 报纸和快件投递、垃圾车的线路优化及连锁商店的送货线路优化等众多社会领域，而且在工业管理、物流管理、交通运输、通讯、电力、计算机设计等领域都有广泛的应用。 １ ＶＲＰ求解算法 ＶＲＰ是一个ＮＰ难问题， 因此根据各具体类型问题的特点应用启发式算法算法求解已经成为研究的主流。其中传统启发式算法主要有节约算法、插入算法、二阶段算法法等；现代启发式算法主要有禁忌搜索算法（ＴａｂｕＳｅａｒｃｈ，ＴＳ）、遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇ ｏｒｉｔｈｍ，ＧＡ）、模拟退火算法（Ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ，ＳＡ）、蚂蚁算法（ａｎｔ ｃｏｌｏｎｙｏｐ ｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）等。近年来应用最多的是禁忌搜索算法、 遗传算法、蚂蚁算法以及它们之间或它们与传统启发式算法之间的结合形成的混合算法。 （１）禁忌搜索算法（ＴＳ） ：是一种全局优化搜索算法，通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。但是存在对初始解有较高的依赖性的缺点。 （２）遗传算法（ＧＡ） ：是一种基于自然进化原理的全局搜索随机算法，它使用群体搜索技术，通过对当前群体施 加选择（ｒｅｐｒｏｄｕｃｔｉｏｎ）、交叉（ｃｒｏｓｓｏｖｅｒ）及变异（ｍｕｔａｔｉｏｎ）等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。该算法有局部搜索能力不强、易陷入早熟、总体上可行解的质量不是很高的缺点。 （３）蚁群算法（ＡＣＯ） ：是一种概率搜索算法，它模拟蚂蚁群体在觅食过程中所体现出的智能行为， 利用信息激素为媒介进行间接的信息传递，根据信息素的强度做出对较优解的选择。此算法有易陷入早熟、停滞、局部最优的缺点。 ２ ＶＲＰ研究现状 ＶＲＰ一直是物流届研究的热点问题， 纵观国内外学者研究都是通过对以上几种算法进行改良或将其结合形成有效地混合算法， 而对不同约束条件下车辆路径优化问题进行求解。本文针对三种主要算法总结研究现状如下：（１ ）应用遗传算法研究。文献分别用改进的遗传算法、免疫遗传算法、小生境遗传算法、以及与爬山算法、禁忌搜索算法、 蚁群算法相结合的混合算法对时间窗的车辆路径优化问题（ＶＲＰＴＷ）进行了求解。另外：张海刚等提出用基于自然数编码的遗传算法同时处理有软硬时间窗的ＶＲＰ，魏航等设计了基于自然数编码的遗传算法，针对有行驶里程限制的多车场满载车辆调度问题。 （２ ）应用禁忌搜索法研究。学者们对禁忌搜索法的应用主要针对两方面进行改良。一是构造好的初始解，在这方面主要形成三种方法：①随机排列，然后将顾客按序列聚类分配到每辆车，从而产生每辆车的路径；②先分组，然后在每个组内采用旅行商算法产生初始解；③用Ｃ－Ｗ启发式构造线路。二是通过改进邻域移动方法构造候选车辆路径优化问题的均衡性
物流配送中几种路径优化算法
物流配送管理中路径优化问题分析
数学建模供应链网络物流配送与车辆路径问题
时间窗车辆路径问题【带有时间窗约束的车辆路径问题的一种改进遗传算法】
动态路径优化算法及相关技术
带时间窗物流配送车辆路径问题
车辆路径问题及遗传算法
车辆路径问题
路径优化的算法
物流配送车辆路线求解算法
粒子群优化算法车辆路径问题
物流系统优化——定位——运输路线安排问题LRP研究评述
车辆路径优化及算法综述_袁建清
相关主题
文本预览