Optimisation du routage de vélo pour livraison de colis

Optimisation du routage de vélo pour livraison de colis

Profil Master universitaire, typiquement en informatique ou physique ou ingénierie
Prérequis Connaissances de base en programmation. Il est souhaitable d’avoir un minimum de connaissance en physique de base (puissance, énergie, pente, accélération, masse). Des connaissances supplémentaires en sport vélo et/ou physiologie (puissance de pédalage, éventuellement modèles de fatigue) sont un atout, mais peuvent être étudiés au début du stage.
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 stage vise à développer un algorithme qui calcule le trajet que doit suivre un livreur à vélo pour transporter des colis.

Ce sujet de stage est lié à l’émergence de quatre tendances

  • Il y a dans nos sociétés une prise de conscience de l’impact négatif des transports de produit en véhicule à pétrole, et un recours accru au transport à vélo, y compris pour le transport de colis
  • Le commerce ligne est en croissance, ce qui augmente le besoin de transport de colis ; le problème du transport de colis inclus ; le transport à vélo constitue un moyen de transport intéressant qui pourrait s’intégrer dans la logistique de l’e-commerce
  • Les embouteillages ainsi que la difficulté du parking font du vélo une alternative crédible au à la voiture pour le transport de petits colis.

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, tel des problèmes de routage de véhicule ou voyageur de commerce. 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 noeuds et 7 véhicules :

Objectif

Le but de ce stage est de proposer un algorithme d’optimisation des trajets à vélo pour effectuer un maximum de transport de colis en un temps imparti, et en tenant compte de la fatigue du cycliste et/ou de l’autonomie de sa batterie si le vélo est électrique.

Il faudra par exemple en prendre en compte

  • Le payload constitué par les colis présents dans le vélo
  • Le profil des trajets (montées/descentes, feux rouges) et leur impact sur la puissance à fournir pour faire avancer le vélo
  • Puissance de pédalage maximale et en endurance
  • La fatigue du cycliste
  • La vitesse du vélo, pour estimer les temps de trajet
  • Autonomie de batterie dans le cas de vélos électriques

Structure du travail

  1. Etude du contexte : le métier du livreur à vélo, modélisation de la fatigue et des performances à vélo
  2. Formulation du problème d’optimisation
  3. Étude d’OscaR.cbls
  4. Élaboration d’une solution au problème de routage sur base d’OscaR.cbls, avec démonstrateur graphique

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