A carregar...
Publicação
Lower-bounding and heuristic methods for a refuse collection vehicle routing problem
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 781.65 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
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 Arc 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.
Descrição
Palavras-chave
Routing Lower Bounds Heuristics
Contexto Educativo
Citação
Mourão, M. Cândida and M. Teresa Almeida. (2000). “Lower-bounding and heuristic methods for a refuse collection vehicle routing problem”. European Journal of Operational Research. Vol. 121, No. 2: pp. 420-434. (Search PDF in 2023).