Comparing descent heuristics and metaheuristics for the vehicle routing problem |
| |
| Affiliation: | 1. Faculdade de Economia da Universidade do Porto, C/O Jorge Valente, Rua Dr. Roberto Frias, s/n, 4200-464 Porto, Portugal;2. LIAAD – INESCTEC LA, Faculdade de Economia da Universidade do Porto, Rua Dr. Roberto Frias, s/n, 4200-464 Porto, Portugal;3. Department of Business Administration, Eastern Connecticut State University, 83 Windham St., Willimantic, CT 06226-2295, USA;1. Grupo da Causa Humana, Ouro Preto, Brazil;2. Instituto de Pesquisa e Desenvolvimento de Tecnologias, Ouro Preto, MG, Brazil;3. Graduate Program in Electrical Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil;4. Department of Computer Science, Universidade do Estado do Rio de Janeiro, RJ, Brazil;5. Department of Automatic Control and Systems Engineering, University of Sheffield, Sheffield, UK;6. Department of Electrical Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil;7. Department of Information and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain;8. Department of Economics and Business, Universitat Pompeu Fabra, Barcelona, Spain;9. Department of Computer Science, Universidade Federal de Ouro Preto, Ouro Preto, MG, Brazil;10. Cité Scientifique, University Lille 1, Lille, France;11. INRIA Lille - Nord Europe Parc Scientifique de la Haute Borne 40, Avenue Halley, Bat A, France;12. Computer Science Laboratory of Paris, Université Pierre et Marie Curie, Paris, France;1. University of Valencia, Department of Statistics and Operations Research, Burjassot, Valencia, Spain;2. Polytechnic University of Valencia, Department of Applied Statistics and Operations Research, and Quality, Valencia, Spain;1. Faculdade de Economia da Universidade do Porto, Rua Dr. Roberto Frias, s/n, 4200-464 Porto, Portugal;2. LIAAD – INESC TEC, Faculdade de Economia da Universidade do Porto, Rua Dr. Roberto Frias, s/n, 4200-464 Porto, Portugal;3. Department of Business Administration, Eastern Connecticut State University, 83 Windham St., Willimantic, CT 06226-2295, USA |
| |
| Abstract: | Three improvement heuristics for the vehicle routing problem are considered: a descent heuristic and two metaheuristics Simulated Annealing and Tabu Search. In order to make an in-depth comparison of the performance of these improvement heuristics, their behavior is analyzed on a heuristic, time-sensitive level as well as on a parametric level. The design and the results of the experiments are outlined. The external validity of the conclusions is discussed.Scope and purposeTabu Search (TS) and Simulated Annealing (SA) have demonstrated to be appropriate metaheuristics for solving NP-hard combinatorial optimization problems, such as the vehicle routing problem with side-constraints. In order to compare the performances of both metaheuristics with each other and with a traditional descent implementation, a comparison of the best solution independent of computing times is fundamentally wrong because metaheuristics have no unambiguous stopping criteria, as opposed to traditional descent implementations. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
