Scientific Program > Talks by Speaker > Vinot Marina

Optimal resolution of the transport problem from a flow into a RCPSP with routing
Philippe Lacomme  1, *@  , Aziz Moukrim  2, *@  , Alain Quilliot  1, *@  , Marina Vinot  1, *@  
1 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes  (LIMOS)  -  Website
Institut Français de Mécanique Avancée, Université Blaise Pascal - Clermont-Ferrand II, Université d'Auvergne - Clermont-Ferrand I, CNRS : UMR6158
Bât ISIMA Campus des Cézeaux BP 10025 63173 AUBIERE cedex -  France
2 : Heuristique et Diagnostic des Systèmes Complexes  (HEUDIASYC)
CNRS : UMR7253, Université de Technologie de Compiègne
Université de Technologie de Compiègne - Centre de Recherches de Royallieu - rue Roger Couttolenc - CS 60319 - 60203 COMPIEGNE cedex -  France
* : Corresponding author

The problem consists in defining a solution of the RCPSPR (Resource-Constrained Project Scheduling Problem (RCPSP) with Routing), considering both the scheduling and the routing addressing the transportation of resources between activities. The scheduling sub-problem can be solved considering the flow between activities to define the precedence constraints between activities and also the location of the transport operation. Commonly, disjunctive graphs have been tuned to model simultaneously both scheduling operations and transport operations addressing the proper coordination between transport operations and scheduling operations. Definition of a solution requires: 1) definition of assignment of vehicle to transport operation; 2) definition of disjunctions between transport operations assigned to the same vehicle; 3) computation of the earliest starting time of both scheduling and transport operation with a longest path algorithm.

This approach falls into the set of indirect resolution scheme but not falls into the category of split approaches. The contribution consists in the definition of an exact algorithm to solve optimally the routing problem considering a flow between activities. Such approach is the first step to define an indirect based resolution scheme where a local search and a metaheuristic could be based on the investigation of the search space defined only by the flow between activities. Our experiments carried out on 18 instances proved the method is strongly efficient.


Online user: 2 RSS Feed