A simple and effective metaheuristic for the Minimum Latency Problem

详细信息	查看全文 | 推荐本文 |

• 作者：Marcos Melo Silva^a ; ^{mmsilva@ic.uff.br} ; Anand Subramanian^a ; ^b ; ^{anand@ct.ufpb.br} ; Thibaut Vidal^c ; ^d ; ^{thibaut.vidal@cirrelt.ca} ; Luiz Satoru Ochi^a ; ^{satoru@ic.uff.br}
• 关键词：Metaheuristics ; Minimum Latency Problem ; GRASP ; Iterated Local Search
• 刊名：European Journal of Operational Research
• 出版年：2012
• 期刊代码：58_03772217
• 类别：et
• 出版时间：16 September, 2012
• 卷：221
• 期：3
• 页码：513-520
• 文件大小：298 K

摘要

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.