车辆路径问题概念、模型与算法(五星推荐).ppt

1、车辆路径问题概念、模型及算法,1、定义,车辆路径问题(VRP)一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定问题的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。,目前有关VRP的研究已经可以表示（如图1）为：给定一个或多个中心点（中心仓库，central depot）、一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从

2、每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化。,2、VRP问题约束,(1) 容量约束：任意车辆路径的总重量不能超过该车辆的能力负荷。引出带容量约束的车辆路径问题(CapacitatedVehicle Routing Problem，CVRP)。 (2) 优先约束：引出优先约束车辆路径问题(VehicleRouting Problem with precedence Constraints，VRPPC)。 (3) 车型约束：引出多车型车辆路径问题(Mixed/Heterogeneou

3、s Fleet Vehicle Routing Problem，MFVRP/ HFVRP)。,(4) 时间窗约束：包括硬时间窗(Hard Time windows)和软时间窗(Soft Time windows) 约束。引出带时间窗(包括硬时间窗和软时间窗)的车辆路径问题(Vehicle Routing Problem withTime windows，VRPTW)。 (5) 相容性约束：引出相容性约束车辆路径问题(VehicleRouting Problem with Compatibility Constraints，VRPCC)。 (6) 随机需求：引出随机需求车辆路径问题(Vehicl

4、eRouting Problem with Stochastic Demand，VRPSD)。,(7) 开路：引出开路车辆路径问题(Open Vehicle RoutingProblem)。 (8) 多运输中心：引出多运输中心的车辆路径问题(Multi-Depot Vehicle Routing Problem)。 (9) 回程运输：引出带回程运输的车辆路径问题(VehicleRouting Problem with Backhauls)。 (10) 最后时间期限：引出带最后时间期限的车辆路径问题(Vehicle Routing Problem with Time Deadlines)。 (1

5、1) 车速随时间变化：引出车速随时间变化的车辆路径问题(Time-Dependent Vehicle Routing Problem)。,3、 CVRP问题描述及其数学模型,CVRP的描述：设某中心车场有k辆车，每辆配送车的最大载重量Q，需要对n个客户(节点)进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i的货物需求量是qi (i=1,2,n)，且qiQ。记配送中心编号为0，各客户编号为i(i=1,2 ,n)， cij表示客户i到客户j的距离。求满足车辆数最小，车辆行驶总路程最短的运送方案。,定义变量如下:,建立此问题的数学模型：,4、车辆路径问题算法综述,目前，

6、求解车辆路径问题的方法非常多，基本上可以分为精确算法和启发式算法2大类。 精确算法是指可求出其最优解的算法，主要运用线性规划、整数规划、非线性规划等数学规划技术来描述物流系统的数量关系，以便求得最优决策。（运筹学领域） 精确算法主要有： 分枝定界法(Branch and Bound Approach) 割平面法(Cutting Planes Approach) 网络流算法(Network Flow Approach) 动态规划算法(Dynamic Programming Approach),分枝定界法(Branch and Bound Approach) 以求相应的线性规划问题的最优解为出发点

7、，如果得到的解不符合整数条件，就将原规划问题分成几支，每支增加了约束条件，即缩小了可行解区域，可行解范围也随之缩小了，因而整数规划的最优值不会优于相应的线性规划最优值。 “定界”是指为目标函数定上下界，以便自动舍去那些最优值较差的子问题，提高计算效率。当整数规划问题的最优目标函数值的上下界相等时，该整数规划最优解已求出。,首先，不考虑变量的整数约束，求解松弛问题线性规划的最优解。如果线性规划的最优解恰好是整数解，则这个解就是整数规划的最优解。 如果线性规划的最优解中至少有一个变量不是整数，把线性规划的可行域切割成两部分，分别求解两个线性规划的最优解。,如果这两个线性规划的最优解还不是整数解，分

8、别把每一个可行域再进行分割。这个过程，叫做“分支”。 分支过程得到的整数解中，目标函数值最优的一个叫做整数规划目标函数值的“界”。分支过程中非整数的线性规划的最优解，如果目标函数值劣于或等于这个“界”，就停止继续分支。这个过程，叫做“定界”。,割平面法(Cutting Planes Approach) 用割平面法求解整数规划的基本思路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止。如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解。这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原

9、已得到的非整数最优解)。而把所有的整数解都保留下来，故称新增加的约束条件为割平面。当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。,网络流算法(Network Flow Approach) 图论中的一种理论与方法，研究网络上的一类最优化问题 。1955年 ，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的

10、赋权有向图 D= （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。,动态规划算法(Dynamic Programming Approach) 动态规划是一种求解多阶段决策问题的系统技术。 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问

11、题。 各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。,总的说来，精确性算法基于严格的数学手段，在可以求解的情况下，其解通常要优于人工智能算法。但由于引入严格的数学方法，计算量一般随问题规模的增大呈指数增长，因而无法避开指数爆炸问题，从而使该类算法只能有效求解中小规模的确定性VRP，并且通常这些算法都是针对某一特定问题设计的,适用能力较差,因此在实际中其应用

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

13、进线路，直到所有点都被安排进线路为止。该类算法的每一步把当前的线路构形(很可能是不可行的)跟另外的构形(也可能是不可行的)进行比较并加以改进，后者或是根据某个判别函数(例如总费用)会产生最大限度的节约的构形，或是以最小代价把一个不在当前构形上的需求对象插入进来的构形，最后得到一个较好的可行构形。这类算法中中最著名的是Clarke和Wright在1964年提出的节约算法。 构造算法最早提出来解决旅行商问题，这些方法一般速度快，也很灵活，但这类方法有时找到的解离最优解差得很远。,两阶段法(Two-phase Algorithm) 学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进，

14、为此提出了两阶段法。第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止。,一般第一阶段常用构造算法，在第二阶段常用的改进技术有2-opt(Lin,1965)，3-opt(Lin Kernighan,1973)和Or-opt (Or,1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。 在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种

15、判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性。,智能化算法(Intelligent Algorithm) 这类算法以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间。 总体来看，尽管启发式算法能够在有限的时间内求出质量较高的解，但由于其搜索解空间的能力有所限制，因此经常无法达到预期的要求。20世纪90年代以来，由于人工智能方法在解决组合优化问题中的强大功能，不少学者开始将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法(智能化启发式算法)。,智能化启发式算法从本质上讲仍然属于启发式算法，其基本思想是从一初

16、始解开始，通过对当前的解进行反复地局部扰乱(Perturbations)以达到较好的解。目前，最常见的智能化启发式算法包括模拟退火算法(Simulated Annealing)、禁忌搜索算法(Tabu Search)、遗传算法(Genetic Algorithm)、蚁群算法(Ant Colony)和神经网络(Neutral Networks)、粒子群算法（Particle Swarm Optimization,PSO）方法等。,模拟退火算法(Simulated Annealing) 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增

17、大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e(-E/(kT)，其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule

18、)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。,禁忌搜索算法(Tabu Search) 禁忌算法是一种随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。 1、在搜索中，构造一个短期循环记忆表-禁忌表，禁忌表中存放刚刚进行过的 |T|（T称为禁忌表）个邻居的移动，这种移动即解的简单变化。 2、禁忌表中的移动称为禁忌移动。对于进入禁忌表中的移动， 在

19、以后的 |T| 次循环内是禁止的，以避免回到原来的解，从而避免陷入循环。|T| 次循环后禁忌解除。 3、禁忌表是一个循环表，在搜索过程中被循环的修改，使禁忌表始终保持 |T| 个移动。 4、即使引入了禁忌表，禁忌搜索仍可能出现循环。因此，必须给定停止准则以避免出现循环。当迭代内所发现的最好解无法改进或无法离开它时，算法停止。,遗传算法(Genetic Algorithm) 遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（g

20、ene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）

21、个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。,蚁群算法(Ant Colony) 各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后