改进的节约算法在车辆路径优化问题中的应用研究.docx

改进的节约算法在车辆路径优化问题中的应用研究摘要：C-W节约算法以其简单的原理在路径优化问题中非常实用但是传统的节约算法是理想化的模型它有一定的局限性实际生活中的问题有更多的限制因素传统的节约算法可能并不十分适用。将传统的节约算法加以改进用当量距离代替原先的距离并引入运达时间的约束求解出另一种配送方案以期更符合实际情况。关键词：节约算法；改进；时间约束；车辆路径优化1传统节约算法概述传统节约算法根据配送中心的运输能力及其到客户之间的距离和各客户之间的相对距离来确定最佳配送路线。它的原理很简单可以用两个图简单地表示（图1）。但是传统的节约算法是基于理想化的条件忽视了很多客观条件的影响存在着一定的局限性它所得出的结果并不一定十分贴合实际情况。两个地点之间的运输距离最短并不意味着运输所使用的时间最短。现实中往往由于路况的原因造成距离看似较短的两处地方却花费了较多的时间来运输货物。此外很多时候配送的商品必须保证在一定的时间点前送达特别是生鲜类等易腐商品对配送的及时性做出了一定的要求而传统的节约算法在求解时并未考虑到这个问题。2改进的节约算法的思路（1）考虑路况等实际因素的影响将时间折合成距离引入当量距离的概念由事先确定的比重算出当量距离进而将这些当量距离用于节约算法中以确定最优的配送路线。而这个比例应由各个企业根据自身情况自行决定实际距离（d1）所占比重设为α时间折合成的距离（d2）占所占比重设为β当量距离设为D则可得计算公式D=αd1+βd2。（2）运输时间折合成当量距离的方法是将车辆在所有点两两之间的实际运输时间测出tij然后累加所有点之间的距离将累加的距离除以累加的时间T得到一个平均速度值v则d2=v*tij。（3）给定一个特定的时间段一辆运输车将商品陆续配送到各个客户时都得保证在这个特定的时间段内。使用节约算法时依次校验新加入该条路线中的配送点是否满足时间的约束如果满足继续增加新的配送点如果不满足则停止加入新的配送点此时该条线路已唯一确定。3实例分析有一家企业只有一个配送中心它同时为8个客户配送商品该企业拥有2t和4t的运输车若干辆。该企业与8个客户的当量距离以及各个客户的需求如图2所示找出路径优化后的配送路线结果。将节约里程按从大到小的顺序排列后顺次连接p5、p6再连接p2、p3按照节约里程的降序按照传统节约算法的规则依次连接。如果不考虑时间约束则可以得到三条配送路线：①P0p4p5p647+22=69；②P0p2p333+23=56；③P0p1p8p755+16=71。而如果把配送时间限定在一定范围内则配送路线可能不符合客户的要求为了便于量化将时间限制反映到距离限制上来如必须在50km（以平均速度行驶）所应花费的时间段内到达则原先的第三条路线是不符合要求的。每一条配送路线根据顺时针或逆时针方向配送时在最后一个配送点的最晚到达时间上一般来说是不同的应选择较早的配送方向。所以最终的配送路线应该是四条分别是：①p0p4p5p6；②p0p2p3；③p0p1p8；④p0p74结束语节约算法自诞生以来有很强的生命力但传统的节约算法有一定的局限性许多人试图改善原始的算法如加入各种的约束。文章同样是以一种局部改善的想法来完善传统的节约算法并通过一个实例来验证加入适当的约束后得出的结果确实与原先的存在差异。节约算法本身的原理十分简单文章在原有基础上加入适当的约束后也没有显著提高节约算法的复杂程度在路径优化问题中可以采用文章的模型求得配送路径。然而文章仍然存在一定的局限性因为实际生活中存在着太多的不确定性因素文章仅仅重点关注了其中的两个方面。参考文献[1]李远远刘彦刘光前等.车辆路径问题优化――基于改进节约算法[J].社会科学家2013（11）：76-79.[2]崔宏志龚加安.带时间窗车辆路径问题的改进节约算法[J].纯粹数学与应用数学201127（5）：688-693.[3]张学志陈功玉.车辆路线安排的一种改进节约算法[J].物流技术200827（10）：139-141.[4]刘诚顾坤坤.具有区间参数的VRP及其改进的C-W节约算法[J].武汉理工大学学报（信息与管理工程版）201032（2）：182-185.作者简介：吴文佳（1995-）女汉族安徽全椒本科南京农业大学。