An iterated local search algorithm for the traveling purchaser problem
针对旅行购买者问题，提出一种基于迭代局部搜索的元启发式算法，通过限制邻域搜索次数和调整市场子集，在不对称实例上显著优于已有结果，在对称实例上也具有竞争力。
The Traveling Purchaser Problem (TPP) is a generalization of the Traveling Salesman Problem (TSP) in which a list of items must be acquired by visiting a subset of markets. The objective is to minimize the total cost sustained along the route, including purchasing and traveling costs. Due to the NP-hard nature of the problem, solving the TPP in an exact manner is computationally challenging, implying the need for heuristic approaches to obtain quality solutions efficiently. This study proposes an algorithm based on the metaheuristic Iterated Local Search (ILS), complemented by a route configuration procedure that adjusts the subset of markets in the solution. The ILS is tested in benchmark instances, providing a performance comparison with other methods. The computational experiment for the asymmetric instances reveals the effectiveness and efficiency of the ILS, outperforming previously published results with statistical significance. Additional experiments are presented for the symmetric instances, pointing to the competitiveness and versatility of the ILS in relation to other heuristic approaches used in the literature. • We propose a metaheuristic approach for the unrestricted traveling purchaser problem. • We introduce a novel procedure that limits the number of neighborhood searches. • We outperform the best results in the literature for the asymmetric instances. • We solve a subset of symmetric instances to optimality. • We provide competitive results for the euclidean symmetric instances.