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

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

Document type :

Communication dans un congrès avec actes

Title :

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

Author(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

Conference title :

7th International Workshop Matheuristics

City :

Tours

Country :

France

Start date of the conference :

2018-06-18

HAL domain(s) :

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

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

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

Source :

Harvested from HAL

Files

https://hal.archives-ouvertes.fr/hal-02304958/document
Open access
Access the document

https://hal.archives-ouvertes.fr/hal-02304958/document
Open access
Access the document

https://hal.archives-ouvertes.fr/hal-02304958/document
Open access
Access the document

document
Open access
Access the document

Matheuristic_GC_TRS.pdf
Open access
Access the document

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

Files

Matheuristics to stabilize column generation: ...

BibTeX

CSV

Excel

RIS