车辆路径问题课件.ppt

.,1,第14章 车辆路径问题（Vehicle Path Problem）,车辆路径问题，又称运输调度问题，简记VRP&VSP,包括两部分，其一是行车路线的设计，其二是出行时间表的安排。该问题1959年由Dantzig和Ramser提出的，是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低，通过研究VRP可以合理使用调运工具，优化运输路线，降低企业物流成本。,.,2,第14章 车辆路径问题（Vehicle Path Problem）14.1 物流配送车辆优化调度的概述（Introduction of VRP for Logistics Distribution）14.1.1 概述（Introduction）14.1.2 路径特性（The Route Characteristic）14.1.3 常用的基本问题（The Basic Problems）14.1.4 车辆路径问题的求解方法（The Method of Solving Route Problem）14.2 单中心非满载送货车辆路径问题启发式算法（Heuristic Methods for One Center VRP with Non-fully Loaded）14.2.1 禁忌搜寻法简介（Tabu-Research Algorithm）14.2.2 问题描述与符号表示（The Problem and Symbol）14.2.3 求解过程（Arithmetic）,.,3,第14章 车辆路径问题（Vehicle Path Problem）14.3 车辆调度的其他算法简介（Some Other Algorithms for VRP）14.3.1 遗传算法（Genetic Algorithm）14.3.2 神经网络算法（Neural Networks Algorithm）,.,4,14.1 物流配送车辆优化调度的概述,14.1.1 概述,车辆路径问题一般定义为：对一系列装货点和(或)卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如：货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如：路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。,.,5,14.1 物流配送车辆优化调度的概述,14.1.1 概述,目前有关VRP的研究已经可以表示为：给定一个或多个中心（中心车库）一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所载的货物不能超过它的容量。,.,6,14.1 物流配送车辆优化调度的概述,14.1.2 路径特性,车辆路径问题的特性比较复杂，总的来说包含四个方面的属性：（1）地址特性包括：车场数目、需求类型、作业要求。（2）车辆特性包括：车辆数量、载重量约束、可运载品种约束、运行路线约束、工作时间约束。（3）问题的其他特性。（4）目标函数可能是总成本极小化，或者极小化最大作业成本，或者最大化准时作业。,.,7,14.1 物流配送车辆优化调度的概述,14.1.2 路径特性,车辆路径问题的特性导致了算法的多样性和复杂性。为简化问题的求解，常常应用一些技术将问题分解或转化成一个或几个已经研究过的基本问题，再用相应比较成熟的基本理论和方法，以得到原满意解。,.,8,14.1 物流配送车辆优化调度的概述,14.1.3 常用的基本问题,（1）旅行商问题（2）带容量约束的车辆路线问题（3）带时间窗的车辆路线问题（4）收集和分发问题（5）多车型车辆路线问题（6）优先约束车辆路线问题（7）相容性约束车辆路线问题（8）随机需求车辆路线问题,.,9,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,由于车辆路径问题是个NP难题，为了找到满足约束条件的最优解，就必须检查很大的设计空间，而设计空间又是多维的非连续空间，很难找到一个规范的搜索集来系统地搜寻整个空间，所以很难得到全局的最优解或满意解。现代研究针对以上问题，现在已有很多方法。,.,10,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,1. 数学解析法 此法以动态规划法、整数规划法、树状搜寻法等方式为主来进行求解，对于配送点数较少的情形能求得一个最优解，但若求解的节点数增加，则其结果相对变差，与实际配送的情相差较大。,.,11,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,2. 人机互动法 提供使用者借由人机互动的方式，结合使用者过去的经验，调整该模型的参数，以作为配送路线规划决策的依据。,.,12,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,3. 先分组再排路线法 先将所有配送点分成数个群组，再分别对各个群组进行路线规划，如扫描法，根据所有配送点的分布，以极坐标的表示方法来呈现各配送点的位置，然后任意选取一配送点为起始点，依顺时针或逆时针的方向选取尚未指派的配送点，并以货车的容量或其他条件作为限制，进行车辆配送的分组作业，再以求解旅行商问题的算法进行最优化的操作。,.,13,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,.,14,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,4. 先排线路再分组法（Rout FirstCluster Second） 与前一种方法相反，这种方法是先进行路线的规划，然后再进行分割，如巨集分割法，此方法又因切割方式的差异，可分为单巨集切割法及多巨集切割法二种。,.,15,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,（1）单巨集切割法 取所有配送点进行旅行商问题的求解，建立一个自原点出发，经过所有结点，最后回到原点的巡回路线，然后以最短路径解法对此路线进行分割，求得所需要的结果。（2）多巨集切割法 与单巨集切割法相似，最大的差异在于建立巡回路线时并不包含原点，因此在切割路线时，可以有较多的切割方式。,.,16,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,5. 节省或插入法（Saving or Insertion） 由于数学解析法具有先天上的限制，对于大规模求解问题的效率与结果较为不佳，因此，求得一个近似的最优解，是本论文研究的目标，为克服这个问题，许多学者提出了各种求解方法，其优点在于能够改善以往数学方法的求解效率，但并不一定保证所求出的解是最优解。节省与插入法即为此一范畴的求解方法。,.,17,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,（1）节省法 此方法以三角不等式为基础，一部车只一个配送点为起始条件，如此若有N个配送点即有N条路线，计算节省量，将较短的路线与原始路线交换，缩短配送距离。假设配送点i与j分别由不同的车辆来服务，如将两个配送点由一辆车服务，即可得到一个节省值，而后依据节省值的大小决定需求点是否可以相互连接，连接的方法有连结、并入、合并等三种。,.,18,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,.,19,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,（2）插入法 将节省法中节省值的观念应用于循序路线构建上，并以距离物流中心最远的配送点作为起始点，再以最临近的一点作为下一个插入点的配送点，求其节省值，取值最大者以决定插入的位置并进行插入，重复进行选取与插入的步骤，直到所有配送点均被服务到为止。,.,20,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,6. 改善或交换法 常见的改善方法有2-opt、3-opt方法，与k-opt方法等，是先以其他方法产生初始解，再利用节点或节线交换的方式，对求出的路线解进行改善，达到更好的目标函数值。,.,21,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,7. 数学规划近似法 此方法针对放松后的数学模式进行最优化处理。如车辆路线问题，转换成由两个相关子问题组成的数学规划，其中一个为一般化配送点的指派问题，另一个则为旅行商问题，并提出一些准则用来产生路径种子点，再利用节省值产生一个指派问题的目标函数，然后先解指派问题，再针对每辆车的旅行商问题求解。,.,22,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,禁忌搜寻法的概念首先由Glover于1977年提出，当时是将其应用于整数规划的求解问题上，直到1989、1990年Glover才将禁忌搜寻法的结构与方法完整提出。其主要内容是使用移步的方式，运用具有弹性的记忆结构，以迭代的方式从目前的解出发展开对邻近解的搜寻，而其记忆结构可分为长期记忆结构和短期记忆结构两种。记忆的目的在于使寻求解的过程能越过局部最优解而找到更好的解。,.,23,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,禁忌搜寻法的演算过程是先在问题中找到一组可行解 ，再依使用者所做的定义找出所有的邻近解N( )，在N( )中找出最优解 ，若F( )优于F( )时，即将现在解移步至 ，为了避免寻求解的范围落入某一区域中，禁忌搜寻法允许当F( )未能优于F( )时，仍然接受 为新的现在解，使寻解的过程能跳离某一区域，找到更佳的解。,.,24,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,1. 初始解 如果没有特殊限制条件，可以任选一可行解作为该问题的初始解，以本论文研究的车辆路线问题为例，初始解的限制条件为“车辆的载重”，因此必须考虑满足所有配送点及车辆载重的限制，并建立适当的初始解。,禁忌搜寻法的主要步骤,.,25,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,2. 移步 每次迭代的过程中，在所有合法的邻近解里，选择其一进行变动的行为，称之为移步。,禁忌搜寻法的主要步骤,.,26,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,3. 禁忌名单 为了避免重复选取已经选取过的解，禁忌搜寻法会将最近几次移步的属性记录在禁忌名单中，作为禁忌限制的参考指标，来防止重复搜寻的现象。 禁忌名单的长度会影响到求解寻优过程的结果，当禁忌名单长度太短时，搜寻过程可能会落入局部解的限制；若禁忌名单太长，除了要花费较多的时间检查移步是否被禁忌外，还可能导致搜寻过程远离最优解位置的可能性。,禁忌搜寻法的主要步骤,.,27,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,4. 免禁准则 当一个移步为禁忌，但是若此一移步被允许，可以使得目前所搜寻到的目标函数值得以改善时，则接受此一移步，免禁准则的目的就是用来释放原本禁忌的状态，在求解过程中能逃脱局部最优解的局限。,禁忌搜寻法的主要步骤,.,28,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,5. 停止准则 停止准则是整个演算过程结束的条件，通常使用以下四种准则： （1）预设最大迭代次数； （2）目标函数值持续未改善的次数； （3）预设允许CPU最长的执行时间； （4）预设可接受的目标函数值。,禁忌搜寻法的主要步骤,.,29,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.2 问题描述与符号表示,所求单中心非满载送货车辆路径问题具有以下特点： （1）物流配送中心的位置为已知并且唯一； （2）需求点的位置及需求量为已知； （3）需求点与需求点间的路线与距离为已知且确定； （4）货车经过需求点时只有卸货而无装货，货物配送完毕以空车返回配送中心； （5）物流中心只有一种货车。 所求的目标函数为：使货车配送路线的总成本最小，在本文中体现为配送路线距离最短。,.,30,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.2 问题描述与符号表示,.,31,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.2 问题描述与符号表示,数学模型建立及公式所代表的意义如下：,.,32,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,本文拟采用“先分组再排线路”的二阶段求解方法，进行配送线路的安排，也就是先将所有的配送点进行分组，然后再对每一组集中的配送点做最优化路线的处理，换句话说，是将车辆路线问题（VRP）转换成多个旅行商问题（TSP）进行求解。,.,33,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,为了使每辆货车所负责的配送点尽量相邻，满足物流业者单一区域配送上的需要，本论文以扫描法为基础，修改其演算方法进行初始解的构造，此方法可以达到先分组的目标，而且此方法在选择配送点进行求解时，可以将邻近的点选入同一群组中，满足初始解的基本需求。而在车辆路线规划方面，在构造初始解路线时，加入“车辆载重限制”的条件，使得初始解的每一群组均能满足此限制。,1. 构造初始解,.,34,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,（1）配送点数据的输入 进行禁忌搜索之前，必须先建立配送点的相关数据，而配送点数据应包括坐标及配送量。为配送点设计数据表。,2. 禁忌搜索,.,35,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,（2）设定参数 禁忌名单（Tabu List）的长度： 文献中大多建议使用7作为禁忌名单的长度。 最大重复搜寻次数： 本文假设其值为100，意即重复搜寻100次。,2. 禁忌搜索,.,36,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,（3）目标函数与移步 在计算目标函数值之前，首先建立一个对称矩阵，目的是为了存放两两配送点之间的距离。,2. 禁忌搜索,.,37,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,（3）目标函数与移步 计算目标函数值时，使用点对交换（ Pair Swap ）的节点交换法作为禁忌搜寻法的移步方法，来达到展开邻近解搜寻的目的。Pair Swap 有两种可能的形式，第一种可能的形式是针对彼此相邻的两个配送点；第二种形式是任选配送路线中的二点进行交换。由以上这种节点交换方法来判断是否有出现较佳的解，来获得较好的目标函数值。,2. 禁忌搜索,.,38,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,本文建立初始解所使用的扫描法，对车辆路线问题而言是一种先分组的方法，因此被纳入组中的配送点就无法在不同的路线中跳动，得到较差的初始解结果。此处使用两种不同路线中交换节点的方法来弥补这个缺陷，期望能在配送点尽量相邻的条件下，找出更好的路线规划。,3. 最优解的改善,.,39,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,方法一：将两不同路线中，相同顺序的连续两个配送点进行交换。如果交换后的总成本较原始路线为佳，则进行路线的变动。,3. 最优解的改善,交换后,交换前,.,40,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,方法二：将二路线中同一顺序的配送点互换后，其后的配送点全部一起交换，因为第一点交换与原路线没有差异，所以使用此法从第二点开始交换。如果交换后的总成本较原始路线为佳，则进行路线的变动。,3. 最优解的改善,交换后,交换前,.,41,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,整个求解的完整流程,3. 最优解的改善,.,42,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,由上页流程图可知，本算法是将车辆路径问题转换成多个旅行商问题进行求解。首先用改进后的扫描法建立初始解，即根据车辆载重限制对所有配送点建立多辆车的配送路径，然后对每辆车的配送路径用旅行商算法进行求解（即上页图所示的“将规划的路线选入TS，进行最优化处理”一步），最后找到总成本最小的解并利用前文所述之方法进行解的改善。,3. 最优解的改善,.,43,14.3 车辆调度的其他算法简介,14.3.1 遗传算法,遗传算法主要由选择、交叉和变异三个算子组成，分别模仿自然界进化过程中的自然选择和群体遗传过程中发生的交配和突变等现象。采用遗传算法求解车辆优化调度问题时，一般按照以下步骤进行：,.,44,14.3 车辆调度的其他算法简介,14.3.1 遗传算法,采用自然数对可行线路进行编码，如长度为lm的染色体可写为：(0,i11,i12,i1s, 0,i21,i2t,0,0,im1,imn)。其中，ikj表示第ikj项任务，这样的染色体结构可理解为车辆从车场0出发，经过任务i11，i12，i1s后回到车场，形成子路径1；如此反复，直到所有的m项任务全部被完成为止。在子路径1内交换i11 和i12的位置表示行走路径的改变，也使函数目标改变，这样，下面的遗传叠代可使函数目标最小，也即趋向于最佳或较佳的路径。,1. 确定染色体的编码和初始群体,.,45,14.3 车辆调度的其他算法简介,14.3.1 遗传算法,初始群体的产生采用随机方法，随机产生l个城市的全排列，根据任务的源点和汇点将0标准插入排列中，形成一条初始染色体。如此反复，直到满足群体数，群体数一般大于20个。,1. 确定染色体的编码和初始群体,.,46,14.3 车辆调度的其他算法简介,14.3.1 遗传算法,2. 确定适应度函数,车辆调度的优化目标有多种多样，常见的目标有总运费最小，总运输时间最短，空载车总运行时间最小，完成任务所需的车辆最小总运输时间最短，空载车总运行时间最小，完成任务所需的车辆最小等，以总运费最小为例，其目标函数为：式中，Cij为从源点i到汇点j每辆车的单位费用，Xij为每班从源点i到汇点j的满载车的数量。m,n为源点和汇点的数目。,.,47,14.3 车辆调度的其他算法简介,14.3.1 遗传算法,为保证车辆调度优化的正确性，约束往往必不可少，常见的约束有汇点处理能力约束，非负约束，车流连续性约束。 一般采用惩罚的方法来处理约束，如果一个染色体对应的解违反了某个约束，根据其违反的程度给予一定的惩罚，使其具有较小的适应度值。这样在不损失群体数目的基础上，随着迭代的进行，使不可行解的数目在群体中所占比例越来越小，可行解的数目则逐渐增加，并趋向最优解。,3. 处理约束,.,48,14.3 车辆调度的其他算法简介,14.3.1 遗传算法,经典的遗传算子包括复制、交叉、变异。复制算子的目的是保留优良个体，避免基因缺失，提高全局收敛性和效率。目前常用的复制算子有放回式随机复制又称轮盘赌复制，无放回式随机复制等十几种。,4. 遗传算子,.,49,14.3 车辆调度的其他算法简介,14.3.1 遗传算法,交叉算子的作用是组合出新的个体，在染色体空间进行有效搜索，同时降低对有效模式的破坏概率。染色体采用自然数编码时，交叉算子一般有部分匹配交叉，顺序交叉，圈交叉等。染色体采用二进制编码时，常采用的交叉算子有单点交叉，双点交叉等。交叉算子中采用的交叉率一般在0.750.95之间。,4. 遗传算子,.,50,14.3 车辆调度的其他算法简介,14.3.1 遗传算法,变异算子是为了克服基因缺失和不成熟收敛。目前常用的变异算子有常规位变异，均匀变异和非均匀变异等。变异算子的变异率一般为0.0050.01。 除了上述的经典遗传算子外，人们又研究了其他一些算子，称为高级算子，如显性算子、倒位算子、分离和易位算子、迁移算子等。,4. 遗传算子,.,51,14.3 车辆调度的其他算法简介,14.3.1 遗传算法,通过上述的遗传操作，产生性能最优的染色体串，根据初始的编码规定将该串解码成最优调度方案。 实用中，人们往往将遗传算法与其他方法如启发式方法和模拟退火算法杂合，以及将调度专家经验融入模型和遗传操作中，以提高求解的效果。,5. 确定调度方案,.,52,14.3 车辆调度的其他算法简介,14.3.2 神经网络算法,人们经常采用Hopfield网络和自组织特征映射神经网络来解决车辆的优化调度问题。在Hopfield网络中，系统能够从初始状态，经过一系列的状态转移而逐渐收敛于平衡状态，此平衡状态是局部极小点。采用神经网络来求解车辆调度问题时，一般按下述步骤进行。,.,53,14.3 车辆调度的其他算法简介,14.3. 2 神经网络算法,将车辆的源点、所经过的各个汇点和停点抽象成网络的结点，它们之间的有向路径抽象成网络的边，由此构成一个有向图G=(N,L,D)，其中N表示结点数，L表示边数，D为NN的矩阵，称为邻接矩阵。如果两个结点间存在路径，则邻接矩阵相应元素的值为路径的长度；如果两个结点间不存在路径，则邻接矩阵相应元素的值为。,1. 产生邻接矩阵,.,54,14.3 车辆调度的其他算法简介,14.3. 2 神经网络算法,对于车辆调度中的约束，将其作为神经网络的一个能量项来处理，将其施加一个惩罚项后加入到网络的能量方程式中，这样随着网络的收敛，约束的能量也逐渐趋于稳态，使约束得到体现。,2. 约束的处理,.,55,14.3 车辆调度的其他算法简介,14.3. 2 神经网络算法,3. 神经网络计算,设邻接矩阵中的每个元素对应着一个神经元，定义位于位置(x,i)的神经元的输出为Vxi。首先确定网络的能量函数，该能量函数包括网络的输出能量函数和各个约束转化的能量函数。式中，E5为距离最短目标，E1为有效路径约束，E2为输入输出路径约束，E3为网络收敛约束，E4为规定的起点终点约束。,.,56,14.3 车辆调度的其他算法简介,14.3. 2 神经网络算法,进而，确定神经元的传递函数和状态转移方程，经过网络的反复演化，直至收敛。当网络经过演化最终收敛时，可形成一个由0和1组成的换位阵，阵中的1所在位置即表示所经过的结点，这些结点间的距离之和即为最短距离。,3. 神经网络计算,.,57,14.3 车辆调度的其他算法简介,14.3. 2 神经网络算法,根据换位阵所形成的最短距离，最终来确定车辆调度的方案。,4. 调度方案的形成,.,58,第14章 车辆路径问题（复习思考题）,1、某物流公司为客户配送一种机电产品，该公司有6辆车，每辆车一次可载运20套该种产品，客户位置和需求数量如图，请运用扫描法在地图上作出配送路线（从正北开始反时针方向扫描）。并就该方法作出评价。,.,59,第14章 车辆路径问题（复习思考题）,2、请运用节约法求解上述习题，该题中网格为道路，单位网格长度为1Km。3、试分析校车的路线规划与快递公司送货取货的路线规划有何异同点。4、某装饰材料公司向各建筑工地配送建材，已知客户所在地位置及其距离，每天的配送任务已知，均为非满载，且存在时间窗，仓库非24小时营业，且卡车司机每天工作时间不超过8小时，连续工作不超过5小时，卡车数量以及载重量已知。试建立配送路线规划模型，给出一个算法。5、针对单中心非满载送货车辆路径问题，选择一个已知的算法，编程并给出算例。,个人观点供参考，欢迎讨论！,