摘要
车辆路径问题属于组合优化领域中的NP–Hard问题.针对带软时间窗的车辆路径问题,提出了一种区域划分—路径优化的数学模型.首先结合最小支撑树算法能产生全局最优解的优点,将客户划分为若干个子区域.然后再结合贪婪算法简单迅速的特点,对每个子区域中的路径进行优化.实验结果表明,该算法收敛速度快、搜索成功率高.
Vehicle routing problem belongs to NP-Hard problems in the field of combinatorial optimization.This paper considers the vehicle routing problem with soft time windows,and propose a mathematical model about regional division and routing optimization.First,with the minimum spanning tree algorithm to produce global optimal solution,and the region of customers are divided into several sub-regions.Then using the simpleness and quickness of Greedy Algorithm to optimize each sub-path in every sub-region.Finally,experimental results show that the algorithm has a fast convergence speed,and high successful rate.
出处
《西南师范大学学报（自然科学版）》
CAS
北大核心
2015年第10期64-70,共7页
Journal of Southwest China Normal University(Natural Science Edition)
基金
四川省教育厅科研创新团队基金项目(14TD0026)
国家级大学生创新创业训练计划项目(201310640004)
关键词
车辆路径问题
软时间窗
区域划分
最小支撑树算法
贪婪算法
vehicle routing problem
soft time windows
region partition
minimum spanning tree algorithm
greedy algorithm
