物流路线（精选6篇）
物流路线 篇1
1 概 述
随着危险品物流需求的快速增长, 我国危险品物流企业数量逐年增多, 企业规模逐步扩大, 现代物流信息技术如GPSGPRSGIS/RFID及企业危险品运输监管系统均开始得以应用。随着国家对危险化学品物流安全问题的重视, 我国危险化学品安全所涉及的各个领域包括危险化学品标准化工作得到了一定的发展。目前我国危险品专用车辆较少, 运营企业的规模普遍较小, 缺乏规模较大的运输和仓储企业。危险品物流运输企业从业人员素质较低, 危险品物流运输调度科学化水平较低, 这些因素造成了我国危险品物流事故频发, 引起了重大的经济损失和不良的社会影响。目前国内外高度重视危险品的运输调度, 政府高度强调安全, 一项报告显示危险品物流公共信息平台的建设可做到危险品物流资源信息的共享, 最大限度地优化配置危险品物流资源、降低危险品物流成本, 提升危险品物流全过程的整体运作水平。当前我国政府正在积极鼓励和参与危险品安全监管信息平台的建设, 并将危险品物流公共信息平台建设纳入《物流业调整和振兴实施方案》。危险品物流配送网络及路线优化是危险品物流公共信息平台建设需要解决的关键问题。
2 国内外研究现状及分析
国内外学者关于危险品物流配送网络规划、危险品运输车辆调度优化研究进行了一系列的研究。
2. 1 危险品物流配送网络优化模型研究现状
Erkut等首先研究了危险品配送单层网络规划, 将网络路径限制为树, 求解以总的运输风险最小的整数规划问题, 并用启发式算法不断添加新的路径以使政府更好地权衡风险企业成本。Kara和Verter第一次将双层规划思想引入危险品物流配送网络规划, 根据危害等级将危险品进行分类, 并为每一类危险品设计配送网络。学者Erkut分析了政府无管制模式、过度管制模式、松弛管理模式和双层规划模型这四种不同的道路危险品运输网络规划模式的优缺点, 并在基于Kara的双层规划模型的基础上, 提出了双层规划模型最符合目前危险品道路运输网络优化现状。Lucio等建立的双层模型不但考虑最小风险, 同时也兼顾了风险在子区域内的均衡性, 将双层模型通过KKT条件和线性化互补约束转化为单层混合整数线性规划问题, 并用启发式算法求解。
我国学者宋杰珍等考虑道路危险货物运输路线选择问题的双重约束特征, 兼顾政府监管部门和运输企业双方不同利益偏好, 建立一个双层路线规划模型。2010年, 储庆中等分析了危险品道路运输网络设计问题的双层特性, 建立了以政府期望的风险最小化为上层目标、运输者期望的成本最小化为下层目标的危险品运输网络双层规划模型。采用遗传算法, 以Pydev为平台, 运用Python编程以及Trans CAD生成网络, 实现了运算和结果可视化; 其实例验证结果表明, 遗传算法能给出稳定的最优解, 而且所得风险符合预期并接近于最低网络风险。
2. 2 危险品物流配送网络是双层多目标规划问题
危险品物流配送网络优化问题涉及管理部门、运输企业以及路线沿线的普通居民等多个参与方, 其中当地政府监管部门和运输企业是两类主要决策体, 但它们的决策目标不同: 运输企业关注运输距离、运输时间、运输成本等, 而当地政府监管部门除重点关注运输影响内的人员风险, 还须考虑运输风险在其管辖区域内的均衡分布问题、危险品在地区行业中的供需平衡问题以及其管辖范围内诸多运输企业的实际经济利益兼顾等问题。在实际决策过程中, 当地政府监管部门与危险品运输企业的决策相互影响, 政府监管部门通过限制某些区域或路段通行危险品运输车辆等方法来规划危险品运输网络, 进而干涉危险品运输企业的路线选择; 而运输企业则通常考虑经济利润, 选择最小运输成本或最小运输时间的路线进行运输, 从而影响政府最小运输风险路线的规划。因此, 危险品物流配送网络优化问题是一个典型的双层多目标规划问题。
2. 3 考虑负载均衡及动态调度的公共调度优化研究现状
公共调度模式下的危险品车辆配送路线优化问题有别于传统的单个企业的危险品配送路线优化。公共调度模式下的危险品车辆配送路线优化问题是一典型的基于均衡优化的动态多目标调度问题, 其优化参数和约束条件随时空变化而变化。关于动态车辆配送路线优化问题, 张娟将人工免疫算法与蚁群算法结合起来, 提出基于免疫疫苗的蚁群优化, 设计并实现了一种解决动态物流配送路径问题的方法。李锋以易腐货物配送中的时变车辆路径问题为研究对象, 提出应用计算机建模的方法建立此类时变车辆路径问题的仿真模型。关于调度的负载均衡问题, 一些学者也进行了相关研究, 清华大学的但正刚等利用Clarke &Wright算法, 结合打包原则和装配路线均衡算法的思想, 设计出一种称为HRC的启发式算法来处理两个目标的车辆路径优化问题: 一是最小化总距离, 二是均衡各条线路间负载。
3 配送网络及路线研究的不足
综上所述, 已有的研究成果表明危险品配送网络优化研究的重要性, 并将双层规划和启发式算法、智能进化算法的思想引入到危险品配送网络优化研究中, 这为科学规划危险品物流配送网络提供了一个很好的思路和途径。但目前针对危险品配送网络优化中, 还有很多问题未得到有效解决, 这些问题主要是:
(1) 现有危险品物流配送网络规划模型大多仅侧重考虑最小化运输风险和运输成本, 未考虑区域整体和子区域间的风险均衡分布、危险品在子区域间的供需平衡等问题。此外, 现有双层规划模型涉及的目标与约束不够全面, 尚无同时考虑区域整体及子区域之间均衡优化、路网通行能力、道路运输风险、且兼顾运输企业的经济效益与危险品供需平衡等问题的优化模型。
(2) 公共调度模式下危险品车辆配送路线优化模型的求解算法研究不足。目前研究多目标优化算法大多是针对小规模运输网络, 大规模运输网络的路线优化则多采用启发式方法进行人为分解和简化, 然后调用如模拟退火算法、遗传算法、禁忌搜索算法、粒子群等进化算法进行求解。而目前尚无统一的分解简化方法和标准, 且传统的进化算法在求解效率和准确性等方面仍存在着不足。
4 总结及展望
随着对危险品需求的增多, 及国家对危险品物流安全的重视, 公共调度模式下考虑负载均衡的动态多目标优化算法的研究还须进一步深入展开。目前各级相关的危险品物流行政管理机构基本设有自己的网站, 但针对于危险品物流的公共调度平台在国内尚无设立, 综合考虑政府和运输企业利益的优化模块开发应用方面更是相对滞后。应进一步研究公共信息平台下的物流管理技术。在运输过程实时优化选线以及选线标准的定量化和标准化处理方面仍需进一步研究。均衡优化在实际危险品物流配送网络规划中是需重点研究的技术, 因此有必要研究考虑均衡优化的模型构建方法。
摘要：我国危险品物流企业的特点是规模小、运量小、管理水平低, 因此单个企业的调度优化 (局部优化) 难以做到区域内整体优化, 本文通过分析国内外危险品物流配送网络及路线优化现状, 提出政府监管模式下的危险品物流公共信息平台管理是我国危险品物流管理发展趋势, 在优化物流配送网络及路线时考虑负载均衡及动态调度的特点。
关键词：配送网络,优化,公共信息平台
参考文献
[1]李俊韬, 刘丙午.中外危险品物流管理对比研究[J].中国流通经济, 2010, 11:
[2]宋杰珍, 丁以中, 孟林丽.基于双层规划的运输网络设计[J].上海海事大学学报, 2006, 27 (2) :56-59.
[3]储庆中, 张家应, 谢之权.基于双层规划的危险品道路运输网络设计[J].重庆交通大学学报 (自然科学版) , 2010, 29 (4) :597-630.
[4]师立晨, 魏利军, 吴宗之.危险品道路运输多目标路径优化方法研究[J].中国安全生产安全技术, 2007, 2 (5) :59-63.
[5]钟凯.B2C模式下第三方物流模式的优化设计——以乐淘网为例[J].中国市场, 2011 (49) .
[6]汪传雷, 唐文博, 刘宏伟.县域农村超市物流配送问题及对策[J].中国市场, 2009 (36) .
物流路线 篇2
对于地下物流系统，国外的学者多集中于对这一系统的可行性研究以及地下物流系统的建设，在德国、日本、荷兰等国家，早已有建成的地下物流线路投入使用。
在国内，从2002年杨涛等[1]发表的《新型城市地下货运交通系统》开始，陆续有越来越多的学者开始关注这一研究方向，主要包括马保松等[2]对地下物流发现现状及历史的介绍，钱七虎院士对用地下物流系统解决特大城市交通拥堵问题这一思路的肯定，以及杨文浩[3]对现存问题的思考和策略。
目前，大多数研究主要探讨的是地下物流系统的可行性，风险评价和整体网络的规划问题。如HenryLiu[4]的《Feasibility of underground freight transport in New York City and lessons learned and implications to other major cities in the world》，介绍了纽约城市管道货物运输的概况,讨论了它对其他城市的启示，为相关领域的交通规划者提供了必要信息。傅方方[5]的《城市地下物流系统风险评价及发展前景研究》则采用层次分析法和综合评分法建立综合评价模型，对地下物流系统面临的投资风险进行评价。而李彤[6]认为，可以采用模拟植物生长算法来进行大型城市地下物流网络的优化布局。
而针对地下物流系统配送线路等问题目前的研究并不多，综合各类文献不难发现，地下物流运输与一般公路运输的区别之一就在于地下物流运输隧道的建设成本远远高于公路建设的成本，所以线路建设成本必须纳入考虑。而在进行物流配送活动时，时间问题正渐渐成为人们非常关注的问题。基于此，本文从整个系统的成本的角度出发，选择了投资成本和时间成本最小为目标函数建立了地下物流配送路线优化模型。
1 考虑时间成本的ULS路线优化模型的建立
1.1 问题分析
在进行地下物流配送路线设计时，可以结合已有的公路运输路径优化的一些方法。但是地下物流系统配送路线的设计还有许多特殊之处。
首先，地下物流系统的大部分工作场所都处于地下，包括运输线路。不同于公路运输的道路网络化，地下物流系统尚未发展成熟，所选路径必须专门进行规划、设计和建设。所以，在进行线路设计工作时，必需考虑因隧道建设等工作所带来的费用问题。
第二，地下物流系统的建设面临着的挑战之一就是巨额的投资。如果仅仅依据ULS所得的直接经济效益和直接费用来进行评价这一新兴运输系统，很显然，与公路运输相比，ULS并不占优势[7][8]。因此，在进行路径设计及优化时，若盲目参照已有的路面运输路径优化方案，一味地考虑运输成本问题则很不合理。
第三，地下物流系统在一定程度上比路面运输要自由，它可以实现直线运输，大大缩短了运输时间[9]。同时，与地面运输相比，“拥堵”这类情况将大大减少。所以，在进行路线选择时，几乎不用考虑因交通事故、道路损毁等引起的交通拥堵造成的时间损失。
在地下物流运输网络中，线路建设费用、运输费用、运输时间、运输质量及运输服务水平都是影响地下物流配送路线选择的重要因素[10]。其中，运输质量和运输服务水平的衡量指标虽然包括设施条件、场站服务质量等要点，但更大程度上来自于货物的配送时间即准点率。由于地下物流系统运行环境和条件的特殊性，在进行配送活动时，货物到达的准点率更易控制，这为配送工作带来便捷的同时，也要求配送线路要更加合理可行。
综合上述原因，本文以路网总成本最小为目标函数建立模型进行讨论。
1.2 模型假设
鉴于地下物流网络建设的投资成本偏高，地下物流系统更适用于发展较快且货流量偏大的城市[11]。为使模型更加合理可行，现对模型作如下假设：
(1)为了研究方便，本文讨论的运输货物不分品种；
(2)参与地下物流运输过程的车辆型号相同、容量相同，车况也相同，本文假设使用的是自动导向车。
(3)物流线路中每个节点的物流需求数量和位置已知；
(4)每个客户都必须接受配送服务；
(5)配送中心的货物量可以满足总的客户需求量；
(6)物流配送车行驶过程中速度固定不变。
1.3 模型构建
假设在一个地下物流系统中，现需在N条备选线路中选出合理的地下物流轨道线路，使得这个地下物流系统可以完成配送任务。因为本文针对的是货流量偏大的城市，为了简化问题，将配送中心和需求节点无差别化，都视作一般节点，一共有M个节点。由于本文在建立模型时，已经单独考虑了货物在各站的停留时间，所以可以不必再考虑货物经线网到达目的地过程中的“换乘时间”。
设地下物流轨道线路k的长度为lk；每公里的建设费用为ck；每公里的运营费用为dk；配送车在行驶过程中速度固定不变，设为v；货物从节点i出发，到达节点j，中间经过h站，每站停留的时间记作tijp，起点处i的停留时间记作tijo，从i到j的线路长度记作Lij；以i为起点，j为终点的路段的货物运输量为xij;C为建设投资成本；T为时间成本；Z为总成本；a为时间成本权重。引入ηk，，其中，
那么，模型的数学形式表示如下：
约束条件如下：
上述各式，式（1）是地下物流运输线路双向约束条件，其中，i,j是物流节点，T为所有节点的集合；式（2）中，Lmin和Lmax分别为地下物流运输线路总的布设长度最小值与最大值，该式保证了线路规模的合理；式（3）保证了任意两个物流枢纽之间的可达性，sij则是任意两个物流枢纽i和j之间的最短路；式（4）和式（5）表示的是取值范围。
2 算法设计
遗传算法[12][13]具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。采用0-1编码的遗传算法可以解决本文的问题。具体步骤如下：
Step 1.编码：因为有N条备选路线，对其编号依次为：1,2，…，n，故染色体长度为n，因含有0-1变量，编码为:{1,0,0,…，1,0}，其中，0表示该位置的备选线路未被选中，1则表示线路被选中。
Step 2.适应度计算：对种群中每一染色体解码求得对应的可行解，根据公式（3）求得目标函数值Z，适应度计算公式如下：
Step 3.算子选择：将每个种群的P个染色体按适应度值依次排序，并将值最大的染色体复制进入下一代。对剩下的染色体采用基于排名的轮盘式选择策略，以选择进入下一代种群的算子。
Step 4.算子交叉：使用单点交叉法进行算子交叉，例如：
Step 5.算子变异：根据变异概率Pm，执行变异操作，令gen=gen+1，从而得到新种群，并转至步骤2。
3 算例验证
某发展规模较大的城市拟规划建设地下物流系统。经考察分析，要以地下物流线路连接7个主要物流区域。图中，线段上数值表示地下物流系统行车距离。设搬运车在路段上的走行速度为固定值,不考虑进出站加减速的情况下按20km/h取值[14]。为简化计算，设所有路段的建设成本均为45万元/m，营运成本为1万元/m，且所有站点的停留时间均设为0.25小时。时间成本权重取12元/h。假设仅考虑物流系统行车时间及每站停留时间。由于货物流量分布基本对称，所以，线路断面货物流量两个方向相等，因此，这里只考虑单方向的线路规划。
已知各边长度情况如表1所示。
假设有5条备选轨道线路，依次为：
规定规划地下物流线路总长度不宜超过40km，各物流区域间货物流通分布见表2。
采用本文所提出的模型和求解方法，采用0-1编码，因备选轨道线路条数为5，故染色体长度设定为5，种群数取200，交叉率取0.65，变异率取0.05，通过MATLAB编程，运行后得到最优地下物流线路如下：
4 结论
与传统的物流配送路径优化模型相比，本文所建的考虑时间成本的地下物流配送路线优化模型以总的运输成本最小为优化目标，并考虑可达性约束与线网合理规模约束条件，建立了地下物流系统网络布局优化的优化模型。不仅考虑了线路的建设成本和运营管理成本，而且考虑了每站停留时间和运行时间对运输成本的影响，这一点对于如今要求有更多可靠性、更快吞吐量时间、更高服务水平和更大灵活性的物流行业尤为重要。同时，运用所建模型可对可能的地下物流线路进行筛选，以得到合理的线路网络布设方案。所建模型为地下物流线路的规划提供了理论依据。
摘要：为了缓解目前紧张的交通拥堵形势,有效规划合理的地下物流网络,文中进行了地下物流系统配送路线优化研究。文中分析了目前地下物流系统的研究概况,指出了配送线路设计的特殊之处,提出了配送时间和线路建设成本对地下物流配送线路的影响问题,考虑配送线网合理规模约束与可达性约束,以地下物流配送线路的总成本最小为目标,建立了基于投资成本和时间成本的地下物流配送路线优化模型。采用遗传算法对模型进行求解,算例结果表明,运用该模型可对所有可能的配送线路进行筛选,并得到最优的线路网络布设方案。该模型可用于城市地下物流系统的规划中,对配送线路网络进行优化布局。
物流路线 篇3
对于每一个即将告别校园走上职业生涯之路的物流类专业毕业生来说, 都面临着不可逃避的选择。如果说从小学到大学, 你一直是在一条惯性轨道上行驶, 你现在仍然要向前行驶。首先是你的一次职业方向选择, 同时你也面临着招聘公司的残酷选择。你要得到好职位, 就要奋进, 就要力争。如果你上大学的学校甚至所学专业还令你有些遗憾, 那么在职业的选择中如果走错这一步, 或走慢半步, 你又将迎来一个抱憾终生的没有选择的选择。有人说, 我是优秀生, 我有名师推荐;还有人自恃有门路, 可以想去哪就去哪。但是你知道最正规的职业生涯是哪条路吗?
物流类专业毕业生的职业生涯路线, 基本可以归结为三种模式:N股、B股、A股。
◎N股:
实际上最“阳春白雪”的职业生涯路线图, 不妨称之为N股。这条路线是极少数精英青年在经历了艰辛的拼搏后才能追求到的“黄金路线”。
◎B股:
国内大学物流类本科或研究生毕业, 或加入国内知名物流企业, 或考取名牌商学院, 常见的职业生涯模式。
◎A股:
A股之路是比较常见的职业生涯模式, 容易实现, 保险系数高。
物流类专业毕业生在选择生涯路线时, 首先要对自己有深入切实的自我认识。
你的优势, 及目前已表现出来的能力与潜力所在
☆1.你学习了什么
在校期间, 你从专业学习中获取些什么收益?实习经历提高了哪方面知识和能力?在知识经济突飞猛进的今天, 知识学习、运用能力越来越引起用人单位的重视, 因而要注意学习, 善于学习, 同时要善于归纳、总结, 把单纯的知识真正转化为自己的智慧, 为自己多准备后备能源。这样, 也许你短时期内感觉不出自己的收获, 但你在潜移默化中不自觉的修养了自我。
☆2.你曾经作过什么
即你已有的人生经历和体验。如在校期间担任的社会工作, 社会实践活动取得的成就及工作经验的积累等。经历是个人最宝贵的财富, 往往从侧面可以反映出一个人的素质、潜力状况, 因而备受招聘单位的关注, 同时这也是自我简历的亮点, 绝对忽视不得。要提高自己经历的丰富性和突出性, 你应该有针对性地选择尽量与职业目标相一致的工作项目, 坚持不懈地努力工作, 这样才会使自己的经历更有说服力和竞争力。
☆3.最成功的是什么
你做过的事情中最成功的是什么?如何成功的, 是否自己能力所为?通过分析, 可以发现自我优越的一面, 譬如坚强、智慧超群等, 以此作为深层次挖掘个人能力的动力之源, 形成职业生涯路线选择的有力支撑。
你的弱势:目前的不足或能力的欠缺
☆1.性格的弱点
人无法避免与生俱来的弱点, 这就意味着, 你在某些方面存在着先天不足, 是你力所不能及的。卡耐基曾说, 人性的弱点并不可怕, 关键要有正确的认识, 认真对待, 尽量寻找弥补克服的办法, 使自我趋于完善。注意多安下心来, 跟别人好好聊聊, 看看别人眼中的你是什么样子, 与你的预想是否一致, 找出其中的偏差并弥补, 这将有助于自我提高。
☆2.经验或经历中的欠缺
由于自我经历的不同, 环境的局限, 我们无法避免一些经验上的欠缺。欠缺并不可怕, 怕的是自己没有认识到或不懂装懂。正确的态度是, 认真对待, 善于发现, 并努力克服和提高, 你可以打出“给我时间, 我可以做得更好”的旗号。认识到自己的“所能”是重要的, 更重要的是认识到自己“所不能”, 这可以减少自己犯错误的几率。
其次, 要客观分析社会形势。
物流企业的发展对人才的需求, 大概可分为3个层次, 一是战略型物流人才, 二是管理型物流人才, 三是技能型物流人才。
一般说来, 战略型物流人才是指具有较强的战略判断和把握能力, 能够敏锐地发现市场的变化, 需要从事企业发展方向研究的高级管理和研究人才。高层次物流人才的特点是通晓物流活动全局, 具有前瞻性思维, 熟知至少一个行业或一种模式的物流理论与应用, 能从战略上分析和把握其发展特点和趋势。
管理型物流人才是指系统化的物流管理人才, 在企业中对物流活动进行计划、组织、指挥、监督、控制、调节工作, 其特点是精通现代物流商务活动, 同时具备足够的物流技术知识, 善于提出满足物流活动需求的方案。
而技能操作型物流人才是指在物流企业中从事设备的操作、维护, 物流信息搜集、加工、整理, 企业配送中心管理和经济核算, 储存、运输、配送、货运代理、报关等从事具体工作的中初级实用型人才。
作为物流管理专业的毕业生可在物流企业、港口、海关、货运公司、商贸企业等就业, 就业前景良好。今后一段时期, 除储存、运输、配送、货运代理等领域的物流人才紧缺外, 相关的系统化管理人才、懂得进出口贸易业务的专业操作人才、电子商务物流人才、掌握商品配送和资金周转以及成本核算等相关知识和操作方法的国际性物流高级人才将更吃香。物流专业人才已被列为我国12类紧缺人才之一, 缺口达60余万。据了解, 目前最为抢手的物流人才, 是那些掌握现代经济贸易、运输与物流理论和技能, 且具有扎实英语能力的国际贸易运输及物流经营型人才, 他们的年薪最高可达100万元。
物流类专业毕业生在选择生涯路线时, 可以从四个方面考虑:
◎我想往哪一路线发展?主要考虑自己的价值、理想、成就动机等主观因素, 以便确定自己的目标取向。
◎我适合往哪一路线发展?主要考虑自己的性格、特长、经历、学历、家庭影响等一些客观条件对职业路线选择的影响, 确定自己的能力取向。
◎我可以往哪一路线发展?主要考虑自身所处的社会环境、政治与经济环境、组织环境等, 确定自己的机会取向。
◎哪条路线可以取得发展?选择自己希望和适合的发展道路后, 进一步综合分析各方面的因素, 判断自己的这条职业目标的实现路线是否可以取得发展。
物流路线 篇4
车辆路径问题(Vehicle Routing Problem, VRP)最早是由Dantzig和Ramser于1959年首次提出的。在物流中的解释是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下(如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等)，达到一定的优化目标(如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高)。
VPR是物流运输过程中的关键环节，将直接影响对客户需求的响应速度、客户对物流环节的满意度以及服务商的配送成本。
由于VRP包含了销售员问题 (Traveling Salesman Problem, TSP) ，而TSP本身就是NP-Hard问题，所以VRP也是一个NP组合优化难题。VRP问题和TSP问题的区别在于：客户群体的数量大，有多辆交通工具的访问顺序进行求解。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。国内外许多学者对VRP问题的求解方法进行了大量研究，总体上分精确算法和启发式算法两类。精确算法可分为分支定界法、动态规划、整数规划、非线性规划。启发式算法有：最近邻点法(N e a r e s t Neighbor)、最近插入法(Nearest Insertion)、节约里程法(Saving Algorithm)、扫描算法(Sweep Algorithm)。
这些解法虽然可以给出较为满意的答案，但也存在计算过程复杂、参数可获得性准确请较差、限制条件较多、时间花费偏长、灵活性差等缺点，尤其不利于中小企业解决物流中的实际问题。那么是否存在较为简便直观的方法，更快速的求解出优化的访问顺序呢?不妨换一种思路进行解答。
二、毛线团的启示
对于古典的欧几里德式的几何，重视的是图形的长度、宽度、厚度等实际可测的几种值。于是我们可以知道：我们生活的空间是三维，平面是二维，直线是一维，一点的维度则为零。
20世纪70年代的数学家毕诺特·曼德布洛特-加龙省 (Benoit Mandelbrot) 提出一个问题：毛线团的维度是多少?他的答案是：这要看你的观点而异。
远距离来看，绳团凝聚成点，维度为零;再近一点，看出来毛线团占据球形的空间，维度扩展成三;再走近一些，看出毛线团是由一根根毛线所构成，他的维度为一，即使它已纠结充斥了三维空间。那么，再看下去呢?当我们看到线绳为圆柱、构成圆柱的一条条纤维……曼德布洛特-加龙省这样阐释：“数据结果视观测者与其对象而改变。”
如此一来，VRP问题可以有一个用图论语言的描述方式：平面上有n个点，如何用最短的线将全部的点连起来，即“一笔画”问题(Drawing by one line)。对于“一笔画”问题可以用“空间填充曲线” (Space Filling Curve, SFC) 方法进行求解。一条线只是一维的，弯折扭曲仍是一维的，但是在这个平面上，没有一点是SFC画不到的。
三、希尔平斯基曲线在物流路线问题中的应用
1. 希尔平斯基曲线与SFC方法简介
SFC法是由Bartholdi和Platzman两人提出的，以Peano (1890) 、Hilbert (1891) 、Sierpinski (1921) 等人开发出来的空间填充曲线为基础，根据配送地点在S F C上出现的顺序决定配送次序的方法。Bartholdi和Platzman把分散在2维空间(X, Y)坐标上的配送地投影到被SFC填充的1维曲线上，再寻找配送地在SFC上所出现的顺序，把此顺序作为配送的顺序，再根据具体路况确定访问路线。因为只需计算投影和顺序排列，所以SFC计算速度非常快。美中不足的是解的质量不算太好，最差的时候巡回距离比最佳解长20%左右。
2. 用希尔平斯基曲线填充VRP平面
希尔平斯基曲线(Sierpinski Curve)是空间填充曲线的一种，它通过自我复制和连接可以无限的扩展。很明显希尔平斯基曲线是一个闭合的线路，而且有着优异的对称性。
可以在上面任意取一点作为起点，当然这一点也就是终点。以沿曲线绕行一周的距离作为1，则在这个线路上的其他任何一点都对应一个0至1之间的数值，这个数值就是确定先后次序的依据，即数值小的点先访问，而数值大的点排在后面访问。
3. 分割希尔平斯基曲线确定顺序数值
用希尔平斯基曲线填充VRP所要经过的点以后，该如何确定各个点的访问顺序呢?例如求出图中A、B点的顺序。最简单的方法就是分割法。
不妨假设左下角为起始点0%(也是终点100%)，由于曲线的闭合性和对称性，则对角点为50%，而且左上方半个区域的点总是优先于右下方的点，两个顶点分别为25%和75%。
第一次从左下角向右上角分割后，可以知道A、B点的顺序数值都在50%和100%之间;继续将50%～100%区域分割为两个相等的三角形，可进一步知道A、B点的顺序数值在75%和100%之间;继续分割剩下的区域，A、B点的顺序数值在75%和87.5%之间;第四次分割后，A点的顺序数值在75%和81.25%之间，B点的顺序数值则在81.25%和87.5%之间;所以A点先于B点。
实际上由于所有的点会相互连接成一条封闭的线路，无论以何处作为起点，访问线路都不会有什么变化，问题的关键在于求出点的次序。需要注意的是，要把仓库(图4中的D点)包括进去才能得到正确的路线。
4. 访问任务分配
简单的TSP问题只假定了一台交通工具，而VRP问题则考虑了一个公司协调多台交通工具进行运输作业的情况。在SFC方法中，安排n个交通工具的路线也很简单，只要把访问路线平分为1/n即可，访问顺序不变。假设一个物流公司有3辆运输车，要完成60个客户，则1号司机就负责送货到线路图上第1到20号客户，2号司机负责送货到第21到40号客户，以此类推。当然，实际操作中也不必要如此精确。
SFC方法还具有很强的灵活性。如果增加新的访问点，只需要在图上确定它的顺序数值，把它插入到已有的点的序列里面去，不再有业务的访问点直接从序列里删去即可;如果出动的车辆数目有变化，只需要简单得重新划分路线;由于只规定了访问序列，具体的道路选择可以由司机灵活掌握，如根据交管部门的临时限制、车流高峰等情况变换道路。
值得注意的是，虽然每辆车分配到的客户数目都差不多，但实际位置的远近很可能不一样，每辆车的路线长短可能差别较大，这就需要不均匀的分配送货量。但如果客户接近于均匀分布，采用希尔平斯基曲线来确定客户点的次序，在此基础上再在各车之间平均分配送货量，每辆车行驶距离的差异就会比较小。
四、SFC方法的适用性
基于空间填充曲线的方法和各种精确算法、启发算法相比具有快速、灵活、运算量少的特点，可以很好的解决确定访问顺序，规划最短路线问题。但对于含有满载约束、分批装货、回程装载、时间窗约束的VRP的复杂情况无法给出解答。
综合上文分析以及其他研究可以发现，每一种算法单独工作都会存在一些比较大的缺陷，而且随着社会的发展、问题规模不断扩大化、结构不断复杂化，单一的算法很难解决现实中复杂的问题，需要将几类算法融合贯通，扬长避短，构造混合算法求解体系。
参考文献
[1]孙丽君胡祥培王征:车辆路径规划问题及其求解方法研究进展[J].当代中国出版社, 2006
[2]苏丽杰聂义勇:旅行商问题典型算法的综合性能[J].企业研究, 2004, (11)
[3]John J.Bartholdi.A routing system based on space filling curves
物流路线 篇5
1.1 配送的概念
配送位于物流活动的最末端,是直接与消费者相连的环节,在整个的物流成本中,占有相当高的比例。按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语”(GB/T 18354—2001),配送是指在经济合理区域范围内根据用户要求,对物品进行拣选、加工、包装、分割、贴标签、组配等作业,并按时送达指定地点的物流活动。
1.2 配送路线优化的意义
配送路线优化是指对多个发货点和收货点,组织适当的行车路线,使车辆有序的到达并通过,在满足一定的条件下,实现最终目标。
对企业和社会来说,选择合理的配送路线具有很重要的意义 :
(1) 优化配送路线,可以减少配送时间,缩短配送里程,提高配送效率,增加车辆利用率,降低配送成本。
(2) 优化配送路线,可以加快物流速度,更快速地将货物送到,提高客户满意度。
(3) 优化配送路线,可以使配送作业合理,提高企业运营效率 .
(4) 优化配送路线,可以节省运输车辆,减少车辆空驶率,降低社会物流成本。
(5) 优化配送路线,可以缓解交通压力,减少噪音、尾气排放等运输污染。
1.3 配送路径问题的描述
一般的物流配送路径问题可描述为 :
有N个客户点,每个客户点的需求量和位置确定,用T辆汽车从配送中心运输货物,分别到达这些客户点,完成任务后返回物流中心,要求合理安排行驶路线。同时还要满足 :
(1) 每条线路上的客户点总需求量不超过汽车的载重量 ;
(2) 每条配送路线总长度不超过汽车一次配送的最大行驶距离 ;
(3) 每个客户点的需求由一辆汽车来完成。
目的是总成本 ( 距离、时间 ) 最小。
2 最近插入法
2.1 最近插入法
最近插入法是Rosenkrantz和Stearns等人在1977年提出的,共有四个步骤 :
(1) 找到c0i最小的节点vi,形成一个子回路(subtour),T={V0,VK,VO} ;
(2) 在剩下的节点中,寻找一个距离子回路中某一节点最近的节点VK;
(3) 在子回路中找到一条弧(i,j),使得Cik+Ckj-Cij最小,然后将节点Vi插入到节点v0,vj之间,用两条新的弧 (i,k),(k,j)代替原来的弧(i,j),并将节点vk加入到子回路中 ;
(4) 重复步骤(2)、(3),直到所有的节点都加入到子回路中。
这样,子回路就演变为了一个TSP的解。因为最近插入法解决的是单回路运输问题,所以需要在此方法基础上进行改进和修正,使其能解决多回路运输VRP问题。
2.2 改进的最近插入法
(1) 找到c0i最小的节点vi,形成一个子回路(subtour),T={V0,VK,VO}。
(2) 在剩下的节点中,寻找一个距离子回路中某一节点最近的节点vk。若此时回路的总货运量未超过车的载重限制,则继续步骤(3)。否则,转(1)寻找新的一条回路。
(3) 在子回路中找到一条弧(i,j)使得Cik+Ckj-Cij最小,然后将节点vi插入到节点vi,vj之间,用两条新的弧 (i,k),(k,j)代替原来的弧(i,j),并将节点vk加入到子回路中。若此时该回路的总路程为未超过车辆的行程限制,则继续步骤(4),否则转步骤(1),寻找新的一条回路。
(4) 重复步骤(2)和(3),直到每一个节点都被归入某一个子回路中。
3 X 公司的配送路线优化研究
3.1 X 公司简介
X公司是位于西安的一家生产密度板的企业,技术力量雄厚,工艺设备先进。公司的客户分为需求量稳定的大客户和需求量随机的小客户两种。
大客户在时间和地点上的需求都不确定,但是需求量大,一般采用租赁车辆的方法进行点对点运输,有时也由客户自己运输。小客户地点确定,主要位于西安的周边县市,但需求量不大,不过公司为推广产品,每周用专车送货上门。公司现拥有两辆11吨的货车,一辆7吨的货车,如果车辆不够时,采取租赁车辆的办法。
目前,对小客户公司采用的配送线路如图2-1所示,
该配送线 路的弊端 在于 :配送路线选择不合理,运距过长,消耗作业时间多,不能充分利用车辆配载容积,浪费人力和物力资源,影响公司的收益。
3.2 X 公司的配送线路分析与优化
基本条件:X公司需给9个客户送货,客户依次为1,2,3,…,9,现有车辆为1辆7T的货车(百公里油耗21L),2辆11T的货车(每百公里油耗27L),柴油每升7.14元,司机每天工资150元。目标 :确定所需要的车辆数目、车辆类型、司机数量以及各车行走的路径,并指派这些车辆到一个回路中,同时包括回路内的路径安排和调度,使得运输总费用最小。
限制条件 :(1)运输里程超过350公里时,需配备两名司机,减去由于装卸货等影响因素,各车最大运输距离为600公里。
(2)为预防突发事件,每辆车完成任务之后都要回到源点0处。
(3)不能超过车辆的容量限制。7吨的货车最多可装300张密度板,11吨的最多可装500张密度板。
设各点间 的距离为节约距离为ΔCij。每辆车的载货量为ri,各点需求量为Ri(i=1,2,… ,9),每辆车的行驶里程为 ,Li(i=1,2,… ,9),Li≤600公里,西安为0点,客户点1,2,,,,9。
各个配送点的运距和运量见表3-1 :
3.2.1 原配送线路基本数据分析
各配送线路总里程,所需运输车辆型号、数量以及所需司机数量见表3-2 :
由上表可知,公司每周需7吨货车进行5次配送,需要司机6人,工资支出900元,总里程为1262.8KM,, 消耗柴油265.2L,所需燃油费1894元,加上司机工资,一共花费2794元。
3.2.2 基于改进的最近插入法的企业配送路线优化
令T={0},N={0,1,2,, ,, ,10}, 比较从0出发的所 有路径大 小。因为min{C0i|i∈N,1≤i≤9}=C05=55.7km,所以就有顾客点0,1构成一个子回路,T1={0,5,0},此时r1'=80,L1=114.0km。
然后在剩 余顾客点(1,2,3,4,6,7,8,9)中寻找到0和5中某一点的最小距 离,
因为r5+r1=260<500 , 所以在子回路T1={0,5,0}插入点1,由于对称性,无论将1插入到0和5之间往返路径中,结果都是一样的,这样,构成了一个新的子回路T1={0,1,5,0} ,r1=260, L=212 km。
再次寻找 剩余顾客 点到0,1, 5中某一点 的最小距 离 :可知最小距 离为c12=46.9km, 此时r2=120, 因为r1’+ r2=260+120=380<500, 所以在子回 路T1={0,1,5,0}插入点2将点2分别插入(0,1),(1,5),(5,0)中,比较得 :插入到(1,5)增量最小,Δ=C12+C25-C15=46.9+46.9-82.1=11.7km。
min{C0i|i∈N,1≤i≤9}=C05=55.7km, 此时构成 了一个新的子回路T1={0,1,2,5,0} ,r1’=370,L1=224.4km。
再次对剩余的顾客点按照上诉方法进行优化,可构成另子回路T1={0,3,4,6,0}和子回路T1={0,7,8,9,0},, 利用改进后的最近插入法得到X公司优化结果 :
由此得出,公司每周需要11吨货车配送3次,配送总里程939.7 km., 燃油费用1811元,司机4人次,工资600元,总共的配送费用为2411元。
3.2.3 优化方案比较分析
本文将从所需车辆数,行驶总里程,总油耗,人力资源和总费用这些指标,对优化后的方案进行评价分析,从对比中可知,优化后的方案需要使用的车次更少,减少了X公司用车紧张的情况,使车辆安排使用上有了更大的弹性。因此,在用车角度上考虑,优化后的方案比优化前的方案合理。从总运输里程角度考虑,优化后的总运输里程为939.7千米,与原方案的1262.8千米相比较,减少了车辆行驶的里程数,减少了公司车辆的损耗和资源的浪费,带来更多效益。
从燃油消耗的角度考虑,优化后的方案的消耗为254升,与原方案的265.2升相比较,降低了油耗量。不仅减少X公司燃油费用的支出,还能降低社会资源的浪费。
从公司人力资源消耗角度来考虑,优化后的方案所需司机人数为4人,减少人力的消耗为2人次,使公司在人员安排上将更具有弹性,还能降低公司费用的支出。从支出的总费用角度来考虑,优化后的方案的费用支出为2413元,与原方案的为2794元相比较,节省了总费用的支出。
摘要：高效合理的配送作业是物流系统顺利运行的保证,配送线路的合理安排对配送速度、配送成本以及配送效益影响很大。本文首先对物流配送的相关理论进行概述,然后以X公司的配送现状为例,运用改进后的最近插入法对配送线路进行优化,提出优化的配送方案。
物流路线 篇6
物流配送主要解决货物的运输问题:一是配送任务分配问题, 一般认为是网络流 (Net Work Flow) 问题;二是配送点之间的线路问题, 也就是车辆路径优化问题 (Vehicle Routing Problem, VRP) 。
该问题最早是由Dantzig和Ramser于1959年首次提出。典型的VRP问题可以描述为:从某物流中心用多台配送车辆向多个客户送货, 每个客户的位置和货物需求量一定、每辆配送车辆的载重量一定、其一次配送的最大行驶距离一定、要求合理安排车辆配送线路、使目标函数得到优化[1]。
经过几十年的发展, 路线优化问题取得了很大进展。综合过去有关路线优化问题的求解方法, 可以分为精确算法与启发式算法。其中精确算法包括:动态规划法、最小生成树法、Dijkstra算法等。常见的启发式算法有:遗传算法、禁忌搜索算法、人工神经网络等。VRP问题属于NP—完全问题, 很难用精确法求解, 因此启发式算法是求解路径优化问题的主要方法。其中, 遗传算法具有求解组合优化问题的良好特性, 它是由Holland教授于1969年提出, 后来经De Jong Goldberg等人归纳总结形成的[2,3,4]。Holland首先采用遗传算法 (GA) 编码解决带有时间窗的路径问题[2]。
迄今为止, 国外研究车辆配送路线优化的理论与算法已经有很多, 在实际应用中也取得了一定成果。如美国利用启发式算法开发出计算机配送调度系统用以解决货运汽车作业中车辆分配和路线选择等问题, 使汽车里程和利用率提高了5%~15%, 同时也大大的降低了运输成本和运输时间。
我国对这一问题的研究起步较晚, 相对落后。如西南交通大学的李军和郭耀煌系统的研究了车辆优化调度的基础理论及各类问题[5]。目前国内已经投放市场的此方面的软件有:奥发公司的“商业送配货地理信息系统”和北大方正的“路径规划系统”, 中远的“汽车调度信息系统”等等。这些系统只能满足用户最基本的需要, 当问题的约束较为复杂时, 这些软件也就显得力不从心了。
2 系统设计
2.1 系统开发平台
开发环境选用Windows XP, 数据库选用Microsoft Access 2007。
开发工具选择ESRI公司推出的开发组件Arc Engine, 开发语言选择Visual Basic语言。
2.2 系统功能设计
该系统以区域电子地图为基础地理信息来源, 同时连接各种动态数据库。主要功能包括:电子地图编辑、配送路线制定、数据维护、统计分析、系统维护等。如下图1所示:
2.2.1 地图管理模块
①功能:实现地图操作的基本功能, 如对地图进行放大、缩小、移动等。实现对地图信息、道路信息和配送网络信息数据的管理。包括数据添加删除修改查找等功能。在本系统中该模块还用来显示配送中心和各配送点以及优化完成后的配送路线。
②输入项目:配送中心和配送点位置信息。
③输出项目:执行操作后的结果、编辑完成后的电子地图。
执行结果:修改完毕;删除完毕;添加完毕。
数据库表:修改完毕后的电子地图。
④出错提示:对不起, 程序发生错误, 已经停止。请确认您的操作是否规范。如有疑问请查看帮助。
2.2.2 客户管理模块
①功能:实现对客户基本信息的编辑, 包括客户编号、公司地址、送货地址、客户需求、联系人、联系电话、最早最晚接受服务时间。
②输入项目:字符数据、时间、数字。
限制:电话号码格式:0000-00000000。
时间格式为:xx:yy。
③输出项目:执行操作后的结果、编辑完成后的数据库表。
执行结果:删除完毕;添加完毕;修改完毕。
数据库表:修改完毕后的客户信息表。
④错误提示:对不起, 程序发生错误, 已经停止。请确认您的操作是否规范。如有疑问请查看帮助。
2.2.3 车辆管理模块
①功能:实现对车辆信息的编辑。包括车辆编号、车辆类型、容量、司机、车辆状态、工作开始时间以及工作结束时间。
②输入项目:字符数据、日期。
限制:输入的时间格式为xx:yy。
身份证号码为18位。
③输出项目:执行操作后的结果、编辑完成后的数据库表。
结果:修改完毕;删除完毕;添加完毕。
数据库表:修改完毕后的车辆信息表。
④错误提示:操作失败, 请检查数据。
2.2.4 路线选择模块
①功能:根据客户提供的配送点信息确定配送路线并进行优化, 最终得到配送中心到各个配送点的最佳路线, 从而降低成本。可以分为单车配送和多车配送, 单车配送是运输货物量小 (不超过一辆车的装载容量) , 但运输地方却较多, 对时间限制不严格的这种情况。
②输入项目:数字。
限制:概率值及车辆满载系数必须小于1。
③输出项目:执行操作后的结果、数据库表。
结果:运行完毕。
④错误提示:对不起, 程序发生错误, 已经停止。请确认您的操作是否规范。如有疑问请查看帮助。
3 关键技术
3.1 空间聚类分析对配送点进行区域划分
对于客户很多时的路径问题, 即使是使用启发式算法, 也很难在较短时间内得到令人满意的路线优化结果。因此, 首先要通过聚类分析将客户按照距离远近进行配送区域划分, 将配送区域划分为若干个子区域, 然后再各小区域内寻找各子区域的最优线路。这样做可以大大降低计算量, 提高求解速度。本系统中使用了传统的K-Means聚类分析方法, 这种方法将距离作为相似性的评价指标, 即认为两个对象的距离越近, 其相似性就越大[6]。
设D={di|i=1, 2, ..., n}表示空间数据集, C={ci|i=l, 2, …, k}表示该数据集的k个聚类中心, 第k个聚类内的客户数用Sj来表示。客户点到聚类中心的距离最小的点的集合用K-Means算法来计算。即。其中d (di, ck) 为客户点到其聚类中心的欧式距离。步骤如下:
第一步:确定初始聚类中心, 方法是随机的在空间平面上选取k个客户点Ck={c1, c2, …, ck};
第二步:分别计算每个节点到聚类中心的距离:;比较d1, d2, …, dk的值, 若dk为最小值, 则将该配送点加入到点集Ck中。循环该过程直到所有点都被分配, 并得到点集C1, C2, …, Ck;
第三步:重新计算C1, C2, …, Ck的聚类中心, 利用公式 (其中|Sk|表示第i个聚类中心内的客户数) 计算得到c1, c2, …ck;
第四步:重复第二步和第三步, 直到聚类中心不再变化;
第五步:采用K-Means算法划分聚类完成。
3.2 改进的遗传算法处理有时间窗的路线问题
3.2.1 问题描述
一般情况下, 带时间窗的车辆优化调度问题描述为:假定一个物流中心拥有车辆数为m, 每辆车的固定运输力用q表示, 现在需要给n个客户运输货物, 客户k的货运量用gk表示, 客户k的卸货时间窗用[MTk, NTk]表示, 并且假定均在车辆的固定运载能力范围内, 问题是求解在满足货运需求的情况下, 使得费用最低的车辆行驶路线。
针对该问题, 有如下假设:
①有且只有一个物流配送中心;
②每个顾客的需求均是固定的, 同时其时间窗也都是限制的, 且均只能被某一辆车访问一次;
③每辆车只有一条送货路线;
④每辆车都有运载限制, 从起点出发, 访问一定数量的客户后回到起点;
⑤每项送货任务必须在客户规定的时间限制内结束;
⑥总的目标是所有的客户都被访问到, 同时要求车辆行驶的总距离达到最小;
针对该调度问题的有关变量和相关的参数符号表述如下:
k=0:物流配送中心, 即车辆起点;
k=1, 2, 3, ..., n:客户的数量;
l=1, 2, 3, ..., m:车辆的数量;
q:车辆的最大运载量,
cij:从客户i到客户j的运输消耗;
gk:客户k的货运量, k=1, 2, ..., n;
tij:从客户i到客户j的运输时间, i, j=1, 2, ..., n;
sk (s0=0) :客户k的运输任务开始时间;
Tk:完成客户k的任务所花费的时间, 即装货或卸货;
[MTk, NTk]:客户k的服务时间窗, 其中MTk表示时间窗的起始时间和NTk表示时间窗的结束时间, 其中k=1, 2, ..., n;
建立带时间窗的VRP问题的数学模型表示如下:
在上述模型中, (2) 是问题的目标函数, 即最小化运输成本。式 (4) - (11) 是问题的约束条件:其中 (4) 表示每个客户只能由一辆车服务; (5) 表示每辆车从配送中心出发并最终回到配送中心; (6) 表示每个客户仅被访问一次; (7) 确保每辆车承载的货物总量在其最大容量范围内; (8) 表示在规定的时间窗内及时把货物送到; (9) 、 (10) 、 (11) 是变量xijl, x0jl, xj0l, zkl的取值范围。为了安排线路, 先对所需车辆数进行估计。可按照下式确定车辆数:
式中, [x]表示不大于x的最大整数, α (0<α<1) 是对装车 (或卸车) 的复杂程度及约束程度的估计。
3.2.2 VRPTW遗传算法设计
3.2.2. 1 产生初始种群
初始种群产生的方法是利用GIS中的空间聚类的相关知识并利用Sweep算法, 将客户点初步分为m组, 每组应当满足约束条件, 然后再每组的第一个元素前加上一个元素0。这样就对原问题进行了一次分组, 然后用一个类似于变异算子的操作调整组间元素的分布 (必须满足原问题的约束) , 促使种群多样化。
3.2.2. 2 对编码方式的改进
根据VRP问题的特点, 本文采用了自然数编码方法, 优点是简单直观。步骤如下:第一步产生1, 2, …, L, L+1个无相同数字的自然数序列, 形成若干个体, 其中0代表配送中心, 1, 2, …, L代表客户, L+1, L+2, …, L+N-1代表虚拟的配送中心, 所需要的车辆总数为N。假设群体的大小是N, 然后从满足约束定义的序列中选取数量为N的个体, 由这些初始个体就构成了原始种群。如, 对一个三台车为七名客户进行货物配送的货车调度问题, 可以使用1, 2, …, 9 (8, 9代表物流配送中心点) 这样的不重复自然数的任意排列, 来代表车辆送货的线路。例如:个体128639547代表线路方案有3条:路线1:0-1-2-8 (0) , 路线2:8 (0) -6-3-9 (0) , 路线3:9 (0) -5-4-7-0;个体573894261代表线路方案有2条:路线1:0-5-7-3-8 (0) , 路线2:9 (0) -4-2-6-1-0。
3.2.2. 3 对遗传算子的改进
①选择操作
a群体内的全部个体按其适应度大小进行降序排序;
b为每个求解的问题计算一个概率分配表, 将各个概率值按照上述顺序分配给每个个体;
c每个个体遗传到下一代的概率即为其分配到的概率值, 依据遗传概率, 采用赌盘选择法从而产生下一代群体[7]。
②交叉操作
以父代种群为基础, 根据交叉概率Pc, 用随机不重复的方法挑选出2条父代染色体, 并进行交叉配对。例如:假定A和B为2条来自父代种群染色体, 其中A=83456217, B=37481625。再采用随机的方法得出2组交叉位置分别为3, 6和2, 5。那么得到的交叉选区为:A=83|4562|17, B=3|7481|625, 在B中要去除与A中要交叉基因4562相同的基因, 并把4562和B中其余部分的基因一同构成一个新的B'=45623781。同样的, 在A中剔除与B中要交叉基因74816相同的基因, 再把74816和A中其余部分的基因一同构成新的A'=74816352。
③变异操作
变异操作针对用路径表示的染色体, 定义连接染色体节点所构成的路径块为基因块, 从而达到染色体的基因块变异目的。详细的方法为:
首先假设选中的待变异染色体为Xi:v0, b1, b2, b3, b4, b5, b6, b7, b8, v1
再任意的确定Xi的基因块长度和坐标, 例如:在基因块为 (b3, b4, b5, b6) 的情况下, 随机的产生起点为b3, 终点为b6的变异基因块 (b3, N, b6) , N为从b3到b6所经过节点构成的另一头路径。实施变异后的染色体为:Mi:v0, b1, b2, b3, N, b6, b7, b8, v1。
通过变异操作的染色体中同样可能存在重复基因, 这说明在路径中产生了环路, 必须进行清除, 一般可采用覆盖的方法消除重复基因。例如:交叉后生成的一个染色体为:3 6 7 32 6 2 5 9。消除重复基因后变为:3 6 2 5 9。
3.2.2. 4 对控制参数范围的改进
Schaffer提出的最佳控制参数范围是:M=20-100, T=100-500, Pc=0.4-0.9, Pm=0.001-0.01。Srinvivas等人提出了PC和Pm能够跟随适应度的不同而自动改变的算法, 即自适应遗传算法。在种群适应度比较分散的情况下, 使二者均减小;而当种群的每个个体适应度都趋于局部最优或者趋势一致时, 使二者均增加;此外, 对适应值高于群体平均适应值的个体, 采用较低的PC和Pm, 使性能优良的个体进入下一代, 而低于平均适应值的个体, 采用较高的PC和Pm, 使性能较差的个体被淘汰[8]。
4 遗传算法的基本步骤和主要流程
第一步:采用自然数编码的方法构造染色体, 用来表示可行的行车路径。
第二步:设置控制参数, 设群体规模为n, 交叉率为PC, 变异率为Pm。
第三步:设置gen=0, 并随机生成初始群体P (0) , 群体中每条染色体均表示一条行车路径, 总共含有n条染色体。
第四步:设i=1。
第五步:设群体P (gen) 中的第i条染色体表示为行车路线。
第六步:计算该群体的适应度。
第七步:判断是否满足算法的终止条件, 如果满足则算法终止, 否则继续下一步。
第八步:设当前i=i+1。
第九步:如果i<=n, 转至第五步, 否则转到第十步。
第十步:按照计算得出的群体适应度, 采用轮盘赌法的方式复制下一代染色体。
第十一步:对新型算子进行交叉和变异操作。
第十二步:设置gen=gen+1。
第十三步:判断是否满足算法的终止条件, 如果满足则算法终止, 否则转到第四步[9]。
5 系统运行
本系统以长沙某连锁超市的配送为例。
①地图显示界面如图2所示。
②运行结果界面如图3所示。
6结论与展望
本文以长沙市某个超市为例, 针对物流配送线路优化问题, 本系统采用了改进的遗传算法, 设计了一个算法流程, 然后在这个基础上开发实现了一个模拟系统, 通过测试得出该算法是有效的, 在一定程度上提高了配送效率, 节约了物流成本。但是本文约束条件比较简单, 只以当前配送距离最小为目标函数, 仍有改进余地, 可以将其他因素如街道等级、路面质量、通畅程度、红绿灯的多少等约束条件添加在该模型上, 使该模型更为完善, 从而更好地运用于实际当中。
摘要：以长沙某超市为例, 设计了将聚类分析和遗传算法结合的算法来求解VRP模型。在此基础上, 将该算法求解模型引入到物流配送路线优化系统中。最后, 通过系统流程的分析, 提出切实可行的系统开发方案, 对数据集成和功能集成进行了深入探讨, 选择了组件式GIS开发工具ArcEngine和VisualBasic语言集成算法程序, 实现物流配送路线的优化与可视化。
关键词：物流配送,路线优化,聚类分析,遗传算法
参考文献
[1]Dantzig G, Ram ser J.The truck dispatching problem[J].Management science, 1959, (6) :80-91.
[2]Holland J H.Genetic algorithms[J].Scientific american, 1992, 267, (1) :66-72.
[3]DeJONG K A.The analysis of the behavior of genetic adaptive systems[D].Ann Arbor University of Michigan, 1975.
[4]GOLDBERG D E.Genetic algorithms in search optimization and machine learning[M].Boston Addison-Wesley Longm an Press, 1989.
[5]李军, 郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社, 2001, 6.
[6]石云平, 辛大欣.基于K-means聚类算法的分析及应用[J].西安工业学院学报, 2006, 26, (1) .
[7]朱会霞, 王福林, 张勇等.改进遗传算法优化非线性规划问题[J].数学的实践与认识, 2013, 43, (7) .
[8]Srinvivas M, Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Trans.on System, Man, and Cybernetics, 1994, 24, (4) .