当前位置: 简表范文网 > 专题范文 > 公文范文 >

基于物流配送路径的优化算法研究

| 来源:网友投稿

摘要:目前,对物流配送车辆优化调度问题(VRP)还是一个研究热点,许多学者采用了各种优化方法来解决实际问题。该文综述了物流配送车辆调度问题的各种优化方法,对其发展历程、优缺点、适用性等都作了详细的说明,并对它们作以比较分析,从而找到最适合现实状况的优化方法。

关键词:优化;物流配送;算法

中图分类号:TP312文献标识码:A文章编号:1009-3044(2011)10-2297-02

The Research on Optimum Algorithm of Logistics Distribution

XU Yan, LI Sheng-qin

(College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China)

Abstract: At present, logistics vehicle routing problem(VRP) is focused on as hot-question. Lots of scholars adopts various optimum ways to solve actual question. This paper sums up all kinds of methods of VRP and particularly explain merit and disadvantages, evolution course and applicability, which compare and analyze them each other in order to discover best of realistic status s optimum ways.

Key words: optimizing; logistics distribution; algorithm

物流(logistics)是指利用现代信息技术和设备,将物品从供应地向接收地准确的、及时的、安全的、保质保量的、门到门的合理化服务模式和先进的服务流程。物流是随商品生产的出现而出现,随商品生产的发展而发展,所以物流是一种古老的传统的经济活动。物流管理是指在社会再生产过程中,根据物质资料实体流动的规律,应用管理的基本原理和科学方法,对物流活动进行计划、组织、指挥、协调、控制和监督,使各项物流活动实现最佳的协调与配合,以降低物流成本,提高物流效率和经济效益。现代物流管理是建立在系统论、信息论和控制论的基础上的。配送路径优化问是一个NP问题,只有在需求点和路段较少时才能求得精确解。随着信息技术的不断进步,企业运营节奏加快,物流配送路径的研究方法也随着进步,可以说问题由简单到复杂。优化方法有精确算.法、传统启发式算法、现代启发式算法这么几种。下文便分类介绍以下几种最优化算法。

1 物流配送路径优化问题的精确算法

1)动态规划法。此算法(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

2)分枝定界法。该法是将原始问题分解,产生一组子问题。分支是将一组解分为几组子解,定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外,就将这一子组舍弃(剪枝)。分支定界法原为运筹学中求解整数规划(或混合整数规划)问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用于过程系统综合可大大减少需要计算的方案数日。

3)切平面法。此方法与分枝定界法相类似,它也是在整数规划与求解相对应的线性规划上,不断的增加新的约束,相区别是会加入一些特别的约束条件,然后切掉非整数规划中的可行解,获得最优解。

2 物流配送路径优化问题的传统启发式算法

传统的启发式算法在求解过程中主要是从初始解出发,以搜索邻域的方式实现解的改进,并在较短的时间内获得一个可以接受的解。传统的启发式算法主要有以下4种:1)节约算法。此算法是将较短路径与原路径定义为节约值,然后将节约值从大到小进行排序,在节点的数量允许的情况下,依此将节点对应的顾客点插入到路径中,直到所有的顾客都被插入路径为止,从而获得可行解,不过解非最优。2)邻接算法。此算法是由数据结构中的邻接表演变过来。邻接表是图的一种链式存储结构,对图的每个顶点建立一个单链表(n个顶点建立n个单链表),第i个单链表中的结点包含顶点Vi的所有邻接顶点。此算法的思想是从一个起始点出发,然后搜索路线中与之距离最近的点,然后在次以此方法不断搜索最近的点,从而进行路线的构造。这种方法可以保持原有路线的可行性,从而搜索着一条疑似最短的路线,节约路线成本。3)插入算法。此算法是又数据结构中的插入排序演变过来。它将邻接算法与节约算法有机的结合起来,先利用节约算法确定一条基本路线,然后根据邻接算法搜索客户节点的位置,依次按距离将客户节点插入到原有路径中,最后形成新的配送路线。4)扫除算法。此算法是将邻接算法与插入算法相结合,它是先对车辆进行分组,然后确定不同的路线,在配送过程中以扫除的方式搜索未被分配的点,然后用插入算发对路线进行扩充,如果一次分组之后还存在未被分配的点,那么继续对路线进行构造,直到所有的点都被分配为止。

3 物流配送路径优化问题的现代启发式算法

与传统的启发式算法相比,现代启发式算法并不是每次在迭代中都延着目标值下降的方向进行搜索,它还允许在搜索中接受目标值上升甚至是不可行的解,现在启发式算法与传统启发式算法的一大区别就是它会在搜索过程中跳出局部邻域进行全局搜索。现代启发式算法有以下4种:1)禁忌搜索算法。此算法是一种亚启发式(meta-heuristic)随机搜索算法,它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选择,指导下一步的搜索方向。禁忌搜索是对人类思维过程本身的一种模拟,它通过对一些局部最优解的禁忌(也可以说是记忆)达到接纳一部分较差解,从而跳出局部搜索的目的。2)遗传算法。此算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,它最初由美国Michigan大学J.Holland教授于1975年首先提出来的。遗传算法从问题解的串集开始嫂索,而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的,容易误入局部最优解。遗传算法从串集开始搜索,覆盖面大,利于全局择优。遗传算法是基于生物进化的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息。3)模拟退火算法。模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。此算法是一种随机松弛技巧,它模拟了退火的过程,在搜索的初始阶段,算法跳向远点,随着时间的延伸或下降,跳跃幅度逐渐减小,最终转向局部搜索的下降方法。4)蚁群算法。蚁群算法又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。

4 各种优化算法的比较

以上各种优化算法在不同时期与情况下都有其优缺点,都有解决某些问题的能力,但随着发展的需要,对优化算法的要求也越来越高。下面对各种方法进行比较分析,通过表格的形式展示出各自的特点,如表1所示。

5 结束语

车辆路径问题由于在管理学和运筹学上非常重要而且求解有一定的难度,同时由于它具有很强的现实价值,可产生极其可观的经济效益,因而是理论界与企业界关注的一个极其具有魅力的优化问题。通过表格的分析比较,可以看出各种方法的优点和缺点,在不同的任务中可以挑选不同的优化算法,从而使物流效率达到最高。本文通过介绍各种优化算法来比较各类算法的优缺点,以便能在实际中解决各种复杂的物流路径优化问题,从而找到最好的优化方法。

参考文献:

[1] 孙学农,徐辉增.物流配送车辆调度问题方法综述[J].科技信息:学术研究,2007(12).

[2] 刘明广,李高扬.物流配送车辆优化调度模型及其求解策略[J].工业工程,2007(2).

[3] 方金城,张岐山.物流配送车辆路径问题(VRP)算法综述[J].沈阳工程学院学报:自然科学版,2006(4).

[4] 李贵春,刘冬梅.物流配送系统车辆的优化调度算法[J].天津工业大学学报,2006(3).

[5] 骆义.物流配送车辆调度优化研究[D].大连:大连海事大学,2003.

推荐访问:算法 路径 物流配送 优化 研究

热门文章

2022员工培训学习心得体会范本合集(范文推荐)

最近发表了一篇名为《员工培训学习心得体会范文》的范文,感觉写的不错,希望对您有帮助,为了方便大家的阅读。培训能让员工不断的提高,并清楚的意识到自己的缺点。经过员工培训,你一定有许多的收获,不妨来写一篇员工培训心得。你是否在找正准备撰写“员工培训心得体会范文”,下面小编收集了相关的素材,

冬至精彩优秀作文600字(全文)

最近发表了一篇名为《冬至精彩优秀作文600字【精选六篇】》的范文,好的范文应该跟大家分享,希望对网友有用。在古时候被认为是非常重要的日子,人们甚至将其称之为小年,每年过冬至的时候,都要做好许多准备,民间甚至有诸多的庆祝活动。下面小编在这里为大家精心整理了几篇冬至精彩优秀作文600字,希望对

大一暑假社会实践报告(精选文档)

本页是最新发布的《2022大一暑假社会实践报告》的详细范文参考文章,感觉写的不错,希望对您有帮助,希望大家能有所收获。这个暑假过得是否充实呢,有些小伙伴在假期中参加了实践,那么如何做一份报告呢?下面是小编整理的2022大一暑假社会实践报告,仅供参考,希望能够帮助到大家。2022大一暑假社会

关于珍爱生命作文800字高中【精选推荐】

范文参**网最近发表了一篇名为《2022关于珍爱生命的作文800字高中【】》的范文,感觉写的不错,希望对您有帮助,重新整理了一下发到这里。在平日的学习、工作和生活里,大家都不可避免地要接触到作文吧。下面小编为大家整理了2022关于的作文800字高中【5

《********大宣讲特别节目》直播观后感

最近发表了一篇名为《2022《********大宣讲特别节目》直播观后感【精选】》的范文,感觉写的不错,希望对您有帮助,希望对网友有用。,安全,在学校里,在校外,安全这个词恐怕是再熟悉不过了吧,让将安全铭记心中,时进刻刻都做到安全,让父母不再操心,让长辈不再担心,让安全从我做起,从身边

以小见大作文500字范本(范文推荐)

最近发表了一篇名为《以小见大作文500字范文【精选】》的范文,感觉写的不错,希望对您有帮助,重新编辑了一下发到。一件事情的发生,离不开时间、地点、人物、事情的起因、经过和结果这六方面,即常说的六要素,只有交待清楚这几方面,才能使读者对所叙述的事,有个清楚、全面的了解。这里小编

2022年大学生档案自我鉴定300字10篇

2022年普通大学生个人社会实践实习报告精选服务社会做好思想准备和业务准备,公司内部电脑系统都是统一英文系统,就要求自己以职场……[详细]2022年党员思想汇报例文两篇【完整版】所以在以后的学习和生活中,经历过苦难的中国,工作以及生活中,特别是通过学习党章党纪……[详细]企业员工服务意识培训心得体会

追梦筑梦圆梦演讲稿

最近发表了一篇名为《追梦筑梦圆梦演讲稿》的范文,感觉很有用处,这里给大家转摘到。演讲稿特别注重结构清楚,层次简明。在日新月异的现代社会中,在很多情况下需要用到演讲稿,如何写一份恰当的演讲稿呢?下面是小编为大家整理的追梦筑梦圆梦演讲稿,希望能够帮助到大家!追梦筑梦圆梦演讲稿1尊敬的

建团百周年活动策划

《2022建团百周年活动策划【精选】》是一篇好的范文,感觉很有用处,希望大家能有所收获。党的领导是共青团顺利发展的关键所在,无论是中国早期青年团的建立,还是中国共青团的正式成立,都离不开党的领导。下面小编为大家整理了2022建团百周年策划【精选】的相关内容,以供参考,希望给大家带来帮助!20

2022年度中考优秀作文素材别样美三篇

最近发表了一篇名为《中考优秀作文素材别样的美精选三篇》的范文,好的范文应该跟大家分享,看完如果觉得有帮助请记得(CTRL+D)收藏本页。雨过天晴,花坛边上,几只蜗牛缓缓的爬行着,留下一道彩虹般的痕迹,那柔软的外面,是坚硬的外壳,那也是一道的美丽。下面是小编为大家收集整理的关于素材别样的美精

小学品德教师期末工作总结范本合集

最近发表了一篇名为《小学品德教师期末工作总结范文》的范文,感觉很有用处,重新整理了一下发到这里[http: www fwwang cn]。时光飞逝,如梭之日,回顾这段时间的工作,一定有许多的艰难困苦,是时候在工作总结中好好总结过去的成绩了。下面小编在这里为大家精心整理了几篇小学教师期

2022年度有关安全学习心得合集(2022年)

本页是最新发布的《有关安全学习心得》的详细范文参考文章,感觉很有用处,看完如果觉得有帮助请记得(CTRL+D)收藏本页。有了一些收获以后,可以记录在心得体会中,这么做能够提升的书面表达能力。相信许多人会觉得心得体会很难写吧,下面是小编为大家收集的有关学习心得,供大家参考借鉴,希望可以帮