基于改进A~*算法的导购路径规划方法
|
摘要
大型超市内商品数目繁多,空间环境复杂,顾客在购物的过程中往往需要耗费大量的时间来寻找所需购买的商品。针对这一问题,提出了遗传-改进A*算法来帮助顾客找到一条通往所需购买商品的最短路径。首先利用矩阵对超市的空间环境进行建模,然后通过改进A*算法找到任意两个商品之间的最短路径,再根据顾客的购物列表利用遗传算法优化生成一条包含超市入口,购物列表上的商品以及超市出口的最短路径。最后仿真实验表明,在多楼层的大型超市里,顾客购买多个不同商品时,遗传-改进A*算法寻优能力更强,求解质量更优,并且运行时间更短,能够高效地解决最短路径规划问题。
Due to the large number of products in large supermarkets and the complex space environment, customers often spend a lot of time shopping to find the purchase of goods. In response to this problem, the genetic & modified A*algorithm is proposed to help customers find a shortest path to the desired purchase. First, the matrix is used to model the spatial layout of the supermarket. Then, the shortest path between any two commodities can be found by using the modified A* algorithm. Next, according to the customer's shopping list a shortest path can be optimized by genetic algorithm,which includes the supermarket entrance, the shopping list, and the supermarket exit. Finally, the simulation results show that in a large supermarket with multiple floors, the more different commodities the customer purchases, the better optimization ability the genetic & modified A* algorithm has, the better quality of solution is, the shorter running time is required,which can efficiently solve the shortest path planning problem.
Due to the large number of products in large supermarkets and the complex space environment, customers often spend a lot of time shopping to find the purchase of goods. In response to this problem, the genetic & modified A*algorithm is proposed to help customers find a shortest path to the desired purchase. First, the matrix is used to model the spatial layout of the supermarket. Then, the shortest path between any two commodities can be found by using the modified A* algorithm. Next, according to the customer's shopping list a shortest path can be optimized by genetic algorithm,which includes the supermarket entrance, the shopping list, and the supermarket exit. Finally, the simulation results show that in a large supermarket with multiple floors, the more different commodities the customer purchases, the better optimization ability the genetic & modified A* algorithm has, the better quality of solution is, the shorter running time is required,which can efficiently solve the shortest path planning problem.
引文
[1] Jia H,Jiang T,Zhao F.Research on route recommendationfor indoor multi-travel destinations[C]//World AutomationCongress,2012:1-4.
[2]曾薪夷.基于Android平台的GPS导航系统的设计与实现[J].计算机与现代化,2012(9):225-228.
[3] Panda R K,Choudhury B B.An effective path planningof mobile robot using genetic algorithm[C]//IEEE Inter-national Conference on Computational Intelligence&Communication Technology,2015:287-291.
[4]朱天楠.基于Android平台的手机超市导购系统的设计[J].南通职业大学学报,2012,26(3):101-104.
[5]邹益民,高阳,高碧悦.一种基于Dijkstra算法的机器人避障问题路径规划[J].数学的实践与认识,2013,43(10):111-118.
[6]柴寅,唐秋华,邓明星,等.机器人路径规划的栅格模型构建与蚁群算法求解[J].机械设计与制造,2016(4):178-181.
[7]韩建妙,刘业政.基于遗传算法的超市最短导购路径推荐[J].计算机工程与应用,2016,52(4):238-242.
[8]张婷娟.基于A*算法的最短路径寻优数学方法研究[J].科技通报,2015(6):244-247.
[9]蒋亚平,李涛,梁刚,等.一种基于免疫原理求解TSP问题的模型[J].计算机工程,2006,32(15):165-167.
[10]郝秦芝,周中良,张誉.支援干扰下战斗机突防段综合航迹规划[J].计算机工程与应用,2017,53(20):95-99.
[11]韩晓龙,李上,杨全业.基于遗传算法的战略供应链集成研究[J].计算机工程与应用,2018,54(2):214-221.
[12] You L U,Jia H E.TSP problems solving based on theoptimization and memory access optimization geneticalgorithm[J].Sichuan University of Arts&Science Jour-nal,2017.
[13]田华亭,李涛,秦颖.基于A*改进算法的四向移动机器人路径搜索研究[J].控制与决策,2017,32(6):1007-1012.
[14] Xie Y,Cheng W.AGV path planning based on smoothingA*algorithm[J].International Journal of Software Engi-neering and Applications,2015,6(5):1-8.
[15] Sun L.Genetic algorithm for TSP problem[C]//InternationalIndustrial Informatics and Computer Engineering Con-ference,2015.
[16]周全,黄云.模拟退火算法与遗传算法在光谱椭偏数据处理中的应用比较[J].应用光学,2008,29(3):385-389.
[17]姚明海,王娜,赵连朋,等.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用,2013,49(14):60-65.
[2]曾薪夷.基于Android平台的GPS导航系统的设计与实现[J].计算机与现代化,2012(9):225-228.
[3] Panda R K,Choudhury B B.An effective path planningof mobile robot using genetic algorithm[C]//IEEE Inter-national Conference on Computational Intelligence&Communication Technology,2015:287-291.
[4]朱天楠.基于Android平台的手机超市导购系统的设计[J].南通职业大学学报,2012,26(3):101-104.
[5]邹益民,高阳,高碧悦.一种基于Dijkstra算法的机器人避障问题路径规划[J].数学的实践与认识,2013,43(10):111-118.
[6]柴寅,唐秋华,邓明星,等.机器人路径规划的栅格模型构建与蚁群算法求解[J].机械设计与制造,2016(4):178-181.
[7]韩建妙,刘业政.基于遗传算法的超市最短导购路径推荐[J].计算机工程与应用,2016,52(4):238-242.
[8]张婷娟.基于A*算法的最短路径寻优数学方法研究[J].科技通报,2015(6):244-247.
[9]蒋亚平,李涛,梁刚,等.一种基于免疫原理求解TSP问题的模型[J].计算机工程,2006,32(15):165-167.
[10]郝秦芝,周中良,张誉.支援干扰下战斗机突防段综合航迹规划[J].计算机工程与应用,2017,53(20):95-99.
[11]韩晓龙,李上,杨全业.基于遗传算法的战略供应链集成研究[J].计算机工程与应用,2018,54(2):214-221.
[12] You L U,Jia H E.TSP problems solving based on theoptimization and memory access optimization geneticalgorithm[J].Sichuan University of Arts&Science Jour-nal,2017.
[13]田华亭,李涛,秦颖.基于A*改进算法的四向移动机器人路径搜索研究[J].控制与决策,2017,32(6):1007-1012.
[14] Xie Y,Cheng W.AGV path planning based on smoothingA*algorithm[J].International Journal of Software Engi-neering and Applications,2015,6(5):1-8.
[15] Sun L.Genetic algorithm for TSP problem[C]//InternationalIndustrial Informatics and Computer Engineering Con-ference,2015.
[16]周全,黄云.模拟退火算法与遗传算法在光谱椭偏数据处理中的应用比较[J].应用光学,2008,29(3):385-389.
[17]姚明海,王娜,赵连朋,等.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用,2013,49(14):60-65.