A parallel VNS scheme with ILP neighbourhoods. Applications to industrial problems: Unit Commitment Problems and VRPTW

Dupin, Nicolas

Type de document :

Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes

Titre :

A parallel VNS scheme with ILP neighbourhoods. Applications to industrial problems: Unit Commitment Problems and VRPTW

Auteur(s) :

Dupin, Nicolas [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]

Titre de la manifestation scientifique :

ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision

Organisateur(s) de la manifestation scientifique :

Société française de recherche opérationnelle et d'aide à la décision

Ville :

Bordeaux

Pays :

France

Date de début de la manifestation scientifique :

2014-02-26

Mot(s)-clé(s) en anglais :

Vehivle Routing Problem with TIme Windows
Variable Neighbourhood Search
Matheuristics. Unit Commit Problem

Discipline(s) HAL :

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

Résumé en anglais : [en]

Integer Linear Programming (ILP) solvers made recent progress with heuristics based on the linear relaxation and variable fixing. On one hand, it allowes to cut off earlier branches of the Branch&Bound tree, and ...
Lire la suite >Integer Linear Programming (ILP) solvers made recent progress with heuristics based on the linear relaxation and variable fixing. On one hand, it allowes to cut off earlier branches of the Branch&Bound tree, and on an other hand, very good solutions are found quickly, that allowes to uses an ILP solver in a heuristic mode with a time limit. Most of the resolution time in a Branch& Bound algorithm is devoted to prove the optimality of the solution. Local search heuristics improve a given solution, with modification allowed in a defined neighbourhood. Difficulties come with local extrema, where no local improvement is possible. Variable Neighbourhood Search (VNS) basic idea is to consider different types of neighbourhoods, and to change systematicaly of neighbourhood within a local search, to have less local extrema. A VNS local extremum is thus is local extremum for all considered neighbourhoods. This paper shows how an ILP solver in a heuristic mode can be very useful and effective in a VNS scheme, considering for neighbourhoods small Integer Linear Programs. This algorithm can naturally be parallelized. These concepts are applied on short term Unit Commitment Problems with discrete dynamic constraints, long term scheduling of nuclear power plants and to the classical Vehicle Routing Problem with Time Windows. For these applications, solutions found with an ILP formulation in a defined time limit were imprioved with our VNS scheme.Lire moins >

Langue :

Français

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

A parallel VNS scheme with ILP neighbourhoods. ... BibTeX CSV Excel RIS

A parallel VNS scheme with ILP neighbourhoods. ...

BibTeX

CSV

Excel

RIS