物流运输与配送管理 教学课件 ppt 作者 杜文 14

1、第14章 车辆路径问题 （Vehicle Path Problem）,车辆路径问题，又称运输调度问题，简记VRP&VSP,包括两部分，其一是行车路线的设计，其二是出行时间表的安排。该问题1959年由Dantzig和Ramser提出的，是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低，通过研究VRP可以合理使用调运工具，优化运输路线，降低企业物流成本。,第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 f

2、or One Center VRP with Non-fully Loaded） 14.2.1 禁忌搜寻法简介（Tabu-Research Algorithm） 14.2.2 问题描述与符号表示（The Problem and Symbol） 14.2.3 求解过程（Arithmetic）,第14章 车辆路径问题（Vehicle Path Problem） 14.3 车辆调度的其他算法简介（Some Other Algorithms for VRP） 14.3.1 遗传算法（Genetic Algorithm） 14.3.2 神经网络算法（Neural Networks Algorithm）,14.1 物流配送车辆优化调度的概述,14.1.1 概述,车辆路径问题一般定义为：对一系列装货点和(或)卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如：货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如：路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。,14.1 物流配送车辆优化调度的概述,14.1.1 概述,目前有关V

3、RP的研究已经可以表示为：给定一个或多个中心（中心车库）一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所载的货物不能超过它的容量。,14.1 物流配送车辆优化调度的概述,14.1.2 路径特性,车辆路径问题的特性比较复杂，总的来说包含四个方面的属性： （1）地址特性包括：车场数目、需求类型、作业要求。 （2）车辆特性包括：车辆数量、载重量约束、可运载品种约束、运行路线约束、工作时间约束。 （3）问题的其他特性。 （4）目标函数可能是总成本极小化，或者极小化最大作业成本，或者最大化准时作业。,14.1 物流配送车辆优化调度的概述,14.1.2 路径特性,车辆路径问题的特性导致了算法的多样性和复杂性。为简化问题的求解，常常应用一些技术将问题分解或转化成一个或几个已经研究过的基本问题，再用相应比较成熟的基本理论和方法，以得到原满意解。,14.1 物流配送车辆优化调度的概述,14.1.3 常用的基本问题,（1）旅行商问题 （2）带容量约束的车辆路线问题 （3）带时间窗的车辆路线问题 （4）收集和分发问题 （5）多车型车辆路线问题 （6）优先约束车辆路线问题 （7）相容性

4、约束车辆路线问题 （8）随机需求车辆路线问题,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,由于车辆路径问题是个NP难题，为了找到满足约束条件的最优解，就必须检查很大的设计空间，而设计空间又是多维的非连续空间，很难找到一个规范的搜索集来系统地搜寻整个空间，所以很难得到全局的最优解或满意解。现代研究针对以上问题，现在已有很多方法。,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,1. 数学解析法 此法以动态规划法、整数规划法、树状搜寻法等方式为主来进行求解，对于配送点数较少的情形能求得一个最优解，但若求解的节点数增加，则其结果相对变差，与实际配送的情相差较大。,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,2. 人机互动法 提供使用者借由人机互动的方式，结合使用者过去的经验，调整该模型的参数，以作为配送路线规划决策的依据。,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,3. 先分组再排路线法 先将所有配送点分成数个群组，再分别对各个群组进行路线规划，如扫描法，根据所有配送

5、点的分布，以极坐标的表示方法来呈现各配送点的位置，然后任意选取一配送点为起始点，依顺时针或逆时针的方向选取尚未指派的配送点，并以货车的容量或其他条件作为限制，进行车辆配送的分组作业，再以求解旅行商问题的算法进行最优化的操作。,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,4. 先排线路再分组法（Rout FirstCluster Second） 与前一种方法相反，这种方法是先进行路线的规划，然后再进行分割，如巨集分割法，此方法又因切割方式的差异，可分为单巨集切割法及多巨集切割法二种。,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,（1）单巨集切割法 取所有配送点进行旅行商问题的求解，建立一个自原点出发，经过所有结点，最后回到原点的巡回路线，然后以最短路径解法对此路线进行分割，求得所需要的结果。 （2）多巨集切割法 与单巨集切割法相似，最大的差异在于建立巡回路线时并不包含原点，因此在切割路线时，可以有较多的切割方式。,14.1 物流配送车辆优化调度的概述

6、,14.1.4 车辆路径问题的求解方法,5. 节省或插入法（Saving or Insertion） 由于数学解析法具有先天上的限制，对于大规模求解问题的效率与结果较为不佳，因此，求得一个近似的最优解，是本论文研究的目标，为克服这个问题，许多学者提出了各种求解方法，其优点在于能够改善以往数学方法的求解效率，但并不一定保证所求出的解是最优解。节省与插入法即为此一范畴的求解方法。,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,（1）节省法 此方法以三角不等式为基础，一部车只一个配送点为起始条件，如此若有N个配送点即有N条路线，计算节省量，将较短的路线与原始路线交换，缩短配送距离。假设配送点i与j分别由不同的车辆来服务，如将两个配送点由一辆车服务，即可得到一个节省值，而后依据节省值的大小决定需求点是否可以相互连接，连接的方法有连结、并入、合并等三种。,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,（2）插入法 将节省法中节省值的观念应用于循序路线构建上，并以

7、距离物流中心最远的配送点作为起始点，再以最临近的一点作为下一个插入点的配送点，求其节省值，取值最大者以决定插入的位置并进行插入，重复进行选取与插入的步骤，直到所有配送点均被服务到为止。,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,6. 改善或交换法 常见的改善方法有2-opt、3-opt方法，与k-opt方法等，是先以其他方法产生初始解，再利用节点或节线交换的方式，对求出的路线解进行改善，达到更好的目标函数值。,14.1 物流配送车辆优化调度的概述,14.1.4 车辆路径问题的求解方法,7. 数学规划近似法 此方法针对放松后的数学模式进行最优化处理。如车辆路线问题，转换成由两个相关子问题组成的数学规划，其中一个为一般化配送点的指派问题，另一个则为旅行商问题，并提出一些准则用来产生路径种子点，再利用节省值产生一个指派问题的目标函数，然后先解指派问题，再针对每辆车的旅行商问题求解。,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,禁忌搜寻法的概念首先由Glover于1977年提出，当时是将其应用于整数规划的求解问题上，直到19

8、89、1990年Glover才将禁忌搜寻法的结构与方法完整提出。其主要内容是使用移步的方式，运用具有弹性的记忆结构，以迭代的方式从目前的解出发展开对邻近解的搜寻，而其记忆结构可分为长期记忆结构和短期记忆结构两种。记忆的目的在于使寻求解的过程能越过局部最优解而找到更好的解。,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,禁忌搜寻法的演算过程是先在问题中找到一组可行解 ，再依使用者所做的定义找出所有的邻近解N( )，在N( )中找出最优解 ，若F( )优于F( )时，即将现在解移步至 ，为了避免寻求解的范围落入某一区域中，禁忌搜寻法允许当F( )未能优于F( )时，仍然接受 为新的现在解，使寻解的过程能跳离某一区域，找到更佳的解。,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,1. 初始解 如果没有特殊限制条件，可以任选一可行解作为该问题的初始解，以本论文研究的车辆路线问题为例，初始解的限制条件为“车辆的载重”，因此必须考虑满足所有配送点及车辆载重的限制，并建立适当的初始解。,禁忌搜寻法的主要步骤,14.2 单中心非满载送

9、货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,2. 移步 每次迭代的过程中，在所有合法的邻近解里，选择其一进行变动的行为，称之为移步。,禁忌搜寻法的主要步骤,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,3. 禁忌名单 为了避免重复选取已经选取过的解，禁忌搜寻法会将最近几次移步的属性记录在禁忌名单中，作为禁忌限制的参考指标，来防止重复搜寻的现象。 禁忌名单的长度会影响到求解寻优过程的结果，当禁忌名单长度太短时，搜寻过程可能会落入局部解的限制；若禁忌名单太长，除了要花费较多的时间检查移步是否被禁忌外，还可能导致搜寻过程远离最优解位置的可能性。,禁忌搜寻法的主要步骤,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,4. 免禁准则 当一个移步为禁忌，但是若此一移步被允许，可以使得目前所搜寻到的目标函数值得以改善时，则接受此一移步，免禁准则的目的就是用来释放原本禁忌的状态，在求解过程中能逃脱局部最优解的局限。,禁忌搜寻法的主要步骤,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.1 禁忌搜寻法简介,5. 停止准则 停止准则是整个演算过程结束的条件，通常使用以下四种准则： （1）预设最大迭代次数； （2）目标函数值持续未改善的次数； （3）预设允许CPU最长的执行时间； （4）预设可接受的目标函数值。,禁忌搜寻法的主要步骤,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.2 问题描述与符号表示,所求单中心非满载送货车辆路径问题具有以下特点： （1）物流配送中心的位置为已知并且唯一； （2）需求点的位置及需求量为已知； （3）需求点与需求点间的路线与距离为已知且确定； （4）货车经过需求点时只有卸货而无装货，货物配送完毕以空车返回配送中心； （5）物流中心只有一种货车。 所求的目标函数为：使货车配送路线的总成本最小，在本文中体现为配送路线距离最短。,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.2 问题描述与符号表示,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.2 问题描述与符号表示,数学模型建立及公式所代表的意义如下：,14.2 单中心非满载送货车辆路径问题启发式算法,14.2.3 求解过程,本文拟采用“先分组再排线路”的二阶

《物流运输与配送管理 教学课件 ppt 作者 杜文 14》由会员E****分享，可在线阅读，更多相关《物流运输与配送管理 教学课件 ppt 作者 杜文 14》请在金锄头文库上搜索。