Drone Delivery Solver

Description du projet

Ce projet vise à optimiser la livraison de colis par une flotte de drones dans une ville de taille moyenne, en l’occurrence Grenoble, en France. L’objectif principal est de minimiser le temps total de livraison.

Pour cela, plusieurs approches ont été testées, 2 méthodes en livraisons diférrées (prendre toutes les commandes d’une journée et les livrer le lendemain de façon optimisé) et 1 en temps réel (dès qu’une commande est faite, l’algorithme doit réagir et effectuer la livraison, les commandes ne sont donc pas connues en avance dans cette approche).

Vidéo de présentation du projet

Méthodes d’optimisation utilisées

  1. Solveur Exact avec GLPK : Utilisation du solveur GNU Linear Programming Kit (GLPK) pour obtenir une solution optimale, bien que cette méthode soit gourmande en ressources pour de grands ensembles de données.
  2. Recuit Simulé : Implémentation d’une méthode de recuit simulé, technique stochastique qui fournit des solutions quasi-optimales avec une meilleure efficacité en ressources.
  3. Application Multi-Agents en SARL : Développement d’une application multi-agents en SARL pour modéliser le comportement des drones et simuler la livraison. Cette approche offre une adaptabilité et une dynamique dans l’environnement de livraison.

Données d’entrée

Pour plus de réalisme, le test du programme a été fait sur une ville basé sur une ville réel (Grenoble dans notre cas), des données de l’INSEE décrivant entre autre le nombre de ménage par carré de 300m x 300m sur toutes la france. On a pris les données correspondant à la ville de Grenoble a laquelle on a appliqué une facteur pour faire une modélisation plus simpliste.
Nous avons également générer des heures de commandes de façon réaliste. Pour cela nous avons eu accès au nombre de commande par heure en moyenne en France et par interpolation on déduit la probablité d’un colis chaque minute.

Technologies et bibliothèques

  • Solveur Exact : GLPK et GNU MathProg pour la modélisation
  • Recuit Simulé : Python avec numpy pour les opérations matricielles, matplotlib et Tkinter pour la visualisation, et pandas pour l’analyse de données
  • SARL : Utilisation de SARL dans un projet Maven pour une simulation sur la plateforme Janus
Rapport détaillé