A simple and effective metaheuristic for the Minimum Latency Problem |
| |
Authors: | Marcos Melo Silva Anand Subramanian Thibaut Vidal Luiz Satoru Ochi |
| |
Institution: | 1. Universidade Federal Fluminense, Instituto de Computação, Rua Passo da Pátria 156, Bloco E – 3o andar, São Domingos Niterói-RJ 24210-240, Brazil;2. Universidade Federal da Paraíba, Departamento de Engenharia de Produção, Centro de Tecnologia, Campus I – Bloco G, Cidade Universitária, João Pessoa-PB 58051-970, Brazil;3. CIRRELT, Département d’informatique et de recherche opérationnelle, Université de Montréal, Montréal, Canada H3C 3J7;4. Institut Charles Delaunay, Université de Technologie de Troyes, 10010 Troyes, France |
| |
Abstract: | 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. |
| |
Keywords: | Metaheuristics Minimum Latency Problem GRASP Iterated Local Search |
本文献已被 ScienceDirect 等数据库收录! |
|