百度地图API及蚁群算法在车辆路径问题中的应用  

The application of Baidu maps API and ACO in VRP

作　　者：林文如[1] 林国福[1] 

机构地区：[1]闽江学院计算机科学系,福建福州350121

出　　处：《闽江学院学报》2015年第2期82-88,共7页Journal of Minjiang University

基　　金：福建省中青年教师教育科研项目(JB13165)

摘　　要：在车辆路径问题(VRP)的研究中,通常采用节点间直线距离之和作为最短路径最优求解的数据基础,而节点间直线距离和与道路(弯曲、单向行驶等情况)实际距离通常相去甚远,使得其最优路径安排难于真正应用在实际需求中.为此,首先通过百度地图API获取节点间实际道路的距离数据,然后通过增加约束条件、修改节点间距离的计算、更换选择策略、调整信息挥发因子ρ取值等方法改进基本蚁群算法,最后将百度地图API获取的道路实际距离数据提交给改进蚁群算法求解.同时,基于PHP、Ajax编程求解程序并运行,实验表明,该方法具有可行性与实用性,完善了VRP问题从理论研究过渡到实际应用的最后一个环节.In the vehicle routing problem（ VRP） research,the linear distance of nodes was usually regarded as datasets for solving the optimal path,but it＇s difficult to apply in the actual demand because the gap is even wider between the linear distance and the actual road distance. So firstly,the datasets of actual road distance was acquired by using Baidu maps API; and then the basic ant colony algorithm was improved by adding constraints,modifying nodes＇ distance datasets,replacing selection strategy,adjusting ρ（ the information volatilization factor） value; lastly,the actual road distance datasets were submitted to the improved ant colony algorithm for solving. Moreover,based on PHP and Ajax,the solver program was developed,the experimental results show that this method is feasible and practical,achieve the last step from theoretical research to practical application for VRP.

关 键 词：百度地图 车辆路径问题 蚁群算法 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]