Name
Abstract | ||
|---|---|---|
This paper introduces a new algorithm, based on the concept of ejection chains, to effectively target vehicle routing problems with time window constraints (VRPTW). Ejection chains create powerful compound moves within Local Search algorithms. Their potential to yield state of the art algorithms has been validated for the traveling salesman problem (TSP), for example. We show how ejection chains can be used to tackle the more general VRPTW as well. The yardstick behind ejection chain procedures is the underlying reference structure; it is used to coordinate the moves that are available for the Local Search algorithm via a given set of transition rules. Our main contribution is the introduction of a new reference structure, generalizing reference structures previously suggested for the TSP. The new reference structure, together with a set of simple transition rules, is tailored to handle the asymmetric aspects in a VRPTW. We use Tabu Search for the generation of the ejection chains, and on a higher algorithmic level, the ejection chain process is embedded into an Iterated Local Search algorithm. Computational results confirm that this approach leads to very fast algorithms, showing that ejection chain algorithms have the potential to compete with state of the art algorithms for the VRPTW. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11546245_8 | Hybrid Metaheuristics |
Keywords | Field | DocType |
ejection chain algorithm,iterated local search algorithm,local search algorithm,general vrptw,ejection chain procedure,art algorithm,ejection chain,tabu search,vehicle routing,time windows,ejection chain process,new reference structure,publication | Mathematical optimization,Vehicle routing problem,Search algorithm,Algorithmics,Algorithm,Combinatorial optimization,Travelling salesman problem,Local search (optimization),Iterated local search,Mathematics,Tabu search | Conference |
Volume | ISSN | ISBN |
3636 | 0302-9743 | 3-540-28535-0 |
Citations | PageRank | References |
1 | 0.35 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Herman Sontrop | 1 | 1 | 0.35 |
| Pieter van der Horn | 2 | 3 | 0.73 |
| Marc Uetz | 3 | 456 | 43.99 |