Paper Info
Title
Computing Sharp Lower and Upper Bounds for the Minimum Latency Problem
Abstract
The Minimum Latency Problem, also known as Traveling Repairman Problem, the Deliveryman Problem and the Traveling Salesman Problem with Cumulative Costs is a variant of the Traveling Salesman Problem in which a repairman is required to visit customers located on each node of a graph in such a way that the overall waiting times of these customers is minimized. In the present work, an algorithm based on tight different linear programming lowerbounds and a specialized GRASP procedure are presented. The linear programming based lower-bounds are based on the Quadratic Assignment Problem with the aid of side constraints. Instances from 10 up to 60 nodes are solved very close to optimality in reasonable time.
Year
DOI
Venue
2007
10.1109/HIS.2007.30
HIS
Keywords
Field
DocType
reasonable time,deliveryman problem,tight different linear programming,upper bounds,linear programming,repairman problem,cumulative costs,computing sharp lower,minimum latency problem,present work,quadratic assignment problem,salesman problem,linear program,traveling salesman problem,lower bound,cumulant
Traveling purchaser problem,Bottleneck traveling salesman problem,Mathematical optimization,GRASP,Quadratic assignment problem,Algorithm,Travelling salesman problem,Cutting stock problem,Linear programming,2-opt,Mathematics
Conference
ISBN
Citations 
PageRank 
0-7695-2946-1
0
0.34
References 
Authors
15
4
Name
Order
Citations
PageRank
Joao Sarubbi1358.53
Henrique Pacca L. Luna2372.69
Gilberto de Miranda Jr.3703.86
Ricardo Saraiva de Camargo4896.26