An iterated local search algorithm for the traveling purchaser problem
Tomás Kapancioglu, Raquel Bernardino · European Journal of Operational Research · 2025
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.