An efficient implementation of local search algorithms for constrained routing problems

M.W.P. Savelsbergh

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

60 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)75-85
TijdschriftEuropean Journal of Operational Research
Volume47
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 1990

Vingerafdruk

Duik in de onderzoeksthema's van 'An efficient implementation of local search algorithms for constrained routing problems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit