基于改进混合蛙跳算法的CVRP求解

骆剑平; 李霞; 陈泯融

doi:10.3724/SP.J.1146.2010.00328

基于改进混合蛙跳算法的CVRP求解

doi: 10.3724/SP.J.1146.2010.00328

基金项目:

国家自然科学基金(60772148)和高等学校博士点基金(200805900 001)资助课题

计量
- 文章访问数: 4114
- HTML全文浏览量: 179
- PDF下载量: 1562
- 被引次数: 0
出版历程
- 收稿日期: 2010-04-01
- 修回日期: 2010-08-23
- 刊出日期: 2011-02-19

Improved Shuffled Frog Leaping Algorithm for Solving CVRP

摘要

摘要: 该文提出基于实数编码模式的混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)求解容量约束车辆路径问题(Capacitated Vehicle Routing Problem，CVRP)；把具有极强局部搜索能力的幂律极值动力学优化(Power Law Extremal Optimization，-EO)融合于SFLA，针对CVRP对-EO过程进行设计和改进。改进的-EO采用新颖的组元适应度计算方法；采用幂律概率分布来挑选需要变异的组元；根据最邻近城市表，采用幂律概率分布挑选变异组元的最佳邻近城市，执行线路间或线路内的变异。求解测试库中的实例，证明该改进算法有效。
- 智能优化 /
- 进化算法 /
- 混合蛙跳算法 /
- 极值动力学优化 /
- 车辆路径问题 /
- 收敛性
Abstract: An improved Shuffled Frog Leaping Algorithm (SFLA) is proposed to solve the Capacitated Vehicle Routing Problem(CVRP)based on real-coded patterns. It is then combined with the power-law Extremal Optimization (-EO) to further improve the local search ability. The fitness for the components of an individual is carefully designed and the neighborhood for-EO mutation is established according to power-law probability distribution. Experimental results show that the proposed algorithm outperforms other heuristic algorithms base on PSO and GA.
- Intelligence optimization /
- Evolutionary algorithm /
- Shuffled Frog Leaping Algorithm (SFLA) /
- Extremal Optimization (EO) /
- Vehicle Routing Problem (VRP) /
- Convergence

HTML全文

参考文献(1)

[1] Dantzig G and Ramser J. The truck dispatching problem[J].Management Science.1959, 6(1):80-91 [2] Thiago A S and Leandro N. Neuro-immune approach to solve routing problems[J]. Neuro Computing, 2009, 72(10): 2189-2197. [3] Dusan T. Swarm intelligence systems for transportation engineering: Principles and applications[J].Transportation Research.2008, 16(6):651-667 [4] 王培崇, 钱旭, 周玉. 求解VRP问题的混合鱼群遗传优化算法[J]. 计算机工程与应用, 2009, 45(24): 201-203. Wang Pei-chong, Qian Xu, and Zhou Yu. Hybrid artificial fish school algorithm to solve Vehicle Routing Problem(VRP)[J]. Computer Engineering and Application, 2009, 45(24): 201-203. [5] Eusuff M M and Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of Water Sources Planning and Management.2003, 129(3):210-225 [6] Thai H H. A modified shuffled frog leaping algorithm for optimal tuning of multivariable PID controllers[C]. International Conference on Information Technology, Singapore, 2008: 128-134. [7] Alireza R V. A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem[J].Computers Industrial Engineering.2007, 53(4):642-666 [8] Sun X and Wang Z Q. A web document classification method based on shuffled frog leaping algorithm[C]. Second International Conference on Genetic and Evolutionary Computing (WGEC 2008), Jingzhou, China, 2008: 205-208. [9] 罗雪晖, 杨烨, 李霞. 改进混合蛙跳算法求解旅行商问题[J].通信学报, 2009, 30(7): 130-135. Luo Xue-hui, Yang Ye, and Li Xia. A modifed shufflled frog leaping algorithm for TSP[J]. Journal on Communications, 2009, 30(7): 130-135. [10] Boettcher S and Percus A G. Extremal Optimization: Methods derived from Co-Evolution[C]. Proceedings of the Genetic and Evolutionary Computation Conference. New York, USA, 1999: 101-106. [11] Wu Jian jun and Tan Yu bo. A particle swarm optimization algorithm for grain logistics vehicle routing problem[C]. International Colloquium on Computing, Communication, Control, and Management, Wuhan, China,2009: 364-367. [12] Chen A L and Yang G K. Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem[J].Journal of Zhejiang University.2006, 7(4):607-614 [13] Chen A L and Yang G K. Production scheduling optimization algorithm for the hot rolling processes[J].International Journal of Production Research.2008, 46(7):1955-1973 [14] Roberto B and Nicos C. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts[J].Mathematical Programming.2008, 115(2):351-385 [15] Wang C H and Lu J Z. A hybrid genetic algorithm that optimizes capacitated vehicle routing problems[J].Expert Systems with Applications.2009, 36(2):2921-2936

施引文献

资源附件(0)

访问统计