Prog-Info > Projets > Problème de ramassage dans une ville virtuelle.

---

Problème de ramassage dans une
ville virtuelle

Introduction
Description
Screenshots
Demonstration
Documentation
Téléchargements

Introduction

Les villes virtuelles sont souvent dépourvues d'animations de flottes de véhicules et de comportements liés aux activités de ramassage, de transport et de distribution. Ces activités posent un problème identique d'optimisation de tournées, par exemples :

• la distribution du courrier, du lait,
• le ramassage des ordures,
• le déneigement des routes,
• le ramassage de supporters pour une rencontre sportive ou
• le ramassage scolaire.

Les objectifs sont les suivants :

• Faire une étude des métaheuristiques (algorithme génétique, recherche tabou, colonie de fourmis, ...) utilisées pour résoudre ce genre de problème.
• Implanter une ou plusieurs méthode(s).
• Réaliser une visualisation 2D ou 3D.

Top

Description

Ce projet de TER (Travaux détudes et de recherches) s'inscrit dans le cadre du projet Dynaspat gérant notamment les problèmes de calculs d'itinéraires liés à un territoire.

Le but de ce TER est de modéliser une ville virtuelle et d'y inclure une flotte de véhicules liée à diverses activités de ramassage, de distribution et de transport.

L'application JAVA qui a été développée permet de calculer des tournées de ces véhicules pour des activités de ramassage à l'aide de l'algorithme génétique. Les algorithmes génétique sont des algorithmes d'optimisation stochastique fondés sur les mécanismes de la sélection naturelle et de la génétique (Théorie de l'évolution de C.Darwin)qui permettent la recherche d'un solution à un probléme.

Les différents types d'algorithmes génétiques qui ont été implémentés sont les suivants :

• GGA (Grouping Genetic Algorithm),
• SSGA (Steady State Genetic Algorithm),
• AI (Algorithme incrémental).

Les différentes méthodes de sélection qui on été implémentées sont :

• La roulette,
• La sélection par tournnois,
• La sélection par rang,
• L'ellitisme.

Les différentes méthodes de croisement qui on été implémentées sont :

• LOX (Linear Order Crossover),
• OX (Order Crossover),
• X1 (croisement à un point de coupure).

Les différentes méthodes de mutation qui on été implémentées sont :

• Move,
• Swap,
• RL (recherche locale).

Pour de plus amples informations, vous pouvez consulter le document de spécification et le document de conception algorithmique.

Le logiciel dispose d'une interface graphique permettant à tout utilisateur d'utiliser simplement le logiciel et permet de visualiser en 2D le résultat obtenu : tournées des véicules précédemment calculées dans une ville virtuelle.

Une ville est constituée d'intersections, de voiries et d'un dépôt.
Les différents types d'intersections qui sont gérées sont les carrefours (impossible de faire demi tour), les rond-points et les impasses.
Les différents types de voiries sont les petits axes et les grands axes. Les deux côtés d'un petit axe sont ramassé en une sule fois alors que pour un grand axe, il faut deux passages.
Il est aussi possible de gérer les interdictions de tourner, les sens interdits, ...

Les principales fonctionnalités de l'interface graphique sont les suivantes :

• Lecture et enregistrement de fichiers ville (XML),
• Editeur de ville (Ajout, Modification, Suppression d'éléments et gestion d'interdictions)
• Sélection d'éléments de la ville,
• Affichage d'informations sur la ville et ses éléments,
• Zoom et Translations,
• Paramétrage du moteur 2D,
• Paramétrage de l'algorithme génétique,
• Chargement de solutions (liste de tournées)
• Animation d'une flotte de véhicules,
• Outil de statitiques,
• Manuel.

Pour de plus amples informations, vous pouvez consulter le document de conception générale et le document de conception de visualisation.

Top

Screenshots

Editeur1 | Editeur2 | Editeur3 | Moteur Graphique1 | Moteur Graphique2 | Algorithme Génétique | Animation1 | Statitiques1 | Statitiques2.

Top

Demonstration

Animation flash de 25 secondes montrant le résultat final.
Si vous n'avez pas Flash cliquez ici.

Top

Documentation

      crr
      modeles
      presentations
      Conception_algo.doc
      Conception_generale.doc
      Conception_Visu2D.doc
      Conv_numerotation.doc
      crr.doc
      Glossaire.doc
      Liste_Des_Documents.doc
      Plan_Qualite.doc
      Ressources.doc
      Specification.doc
      Sujet_Du_TER.doc
      Test_integration.doc
      Test_Validation.doc

Top

Téléchargements

Le projet en entier. (application, sources, docs, tutoriaux) (zip) [9.2 Mo]
L'application seule. (zip) [734 Ko]

Code source de l'application : (cliquable)
Dossier aide :
modules.htm, sommaire.htm, introduction.htm, editeur.htm, style.css, apropos.htm, animation.htm, algorithme.htm, generalites.htm, moteur_graphique.htm
Dossier instances
VilleTest.xml, best5B.sol, villeInstance3C.xml, best1B.sol, villeInstance4A.xml, villeInstances4-C.xml, bestvilleTestIntegration.sol, villeTestRouteBarree.xml, villeInstance2B.xml, villeTestIntegration.xml, best4C.sol, best4D.sol, bests4-C.sol, ville.dtd, best3A.sol, villeInstanceGDB15e.xml, best1C.sol, bestville2.sol, villeInstance1APetiteFlotte.xml, villeInstance3B.xml, best1APetiteFlotte.sol, best5C.sol, best5D.sol, best2A.sol, villeInstance1A.xml, best4B.sol, villeInstance2C.xml, villeTestClone.xml, ville2.xml, VilleDeLag.xml, villeInstance5A.xml, best3C.sol, best4A.sol, villeInstance1B.xml, villeDistancier.xml, ville1.xml, villeInstance5B.xml, villeInstance4D.xml, villeInstance4C.xml, villeInstance3A.xml, bestville1.sol, best2B.sol, villeInstance5D.xml, villeInstance5C.xml, villeInstance2A.xml, villeInstance1C.xml, best3B.sol, best2C.sol, best5A.sol, bestGDB15e.sol, villeInstance4B.xml, best1A.sol
Package algo_genetique
ParametreAG.java, Couple.java, Chromosome.java, Genome.java, Gene.java, Resolution.java, GenomeList.java, GeneList.java, Distancier.java, Population.java
Package ihm
MainFrame.java
Package ihm.actions
ActionQuitter.java, XMLFilter.java, ActionNouvelleVille.java, ActionAPropos.java, ActionOuvrirVille.java, ActionEnregistrerVille.java, ActionManuel.java
Package ihm.algo
Style.java, AlgoFrame.java, ParamAGPane.java
Package ihm.composant
JTextFieldEA.java, JMenuItemEA.java, JCheckBoxEA.java, JComboBoxEA.java, TitledBorderEA.java, JCheckBoxMenuItemEA.java, JMenuEA.java, JRadioButtonMenuItemEA.java, JRadioButtonEA.java, JLabelEAPar.java, JLabelEAPres.java
Package ihm.controle
TexteNbIndividu.java, TexteNbAmeliorations.java, SliderCroisement.java, SliderMutation.java, TexteNbOverlap.java, TexteNbGeneration.java
Package ihm.menu
MenuVisu2D.java, MenuEditeur.java, MenuFichier.java, Outils2D.java, MenuAnimation.java, MenuModules.java, MenuAG.java, MenuAide.java
Package structure
Solution.java, Intersection.java, Ville.java, Tournee.java, Constants.java, Voirie.java, Vehicule.java, Depot.java
Package structure.xml
VilleReader.java, VilleSource.java, GestionnaireDeVille.java
Package test
TestStructure.java, TestPrincipal.java, Fabrique.java
Package test.ag
TestEvolution.java, TestAlgoChro.java, TestSelection.java, TestClone.java, TestMutation.java, TestInitialisation.java, TestCroisement.java, TestFitness.java, TestAG.java, TestDistancier.java, TestMutationCroisement.java, TestCopie.java
Package test.visu
TestVisu2D.java, TestEnregistrementVille.java, TestAnimation.java, TestVisu2DLag.java
Package visualisation2D
Polygon2.java
Package visualisation2D.actions.algo
ActionVisibilite.java, ActionPauserAlgo.java, ActionLancerAG.java
Package visualisation2D.actions.animation
ActionRalentirAnimation.java, ActionAccelererAnimation.java, ActionArreterAnimation.java, ActionChargerSolution.java, ActionDemarrerAnimation.java, ActionPauserAnimation.java
Package visualisation2D.actions.editeur
ActionSupprimer.java, Selection.java, ActionGrille.java, ActionModifier.java, ChoixAjout.java, ActionAjouter.java, ActionInterdictions.java
Package visualisation2D.actions.infos
InfosMoteur2D.java, InfosVoirie.java, MenuContextuelEntite.java, MenuContextuelVille.java, InfosInterdictions.java, InfosVille.java, ActionVille.java, InfosVehicule.java, InfosIntersection.java, ActionEntite.java
Package visualisation2D.actions.moteur
ActionChangerMode.java, ActionOrigine.java, ActionTranslaterH.java, ActionTranslaterD.java, ActionZoomMoins.java, ActionTranslaterB.java, ActionTranslaterG.java, ActionZoomPlus.java, ActionParamMoteur2D.java
Package visualisation2D.actions.stats
ActionStats.java
Package visualisation2D.ecouteurs
StatsMouseMotionListener.java, VilleMouseWheelListener.java, VilleMouseListener.java, VilleMouseMotionListener.java, VilleKeyListener.java, EcouteurMenuEntite.java
Package visualisation2D.entites
Impasse.java, RondPoint.java, Entite.java, GrandAxe.java, Camion.java, Carrefour.java, PetitAxe.java, Entrepot.java
Package visualisation2D.moteur
Mode.java, Animation.java, DessinerVille.java, Translation.java, Zoom.java, Echelle.java, ThreadDepot.java, Grille.java, Convertisseur.java
Package visualisation2D.stats
Statistiques.java

Top