Matheuristics to stabilize column generation: application to a technician routing problem

Dupin, Nicolas; Parize, Rémi; Talbi, El-Ghazali

Type de document :

Communication dans un congrès avec actes

Titre :

Matheuristics to stabilize column generation: application to a technician routing problem

Auteur(s) :

Dupin, Nicolas [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Parize, Rémi [Auteur]
Unknown Labs [Inria]
Talbi, El-Ghazali [Auteur]

Optimisation de grande taille et calcul large échelle [BONUS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Université de Lille

Titre de la manifestation scientifique :

7th International Workshop Matheuristics

Ville :

Tours

Pays :

France

Date de début de la manifestation scientifique :

2018-06-18

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

This paper considers a simplified Technician Routing and Scheduling Problem with skill constraints, where a Column Generation (CG) heuristic was shown effective. This work proposes new CG schemes to stabilize the CG process ...
Lire la suite >This paper considers a simplified Technician Routing and Scheduling Problem with skill constraints, where a Column Generation (CG) heuristic was shown effective. This work proposes new CG schemes to stabilize the CG process and thus to accelerate the CG heuristics. Solving CG subproblems with matheuristics allows to diversify the column generation. Furthermore, a tabu search matheuristic allows to generate aggressively columns at each iteration. Both techniques imply a better stability of the CG scheme: the diversification is interesting for the first iterations whereas tabu intensification is especially useful for the last iterations. It implies a significant acceleration of the CG convergence. A perspective of these CG strategies proposed is an extension to other problems where CG induces independent and heterogeneous subprob-lems.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.archives-ouvertes.fr/hal-02304958/document
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-02304958/document
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-02304958/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

Matheuristic_GC_TRS.pdf
Accès libre
Accéder au document

Matheuristics to stabilize column generation: ... BibTeX CSV Excel RIS

Fichiers

Matheuristics to stabilize column generation: ...

BibTeX

CSV

Excel

RIS