物流配送中的最优路径规划模拟软件课件.doc
《物流配送中的最优路径规划模拟软件课件.doc》由会员分享,可在线阅读,更多相关《物流配送中的最优路径规划模拟软件课件.doc(27页珍藏版)》请在咨信网上搜索。
1、物流配送中的最优路径规划模拟软件说明书 学校:武汉轻工大学院系:数学与计算机学院 专业:信息与计算科学 指导教师:王防修 小组名称:一苹微歌 小组成员:胡鹏 程新强 彭肖飞日期:_年_月_日目录1引言-12算法思路-23总体设计-154系统出错处理设计-175客户数据生成模块设计说明-186行车路径最短模块设计说明-187行车时间最短模块设计说明-198解决堵车问题模块设计说明-209未解决的问题-2110参考资料-211引言1.1编写目的在B2C农产品电子商务物流配送时,物流车装载当日需要配送的货品从仓库出发,按照事先规划好的最优配送路径为每一个客户进行配送,最后返回仓库。物流配送模拟系统就
2、是在配送之前需要根据客户的配送地址间线路间距、经验路况做分析计算出一条最优配送路径。在配送过程中,如果某路段堵车,物流配送模拟系统需要动态调整配送路线。1.2背景说明设计一个物流配送中的最优路径规划模拟软件,解决物流配送过程中路程最短,时间最短以及堵车后重新规划等问题,并在软件的界面上模拟车辆的运行。随着市场经济的发展和物流技术专业化水平的提高,物流配送业得到了迅猛发展。配送路径的选择是否合理,对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。配送路径的优化问题是物流配送系统的一个主要问题,物流配送路径的优化就是以最低的运营成本,最快捷的响应速度、最短的配送运输时间,把货物
3、运至用户手中,而后两个指标与第一个指标之间存在着一定的制约关系,无法达到全体的最优,因此严格地讲,这是一个多目标的优化问题。1.3定义 T S P(Traveling Salesman Problem):旅行商问题 Backtrack:回溯 GA(Genetic Algorithm):遗传算法 SA(Simulated Annealing):模拟退火算法2算法思路2.1回溯算法2.1.1回溯法的定义 回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为
4、“回溯点”。2.1.2 回溯法的描述 可用回溯法求解的问题P,通常要能表达为:对于已知的由n元组组成的一个状态空间E= ,i=1,2,n,给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中是分量的定义域,且 | 有限,i=1,2,n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法,即对E中的所有n元组逐一地检测其是否满足D的全部约束,若满足,则为问题P的一个解。但显然,其计算量是相当大的。 我们发现,对于许多问题,所给定的约束集D具有完备性,即i元组满足D中仅涉及到,的所有约束意味着j元组(,)一定也满足D中仅
5、涉及到,的所有约束,i =1,2,n。换句话说,只要存在0jn-1,使得(,)违反D中仅涉及到,的约束之一,则以(,)为前缀的任何n元组(,)一定也违反D中仅涉及到,的一个约束,因此,对于约束集D具有完备性的问题P,一旦检测断定某个j元组(,)违反D中仅涉及,的一个约束,就可以肯定,以(,)为前缀的任何n元组(,)都不会是问题P的解,因而就不必去搜索它们、检测它们。回溯法正是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法。 回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树,它可以
6、这样构造: 设中的元素可排成(1),(2),(-1),| =,i=1,2,n。从根开始,让T的第I层的每一个结点都有个儿子。这个儿子到它们的双亲的边,按从左到右的次序,分别带权(1) ,(2) ,() ,i=0,1,2,n-1。照这种构造方式,E中的一个n元组对应于T中的一个叶子结点,T的根到这个叶子结点的路径上依次的n条边的权分别为,反之亦然。另外,对于任意的0in-1,E中n元组的一个前缀I元组对应于T中的一个非叶子结点,T的根到这个非叶子结点的路径上依次的I条边的权分别为,反之亦然。特别,E中的任意一个n元组的空前缀(),对应于T的根。 因而,在E中寻找问题P的一个解等价于在T中搜索一个
7、叶子结点,要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权满足约束集D的全部约束。在T中搜索所要求的叶子结点,很自然的一种方式是从根出发,按深度优先的策略逐步深入,即依次搜索满足约束条件的前缀1元组()、前缀2元组(,)、,前缀I元组,直到i=n为止。 在回溯法中,上述引入的树被称为问题P的状态空间树;树T上任意一个结点被称为问题P的状态结点;树T上的任意一个叶子结点被称为问题P的一个解状态结点;树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点,它对应于问题P的一个解。2.1.3回溯法的基本思想 (1)针对所给问题,定义问题的解空间; (2)确定易于搜索的
8、解空间结构; (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为O(n)。而显式地存储整个解空间则需要O(2n)或O(n!)内存空间.2.1.4回溯法在TSP问题上的应用 旅行商问题的回溯算法可作为类Traveling 的一个成员。在其他例子中,有一个成员函数:Backtrack与T S P。前者是一个保护或私有成员,后者是一个共享成员。函数G .T S P ( v )返回最
9、少耗费旅行的花费,旅行自身由整型数组 v 返回。若网络中无旅行,则返回No edge。Backtrack在排列空间树中进行递归回溯搜索, T S P是其一个必要的预处理过程。TSP假定x(用来保存到当前节点的路径的整型数组),best x(保存目前发现的最优旅行的整型数组),c c(类型为T的变量,保存当前节点的局部旅行的耗费),best c(类型为T的变量,保存目前最优解的耗费)已被定义为Traveling中的静态数据成员。 函数Backtrack见下。它的结构与函数Perm相同。当i=n 时,处在排列树的叶节点的父节点上,并且需要验证从到有一条边,从到起点 也有一条边。若两条边都存在,则发
10、现了一个新旅行。在本例中,需要验证是否该旅行是目前发现的最优旅行。若是,则将旅行和它的耗费分别存入best x与best c中。当in 时,检查当前i-1 层节点的孩子节点,并且仅当以下情况出现时,移动到孩子节点之一:1. 有从 到的一条边(如果是这样的话,定义了网络中的一条路径);2.路径 的耗费小于当前最优解的耗费。变量cc 保存目前所构造的路径的耗费。每次找到一个更好的旅行时,除了更新best x 的耗费外,Backtrack需耗时O(n- 1 )!)。因为需发生O(n-1)!)次更新且每一次更新的耗费为(n)时间,因此更新所需时间为O(n(n- 1)!)。通过使用加强的条件能减少由Ba
11、cktrack搜索的树节点的数量。2.2遗传算法2.2.1遗传算法的定义 遗传算法(Genetic Algorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,它是由美国Michigan大学J. Holland教授于1975年首先提出来的,并出版了颇有影响的专著Adaptation in Natural and Artificial Systems,GA这个名称才逐渐为人所知,J. Holland教授所提出的GA通常为简单遗传算法(SGA)。 遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由
12、经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(sele
13、ction)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。2.2.2遗传算法的特点 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法,与传统的优化算法相比,主要有以下特点:(1)遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身,而遗传算法处理决策变量的某种编码形式,使得我们可以借鉴生物学中的染色体和基因的概
14、念,可以模仿自然界生物的遗传和进化机理,也使得我们能够方便的应用遗传操作算子。(2)遗传算法直接以适应度作为搜索信息,无需导数等其它 辅助信息。(3)遗传算法使用多个点的搜索信息,具有隐含并行性。(4)遗传算法使用概率搜索技术,而非确定性规则。2.2.3遗传算法求解TSP问题的实现(1)编码方法:对于一个TSP问题的城市列表W,假定每个城市的一个访问顺序为T=,规定每访问完一个城市,就从城市列表中将该城市去掉,则用第i(i=1,2,3,n)个访问的城市在所有未访问城市列表W中的对应位置序号(i = 1,2,3,n+1)就可表示具体访问哪个城市,如此这样直到处理完W中所有的城市。将全部gi顺序摆
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 物流配送 中的 最优 路径 规划 模拟 软件 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。