多车场多车型车辆路径问题的改进遗传算法

《多车场多车型车辆路径问题的改进遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机与现代化2008年第9期JISUANJIYUXIANDAIHUA总第157期文章编号：1006—2475(2008)09-00104)4多车场多车型车辆路径问题的改进遗传算法杨元峰(苏州市职业大学计算机工程系，江苏苏州215104)摘要：在给出有时间窗约束的多车场多车型车辆路径问题的基于直观描述的数学模型基础上，引入一种新的编码方式，并将Rc交叉算子进行修正，构造出一种解决该问题的模拟退火遗传算法，实验证明能够有效地解决优化问题。关键词：车辆路径问题；多车场；多车型；遗传算法；模拟退火算法中图分类号：TP301．6文献标识码：A

2、AnImprovedGeneticAlgorithmforMultiple-·depotandHeterogeneous-vehicleVehicleRoutingProblemYANGYuan—feng(DepartmentofComputerEngineering，S~houVocationalUniversity，Suzhou215104，China)Abstract：Thispaperstatesamodelofmultiple-·depotandheterogeneous·-vehiclevehicleroutingprob

3、lemwithtimewindowsbasedonnaturaldescription．AnimprovedgeneticalgorithmisproposedbasedOilanewcodingmethodandamendedRCcrossover叩·erator．TheexperimentalresultsshowthatthisgeneticalgorithmCansuitforsolvingmultiple-depotandheterogeneous—vehicleve—hicleroutingproblem．Keywords

4、：vehicleroutingproblem；multi—depot；heterogeneous—vehicle；geneticalgorithm；simulatedannealingalgorithm0引言’1问题的描述和数学模型车辆路径问题(Vehiclemutingproblem，VRP)由有时间窗约束的多车场多车型车辆调度问题描Dantzing和Ramser于1959年首次提出，它是指对一述为：有M个车场，各自拥有L种类型的车辆构成的系列发货点(或收货点)，组织适当的行车路线，满足混合车队，每种类型车的载重量为Q。(1∈L)，

5、且此类客户的需求，并在一定的约束条件下，达到一定的目型车辆数为K。(m∈M，l∈L)。负责对N个用户进标(诸如路程最短、成本最小、耗费时间尽量少等)，行货物运输工作，用户i的货物需求为gi(i=1，2，⋯属于NP难度问题。，N)，且必须在时间窗口[ET；，LT；]完成，若车辆在遗传算法有较强的全局搜索性能，但它的爬山能ET；之前到达用户i处，则在此等待；如果车辆到达时力弱，在实际应用中容易产生早熟收敛的问题，且在间晚于LT；，用户i的需求将被延迟进行。要求一个进化后期搜索效率较低。而模拟退火算法却具有摆合适的车辆调度方案，使各车场的车

6、辆能满足所有用脱局部最优点的能力，能抑制遗传算法的早熟现象。户的需求，并使车辆总的运输成本最低。本文提出的模拟退火遗传算法即模拟退火算法和遗在文献中，多车场问题常转化为单车场问题来处传算法相结合的进化算法⋯，主要是利用模拟退火理，其关键是首先对每个车场确定它所服务的客算法的Boltzmann机制来控制遗传算法的交叉、变异户[2-3]。但是由于这种解决思路首先将客户分配给各操作中子代染色体的选择，在父代与子代染色体中引车场，再求解单个车场的优化解，这样即使每个车场入竞争。模拟退火算法能使解的收敛从局部最优跳的路径优化都得到了最优解，但从

7、整个调度问题来出，最终达到全局收敛。看，很难得到全局最优解。基于中国配送调度的实际情况、特点，本文吸收前人的研究成果训和对实收稿日期：2007-06—11．作者简介：杨元峰(1973一)，男，江苏盐城人，苏州市职业大学计算机工程系讲师，硕士，研究方向：智能信息处理及网络应用。2008年第9期杨元峰：多车场多车型车辆路径问题的改进遗传算法l1际应用中的车辆调度问题进行分析，将多车场车辆调由此获得的解仅表示每辆车访问了哪些用户，并度问题本身看作一个复杂的组合优化问题进行研究，没有给出访问的顺序。但问题就转变为确定每辆车在原有的研究基础上考

8、虑多车场、多车型、有时间窗访问用户的顺序，即n个小规模的TSP问题。本文用等情况，并初步考虑了交通对配送的影响和车辆行驶文献[8]中改进的节约算法来求解这些TSP问题。成本，建立下文的数学模型。并对用户的时间窗得不由于规