Localisation d'un centre de distribution

OS11

Mini-projet 1 : Localisation d’un centre de distribution

Sujet

Le but de ce projet est de maîtriser la modélisation et la résolution d’un problème de localisation dans la grande distribution. Il s’agit de la localisation d’un centre de distribution pour servir un ensemble de magasins géographiquement dispersés. L’objectif du problème peut être : 1) minimiser la somme des distances du centre de distribution aux magasins ; 2) ou bien minimiser le coût total de transport du centre aux magasins. On suppose que la demande annuelle de chaque magasin soit donnée et que ce coût total soit évalué à la somme de ces distances pondérées par les demandes correspondantes.

1) Modéliser le problème de localisation du centre de distribution dans les deux cas mentionnés ci-dessus.

2) Résoudre le problème dans les deux cas par un solveur commercial ou par un algorithme développé et programmé par vous-même.

C’est à votre choix de traiter ce problème comme un problème de localisation continue dans lequel chaque magasin ou le centre de distribution peut se trouver à tout point dans un carré, ou bien un problème de localisation discrète dans lequel les magasins et le centre de distribution ne se trouvent qu’à un ensemble fini de points dans le carré.

Consignes

Le projet sera fait en binôme (en groupes de deux étudiants). Les données du problème seront envoyées plus tard à chaque binôme. Vous pouvez utiliser n'importe quel outil d’optimisation ou langage de programmation (Excel, C++, Visual Basic, Matlab, CPLEX, etc.) pour résoudre le problème concerné. Il faut nous rendre un petit rapport en Word ou PDF en 2-5 pages par e-mail avant l'examen final d’OS11. Ce rapport doit contenir une description des modèles et d’un éventuel algorithme de résolution, les codes-sources des modèles et/ou de l’algorithme, et les solutions du problème dans les deux cas. De plus, chaque étudiant dans un groupe est demandé de résoudre le problème dans l’un des deux cas individuellement, vous devez donc préciser l’auteur de chaque solution dans le rapport.

OS11

Mini-projet 2 : Heuristique de balayage pour le VRP

Sujet

Le but est de programmer l'heuristique "sweep" pour le VRP. Pour simplifier on considère des hélicoptères qui se déplacent en ligne droite. On suppose qu'on a les coordonnées x0 et y0 du dépôt et celles xi et yi de chaque client (i = 1, 2, …, n). On connait aussi les demandes qi des clients et la capacité Q des véhicules. Le nombre de véhicules est largement suffisant.

L'heuristique détermine des groupes de clients (secteurs angulaires) compatibles avec la capacité des véhicules puis résout un TSP pour chaque groupe. Pour déterminer les groupes, on crée une demi-droite qui part du dépôt et passe par un client quelconque, puis on fait tourner cette demi-droite dans un sens choisi (sens trigonométrique

...