基于磁滞优化车辆路径问题的研究

《基于磁滞优化车辆路径问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要摘要车辆路径问题是物流配送领域涉及到的典型问题，也是组合优化领域最为重要和流行的研究问题之一。本文研究有能力约束车辆路径问题(CVRP)。首先以数学规划模型为基础，针对CVRP分别应用磁滞优化算法(HO)和改进的磁滞优化算法进行了求解，并针对标准的测试问题，进行了实验仿真，并给出了与其它优化算法如粒子群算法(PSO)和遗传算法(GA)相比较的结果。本文首先介绍了CVRP的基本理论。在这个问题中，所有的顾客都有预先决定好的需求，每个车辆都有相同的容量约束，现在有一个从公共车场点出发的一列运输车队来服务这

2、些顾客，最终要决定每辆车所服务的顾客，并且确定其访问顺序，从而使得总花费最小。首先给出了其图模型和数学模型。在详细说明了几种常见的智能优化方法的基本原理以后．分别给出了‘每种方法应用到CVRP上的过程和算法步骤。包括模拟退火算法、禁忌搜索算法、遗传算法和蚁群算法等。接着，本文首次把磁滞优化算法(Ho)应用到有能力约束车辆路径问题中。Ho是一种起初针对旋转玻璃模型所提出的物理优化算法，最早由Zarfind等人于2002年提出。HO的核心在于利用交流去磁过程达到优化的效果。具体来说，通过在原来模型中引入一个幅

3、值逐步衰减的外部交变磁场，随着外部场强方向的依次交替变化，来优化目标函数，使其逐步趋于最-优解。Zarltnd等人曾把它应用到100个城市规模的旅行商问题(TSP)求解中，并验证了该算法的有效性．本文首次把HO算法应用到有能力约束车辆路径问题中，针对5个标准的问题进行了仿真测试．实验结果表明HO算法能够找到车辆路径问题的次优解，且其解优于其它智能优化算法得到的结果。其次，本文针对有能力约束车辆路径问题提出了改进的磁滞优化算法。由于磁滞优化算法相对于模拟退火算法等其它智能算法设计更为复杂，且对于一般的优化问

4、题来说。定义构象空间距离又相对麻烦，所以本文考虑采用改进的磁滞优化算法来求解车辆路径问题。通过定义泛化的外磁场，并且设定突变的雪崩点，本文进一步改进了基于磁滞优化算法的车辆路径问题的求解．使得算法的求解变得更加通用、简单和快速。111浙江大学硕士学位论文IV最后，本文对全文做了总结，并对未来的研究做了展望。关键词：车辆路径问题；图模型；启发式算法；智能优化算法；磁滞优化算法摘要AbstractTheVehicleRoutingProblem(VRP)isatypicalproblemrelatedtodi

5、spatchingsubjectinlogisticsandalsooneofthemostimportantandintensivelystudiedcombinatorialoptimizationproblems．ThisthesisstudiesontheCapacitatedVehicleRoutingProblem(CVRP)．Basedonthemathematicalprogrammingmodel，hystereticoptimization(HO)algorithmandallimpr

6、ovedHOoptimizationalgorithmareusedrespectivelytostudytheCVRP．Theexperimentalresultswithbenchmarkproblemsaregivenincludingcompareddataandanalysiswithotheroptimizationalgorithms，suchasparticleswarmoptimization，geneticalgorithms，etc．Firstly，thebasictheoryofC

7、VRPisintroduced．Inthisproblem，allcustomershaveapre-determineddemand，andeachvehiclehasthesamecapacityconstraints．Wehavetodecideafleetofvehicleswhichstartfromthedepottoservethesecustomerswithaminimumcost，includingwhichvehicleseinespecifiedcustomersandthevis

8、itingsequence．Wefirstgiveitsgraphmodelandmathematicalmodel．Basedadetaileddescriptionofbasicprinciplesofseveralcommonintelligentoptimizationmethods，theprocessandstepsofthesealgorithmonhowtobeappliedtoCVRPisgivenforea