基于聚类的多配送中心车辆调度问题研究

《基于聚类的多配送中心车辆调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn基于聚类的多配送中心车辆调度问题研究陈美军张志胜史金飞（东南大学机械工程学院，南京211189）E-mail:jsnjcmj@163.com摘要：多配送中心有时间窗的车辆路径问题是一个典型的NP难题，用传统的方法求解往往不能得到令人满意的结果，因此成为了当前运筹学与组合优化领域的一个前沿与研究热点。该文在对多配送中心带时间窗的车辆路径问题进行详细阐述的基础上，建立了数学模型，提出采用快速动态聚类分配法将多配送中心带时间窗的车辆路径问题分解为若干个单配送中心车辆路径优化问题进行求解的思路。利用求解单配送中心

2、带时间窗的车辆路径问题的蚁群算法，设计了求解多配送中心带时间窗的车辆路径问题的改进蚁群算法，并进行了实例分析。试验结果表明了此方法对优化多配送中心有时间窗的车辆路径问题的有效性。关键词：多配送中心车辆路径问题；时间窗；数学模型；动态聚类；改进蚁群算法中图分类号：U492文献标识码:AStudyonMulti-DepotVehicleRoutingProblemwithTimeWindowsBaseonClusteringandAntColonyAlgorithmCHENMeijun,ZHANGZhisheng,SHIJinfei(SchoolofMe

3、chanicalEngineering,SoutheastUniversity,Nanjing211189,China)Abstract:BecauseMulti-DepotVehicleRoutingProblemwithTimeWindows（MDVRPTW）isatypicalNPhardproblem,theresultsbytraditionalmethodssolvingthemarenotfamous,ithasbeenanstudyinghotspotproblemandthefrontofoperationsresearchandc

4、ombinationoptimizationfieldincurrent.Onthebasisofexpoundingdetailtothemulti-depotvehicleroutingproblem,themathematicmodeloftheproblemisbuiltinthispaper.Thesolvingmethodsofdividingamulti-depotvehicleschedulingproblemwithtimewindowsintoseveralsingle-depotvehiclerouteoptimizingpro

5、blembyusingtheassigningmethodoffleetnessclusteringispresented.Andthen,theantcolonyoptimizingimprovedalgorithmforthemulti-depotvehicleroutingproblemsisdesignedbyusingantcolonyoptimizingalgorithmforthesingle-depotvehicleroutingproblem.Finally,acaseanalysishasbeencarriedout;theres

6、ultofexperimentindicatesthevalidityofthetechniquetoMDVRPTWwiththeabove-mentionedconditions.Keywords:Multi-DepotVehicleRoutingProblem,TimeWindows,Mathematicmodel,dynamicclustering，ImprovedAntColonyAlgorithm0引言物流配送路径问题又称为车辆路径问题（VehicleRoutingProblem,VRP），最初是由G.Dantzig和J.Ramser于19

7、59年提出来的，车辆路径问题通常定义为：对一系列收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、车辆容量等限制)下，达到一定的目标(如路程最短、费用最小等)。针对VRP问题，有精确求解方法和近似求解方法，由于精确算法只能求解简单的VRP问题，复杂问题几乎无法精确求解，而实际绝大部分VRP是NP难题，因此近年来国内外学者提出了大量启发式算法，如扫描法（Sweep）、节约法(Saving)、禁忌搜索算法(TabuSearch)、遗传算法(GA)等，并取得了一些成果。但当前对车辆路径问题的研究主要集中在单配送中心问题上

8、，对多配送中心车辆调度问题的研究较少，尤其在多配送中心带时间窗的车辆路径问题（Multiple-Depots