公司新闻 行业动态

物流配送途径优化问题剖析与算法解读(一)

发布时间:2022-09-26 10:47:12 来源:天博官网下载链接

  上一年五一跳蚤今后,一向在一家公司参加物流配送软件开发的相关作业,担任的作业内容包括物流配送途径优化这一块。关于物流配送这一专业范畴,自己曾经也是外行人,对这一范畴也没有触摸过,更谈不上了解。所以,一向在学习,一向在探究。在这个进程中由于作业需要学习了许多大牛的博客(太多了,记不住,所以咱们别盼望了,仍是结壮看我的帖子吧),也研讨了在开发进程中客户提出的物流配送途径优化范畴的相关需求(由于客户来头较威望,需求比较专业,所以问题很具有代表性),有所收成。好东西当然要拿出来与咱们共享。我会把这段时刻的学习和研讨所得整理成一个系列(好吧,诚心有点装,不过考虑了一下,发现要写的的确不少),欢迎咱们批评指正。别的,在这个进程中,我还使用了许多的谷歌地图API技能,也有所堆集,假如咱们有需求,发帖顶起啊,我也可以找个时刻整理出来与咱们共享!假如遇上同行,还请不吝赐教。

  在这个系列里,我会依照从易到难,从简略到杂乱的次序,向咱们分类,分级逐步介绍物流配送途径优化进程中的问题。

  今日先起一个头,这也是全部物流配送途径优化问题的起点,那便是旅行商问题。信任阅览这篇文章的同学应该对旅行商问题有所了解,我就不赘述了。

  物流企业A在B市有一个配送中心,有M个固定的配送客户。企业A每天需要为这M个客户配送必定量的货品。现在,有这样一个问题,要求企业A派出

  一辆车配送一切客户,不考虑车辆载重与结点需求,且该辆车不论怎么行进,均可以一次性配送完一切客户,现在只需考虑一个问题,那便是怎么行车才干确保一切点均已配送且只配送一次,且总的行车途径最短。这是典型的TSP问题,也是物流配送途径优化问题中最根本和最简略的问题。

  现在针对该问题,有许多的处理方法,包括有名的蚁群算法,包括遗传算法等等,这些都可以有用的获取相对最优解。我只捡我实践过且现在运转杰出的几种算法来说:

  如上图所示,P0为起始点,其它点为配送需求点。选用极坐标来表明各点的相对方位,然后以P0点为坐标原点,以P1为起始点,定其视点为零度,以顺时钟或逆时钟方向开端扫描各个点,取得各点与原点连线的视点巨细。依据视点巨细确认其次序,直至扫描完毕。扫描完毕后取得的点的序列便是各点的配送次序。

  简略扫描法并不能确保获取最短途径。可是其算法原理简略,履行功率高,并且所获取的成果与最优途径之间的误差较小。

  分支限界法又称为剪枝限界法或分支定界法,它类似于回溯法,也是一种在问题的解空间树T上查找问题解的算法。它与回溯法有两点不同:

  ①回溯法只经过约束条件剪去非可行解,而分支限界法不只经过约束条件,并且经过方针函数的限界来削减无效查找,也便是剪掉了某些不包括最优解的可行解。

  ②在解空间树上的查找方法也不相同。回溯法以深度优先的方法查找解空间树,而分支限界法则以广度优先或以最小消耗优先的方法查找解空间树。

  分支限界法的查找战略是:在扩展结点处,先生成其一切的子结点(分支),然后再从当时的活结点表中挑选下一个扩展结点。为了有用地挑选下一扩展结点,以加快查找的进程,在每一活结点处,核算一个函数值(限界),并依据这些已核算出的函数值,从当时活结点表中挑选一个最有利的结点作为扩展结点,使查找朝着解空间树上有最优解的分支推动,以便尽快地找出一个最优解。从活结点表中挑选下一扩展结点的不同方法导致不同的分支限界法。最常见的有以下两种方法:

  ①行列式(FIFO)分支限界法:行列式分支限界法将活结点表组织成一个行列,并按行列的先进先出准则选取下一个结点为当时扩展结点。

  ②优先行列式分支限界法:优先行列式分支限界法将活结点表依照某个估值函数C(x)的值组织成一个优先行列,并按优先行列中规则的结点优先级选取优先级最高的下一个结点成为当时扩展结点。

  分支限界法常以广度优先或以最小消耗(最大效益)优先的方法查找问题的解空间树。在分支限界法中,每一个活结点只要一次时机成为扩展结点。活结点一旦成为扩展结点,就一次性发生其一切儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被放弃,其他儿子结点被参加活结点表中。

  尔后,从活结点表中取下一结点成为当时扩展结点,并重复上述结点扩展进程。这个进程一向继续到找到所需的解或活结点表为空时停止。

  影响分支限界法查找功率的有两个主要因素:一是优先行列Q的优先级由C(x)确认,它能否确保在尽或许早的情况下找到最优解,假如一开端找到的便是最优解,那么查找的空间就能降低到最小;二是限界函数u(x),它越严厉就越或许多地剪去分支,然后削减查找空间。

  在用分支限界法处理TSP问题时,有不少很好的限界函数和估值函数现已结构出来出了,使得分支限界法在大多数情况下的查找功率大大高于回溯法。可是,在最坏情况下,该算法的时刻杂乱度仍然是O(n!),并且有或许一切的(n-1)!个结点都要存储在行列中。3、蚁群算法

  意大利学者M.Dorigo,V.Maniezzo等人在调查蚂蚁的寻食习性时发现,蚂蚁总能找到巢穴与食物源之间的最短途径。经研讨发现,蚂蚁的这种团体协作功用是经过一种留传在其交游途径上的叫做信息素(Pheromone)的挥发性化学物质来进行通讯和协调的。化学通讯是蚂蚁采纳的根本信息沟通方法之一,在蚂蚁的日子习性中起着重要的效果。经过对蚂蚁寻食行为的研讨,他们发现,整个蚁群便是经过这种信息素进行相互协作,构成正反应,然后使多个途径上的蚂蚁都逐步集合到最短的那条途径上。

  这样,M.Dorigo等人于1991年首先提出了蚁群算法。其主要特色便是:经过正反应、分布式协作来寻觅最优途径。这是一种根据种群寻优的启发式查找算法。它充分利用了生物蚁群能经过个别间简略的信息传递,查找从蚁巢至食物间最短途径的团体寻优特征,以及该进程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优回答。

  如上图所示,蚂蚁在最开端的时分由于障碍物阻挠,不得不延上下两条路绕行。上面的途径比下面的途径要长。咱们假定一切蚂蚁的运动速度相同,那么在单位时刻里经过下面途径的蚂蚁数量在概率上说,明显要比从上面经过的蚂蚁数量要多。由于蚂蚁的移动进程中会发生信息素,咱们假定每只蚂蚁单位时刻内发生的信息素是必定的,那么下面途径的信息素浓度明显要大于上面的途径。跟着时刻的添加,这种不同越来越大,而蚂蚁之间是经过信息从来传递信息的,所以越来越多的蚂蚁由于蚂蚁浓度的影响,从下面的途径经过,直至终究绝大多数的蚂蚁都从下面的路经过。

  蚁群算法是一种正反应的算法。从实在蚂蚁的寻食进程中咱们不难看出,蚂蚁可以终究找到最短途径,直接依赖于最短途径上信息激素的堆积,而信息激素的堆积却是一个正反应的进程。对蚁群算法来说,初始时刻在环境中存在完全相同的信息激素,给予体系一个细小扰动,使得各个边上的轨道浓度不相同,蚂蚁结构的解就存在了好坏,算法选用的反应方法是在较优的解经过的途径留下更多的信息激素,而更多的信息激素又招引了更多的蚂蚁,这个正反应的进程使得初始的不同得到不断的扩展,一起又引导整个体系向最优解的方向进化。因而,正反应是蚂蚁算法的重要特征,它使得算法演化进程得以进行。

  蚁群算法并不能确保必定可以获取最短途径。可是经过修正其算法因子,咱们可以得到最优近似解。假如对其进行屡次循环处理,从得到的一组最优近似解中筛选出的最小值,一般便是最优解。4、三种算法比照

  选用分布式核算,具有较强的鲁棒性,可以经过操控算法因子对成果进行优化。屡次循环可以得到最优近似解。

天博官网下载链接 粤ICP备14071706号-1   Powered by :www.aiorange.cn