《物流车辆路径算法解析》由会员分享，可在线阅读，更多相关《物流车辆路径算法解析（21页珍藏版）》请在金锄头文库上搜索。
1、物流车辆路径算法的优化与设计物流车辆路径算法的优化与设计【摘要】：随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得 越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的 50 %左右，所以降低物流成本首先要从降低物流配送的运输成本开始。一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。 起初车辆都在中心点， 顾客在空间任意分布， 车把货物从车库运送到每 一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或
2、随机、或以时间规律变化，这正是本文要研究的课题。【关键词】：物流配送；路径；车辆路径问题（VRP）; MATLAB1前言1.1 课题研究背景运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量， 增强客户对物流环节的满意度，降低服务商运作成本。因此，自从1959年Danting和Ramser提出车辆路径问题（Vehicle Routing Problem, VRP）以来，VRP便成为近年来物流领域中的研究热点。VR般定义为：对一系列发货点和/或收货点，组织适当的行车路线，使车辆有序地通过
3、它们，在满足一定的约束条件 （如货物需求量、发送量、交发货时间、车辆容量限制、行驶 里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车 辆尽量少等）。本文围绕VRP展开了研究，共包括五章内容。首先，本文收集国内外关于VRP研究的文献资料并进行整理、分类，详细介绍了VRP园内外研究现状，尤其对经典VRR有时间窗的VRP（VRPTW）动态VRP（DVRP）带能力约束的 VRP（CVRP国内外研究现状分别展 开了介绍：然后通过介绍物流配送在整个物流过程中具有的重要意义及我国物流配送的现 状，说明了解决VRP的必要性及现实意义：建立了物流配送中 VRP的两种数学模型：禾
4、U用回 路表示的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的算法都属于两阶段法。一 般第一阶段常用构造算法，在第二阶段常用的改进技术有2-o
10、pt(Lin,1965)，3-opt(Lin Kernighan,1973)和Or-opt (Or,1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。一些基于数学规划的算法也属于两阶段法，把问题直接描述成一个数学规划问题，根据其模型的特殊构形，应用一定的技术 (如分解)进行划分，进而求解己被广泛研究过的子问题(Fisher 和 Jaikumar,1981)。在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解 过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这
11、样做通常会增加模型最终实现并被采用的可能性。此方法是目前成果最丰富、应用最多的一类方法。每一种方法讨论的情况不尽一致，适用范围也不完全相同。2.2.3 智能化算法(Intelligent Algorithm)这类算法以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间。总体来看，尽管启发式算法能够在有限的时间内求出质量较高的解，但由于其搜索解空间的能力有所限制，因此经常无法达到预期的要求。20世纪90年代以来，由于人工智能方法在解决组合优化问题中的强大功能，不少学者开始将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法(智能化启发式算法)。智能化启发式算法从本质上
12、讲仍然属于启发式算法，其基本思想是从一初始解开始，通过对当前的解进行反复地局部扰乱 (Perturbatio ns)以达到较好的解。目前，最常见的智能化启发式算法包括模拟退火算法(Simulated Annealing)、禁忌搜索算法(Tabu Search)、遗传算法(Genetic Algorithm)、蚁群算法(Ant Colony)和神经网络(Neutral Networks)方法等。2.3 VRP 中常见的约束条件在VRP中，最常见的约束条件有：(1) 容量约束：任意车辆路径的总重量不能超过该车辆的能力负荷。引出带容量约束的车辆路径问题(CapacitatedVehicle Rout
13、ing Problem, CVRP。(2) 优先约束：引出优先约束车辆路径问题(VehicleRout ing Problem with precede nee Constraints, VRPPC)(3) 车型约束：引出多车型车辆路径问题(Mixed/Heteroge neous Fleet Vehicle Rout ingProblem , MFVRP/ HFVRP)(4) 时间窗约束：包括硬时间窗(Hard Time windows) 和软时间窗(Soft Time windows)约束。引出带时间窗(包括硬时间窗和软时间窗 )的车辆路径问题(Vehicle Routing Proble
14、m withTime windows ，VRPTW。(5) 相容性约束：引出相容性约束车辆路径问题(VehicleRout ing Problem with Compatibility Constraints， VRPCC)(6) 随机需求：引出随机需求车辆路径问题(VehicleRouti ng Problem with Stochastic Dema nd, VRPSD)(7) 开路：引出开路车辆路径问题(Open Vehicle Routi ngProblem)。(8) 多运输中心：引出多运输中心的车辆路径问题(Multi-Depot Vehicle Routi ng Problem)。
15、(9) 回程运输：引出带回程运输的车辆路径问题(VehicleRout ing Problem with Backhauls)。(10) 最后时间期限：弓I出带最后时间期限的车辆路径问题(Vehicle Routi ng Problemwith Time Deadli nes) 。(11) 车速随时间变化：引出车速随时间变化的车辆路径问题(Time-Depe nde nt Vehicle Routi ng Problem)。2.4 CVRP问题描述及其数学模型CVRP的描述：设某中心车场有k辆车，每辆配送车的最大载重量Q需要对n个客户(节点)进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i的货物需求量是 qi (i=1,2,n),且qQ记配送中心编号为0，各客户编号为i(i=1,2 ,，n), Cj表示客户i到客户j的距离。求满足车辆数最小，车辆行驶总路程最短的运送方案。 定义变量如下：1 车车辆*由那卩儿科0 否则张習则建立此问题的数学模型：mi nz =cijXijk(2.2
