Localization : LIMOS, Clermont-Ferrand (France)
Title : Hybridization of methods Of Machine Learning
and Operation Resarch for scheduling and routing problems
PhD Advisors: JP Gayon, Ph. Lacomme, N. Tchernev,
Candidate skill:
Graduated from a school or a master
Basic training in Opitmization (including linear programming, scheduling, routing, graph
theory)
Correct level in programming (C, …)
Basic knowledge of Python
Description of research work:
The subject focuses on transportation problem in multi-configuration workshops with the
objective to tackle the fleet of vehicles efficiently. A configuration can be defined at a skim
that defined the operation duration and one operation is the processing of one job on a
machine, with a duration that depends on the resource assignment.
During the research, different resolution schemes could be investigated including but not
limited to linear programming, constraint programming and any methods of Artificial
Intelligence that could be of interest for solving.
The sub-problems could include:
Management of configuraiton ;
The quality of service as an extension of the famous work of Cordeau et Laporte (2003),
considring extra delay between loading and unloasing operation..
The management of vehicle recharging periods (modelized by break) with constraint that
are extensions of maximal time lags, and partially splitted breaks as defined in the legal
constraint of the transport.
The transportation time variation depending on the access time to routes which could
required a new definition of shortest time where the arc cost could be time dependant.
The transportation problem falls into the family of DARP problems (or Pick-Up and Delivery
problems) and by consequence a solution is an ordered sequence of loaded and unloaded
transport operation.
The originality of the resolution procedures should be based on the connection with elements
of the Artificial Intelligence type. The objective may be to understand how a priori knowledge
can guide algorithms and how to acquire and store this knowledge. The latest major
advances in SAT-type PPC solvers are pushing in this direction
Currently few researchers have reached significant results and mainly concern routing
problems. There are few publications and the major ones are the Kenneth Sorensen's
researches.
The reference article is that published in 2019 in the journal Computers and Operations
Research.
Florian Arnold and Kenneth Sörensen. What makes a VRP solution good? The generation of problem-specific knowledge for heuristics, Computers & Operations Research Volume 106, June 2019, Pages280-288
But we can also cite:
Gianluca Costa, Maxence Delorme, Manuel Iori, Enrico Malaguti, Silvano Martello. Training software for orthogonal packing problems. Computers & Industrial Engineering Volume 111, September 2017,
Pages 139-147
B. Dalmas, D. Lamy, A. Laurent, V. Clerc."An optimization and pattern mining based approach for solving the RCPSP". In Proceedings of the 13th Metaheuristics International Conference (MIC 2019).
From an Artificial Intelligence point of view, the scientific and technical obstacles to overcome are as follows:
Characterize the differences between quality solutions and poor quality solutions by
analyzing the structure of the solutions or more precisely the structure of the objects
coding the solution. For a scientific point of view, the problem is to analyze and to
understand the relation between the data of the problem (processing time ....) and the
vectors giving, after decoding, a high quality solution. This probably involves doing post-
mortem analyzes of the solutions evaluated during the resolution, and then defining a
powerful algorithmic approach to investigate parallel execution to proposed an algorithm
that not impact the computation time of an iteration.
Dynamically, during the optimization process, identify the information allowing to define a
local search taking advantage of global information. The notion of global information could
be defined as a set of patterns to be favored at a given time while integrating the fact that
these patterns are partial information based only on the first iterations of the method.
The technical difficulty then consists in impacting the speed of convergence without falling
prematurely into local minima.
Definition of mechanisms for dynamic adaptation of local research movements in the
trend of (Thevenin et al., 2019) with the notion of LVNS (Learning Variable Neighborhood
Search). The basic approaches could take advantage of dynamic probabilities of
executing a specific (Chassaing et al., 2016) and to dynamically update these
probabilities.
Define mechanisms to analyze a priori the structure of a coding element and classify it
(without carrying out its evaluation) possibly as not promising and thus avoid costly and
unnecessary evaluations. Preliminary work presented in conference by D. Vigo is based
on neural networks. Here we plan to study regression mechanisms, neural networks and
possibly extend the concept of convolution.
To candidate, constact:
Jean-Philippe Gayon – 04 76 57 47 46 – Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Philippe Lacomme – 04 73 40 75 85 – Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Nijolay Tchernev – 04 73 40 77 71 – Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
