车辆路径问题PPT课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《车辆路径问题PPT课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 车辆 路径 问题 PPT 课件
- 资源描述:
-
1、.1第14章 车辆路径问题(Vehicle Path Problem) 车辆路径问题,又称运输调度问题,简记VRP&VSP,包括两部分,其一是行车路线的设计,其二是出行时间表的安排。该问题1959年由Dantzig和Ramser提出的,是指在客户需求位置已知的情况下,确定车辆在各个客户间的行程路线,使得运输路线最短或运输成本最低,通过研究VRP可以合理使用调运工具,优化运输路线,降低企业物流成本。.2第14章 车辆路径问题(Vehicle Path Problem)14.1 物流配送车辆优化调度的概述(Introduction of VRP for Logistics Distribution
2、)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 Proble
3、m 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).414.1 物流配送车辆优化调度的概述 14.1.1 概述 车辆路径问题一般定义为:对一系列装货点和(或)卸货点,组织适当的行车线路,使车辆有序地通过它们,在满足一定的约束条件(如:货物需求量、发送量、交发货时间、车辆容量
4、限制、行驶里程限制、时间限制等)下,达到一定的目标(如:路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。 .514.1 物流配送车辆优化调度的概述 14.1.1 概述 目前有关VRP的研究已经可以表示为:给定一个或多个中心(中心车库)一个车辆集合和一个顾客集合,车辆和顾客各有自己的属性,每辆车都有容量,所载的货物不能超过它的容量。 配送中心.614.1 物流配送车辆优化调度的概述 14.1.2 路径特性 车辆路径问题的特性比较复杂,总的来说包含四个方面的属性:(1)地址特性包括:车场数目、需求类型、作业要求。(2)车辆特性包括:车辆数量、载重量约束、可运载品种约束、运行路线约束、工作时间
5、约束。(3)问题的其他特性。(4)目标函数可能是总成本极小化,或者极小化最大作业成本,或者最大化准时作业。.714.1 物流配送车辆优化调度的概述 14.1.2 路径特性 车辆路径问题的特性导致了算法的多样性和复杂性。为简化问题的求解,常常应用一些技术将问题分解或转化成一个或几个已经研究过的基本问题,再用相应比较成熟的基本理论和方法,以得到原满意解。.814.1 物流配送车辆优化调度的概述 14.1.3 常用的基本问题 (1)旅行商问题(2)带容量约束的车辆路线问题(3)带时间窗的车辆路线问题(4)收集和分发问题(5)多车型车辆路线问题(6)优先约束车辆路线问题(7)相容性约束车辆路线问题(8
6、)随机需求车辆路线问题.914.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 由于车辆路径问题是个NP难题,为了找到满足约束条件的最优解,就必须检查很大的设计空间,而设计空间又是多维的非连续空间,很难找到一个规范的搜索集来系统地搜寻整个空间,所以很难得到全局的最优解或满意解。现代研究针对以上问题,现在已有很多方法。.1014.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 1. 数学解析法 此法以动态规划法、整数规划法、树状搜寻法等方式为主来进行求解,对于配送点数较少的情形能求得一个最优解,但若求解的节点数增加,则其结果相对变差,与实际配送的情相差
7、较大。.1114.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 2. 人机互动法 提供使用者借由人机互动的方式,结合使用者过去的经验,调整该模型的参数,以作为配送路线规划决策的依据。 .1214.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 3. 先分组再排路线法 先将所有配送点分成数个群组,再分别对各个群组进行路线规划,如扫描法,根据所有配送点的分布,以极坐标的表示方法来呈现各配送点的位置,然后任意选取一配送点为起始点,依顺时针或逆时针的方向选取尚未指派的配送点,并以货车的容量或其他条件作为限制,进行车辆配送的分组作业,再以求解旅行商问题的算法
8、进行最优化的操作。.1314.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 abdcefijghlkmnopqrtsuwvxyz扫描方向D.1414.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 4. 先排线路再分组法(Rout FirstCluster Second) 与前一种方法相反,这种方法是先进行路线的规划,然后再进行分割,如巨集分割法,此方法又因切割方式的差异,可分为单巨集切割法及多巨集切割法二种。.1514.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 (1)单巨集切割法 取所有配送点进行旅行商问题的求解,建立
9、一个自原点出发,经过所有结点,最后回到原点的巡回路线,然后以最短路径解法对此路线进行分割,求得所需要的结果。(2)多巨集切割法 与单巨集切割法相似,最大的差异在于建立巡回路线时并不包含原点,因此在切割路线时,可以有较多的切割方式。 .1614.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 5. 节省或插入法(Saving or Insertion) 由于数学解析法具有先天上的限制,对于大规模求解问题的效率与结果较为不佳,因此,求得一个近似的最优解,是本论文研究的目标,为克服这个问题,许多学者提出了各种求解方法,其优点在于能够改善以往数学方法的求解效率,但并不一定保证所求
10、出的解是最优解。节省与插入法即为此一范畴的求解方法。 .1714.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 (1)节省法 此方法以三角不等式为基础,一部车只一个配送点为起始条件,如此若有N个配送点即有N条路线,计算节省量,将较短的路线与原始路线交换,缩短配送距离。假设配送点i与j分别由不同的车辆来服务,如将两个配送点由一辆车服务,即可得到一个节省值,而后依据节省值的大小决定需求点是否可以相互连接,连接的方法有连结、并入、合并等三种。 .1814.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 连结并入合并abcbbbbaaaaabcccdddd
11、ee.1914.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 (2)插入法 将节省法中节省值的观念应用于循序路线构建上,并以距离物流中心最远的配送点作为起始点,再以最临近的一点作为下一个插入点的配送点,求其节省值,取值最大者以决定插入的位置并进行插入,重复进行选取与插入的步骤,直到所有配送点均被服务到为止。 .2014.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 6. 改善或交换法 常见的改善方法有2-opt、3-opt方法,与k-opt方法等,是先以其他方法产生初始解,再利用节点或节线交换的方式,对求出的路线解进行改善,达到更好的目标函数值。
12、 .2114.1 物流配送车辆优化调度的概述 14.1.4 车辆路径问题的求解方法 7. 数学规划近似法 此方法针对放松后的数学模式进行最优化处理。如车辆路线问题,转换成由两个相关子问题组成的数学规划,其中一个为一般化配送点的指派问题,另一个则为旅行商问题,并提出一些准则用来产生路径种子点,再利用节省值产生一个指派问题的目标函数,然后先解指派问题,再针对每辆车的旅行商问题求解。 .2214.2 单中心非满载送货车辆路径问题启发式算法 14.2.1 禁忌搜寻法简介 禁忌搜寻法的概念首先由Glover于1977年提出,当时是将其应用于整数规划的求解问题上,直到1989、1990年Glover才将禁
13、忌搜寻法的结构与方法完整提出。其主要内容是使用移步的方式,运用具有弹性的记忆结构,以迭代的方式从目前的解出发展开对邻近解的搜寻,而其记忆结构可分为长期记忆结构和短期记忆结构两种。记忆的目的在于使寻求解的过程能越过局部最优解而找到更好的解。 .2314.2 单中心非满载送货车辆路径问题启发式算法 14.2.1 禁忌搜寻法简介 禁忌搜寻法的演算过程是先在问题中找到一组可行解 ,再依使用者所做的定义找出所有的邻近解N( ),在N( )中找出最优解 ,若F( )优于F( )时,即将现在解移步至 ,为了避免寻求解的范围落入某一区域中,禁忌搜寻法允许当F( )未能优于F( )时,仍然接受 为新的现在解,使
14、寻解的过程能跳离某一区域,找到更佳的解。 x xxxxxx x x x .2414.2 单中心非满载送货车辆路径问题启发式算法 14.2.1 禁忌搜寻法简介 1. 初始解 如果没有特殊限制条件,可以任选一可行解作为该问题的初始解,以本论文研究的车辆路线问题为例,初始解的限制条件为“车辆的载重”,因此必须考虑满足所有配送点及车辆载重的限制,并建立适当的初始解。禁忌搜寻法的主要步骤 .2514.2 单中心非满载送货车辆路径问题启发式算法 14.2.1 禁忌搜寻法简介 2. 移步 每次迭代的过程中,在所有合法的邻近解里,选择其一进行变动的行为,称之为移步。 禁忌搜寻法的主要步骤 .2614.2 单中
15、心非满载送货车辆路径问题启发式算法 14.2.1 禁忌搜寻法简介 3. 禁忌名单 为了避免重复选取已经选取过的解,禁忌搜寻法会将最近几次移步的属性记录在禁忌名单中,作为禁忌限制的参考指标,来防止重复搜寻的现象。 禁忌名单的长度会影响到求解寻优过程的结果,当禁忌名单长度太短时,搜寻过程可能会落入局部解的限制;若禁忌名单太长,除了要花费较多的时间检查移步是否被禁忌外,还可能导致搜寻过程远离最优解位置的可能性。禁忌搜寻法的主要步骤 .2714.2 单中心非满载送货车辆路径问题启发式算法 14.2.1 禁忌搜寻法简介 4. 免禁准则 当一个移步为禁忌,但是若此一移步被允许,可以使得目前所搜寻到的目标函
16、数值得以改善时,则接受此一移步,免禁准则的目的就是用来释放原本禁忌的状态,在求解过程中能逃脱局部最优解的局限。禁忌搜寻法的主要步骤 .2814.2 单中心非满载送货车辆路径问题启发式算法 14.2.1 禁忌搜寻法简介 5. 停止准则 停止准则是整个演算过程结束的条件,通常使用以下四种准则: (1)预设最大迭代次数; (2)目标函数值持续未改善的次数; (3)预设允许CPU最长的执行时间; (4)预设可接受的目标函数值。 禁忌搜寻法的主要步骤 .2914.2 单中心非满载送货车辆路径问题启发式算法 14.2.2 问题描述与符号表示 所求单中心非满载送货车辆路径问题具有以下特点: (1)物流配送中
17、心的位置为已知并且唯一; (2)需求点的位置及需求量为已知; (3)需求点与需求点间的路线与距离为已知且确定; (4)货车经过需求点时只有卸货而无装货,货物配送完毕以空车返回配送中心; (5)物流中心只有一种货车。 所求的目标函数为:使货车配送路线的总成本最小,在本文中体现为配送路线距离最短。.3014.2 单中心非满载送货车辆路径问题启发式算法 14.2.2 问题描述与符号表示 问题中的参数做以下定义: V:需求点集合 O:物流配送中心 K:货车的容量 qi:配送点i的需求量 cij:配送点i到配送点j的距离 1 如果配送点i由货车k服务时;yik= 0 其他情形时 1 如果货车k经由配送点
展开阅读全文