It is difficult for the double suppression division algorithm of bee colony to solve the spatio-temporal coupling or have higher dimensional attributes and undertake sudden tasks.Using the idea of clustering,after clu...It is difficult for the double suppression division algorithm of bee colony to solve the spatio-temporal coupling or have higher dimensional attributes and undertake sudden tasks.Using the idea of clustering,after clustering tasks according to spatio-temporal attributes,the clustered groups are linked into task sub-chains according to similarity.Then,based on the correlation between clusters,the child chains are connected to form a task chain.Therefore,the limitation is solved that the task chain in the bee colony algorithm can only be connected according to one dimension.When a sudden task occurs,a method of inserting a small number of tasks into the original task chain and a task chain reconstruction method are designed according to the relative relationship between the number of sudden tasks and the number of remaining tasks.Through the above improvements,the algorithm can be used to process tasks with spatio-temporal coupling and burst tasks.In order to reflect the efficiency and applicability of the algorithm,a task allocation model for the unmanned aerial vehicle(UAV)group is constructed,and a one-to-one correspondence between the improved bee colony double suppression division algorithm and each attribute in the UAV group is proposed.Task assignment has been constructed.The study uses the self-adjusting characteristics of the bee colony to achieve task allocation.Simulation verification and algorithm comparison show that the algorithm has stronger planning advantages and algorithm performance.展开更多
We investigate a kind of vehicle routing problem with constraints(VRPC)in the car-sharing mobility environment,where the problem is based on user orders,and each order has a reservation time limit and two location poi...We investigate a kind of vehicle routing problem with constraints(VRPC)in the car-sharing mobility environment,where the problem is based on user orders,and each order has a reservation time limit and two location point transitions,origin and destination.It is a typical extended vehicle routing problem(VRP)with both time and space constraints.We consider the VRPC problem characteristics and establish a vehicle scheduling model to minimize operating costs and maximize user(or passenger)experience.To solve the scheduling model more accurately,a spatiotemporal distance representation function is defined based on the temporal and spatial properties of the customer,and a spatiotemporal distance embedded hybrid ant colony algorithm(HACA-ST)is proposed.The algorithm can be divided into two stages.First,through spatiotemporal clustering,the spatiotemporal distance between users is the main measure used to classify customers in categories,which helps provide heuristic information for problem solving.Second,an improved ant colony algorithm(ACO)is proposed to optimize the solution by combining a labor division strategy and the spatiotemporal distance function to obtain the final scheduling route.Computational analysis is carried out based on existing data sets and simulated urban instances.Compared with other heuristic algorithms,HACA-ST reduces the length of the shortest route by 2%–14%in benchmark instances.In VRPC testing instances,concerning the combined cost,HACA-ST has competitive cost compared to existing VRP-related algorithms.Finally,we provide two actual urban scenarios to further verify the effectiveness of the proposed algorithm.展开更多
基金This work was supported by the National Natural Science and Technology Innovation 2030 Major Project of Ministry of Science and Technology of China(2018AAA0101200)the National Natural Science Foundation of China(61502522,61502534)+4 种基金the Equipment Pre-Research Field Fund(JZX7Y20190253036101)the Equipment Pre-Research Ministry of Education Joint Fund(6141A02033703)Shaanxi Provincial Natural Science Foundation(2020JQ-493)the Military Science Project of the National Social Science Fund(WJ2019-SKJJ-C-092)the Theoretical Research Foundation of Armed Police Engineering University(WJY202148).
文摘It is difficult for the double suppression division algorithm of bee colony to solve the spatio-temporal coupling or have higher dimensional attributes and undertake sudden tasks.Using the idea of clustering,after clustering tasks according to spatio-temporal attributes,the clustered groups are linked into task sub-chains according to similarity.Then,based on the correlation between clusters,the child chains are connected to form a task chain.Therefore,the limitation is solved that the task chain in the bee colony algorithm can only be connected according to one dimension.When a sudden task occurs,a method of inserting a small number of tasks into the original task chain and a task chain reconstruction method are designed according to the relative relationship between the number of sudden tasks and the number of remaining tasks.Through the above improvements,the algorithm can be used to process tasks with spatio-temporal coupling and burst tasks.In order to reflect the efficiency and applicability of the algorithm,a task allocation model for the unmanned aerial vehicle(UAV)group is constructed,and a one-to-one correspondence between the improved bee colony double suppression division algorithm and each attribute in the UAV group is proposed.Task assignment has been constructed.The study uses the self-adjusting characteristics of the bee colony to achieve task allocation.Simulation verification and algorithm comparison show that the algorithm has stronger planning advantages and algorithm performance.
基金Project supported by the National Science and Technology Innovation 2030 Major Project of the Ministry of Science and Technology of China(No.2018AAA0101200)。
文摘We investigate a kind of vehicle routing problem with constraints(VRPC)in the car-sharing mobility environment,where the problem is based on user orders,and each order has a reservation time limit and two location point transitions,origin and destination.It is a typical extended vehicle routing problem(VRP)with both time and space constraints.We consider the VRPC problem characteristics and establish a vehicle scheduling model to minimize operating costs and maximize user(or passenger)experience.To solve the scheduling model more accurately,a spatiotemporal distance representation function is defined based on the temporal and spatial properties of the customer,and a spatiotemporal distance embedded hybrid ant colony algorithm(HACA-ST)is proposed.The algorithm can be divided into two stages.First,through spatiotemporal clustering,the spatiotemporal distance between users is the main measure used to classify customers in categories,which helps provide heuristic information for problem solving.Second,an improved ant colony algorithm(ACO)is proposed to optimize the solution by combining a labor division strategy and the spatiotemporal distance function to obtain the final scheduling route.Computational analysis is carried out based on existing data sets and simulated urban instances.Compared with other heuristic algorithms,HACA-ST reduces the length of the shortest route by 2%–14%in benchmark instances.In VRPC testing instances,concerning the combined cost,HACA-ST has competitive cost compared to existing VRP-related algorithms.Finally,we provide two actual urban scenarios to further verify the effectiveness of the proposed algorithm.
