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

Dupin, Nicolas

Document type :

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

Title :

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

Author(s) :

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

Conference title :

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

Conference organizers(s) :

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

City :

Bordeaux

Country :

France

Start date of the conference :

2014-02-26

English keyword(s) :

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

HAL domain(s) :

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

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

Language :

Français

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

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

A parallel VNS scheme with ILP neighbourhoods. ...

BibTeX

CSV

Excel

RIS