Multi-Objective Genetic Algorithm for Solving Capacitated Vehicle Routing Problems
-
摘要: 针对有容量约束车辆路径问题,提出了基于Pareto方法的多目标优化遗传算法.该算法引入基于擂台法的Pareto锦标赛选择算子,避免了求解非凸解的困难.采用最邻近算法和扫描算法构造初始种群及引入启发式交叉算子来加快算法的收敛速度.通过E-n30-k3算例实验表明:应用该算法得到的Pareto解集,为决策者提供了多种途径有效解决有容量约束车辆路径问题.
-
关键词:
- 车辆路径问题 /
- 多目标遗传算法 /
- Pareto锦标赛选择算子 /
- 擂台法则 /
- 启发式算法
Abstract: A multi-objective genetic algorithm based on Pareto approach was proposed for capacitated vehicle routing problems (CVRPs).In this algorithm,a new Pareto tournament selection operator based on arena’s principle is used to avoid the difficulty of solving non-convex problems;meanwhile,the nearest-neighbor algorithm and sweep algorithm are adopted to initialize population,and heuristic crossover operator is introduced to accelerate the convergence speed.The simulation result on the E-n30-k3 test specimen shows that the Pareto set obtained by this algorithm can provide manifold paths for decision makers to solve CVRPs. -
代颖.基于遗传算法的供应链联盟伙伴选择[J].西南交通大学学报,2004,39(4):531-534.DAI Ying.Partner selection in supply chain alliance based on genetic algorithm[J].Journal of Southwest Jiaotong University,2004,39(4):531-534.[2] GEN M,LI Y.Spanning tree-based genetic algorithm for bicriteria fixed charge transportation problem[C] ∥Proceedings of the 1999 Congress on Evolutionary Computation.Washington DC:IEEE Congr,1999:2265-2271.[3] 张潜,高立群,胡祥培,等.物流配送路径多目标优化的聚类-改进遗传算法[J].控制与决策,2003,18(4):418-422.ZHANG Qian,GAO Liqun,HU Xiangpei,et al.Research on multi-objective vehicle muting problem of optimization based on clustering analysis and improved genetic algorithm[J].Control and Decision,2003,18(4):418-422.[4] INDRANEEL D,JOHN D,A closer look at drawbacks of minimizing weighted sums of objectives for pareto set generation in multicriteria optimization problems[J].Structural Optimization,1997,14(1):63-69.[5] 郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学,2002,5(10):51-56.LANG Maoxiang,HU Siji.Study on the optimization of physical distribution routing problem by hybrid genetic algorithm[J].Chinese Journal of Management Science,2002,5(10):51-56.[6] 陈子侠,叶庆泰.基于城市配送的单车线路算法研究[J].计算机工程,2005,31(11):32-34.CHEN Zixia,YE Qingtai.An algorithm iesearch on single vehicle routing problem based on real streets distribution[J].Computer Engineering,2005,31(11):32-34.[7] 郑金华,蒋浩,祁达,等.擂台赛法则构造多目标Pareto最优解集的方法研究[J].软件学报,2007,18(6):1287-1297.ZHENG Jinhua,JIANG Hao,QI Da,et al.An approach of constructing multi-objective pareto optimal solutions using arena's principle[J].Joumal of Software,2007,18(6):1287-1297.[8] DEB K,PRATAP A,Agrawal S,et al.A fast and elitist multi-objective genetic algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.[9] 郎茂祥.物流配送车辆调度问题的模型和算法研究[D].北京:北方交通大学,2003.
点击查看大图
计量
- 文章访问数: 1758
- HTML全文浏览量: 78
- PDF下载量: 583
- 被引次数: 0