Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 121, Issue 2, Pages 420-434Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0377-2217(99)00045-4
Keywords
routing; lower bounds; heuristics
Ask authors/readers for more resources
A set of routes that minimizes the total collecting cost of the household refuse in a quarter of Lisbon may be obtained solving a Capacitated Are Routing Problem (CARP) with side constraints. The CARP is known to be an NP-hard problem. We present two lower-bounding methods, both based on the transportation model, in which we have been able to incorporate some of the side constraints. We also present a three-phase heuristic to generate a near-optimal solution from the solution obtained with the first lower-bounding method. For the relative gap between the heuristic solution value and its associated lower bound value we give a theoretical worst-case bound and computational experience obtained with a set of test problems. (C) 2000 Elsevier Science B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available