2020-02497 - Post-Doctoral Research Visit F/M (BN 20) Generic Algorithms for Electric Vehicle Routing Problems
Le descriptif de l’offre ci-dessous est en Anglais

Type de contrat : CDD

Niveau de diplôme exigé : Thèse ou équivalent

Fonction : Post-Doctorant

A propos du centre ou de la direction fonctionnelle

Our aim is to develop tight formulations for combinatorial problems by combining the latest
reformulation techniques, such as Lagrangian and polyhedral approach, non-linear programming
tools and graph theoretics tools. Through industrial partnerships, the team targets large scale
problems such as those arising in logistics (routing problems), in planning and scheduling, in network
design and control, and in placement problems (cutting stock problems).

Contexte et atouts du poste

The work will be conducted in the Inria project-team ReAlOpt, in the building of Mathematics
Institute of Bordeaux (IMB). The team is specialised in developing tight formulations and algorithms
for combinatorial optimization problems exploiting the complementarity between the latest
reformulation techniques, such as Lagrangian and polyhedral approaches (the generation of columns
and cutting planes), and graph theoretic tools (for induced properties and implicit representations
of solutions). Our focus is on deterministic optimization approaches based on mathematical
programming, but our experience extends to stochastic programming, constraint programming, and graph
theory.

Mission confiée

Mixed Integer Linear Programming (MILP) is the most widespread approach for solving combinatorial
optimization problems. There exist many important problems which should necessarily be modelled
using MILP formulations with exponential number of variables in order to be solved in a reasonable
time. Existing MILP solvers implementing the Branch-and-Cut method are not capable of solving such
models. An alternative approach suitable for such formulations is Branch-Cut-and-Price
(BCP).

Recently an exact BCP solver has been proposed called VRPSolver, which
exploits the resource constrained path (RCP) structure, often encountered in combinatorial
optimization problems. Although this solver is less generic than existing MILP solvers, it still can
be used for solving a large variety of problems including vehicle routing and packing problems.
VRPSolver is much more efficient than MILP or other BCP solvers for such problems, and thus it can
solve instances of practically relevant size.

At the moment, VRPSolver can handle only trivial additive resources, which limits its modelling
capabilities. Many vehicle routing problems cannot be tackled using VRPSolver because of this
limitation, including the important class of electric vehicle routing problems.

The commercial adoption of electric vehicles requires routing optimization tools that address
charging decisions. Electric vehicle routing problems (eVRPs) introduce an interdependency between
resources (notably between the time spent charging and the battery's energy level) meaning that
tackling eVRPs using BCP involves managing infinitely non-dominated states in the subproblem. Linear
charging functions have been considered in, but there is still a lack of a
generic tool that takes more realistic charging functions (e.g., piecewise linear) into account.

Principales activités

The goal of the work is to extend capabilities of VRPSolver, by allowing the user to model and
solve a much larger class of problems, including electric vehicle routing problems. To achieve this
goal, three following topics should be addressed. 

  • One needs to design an interface for easily modelling various vehicle routing
    problems. This interface should include the possibility to specify resources with non-trivial
    resource extension functions, including functions whose values depend on the current
    resource consumption.
  • Most importantly, one needs to develop and implement a route generation (labeling) algorithm
    which is capable to take into account non-trivial resources mentioned above. Such algorithm
    should generalize algorithms known in the literature.
  • The implemented algorithm should be embedded into VRPSolver. Then, the latter should be tested
    on various electric vehicle routing benchmarks from the literature such as the eVRP with time
    windows, the eVRP with non linear charging functions and other variants.

Compétences

Background: Operations Research
Knowledge: Integer Linear Programming (required), Dynamic Programming (required),
Column Generation (optional), Vehicle Routing Problems (optional).
Skills: Significant experience with programming languages (required), C++ and/or Julia is a plus. 

Avantages

  • Subsidized meals
  • Partial reimbursement of public transport costs
  • Possibility of teleworking (after 6 months of employment) and flexible organization of working hours
  • Professional equipment available (videoconferencing, loan of computer equipment, etc.)
  • Social, cultural and sports events and activities
  • Access to vocational training
  • Social security coverage

Rémunération

2653€ / month (before taxs)