Transportation

Applications :
  • Vehicle routing
  • Waste collection
  • On-demand transportation
  • Railway transportation
Methods:
  • (Integer)linear programming
  • heuristics and metaheuristics
  • constraint programming
  • stochastic processes
  • game theory

Vehicle routing

In transportation research, our research activities have several applications such as waste collecting, on-demand passenger transportation and railway transportation.

We studied the dynamic aspects of waste collection linked to variations of waste quantities and to insertion of new collecting points (see figure). To limit the disruptions occurred in presence of new information, we defined a stability criterion for the routing of waste collection vehicles. We developed and evaluated different insertion methods extending standard vehicle routing algorithms.

For on-demand transportation, we designed column generation and local search methods to solve vehicle routing problems, optimizing various quality-of-service criteria. The proposed algorithms were embedded in a real reservation system.

We are also interested in solving general vehicle routing problems. We proposed exact and heuristic methods to solve vehicle routing problems with time-windows defined on a multigraph representing alternative routes. We also proposed new large neighbourhood search methods for generalized travelling salesman problems.

We study multiobjective vehicle routing problems and we propose new methods issued from multiobjective optimization adapted to this class of problems. A classification of existing problems in the literature was proposed and several problems illustrating the interest of such approaches were presented. These problems include load balancing between routes, accessibility to routes, etc. To face the new challenges brought by theses complex problems, we propose new methods such as adaptative memory principles coupled with parallelism, in a specific application to "rich" vehicle routing problems.

Contacts : Christian Artigues, Marie-José Huguet, Nicolas Jozefowiez, Pierre Lopez

PhD student : Frédérique Baniel, Fallou Gueye, Sébastien Lannez

Selected publications (see complete list on LAAS server) :

  • F.BANIEL, M.J.HUGUET, T.VIDAL, Evolution et réorganisation de la collecte des déchets ménagers et stabilité des tournées, Workshop International: Logistique et Transport 2007 (LT'2007), Sousse (Tunisie), 18-20 Novembre 2007, pp.25-30

  • B.BONTOUX, D.FEILLET, C.ARTIGUES, Large neighborhood search for variants of TSP, The Seventh Metaheuristics International Conference (MIC 2007), Montréal (Canada), 25-29 Juin 2007

  • T.GARAIX, C.ARTIGUES, D.FEILLET, D.JOSSELIN, Vehicle routing problems with alternative paths: an application to demand responsive transports Rapport LAAS N°06695, Octobre 2006

  • N. JOZEFOWIEZ, F. GLOVER, M. LAGUNA, Multi-objective meta-heuristics for the traveling salesman problem with profits, Journal of Mathematical Modelling an Algorithms, 7, 2008.

  • N. JOZEFOWIEZ, F. SEMET, E.-G. TALBI, Multi-objective vehicle routing problems,European Journal of Operational Research, Volume 189, Issue 2, 1 September 2008, Pages 293-309