探索城市物流配送的车辆路径算法研究

《探索城市物流配送的车辆路径算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：U121密级：公开UDC：单位代码：10424学位论文城市物流配送的车辆路径算法研究冯泉超申请学位级别：硕士学位专业名称：交通信息工程及控制指导教师姓名：樊铭渠职称：教授山东科技大学二零零九年五月论文题目：城市物流配送的车辆路径算法研究作者姓名：冯泉超入学时间：2006年9月专业名称：交通信息工程及控制研究方向：交通信息工程指导教师：樊铭渠职称：教授论文提交日期：2009年5月论文答辩日期：2009年6月授予学位日期：ResearchonVehicleRoutingProblemforCityLogistics

2、DistributionADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofMASTEROFPHILOSOPHYfromShandongUniversityofScienceandTechnologybyFengQuanChaoSupervisor:ProfessorFanMingQuCollegeofInformationandElectricalEngineeringMay2009声明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考

3、文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕士生签名：日期：AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofphilosophyinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofacknowledge.T

4、hedocumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Date:山东科技大学硕士学位论文摘要摘要城市物流配送是城市物流活动的一个重要环节。科学有效的城市物流配送体系，一方面有利于城市经济健康发展，另一方面有利于缓解现代城市中环境污染与交通堵塞严重、交通事故频发的问题。物流配送是连接生产与消费的一种中介服务，也是物资供应的重要环节之一。一般意义上的城市物流配送运输，是指配送中心不同客户多频度、小批量的订货要求进

5、行组织配送，在合适的时间，合适的地点，将正确的产品以适当的数量准确地交给客户，并保证服务的质量和合理的成本。由于从事城市配送的货运汽车工作条件复杂，不仅配送点多、货物种类繁多、路况及道路网复杂，而且运输服务地区内运输网点分布也不均匀，因此，设计合理、有效的配送路线方案，控制物流成本，减少车辆数量、配送里程，限制车辆在城市中的运行时间，就成为非常现实的问题。城市物流配送作业的重点将是如何高效的使用车辆并决定最“科学经济”的行驶路线，使商品能够以合理的成本送达顾客手中。本文研究的是如何在城市环境中实现科学有效的配送规划。目

6、前的物流配送规划研究大多放在采用启发式算法逐渐逼近最优解，主要采用的方法是遗传算法、免疫算法、退火算法、禁忌搜索算法及神经网络算法等，如姜大立建立了VRP的遗传算法,WEE-KTI重点研究了禁忌算法和遗传算法混合的启发式算法,1991年，Gendreau等人将禁忌搜索方法应用于VRP。本文中采用的是蚁群算法和聚类算法。蚁群算法是受自然界中真实蚁群觅食行为的启发而提出的一种启发式搜索算法。它具有正反馈、并行计算、较强的鲁棒性等诸多特点。然而，一般蚁群算法在车辆路径问题过程中容易出现过早收敛或停滞现象，而且蚁群算法的搜索时

7、间较长。为了解决这些问题，本文在认真分析国内外VRP研究的基础上，将蚁群算法与聚类算法相结合，提出了一个二阶段启发式车辆路径算法。该算法首先利用空间聚类的方法，对交通网络进行简化。以交通网络中各个结点之间行驶距离作为聚类的度量，以车辆容量为聚类的约束，将所有结点分配到各个簇中，形成有限个簇，再将每个簇抽象为一个新的结点，最终将整个交通网络（或者称为G图）简化成为一个二层结构,大大简化模型的规模。然后在簇结构和簇内两个层次上分别运用蚁群算法，生成以簇为基本需求点的行车路线和簇内点集的行车路线，最后获得最佳山东科技大学硕士

8、学位论文摘要路径表。文章除了对算法思想和算法描述做了详细介绍外，还分析了算法的时间复杂度，并通过系统实例验证了算法的有效性。关键词：物流配送，空间聚类，蚁群算法，容量约束山东科技大学硕士学位论文摘要ABSTRACTCitylogisticsdistributionisanimportantsectorincitylogistics