带时间窗车辆路径问题与其算法设计

《带时间窗车辆路径问题与其算法设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ClassifiedIndex:O224U.D.C.:519.863DissertationfortheMasterDegreeinScienceTHEOPTIMIZATIONANDALGORITHMDESINNOFVEHICLEROUTINGPROBLEMSWITHTIMEWINDOWSCandidate:SuLihongSupervisor:Prof.ShangShoutingAcademicDegreeAppliedfor:MasterofScienceSpecialty:FoundationalMathematicalAffiliatio

2、n:HeilongjiangCollegeofConstructionDateofOralExamination:June,2010University:HarbinInstituteofTechnology哈尔滨工业大学理学硕士学位论文摘要物流是一个新兴学科，配送是现代物流的一个重要内容，合理安排车辆配送路线可以降低运输成本，提高经济效益。车辆路径问题是一类在物流配送调度中具有广泛应用的组合优化问题，属于强NP难题。有时间窗车辆路径问题比具有简单约束的车辆路径问题更加难以求解。本文对标准遗传算法的发展概况、基本概念、基本原理、理论基础、收敛性、

3、特点及其应用等方面作了简明扼要的介绍，并对遗传算法的实现技术作了较详细的总结。为研究有时间窗装卸问题的遗传算法作了充分准备。本文在VRP研究工作的基础上，考虑现有的VRPTW模型，通过设定惩罚函数，更加全面的把握客户对服务时间的约束、车辆运输费用和时间效应成本等因素，切合实际建立了有惩罚函数的VRPTW优化模型。并针对该模型设计了基于客户分组的两阶段求解思路：第一阶段，从影响客户满意因素的角度出发，先应用k-means算法对配送网点进行配送区域划分，将大规模的VRP简化成小规模的VRP，降低计算量，提高求解速度；第二阶段，针对每个客户组组内构造最

4、优路径，采用具有全局空间搜索和隐含并行性优点的遗传算法对优化模型进行求解，并运用Matlab的遗传算法工具箱加以实现，进而形成一种系统的考虑客户全面需求属性和减少计算工作量的求解方法。并通过具体实例，将运算结果与其他优化算法进行比较，证明了本文提出的改进遗传算法在处理路径优化问题上具有明显的优势，在所用配送车数量最小的前提下，可得到一个相对最短的行驶路线，实现总运输成本最低的目的。关键词：车辆路径问题；客户分组；时间窗；k-means算法；遗传算法--I哈尔滨工业大学理学硕士学位论文AbstractLogisticsisanemergingdis

5、ciplineanddistributionisanimportantelementofmodernlogistics．Wellarrangementforvehicleroutesdistributioncancutdowntransportcostandimproveefficiency．VehicleRoutingProblem(VRP)isacombinationoptimizationproblemintransportationlogistics，whichhasbeenappliedinmanyfields．ItisastrongN

6、Pproblem．ThevehicleroutingproblemwithtimewindowsVRPTWismoredifficulttosolvethanVRPwithsimpleconditions．Inthispaper,brieflyintroducethestandardgeneticalgorithminthegeneralsituationofthedevelopment，basicconcept，basicprinciple，rationale，convergence，characteranditsapplication.The

7、seresearchesmadefullpreparationforustostudyVRPTW．BasedontheVRP,thispaperconsiderstimewindowsconstraintsofcustomerservice，transportationcostsandtimeeffectcostsmorecomprehensivly,soastosetthepenaltyfunctionandestablishthemodelofthevehicleroutingproblemwithtimewindows．Then，thetw

8、o-stageapproachhasbeendesigned：thefirststage，theconsiderationofcusto