基于三阶段法的VRP求解研究

李晔; 钱慎一; 张保威; 李建春

doi:10.3969/j.issn.2095-476X.2013.04.023

CN 41-1437/TS ISSN 2096-1553

基于三阶段法的VRP求解研究

李晔 , 钱慎一 , 张保威 , 李建春

李晔, 钱慎一, 张保威, 等. 基于三阶段法的VRP求解研究[J]. 轻工学报, 2013, 28(4): 95-98. doi: 10.3969/j.issn.2095-476X.2013.04.023

引用本文: 李晔, 钱慎一, 张保威, 等. 基于三阶段法的VRP求解研究[J]. 轻工学报, 2013, 28(4): 95-98. doi: 10.3969/j.issn.2095-476X.2013.04.023

LI Ye, QIAN Shen-yi, ZHANG Bao-wei and et al. Research on logistics vehicle routing problem based on three-phase approach[J]. Journal of Light Industry, 2013, 28(4): 95-98. doi: 10.3969/j.issn.2095-476X.2013.04.023

Citation: LI Ye, QIAN Shen-yi, ZHANG Bao-wei and et al. Research on logistics vehicle routing problem based on three-phase approach[J]. Journal of Light Industry, 2013, 28(4): 95-98. doi: 10.3969/j.issn.2095-476X.2013.04.023

基于三阶段法的VRP求解研究

郑州轻工业学院计算机与通信工程学院, 河南郑州 450001
基金项目: 国家自然科学基金项目(60974005)
河南省教育厅科学技术研究重点项目(13A520379)
河南省科技攻关项目(092102210026)
中图分类号: TP391.1

Research on logistics vehicle routing problem based on three-phase approach

College of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450001, China
Received Date: 2013-05-06
Available Online: 2013-07-15
CLC number: TP391.1

摘要: 提出了基于三阶段法的VRP求解方法,将Floyd算法、节约法、遗传算法融合于求解过程中,使用Floyd算法求解各点对间的最短路径,使用节约法进行回路扩充,使用遗传算法寻求最优方案,克服了遗传算法早收敛和搜索效率低的问题.实验结果表明本算法具有较好的应用价值.
- 物流配送 /
- 车辆调度 /
- 遗传算法 /
- 三阶段法
Abstract: The algorithm based on three-phase approach to solve the logistics vehicle routing problem(VPR) was proposed, in which three kinds of technologies-Floyd algorithm, saving method and genetic algorithm-were fused. The algorithm overcame the shortcomings of premature convergence and low efficiency of the genetic algorithm by using floyd algorithm to solve all-pairs shortest-path problem, using saving method for loop expansion, and using genetic algorithm to find the optimal solution. The experimental results showed that the algorithm had preferable application value on VPR.
- logistics dispatching /
- vehicle routing problem /
- genetic algorithm /
- three-phase approach
1. [1]
  李军,郭耀煌.物流配送车辆优化调度理论[M].北京:中国物资出版社,2001.
2. [2]
  唐坤.车辆路径问题中的遗传算法设计[J].东华大学学报:自然科学版,2002,28(1):66.
3. [3]
  Bent R,Van Hentenryck P.A two-stage hybrid algorithm for pick-up and delivery vehicle routing problems with time windows[J].Computers and Operations Research,2006,33(4):875.
4. [4]
  Holland J H.Adaptation in natural and artificial systems[M].Massachusetts:MIT Press,1975.
5. [5]
  谢天保,雷西玲,席文玲.物流配送中心配载车辆调度问题研究[J].计算机工程与应用,2010,46(36):237.
6. [6]
  王振峰,王旭,葛县龙.基于遗传算法的不同约束条件车辆调度问题研究[J].计算机应用研究,2010,27(10):3673.
7. [7]
  Clarke G,Wright J W.Scheduling of vehicles form a central depot to a number of delivery points[J].Operations Research,1964,12(4):568.
1. [1]
  刘广超 , 邓莎 , 高峄涵 , 吴涛 , 邓锐杰 . 加热卷烟辊压法薄片丝吸湿性影响因素研究. 轻工学报, 2024, 39(5): 109-117. doi: 10.12187/2024.05.013