多车场满载车辆路径优化算法

《多车场满载车辆路径优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第29卷第22期计算机工程与设计2008年11月VO1．29NO．22ComputerEngineeringandDesignNOV．2008多车场满载车辆路径优化算法陈新庄，郭强，范昌胜(西北工业大学理学院应用数学系，陕西西安710072)摘要：针对多车场满载车辆路径问题(MDVRPFL)，结合节约法提出了一种依次对车场、配送中心、用户进行循环调整直到最优的迭代算法。该算法具有使总费用随迭代次数逐渐降低的特点，其运算结果能同时得到最优车辆分配方案和车辆行驶路径。最后用该算法对不同规模的算例进行试验。

2、试验结果表明，该算法对多车场车辆路径问题有效适用。关键词：车辆路径问题；满载运输；多车场；节约法；优化算法中图法分类号：TP39；022文献标识码：A文章编号：1000—7024(2008)22—5866—03Optimalalgorithmformultiple—depotvehicleroutingproblemwithfullloadsCHENXin—zhuang，GUOQiang，FANChang—sheng(DepartmentofAppliedMathematics，SchoolofSci

3、ence，NorthwesternPolytechnicalUniversity,Xi’an710072，China)Abstract：CombiningC—Wsavingmethodalgorithm,akindofcycleiterativealgorithmisproposedformultiple-depotvehicleroutingproblemwithfullloads(MDVRPFL)．Thealgorithmcontinuousadjustsdepot，distributioncen

4、terandconsumerinturntogettheoptimalsolution．Theamountchargesgraduallyaredecreasedwiththeincreasingiterativetimes．Whenthealgorithmends，theoptimalvehicledistributionprojectsandtheoptimalvehicleroutesarecomputed．Intheend，diferentdimensionsofexamplesareexpe

5、riencedonthealgorithm．theresultsshowsthatthealgorithmiSsuitableandefectivetosolveMDVRPFL．Keywords：vehicleroutingproblem；fullloadedtransportation；multiple·depot；savingmethodalgorithm；optimalalgorithm点分离的运输问题等，所采用的算法也都是近似算法。另0引言外，现有文献对满载VRP的研究，主要集中在两层关系的满

6、车辆路径问题(vehicleroutingproblems，v1)是交通运输载VRP上，对三层多车场的情况没有研究。随着第三方物流系统中的关键问题，在水运、航空、通讯、电力、工业管理、计算的发展，物流配送问题不再是由车场、用户构成的两层运送关机及VLSL设计等领域得到了广泛的应用，它直接影响到完系了，而是一个由车场、配送中心、用户构成的三层配送：随着成任务的成本和质量。多车场满满载车辆路径问题(multiple—规模的扩大，物流公司拥有的车场数目和车辆数目也会随之depotvehiclerouting

7、problemwithfu11load，MDVRPFL)是VRP的增加，研究三层关系的多车场车辆路径问题非常必要。扩展，指的是有数个车场同时对多个用户进行服务，各用户有本文针对三层运输关系的MDVRP提出了一种通过循环一定的货物需求，每个车场有若干辆车，车辆从车场出发行驶迭代获取精确最优解的算法，即按一定的规则调整车辆经过至仓库装载货物，运送到各个用户，最后返回原车场。要求对的车场、配送中心、用户，改变车辆行车路线进行降费，最终达各车场的车辆和行驶路线进行适当的安排，在保证满足各用到最优。户的需求的前

8、提下，使总的运输成本最低。1问题描述对满载VRP的研究，早期主要针对单车场的情况[1-2]对多车场的研究较少。由于MDVRP是N-P难问题，不存在多在一连通的运输网络上有n个节点，其中节点Cf为车场，项式算法，而且很难建立精确最优解算法。因此，现有文献对停有车辆c舾O=1,2，⋯，)；节点为配送中心，存储的货物可供MDVRP问题多采用近似算法进行研究，如文献[3]把多车场研辆整车装载(，=m+l，m+2，⋯，)；节点为用户点所在地，需问题划分为多个单车场