The dynamic traveling salesman problem(DTSP)is significant in logistics distribution in real-world applications in smart cities,but it is uncertain and difficult to solve.This paper proposes a scheme library-based ant...The dynamic traveling salesman problem(DTSP)is significant in logistics distribution in real-world applications in smart cities,but it is uncertain and difficult to solve.This paper proposes a scheme library-based ant colony optimization(ACO)with a two-optimization(2-opt)strategy to solve the DTSP efficiently.The work is novel and contributes to three aspects:problemmodel,optimization framework,and algorithmdesign.Firstly,in the problem model,traditional DTSP models often consider the change of travel distance between two nodes over time,while this paper focuses on a special DTSP model in that the node locations change dynamically over time.Secondly,in the optimization framework,the ACO algorithm is carried out in an offline optimization and online application framework to efficiently reuse the historical information to help fast respond to the dynamic environment.The framework of offline optimization and online application is proposed due to the fact that the environmental change inDTSPis caused by the change of node location,and therefore the newenvironment is somehowsimilar to certain previous environments.This way,in the offline optimization,the solutions for possible environmental changes are optimized in advance,and are stored in a mode scheme library.In the online application,when an environmental change is detected,the candidate solutions stored in the mode scheme library are reused via ACO to improve search efficiency and reduce computational complexity.Thirdly,in the algorithm design,the ACO cooperates with the 2-opt strategy to enhance search efficiency.To evaluate the performance of ACO with 2-opt,we design two challenging DTSP cases with up to 200 and 1379 nodes and compare them with other ACO and genetic algorithms.The experimental results show that ACO with 2-opt can solve the DTSPs effectively.展开更多
An energy-efficient heuristic mechanism is presented to obtain the optimal solution for the coverage problem in sensor networks. The mechanism can ensure that all targets are fully covered corresponding to their level...An energy-efficient heuristic mechanism is presented to obtain the optimal solution for the coverage problem in sensor networks. The mechanism can ensure that all targets are fully covered corresponding to their levels of importance at minimum cost, and the ant colony optimization algorithm （ACO） is adopted to achieve the above metrics. Based on the novel design of heuristic factors, artificial ants can adaptively detect the energy status and coverage ability of sensor networks via local information. By introducing the evaluation function to global pheromone updating rule, the pheromone trail on the best solution is greatly enhanced, so that the convergence process of the algorithm is speed up. Finally, the optimal solution with a higher coverage- efficiency and a longer lifetime is obtained.展开更多
The traveling salesman problem( TSP) is a well-known combinatorial optimization problem as well as an NP-complete problem. A dynamic multi-swarm particle swarm optimization and ant colony optimization( DMPSO-ACO) was ...The traveling salesman problem( TSP) is a well-known combinatorial optimization problem as well as an NP-complete problem. A dynamic multi-swarm particle swarm optimization and ant colony optimization( DMPSO-ACO) was presented for TSP.The DMPSO-ACO combined the exploration capabilities of the dynamic multi-swarm particle swarm optimizer( DMPSO) and the stochastic exploitation of the ant colony optimization( ACO) for solving the traveling salesman problem. In the proposed hybrid algorithm,firstly,the dynamic swarms,rapidity of the PSO was used to obtain a series of sub-optimal solutions through certain iterative times for adjusting the initial allocation of pheromone in ACO. Secondly,the positive feedback and high accuracy of the ACO were employed to solving whole problem. Finally,to verify the effectiveness and efficiency of the proposed hybrid algorithm,various scale benchmark problems were tested to demonstrate the potential of the proposed DMPSO-ACO algorithm. The results show that DMPSO-ACO is better in the search precision,convergence property and has strong ability to escape from the local sub-optima when compared with several other peer algorithms.展开更多
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.展开更多
蚁群优化(ACO)算法是一种常用的元启发式算法,它通过模拟蚁群寻找食物的过程,为求解多维背包问题(MKP)等NP难(Non-deterministic Polynomial hard)问题提供可行途径。原始ACO算法及其改进算法,通常分为多个轮次,每个轮次均会生成一个蚂...蚁群优化(ACO)算法是一种常用的元启发式算法,它通过模拟蚁群寻找食物的过程,为求解多维背包问题(MKP)等NP难(Non-deterministic Polynomial hard)问题提供可行途径。原始ACO算法及其改进算法,通常分为多个轮次,每个轮次均会生成一个蚂蚁种群寻找可行解。在不同轮次中,每轮蚁群中蚂蚁的数量是固定的,因此,如果将其指定一个较大的值,会导致算法出现不必要的时间消耗;反之,如果指定的值较小,则会降低算法全局最优解搜索能力。为此,提出了一种基于蚁群数量动态调整的改进蚁群优化算法ACO-ANDA(ACO algorithm based on Ant Number Dynamic Adjustment),所提算法在可行解搜索过程中,引入了一种新的蚁群数量动态调整机制。在每轮可行解搜索结束后,均根据近几轮可行解和历史最优解之间的关系,调整下一轮蚁群数量,实现对算法时间耗费和最优解搜索能力的平衡。再基于MKP基准测试集SAC-94的多组实验结果表明,相较于原始ACO算法,所提算法能够在最优解利润平均降低0.02%的情况下,平均降低77.85%的时间耗费。展开更多
提出了一种基于蚁群优化和粒子群优化的混合算法求解TSP(Traveling Salesm an Prob lem)问题。在应用蚁群算法对TSP问题的求解过程中,利用粒子群算法对蚁群系统的参数进行优化,其目的是提高蚁群系统的优化性能,使蚁群系统的参数不必靠...提出了一种基于蚁群优化和粒子群优化的混合算法求解TSP(Traveling Salesm an Prob lem)问题。在应用蚁群算法对TSP问题的求解过程中,利用粒子群算法对蚁群系统的参数进行优化,其目的是提高蚁群系统的优化性能,使蚁群系统的参数不必靠人工经验或反复试验选取,而是通过粒子搜索自适应选取。展开更多
基金supported in part by the National Research Foundation of Korea (NRF-2021H1D3A2A01082705).
文摘The dynamic traveling salesman problem(DTSP)is significant in logistics distribution in real-world applications in smart cities,but it is uncertain and difficult to solve.This paper proposes a scheme library-based ant colony optimization(ACO)with a two-optimization(2-opt)strategy to solve the DTSP efficiently.The work is novel and contributes to three aspects:problemmodel,optimization framework,and algorithmdesign.Firstly,in the problem model,traditional DTSP models often consider the change of travel distance between two nodes over time,while this paper focuses on a special DTSP model in that the node locations change dynamically over time.Secondly,in the optimization framework,the ACO algorithm is carried out in an offline optimization and online application framework to efficiently reuse the historical information to help fast respond to the dynamic environment.The framework of offline optimization and online application is proposed due to the fact that the environmental change inDTSPis caused by the change of node location,and therefore the newenvironment is somehowsimilar to certain previous environments.This way,in the offline optimization,the solutions for possible environmental changes are optimized in advance,and are stored in a mode scheme library.In the online application,when an environmental change is detected,the candidate solutions stored in the mode scheme library are reused via ACO to improve search efficiency and reduce computational complexity.Thirdly,in the algorithm design,the ACO cooperates with the 2-opt strategy to enhance search efficiency.To evaluate the performance of ACO with 2-opt,we design two challenging DTSP cases with up to 200 and 1379 nodes and compare them with other ACO and genetic algorithms.The experimental results show that ACO with 2-opt can solve the DTSPs effectively.
基金The Natural Science Foundation of Jiangsu Province(NoBK2005409)
文摘An energy-efficient heuristic mechanism is presented to obtain the optimal solution for the coverage problem in sensor networks. The mechanism can ensure that all targets are fully covered corresponding to their levels of importance at minimum cost, and the ant colony optimization algorithm （ACO） is adopted to achieve the above metrics. Based on the novel design of heuristic factors, artificial ants can adaptively detect the energy status and coverage ability of sensor networks via local information. By introducing the evaluation function to global pheromone updating rule, the pheromone trail on the best solution is greatly enhanced, so that the convergence process of the algorithm is speed up. Finally, the optimal solution with a higher coverage- efficiency and a longer lifetime is obtained.
基金National Natural Science Foundation of China(No.70971020)the Subject of Ministry of Education of Hunan Province,China(No.13C818)+3 种基金the Project of Industrial Science and Technology Support of Hengyang City,Hunan Province,China(No.2013KG63)the Open Project Program of Artificial Intelligence Key Laboratory of Sichuan Province,Sichuan University of Science and Engineering,China(No.2012RYJ03)the Fund Project of Humanities and Social Sciences,Ministry of Education of China(No.13YJCZH147)the Special Fund for Shanghai Colleges' Outstanding Young Teachers' Scientific Research Projects,China(No.ZZGJD12033)
文摘The traveling salesman problem( TSP) is a well-known combinatorial optimization problem as well as an NP-complete problem. A dynamic multi-swarm particle swarm optimization and ant colony optimization( DMPSO-ACO) was presented for TSP.The DMPSO-ACO combined the exploration capabilities of the dynamic multi-swarm particle swarm optimizer( DMPSO) and the stochastic exploitation of the ant colony optimization( ACO) for solving the traveling salesman problem. In the proposed hybrid algorithm,firstly,the dynamic swarms,rapidity of the PSO was used to obtain a series of sub-optimal solutions through certain iterative times for adjusting the initial allocation of pheromone in ACO. Secondly,the positive feedback and high accuracy of the ACO were employed to solving whole problem. Finally,to verify the effectiveness and efficiency of the proposed hybrid algorithm,various scale benchmark problems were tested to demonstrate the potential of the proposed DMPSO-ACO algorithm. The results show that DMPSO-ACO is better in the search precision,convergence property and has strong ability to escape from the local sub-optima when compared with several other peer algorithms.
基金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.
文摘蚁群优化(ACO)算法是一种常用的元启发式算法,它通过模拟蚁群寻找食物的过程,为求解多维背包问题(MKP)等NP难(Non-deterministic Polynomial hard)问题提供可行途径。原始ACO算法及其改进算法,通常分为多个轮次,每个轮次均会生成一个蚂蚁种群寻找可行解。在不同轮次中,每轮蚁群中蚂蚁的数量是固定的,因此,如果将其指定一个较大的值,会导致算法出现不必要的时间消耗;反之,如果指定的值较小,则会降低算法全局最优解搜索能力。为此,提出了一种基于蚁群数量动态调整的改进蚁群优化算法ACO-ANDA(ACO algorithm based on Ant Number Dynamic Adjustment),所提算法在可行解搜索过程中,引入了一种新的蚁群数量动态调整机制。在每轮可行解搜索结束后,均根据近几轮可行解和历史最优解之间的关系,调整下一轮蚁群数量,实现对算法时间耗费和最优解搜索能力的平衡。再基于MKP基准测试集SAC-94的多组实验结果表明,相较于原始ACO算法,所提算法能够在最优解利润平均降低0.02%的情况下,平均降低77.85%的时间耗费。
文摘提出了一种基于蚁群优化和粒子群优化的混合算法求解TSP(Traveling Salesm an Prob lem)问题。在应用蚁群算法对TSP问题的求解过程中,利用粒子群算法对蚁群系统的参数进行优化,其目的是提高蚁群系统的优化性能,使蚁群系统的参数不必靠人工经验或反复试验选取,而是通过粒子搜索自适应选取。
