A simple and effective metaheuristic for the Minimum Latency Problem

The Minimum Latency Problem (MLP) is a variant of the Traveling Salesman Problem which aims to minimize the sum of arrival times at vertices. The problem arises in a number of practical applications such as logistics for relief supply, scheduling and data retrieval in computer networks. This paper introduces a simple metaheuristic for the MLP, based on a greedy randomized approach for solution construction and iterated variable neighborhood descent with random neighborhood ordering for solution improvement. Extensive computational experiments on nine sets of benchmark instances involving up to 1000 customers demonstrate the good performance of the method, which yields solutions of higher quality in less computational time when compared to the current best approaches from the literature. Optimal solutions, known for problems with up to 50 customers, are also systematically obtained in a fraction of seconds.

► A new metaheuristic is proposed for the Minimum Latency Problem (MLP).
► Move evaluations can be handled in O(1) time for classical local-search neighborhoods.
► High-quality solutions are found with a simple approach and few parameters.
► Known optimal solutions are rapidly obtained for instances with up to 107 customers.