Optimisation de transport multimodal de personnes

Optimisation de transport multimodal de personnes

Profil Master universitaire en informatique ou en mathématique ou en sciences de l’ingénieur
Prérequis Connaissances de programmation objet (Java) et bases en fonctionnels (si possible scala)
Durée min 12 semaines, ampleur du travail modulée en fonction de la durée

Possibilité de stage de pôles (financement des déplacements)

Département: Algorithmique combinatoire ⊕

Expertises:

Algorithmique et Optimisation Combinatoire ⊕

Asset: Oscar.CBLS ⊕

Contact : Renaud De Landtsheer

Contexte

Le transport de personnes devient un enjeu de société grandissant avec la volonté de réduire la dépendance au carbone, l’augmentation des coûts du pétrole, l’apparition de l’uberisation des transports, etc.

Le CETIC développe depuis de longues années une technologie d’optimisation (OscaR.cbls), qui vise à traiter efficacement des problèmes de grande taille, et à supporter une grande flexibilité sur la définition des problèmes à optimiser. Oscar.cbls dispose notamment d’un très bon module d’optimisation de routage de véhicule. Il est actuellement possible par exemple de traiter des problèmes de voyageur de commerce avec mille nœuds quasi instantanément et de dix mille nœuds en un temps raisonnable. Voici par exemple, routage de véhicule à 1000 nœuds et 7 véhicules.

Objectif du stage

Le but de ce stage est de mettre oscar.cbls en œuvre pour résoudre un problème d’optimisation multimodal de transport de personnes :

Étant donné

  1. Des personnes souhaitant voyager d’une origine donnée à une destination donnée, avec une deadline sur l’heure d’arrivée
  2. Une flotte de véhicules, à capacité limitée (mettons 6 places passager)
  3. Des transports en commun (lignes de bus ou de train à heure fixe)

Trouver
- Les parcours des passagers et des véhicules qui permette de minimiser le coût global et de transporter chacun endéans ses contraintes de temps.
- Les passagers peuvent être déposés à un arrêt de bus/train, prendre un train/bus, et être rechargés par un autre taxi après son voyage en transport en commun.
- Les taxis peuvent faire des détours pour charger et décharger des passagers.
OscaR.CBLS

Structure du travail

  1. Étude de oscar.cbls, et des exemples de routage
  2. Étude du problème multimodal et des différentes procédures de recherche locale essayées
  3. Implémentation d’un solveur
  4. Benchmarks

Encadrement

Tout le travail sera encadré, mais nécessitera un minimum d’autonomie. Il s’agit d’un stage à forte connotation algorithmique, sur un outil Open Source en pleine expansion.

Références

- OscaR : https://bitbucket.org/oscarlib/oscar/wiki/Home
- Scala : http://www.scala-lang.org

Contact : Renaud De Landtsheer