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.展开更多
最大最小蚂蚁系统(Min Max Ant System, MMAS)在求解旅行商问题(Travelling Salesman Problem, TSP)时,存在局部搜索能力有限,解质量较低,收敛速度较慢的问题,原因在于精英策略的弱化,以及算法中缺少局部搜索功能。针对这些问题,提出一...最大最小蚂蚁系统(Min Max Ant System, MMAS)在求解旅行商问题(Travelling Salesman Problem, TSP)时,存在局部搜索能力有限,解质量较低,收敛速度较慢的问题,原因在于精英策略的弱化,以及算法中缺少局部搜索功能。针对这些问题,提出一种基于MMAS改进的动态精英平衡蚁群优化算法。首先,针对解质量低的问题,通过引入动态调整精英蚂蚁比例机制,有效提高了解的质量;其次,针对MMAS局部搜索能力有限的问题,使用局部2-opt搜索算法,并使用增量技术,将距离计算部分的算法复杂度从O(n)降为了O(1),有效解决了MMAS局部搜索能力有限的问题;最后,使用并行独立构造解,以及精英混合选择路径策略,大大加快了收敛速度,有效解决了MMAS收敛速度较慢的问题。使用标准TSPLIB库中几个经典实例测试提出的算法,结果表明该算法的解与收敛速度比较MMAS有明显提升。展开更多
基金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.
文摘最大最小蚂蚁系统(Min Max Ant System, MMAS)在求解旅行商问题(Travelling Salesman Problem, TSP)时,存在局部搜索能力有限,解质量较低,收敛速度较慢的问题,原因在于精英策略的弱化,以及算法中缺少局部搜索功能。针对这些问题,提出一种基于MMAS改进的动态精英平衡蚁群优化算法。首先,针对解质量低的问题,通过引入动态调整精英蚂蚁比例机制,有效提高了解的质量;其次,针对MMAS局部搜索能力有限的问题,使用局部2-opt搜索算法,并使用增量技术,将距离计算部分的算法复杂度从O(n)降为了O(1),有效解决了MMAS局部搜索能力有限的问题;最后,使用并行独立构造解,以及精英混合选择路径策略,大大加快了收敛速度,有效解决了MMAS收敛速度较慢的问题。使用标准TSPLIB库中几个经典实例测试提出的算法,结果表明该算法的解与收敛速度比较MMAS有明显提升。
