Iterated local search for the multiple depot vehicle scheduling problem

TitreIterated local search for the multiple depot vehicle scheduling problem
Type de publicationArticle de revue
AuteurLaurent, Benoit, Hao, Jin-Kao
EditeurElsevier
TypeArticle scientifique dans une revue à comité de lecture
Année2009
LangueAnglais
Date2009/08
Numéro1
Pagination277 - 286
Volume57
Titre de la revueComputers & Industrial Engineering
ISSN0360-8352
Mots-clésConstraints satisfaction, iterated local search, multiple depot vehicle scheduling
Résumé en anglais

The multiple depot vehicle scheduling problem (MDVSP) is a well-known and important problem arising in public transport. Although many solution approaches have been published in the literature, algorithms using metaheuristics appeared only very recently (large neighborhood search and Tabu search). In this paper, we introduce an iterated local search algorithm for the MDVSP, incorporating a neighborhood schema called “block moves”, based on the notion of ejection chains. Using a set of benchmark instances, we show empirically that the proposed algorithm performs better than the best metaheuristics implemented so far and obtains high quality results within short computational times.

URL de la noticehttp://okina.univ-angers.fr/publications/ua4286
DOI10.1016/j.cie.2008.11.028
Lien vers le document

http://dx.doi.org/10.1016/j.cie.2008.11.028