An efficient implementation of local search algorithms for constrained routing problems

M.W.P. Savelsbergh

Research output: Contribution to journalArticleAcademicpeer-review

58 Citations (Scopus)
1 Downloads (Pure)

Abstract

We investigate the implementation of local search algorithms for routing problems with various side constraints such as time windows on vertices and precedence relations between vertices. The algorithms are based on the k-exchange concept. In the case of unconstrained routing problems, a single k-exchange can obviously be processed in constant time. In the presence of side constraints feasibility problems arise. Testing the feasibility of a single solution requires an amount of time that is linear in the number of vertices. We show how this effort can, on the average, still be reduced to a constant.
Original languageEnglish
Pages (from-to)75-85
JournalEuropean Journal of Operational Research
Volume47
Issue number1
DOIs
Publication statusPublished - 1990

Fingerprint Dive into the research topics of 'An efficient implementation of local search algorithms for constrained routing problems'. Together they form a unique fingerprint.

  • Cite this