PresentationStage IdrissHASSINE .pdf


À propos / Télécharger Aperçu
Nom original: PresentationStage_IdrissHASSINE.pdf

Ce document au format PDF 1.4 a été généré par Online2PDF.com, et a été envoyé sur fichier-pdf.fr le 27/10/2015 à 17:26, depuis l'adresse IP 194.57.x.x. La présente page de téléchargement du fichier a été vue 413 fois.
Taille du document: 2.8 Mo (46 pages).
Confidentialité: fichier public


Aperçu du document


CIMO : un calculateur exact d'itinéraires
multimodaux trans-territoires basé sur un
algorithme de programmation dynamique Cut and
Price and Share multi-objectifs et multi-contraintes
terrain

Réalisé par:
 Idriss HASSINE
idriss.hassine.2015@ieee.org

Vendredi 10 Avril 2015

Encadré par :
 M. Philippe CANALDA
philippe.canalda@femto-st.fr

Sommaire

2/ 46

Introduction

Nous nous déplaçons pour travailler, étudier, faire des
courses …
Être à l’heure à un rendez vous très important .

Pour répondre à ce besoin de mobilité, on a recours à
plusieurs modes de transport.
Nécessité d’un système qui permet de gérer ces modes.

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
3/ 46

Génèse du projet)

Ligne
bus

Horaire
passage

2

6h00

2

6h15

2

6h30

2

7h00

2

7h15

2

7h30

2

7h45

2

8h00

2

8h15

Origine

Ligne
bus

 Examples of application

Fenêtre
de temps
6h-8h30

Horaire
passage

4

6h00

2

6h15

4

6h30

2

6h45

4

7h00

2

7h15

2

7h30

2

7h45

4

8h00

2

8h15

Destination

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
4/ 46

Génèse du projet)

Fournir une forme de solutions d’itinéraires permettant de comprendre :


les montées descentes,



les correspondances et les temps d’attente,



les différentes modalités,



les alternatives de passage,



le temps global de transport, …

Cette forme de solutions d’itinéraires doit :


prendre en considération l’origine et la destination,



prendre en considération le départ au plus tôt et l'arrivée au plus tard, ce qui constitue
la fenêtre de temps de la demande de transport,



Minimiser les montées descentes, les correspondances et les temps d’attente, le temps
global de transport, …



satisfaire les contraintes,

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
5/ 46

Problématique
Besoin d’une solution qui :


fournit une liste d’itinéraires possibles pour un voyageur qui doit spécifier sa station de départ et
celle d’arrivée, ainsi que son horaire de départ et l’horaire d’arrivée souhaité .



est capable de gérer toutes les modalités,



qui couvre une zone géographique de tailles croissantes (réseaux (données), acteurs),



Accède à l’information rapidement et réactivement à partir de plusieurs systèmes d’informations ,



Rafraîchit l’information dynamiquement.
(Dynamisme= le rafraichissement + La réactivité)
 Examples of application



gère la complexité :



AOTs, opérateurs,



les services innovants transports déclenchés, transports dynamiques, accès parkings, …



nécessité d’interactions.

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
6/ 46

Problématique
PROBLÈME

MÉTRIQUES

Problème de calcul des itinéraires

Temps effectif de transport

Problème de planification des voyages

Temps de trajet
Nombre de correspondances

ENTRÉES &

Temps d’attentes aux
correspondances, etc…

SORTIES
Origine
Destination

Horaire de départ souhaité
(oraire d’arrivée au plus tard
Profile et préférence de l’usager
Liste d’itinéraire s

DONNÉES
tableau d’horaires statique / dynamique
fenêtres de temps
l’ensemble des lignes de toutes les modalités

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
7/ 46

Les méthodes de résolution
exactes


Exemples







Les Heuristiques

La méthode séparation et
évaluation (Branch and Bound)
La méthode de coupes planes
(Cutting-Plane)
La méthode (Branch and Cut)
La méthode de génération de
colonnes



Garantie de trouver la solution
optimale




Avantages



Les Métaheuristiques

Méthodes constructives qui génèrent des
solutions à partir d’une solution initiale en
essayant d’en ajouter petit à petit des
éléments jusqu’à ce qu’une solution complète
soit obtenue
Méthodes de fouilles locales qui démarrent
avec une solution initialement complète
(probablement moins intéressante), et de
manière répétitive essaie d’améliorer cette
solution en explorant son voisinage.
Temps de réponse polynomiale
Une solution rapide














Temps de calculs énorme

Inconvénients




Une solution pas obligatoirement optimale
Tomber sur un minimal local et le considérer
comme minimum global





Exemples
Applications




Le problème du voyageur de
commerce
Les problèmes d’optimisation
combinatoire (POC) qui se
formulent sous la forme d’un
programme linéaire





Le recuit simulé (simulated annealing)
La recherche Tabou (Tabu Search)
Les algorithmes génétiques
Les algorithmes de colonies de fourmis
L’optimisation par essaim de particules

Solution réalisable de bonne qualité
Une solution rapide
Algorithme plus complet et complexe
qu'une simple heuristique
Un bon rapport entre le temps d’exécution
et la qualité de la solution
Démarrer par un processus d’initialisation
aléatoire
Tomber sur une mauvaise initialisation au
début
Nombreux tests sont nécessaires pour
trouver les bon paramètres
le problème du voyageur de commerce
le problème d’ordonnancement,
Le problème de tournées de véhicules, etc

Ce travail de comparaison a été effectué grâce au référence suivant :SIDI MOAMED DOUIRI, SOUAD ELBERNOUSSI, HALIMA LAKHBAB Cours des méthodes de résolution exactes heuristiques et méta heuristiques
Université MOHAMED V,
Faculté des sciences de Rabat Laboratoire de Recherche Mathématiques, Informatique et Applications

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
8/ 46

Solution existantes
Contexte statique

3. Solutions
•J.Q. Li, K. Zhou, L.existantes
Zhang, L. and W.-B. Zhang. A Multimodal Trip Planning System Incorporating the Park-and-Ride Mode and RealTime Traffic and Transit Information,

•J.-M. Su and C.-H. Chang. The multimodal trip planning system of intercity transportation in Taiwan.

Les aléas dynamiques sont rarement appréhendés (avances, retard, annulation, panne,
nouvelle course déclenchée, …
Contexte dynamique:
•N. Borole, D. Rout, N. Goel, P. Vedagiri and T. V. Mathew. Multimodal Public Transit Trip Planner with Real-time Transit Data
•V. Spitadakis and M. Fostieri. WISETRIP- International multimodal journey planning and delivery of personalized trip information

Les aléas dynamiques sont traités :
D'autres éléments s'ajoutent à la complexité du problème :
1. La rapidité de mise à jour d’information
2. la rapidité du calcul et/ou de la mise à disposition des itinéraires satisfaisant
aux contraintes

L'état de l'art
Introduction
Problématique
Résultats & Analyses
Conclusions & Perspectives

Contributions
9/ 46

Étude du cas pratique

Solution offerte par CTPM. Elle couvre l’aire de Montbéliard.

Solution offerte par Optymo. Elle couvre l’aire de Belfort.

Solution offerte par Keolis, CTPM et Pays de Montbéliard Agglomération.

Solution offerte par SNCF.

Solution offerte par google.

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
10/ 46

Étude du cas pratique
Le voyageur ne peut pas choisir l’horaire
exacte de départ.

(journée, Matin, Midi, Après Midi, Soir) !!!!!!!
Une grande ambiguïté : Quel bus le voyageur
dois il prendre à chaque fois?
A quel station le voyageur dois il changer le

bus?
Combien de temps le voyageur doit il attendre à
la correspondance?
Pas de réponse de retour si cet itinéraire

coïncide avec les contraintes de ne pas arriver en
retard?

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
11/ 46

Étude du cas pratique

Arriver le plus rapidement.
Indiquer à quelle station on doit changer le
bus.
Calcul de temps d’attente à la
correspondance.
Problème : Toujours on est dépendant d’un
seul système d’information le S) de CTPM

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
12/ 46

Étude du cas pratique

Indiquer à quelle station on doit changer le
train.
Calcul de temps d’attente à la

correspondance.

Toutes les solutions sont basées sur le mode
train
Toujours on est dépendant d’un seul
système d’information cette fois ci c’est le S)
de SNCF).

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusion & Perspectives

Contribution
13/ 46

Étude du cas pratique

Google maps calcule les itinéraires moyennant la voiture
personnelle dans les régions où il n’y a pas d’accès aux
différentes systèmes d’informations des réseaux de
transport présentes .
Google maps a l’accès à ces systèmes d’informations
seulement dans les grandes villes telles que: Paris, Lyon,
Bordeaux,…

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
14/ 46

Solution existantes

Ces systèmes sont ni cohérents, ni dynamiques.
Pas de système qui traite l’aire urbaine Belfort-Montbéliard(idem pour les territoires en mouvement).
Non inclusion des modes exhaustifs (mode doux: vélo, pied; voiture individuelle: covoiturage; auto
partage, taxi; autres transports déclenchés).

Chaque application fournit une solution en se basant sur le mode de transport de l’opérateur SNCF :
ter, liaisons grandes lignes, Keolis : bus CTPM; CAB: réseau optymo … .
 Examples of application

Problématique
L'état de l'art
Introduction
Résultats & Analyses
Conclusions & Perspectives

Contributions
15/ 46

Contributions attendues

Notre problème : « Une garantie de trouver la solution optimale pour un réseau de transport
de grande taille incorporant plusieurs autorités organisatrices de transports (Aots) dans un

temps limité et de prouver son optimalité ».
Nos hypothèses :
• Tableaux d’horaires de passage statique pas d’aléas ,
• Une fenêtre de temps considérée de 6h à 8h30,

• Modes de transport : bus, train, car,
Nos approches : Approche exacte, Algorithme de programmation dynamique cut+price+share
Nos attentes :
• Une solution exacte et optimale,
• Temps de calcul rapide,
• Satisfaire les attentes des voyageurs

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
16/ 46

Contributions
3. Solutions existantes
Calculateur d’)tinéraires Multimodaux Ordonnés C)MO

 Examples of application

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusion & Perspectives

Contribution
17/ 46

Méthodologie de travail

Conception

Modélisation
des données

Extraction
de
prototype

APD_CPS_V0

Tester
l’algorithm
e APD_CPS
Sur le
prototype

ConceptionA
PD_CPS_V1.
2&2.0

Générer un
simulateur
aléatoire

 Examples of application

Application Price1 & Price2
Application Price2 & price2’
CUT_V0

Tester
l’algorithm
e APD_CPS
sur le
simulateur

Conception
APD_CPS
V.3

Validation
sur des
grands
réseaux

CUT_V1&V2

Ordre sur les voisinage d’une
station
CUT_V2+Price2’+S(ARE

SHARE
Price_V0
SHARE

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
18/ 46

Architecture de Calculateur CIMO

Station de départ

Calculateur
d’itinéraires

Horaire de départ au plus tôt

Station d’arrivée
Horaire
d’arrivée au plus tard

Liste d’itinéraires ordonnés coïncidant
à la recherche

 Examples of application

Données
Optymo

Données
internes
statiques :
•Lignes
•Stations
•Horaires

Données
illicom

Données
CTPM

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
19/ 46

Matrice de déplacement
Modalité(bus, train, car)

Bus

Train

Car

True

False

False

Matrice de déplacement de taille s*s
(s est le nombre de stations du réseau)

Tableaux d’horaire de passage correspondant aux
modes existants

Ligne

Sens

Heure passage

1

Valentigney→Les bruyères

6h00

4
1

Bethoncourt→Champvallon
Valentigney→Les bruyères

Les lignes(ainsi les colonnes) sont
formées de l’ensemble des stations

6h10
6h20

Fonctions de calculs : prochain mode, son horaire

de passage, nombre de modalité, temps d’attentes,….

S1

Si
Ss

Problématique
L'état de l'art
Introduction
Résultats & Analyses
Conclusions & Perspectives

S1

SJ

Ss

S1→S1

S1→SJ

S1→SS

Si→S1

Si→Sj

Ss→S1

Ss→Sj



Si→SS
Ss→SS

Contributions
20/ 46

Modélisation du problème

Problématique
L'état de l'art
Introduction
Résultats & Analyses
Conclusions & Perspectives

Contributions
21/ 46

Objectifs
Les objectifs de cet algorithme sont multiples:
1.

prendre en considération la station de départ ainsi que la station d'arrivée,

2.

prendre en considération le départ au plus tôt et l'arrivée au plus tard, ce qui
constitue la fenêtre de temps de la demande de transport,

3.

minimiser le nombre de reports modaux: ce qui revient à minimiser le nombreLTl
des quadruplets dans l'itinéraire Itini

4.

minimiser la durée du trajet tt

5.

minimiser le temps en transport, ou encore le temps effectif tet

6.

minimiser la somme des temps d'attentes aux correspondances tac

7.

satisfaction l'ensemble des contraintes

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusion & Perspectives

Contributions
22/ 46

Contraintes

• les contraintes d'une paire de prise en charge PU et livraison D :
1.

une même station ne peut pas apparaître à la fois à la prise en charge et à la
livraison.

2.

la date de livraison est supérieure à la date de prise en charge

3.

la ligne est la même.

4.

la direction de la ligne demeure la même.

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusion & Perspectives

Contributions
23/ 46

Contraintes

• les contraintes entre deux paires consécutives de livraison et de prise en charge :

1.

la station de prise en charge succède toujours à une même station de livraison :

2.

la prise en charge qui succède à une livraison peut se faire simultanément :

3.

on ne quitte pas une ligne pour la reprendre:

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
24/ 46

Contraintes

• les contraintes sur l'ensemble de l'itinéraire :
1.

on ne prend pas deux fois la même ligne:

2.

une même station ne peut pas apparaître deux fois en prise en charge ou deux fois en livraison:

3.

le nombre de reports modaux dans un itinéraire i , doit être supérieur ou égal au nombre du
reports modaux du Best-Itinerary :

4.

en cas d'égalité du nombre de modalités, le temps de transport effectif dans un itinéraire i doit
être supérieur ou égal à celui de temps effectif de transport tet de Best-Itinerary :

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
25/ 46

Contraintes

• la contrainte de l'existence d'une chaine de modalités et des horaires de passage entre
deux stations consécutives de l'itinéraire de longueur l :

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
26/ 46

Modélisation du problème

3

Calcul des itinéraires
CUT+PRICE+SHARE

So : Station origine
Sd : Station destination

Affichage des
itinéraires qui
coïncident le
mieux avec la
recherche du
voyageur

4

1

LigneTransport: Ensemble de toutes les lignes
th : la table horaire de recensement de la liste
des horaires de passage d’une station Sjk associé
à ligne LTj et sa direction SensLTjr

2

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusion & Perspectives

Contribution
27/ 46

Réalisation & Jeux de tests

On a travaillé sur un prototype de 9 stations

Pour tester l'algorithme sur des grands réseaux
de transport, on a construit un simulateur basé

sur des réseaux formé par des lignes de bus
et de train générées aléatoirement.

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
28/ 46

Description de l’algorithme

Requête du voyageur:
(Origine, Destination, horaire de départ)
souhaité, arrivée au plus tard,…
Itini<-⌽ ; i=0;
Solution <-⌽
from=Origine

Appel récursif: (from,Destination,horaire actuel
Itini  Itini +Destination
Solution ← )tini
i++
Passer à chercher autre Itini










Mat : matrice de déplacement
Mat.modalité : fonction indique
le mode de transport
Solution : Liste ordonnées des
itinéraires
Itin : Itinéraire formé par des
stations visités
Origine: station de départ
Destination : station arrivée
Métriques : nombre de
correspondances+ temps
effectif de transport + temps de
trajet+…

Oui
On trouve Itini

from=Destination

Réinitialisation origine et destination

Affichage Solution:
Recherche de mode de transport
adéquat entre chaque couple de
stations

Non

Exploration des positions

Oui

Stop

Chercher S dans V(from) tels que:
Mat[origine][S].modalité(bus) =true or
Mat[origine][S].modalité(train) =true )
from←S
Itini  Itini +S
V from ← V from - S

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

APD_CPS_V0
Contributions
29/ 46

APD_CPS_V1.0
5
l=1
tet=5

Cut_V0 : Une station visité ne se répète
pas deux fois
0

l=1
tet=10

l=2
tet=50

l=4
tet=60

6
l=4
tet=65

l=3
tet=60

8

l=3
tet=60

3

8

8
l=4
tet=65
tt=1h37

l=3
tet=60
tt=1h22

8
l=3
tet=60
tt=1h26

l= nombre de report modaux
tet : temps effectif de transport
tt : temps de trajet

l=3
tet=60
tt=1h10

l=4
tet=55

6
l=4
tet=60

6

2

8

l=3
tet=50

l=3
l=3
l=3
tet=50 tet=50 tet=50

3
l=3
tet=55

8
l=3
tet=55
tt=1h41

8

6
l=3
l=3
tet=55 tet=55

3
l=3
tet=60

l=3
tet=55
tt=1h40

8

8

l=3
tet=45

8
l=3
tet=45
tt=1h11

l=3
tet=50
tt=1h37

l=3
tet=45
tt=1h22

8
l=3
tet=50
tt=1h26

8
l=3
tet=55
tt=1h52

l=4

6
l=4

l=2
tet=40

4
l=3
tet=40
tt=1h10

8

3

4

l=2
tet=30

6
l=3
tet=45

l=3
tet=45

l=2
tet=25

1
l=3
tet=40

l=3
tet=40

3
l=2
tet=45

l=3
tet=55

l=3
tet=55

l=3
tet=60

l=3
tet=60
tt=1h11

l=3
tet=40

4

2

6

3

2
l=2
tet=30

1

l=1
tet=15

1

4

l=1
tet=10

0

4
l=2
tet=35

l=1
tet=15

7

l=1
tet=10

l=2
tet=20

7

l=2
tet=35

l=3
tet=55

1

l=1
tet=10

1

l=1
tet=5

l=1
tet=5

l=3

8

l=3

2
l=3

l=3

3

8

8

l=4
tet=60
tt=2h05

l=3
tet=60
tt=1h56

l=4
tet=60
tt=2h05

8
l=3

l=3
tet=55
tt=1h40

8
l=3
tet=55
tt=1h52

l=3
tet=55
tt=1h41

8

l=4

l=3

6

3
l=3

2

l=2
tet=45

3

6
l=4

8
l=4
tet=55
tt=1h37

l=3

l=3

6

8
l=3

8

8

3
l=3

l=3
tet=50
tt=1h11

l=3
tet=45
tt=1h10

l=3
tet=50
tt=1h22

8
l=3
tet=55
tt=1h26

8
l=3
tet=60
tt=1h51

Nombre d’itinéraires calculés & affichés = 5 [tableau horaires de passage & combinaison de modalité]
Complexité =

30/ 46

Réalisation & Jeux de tests

ADP_CPS_v1.0 prend un temps très grand pour trouver les itinéraires
dans des réseaux de transport à l’échelle de l’aire urbaine de Belfort
Montbéliard

Nombre de stations

8

9

11

12

13

0,275sec

1,3sec

9,045sec

1min. 51sec

2min. 53sec

227

210

3406

52165

74895

Temps exécution
Nombre d’itinéraires

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
31/ 46

Réalisation & Jeux de tests

Besoin d’effectuer des optimisations pour rendre C)MO capable de répondre au demande du
voyageur dans un temps envisageable
On a réalisé 3 versions de CIMO :
1. ADP_CPS_v1.2
2. ADP_CPS_v2.0
3. ADP_CPS_v3.0

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
32/ 46

ADP_CPS_v1.2

Afficher seulement les itinéraires dont le nombre de report modaux ne dépasse pas trois.

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
33/ 46

APD_CPS_V1.2
5
l=1
tet=5

Cut_V0 : Une station visité ne se répète
pas deux fois
0

l=1
tet=10

l=4
tet=60

6

l=4
tet=65

l=2
tet=50

l=3
tet=60

8

l=3
tet=60

3

l=4
tet=65
tt=1h37

8
l=3
tet=60
tt=1h22

8
l=3
tet=60
tt=1h26

l=3
tet=60
tt=1h10

l=4
tet=55

6
l=4
tet=60

6

2

8
l=3
tet=60

l=3
tet=50

l=3
l=3
l=3
tet=50 tet=50 tet=50

l=3
tet=55

8
l=3
tet=55
tt=1h41

8

6

3

l=3
l=3
tet=55 tet=55

3
l=3
tet=60

l=3
tet=55
tt=1h40

8

8

l=3
tet=45

8
l=3
tet=45
tt=1h11

l=3
tet=50
tt=1h37

8

8

l=3
tet=45
tt=1h22

l=3
tet=50
tt=1h26

l=3
tet=55
tt=1h52

l=3

l=3

8

6

8

8

l=4
tet=60
tt=2h05

l=3
tet=60
tt=1h56

l=4
tet=60
tt=2h05

2
l=3

3

l=4

l=3

l=3

6

8
l=3

l=3

8

6
l=3

3

l=3

l=3
tet=55
tt=1h52

8

3
l=3

l=3

l=3
tet=55
tt=1h40

8

8

6

l=4 tet=50

tt=1h11

8
l=4
tet=55
tt=1h37

l=3
tet=45
tt=1h10

l=3
tet=50
tt=1h22

8
l=3
tet=55
tt=1h26

8

l= nombre de report modaux
tet : temps effectif de transport
tt : temps de trajet
Nombre d’itinéraires calculés & affichés =
[tableau horaires de passage & combinaison de modalité]
Speed Up SU entre version 1.2 et version0 : SU =2,65
Le gain relatif RG entre version 1.2 et version0 RG=0,623

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

l=3

l=3
tet=55
tt=1h41

8

2

l=2
tet=45

3

l=4

l=4

l=2
tet=40

4
l=3
tet=40
tt=1h10

3

8

4

l=2
tet=30

6
l=3
tet=45

l=3
tet=45

l=2
tet=25

1
l=3
tet=40

l=3
tet=40

3
l=2
tet=45

l=3
tet=55

l=3
tet=55

6

3

l=3
tet=60
tt=1h11

8

4

2

l=3
tet=55

2
l=3
tet=40

l=2
tet=30

1

l=1
tet=15

1

4

l=1
tet=10

0

4
l=2
tet=35

l=1
tet=15

7

l=1
tet=10

l=2
tet=20

7

l=2
tet=35

Cut_V1 : nombre de
modalité l⩽ 3
(Price1)

1

l=1
tet=10

1

l=1
tet=5

l=1
tet=5

l=3
tet=60
tt=1h51

Contributions
34/ 46

ADP_CPS_v2.0

Calculer le meilleur itinéraire qui minimise le Price (nombre de report modaux, temps
effectif de transport, temps de trajet) .
Le CUT_V2 et CUT_V2’ sera établi si l’itinéraire calculé en cours dépasse le coût minimal de
Price2 & Price2’ .
Réduction de nombre d’appel récursif →Réduction de complexité

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
35/ 46

ADP_CPS_v2.0
Price2=

Price2’=

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
36/ 46

APD_CPS_V2.0
5
l=1
tet=5

Cut_V0 : Une station visité ne se répète
pas deux fois
0

l=1
tet=10

Cut_V & cut V ’ :
Price & price ’

l=2
tet=50

l=4
tet=60

6
l=4
tet=65

l=4
tet=65
tt=1h37

4

2
l=3
tet=55

l=3
tet=60

8

l=3
tet=60

3

8
l=3
tet=60
tt=1h22

8
l=3
tet=65
tt=1h26

l=3
tet=55

l=3
tet=60
tt=1h10

l=4
tet=55

6
l=4
tet=60

l=3
tet=50

l=3
l=3
l=3
tet=50 tet=50 tet=50

l=3
tet=55

8

8

6

3

l=3
tet=55
tt=1h41

8

6

2

l=3
l=3
tet=55 tet=55

3
l=3
tet=60

l=3
tet=55
tt=1h40

8

8

l=3
tet=45

8
l=3
tet=45
tt=1h11

l=3
tet=50
tt=1h37

8
l=3
tet=55
tt=1h52

l=3

l=3
tet=45
tt=1h22

l=3
tet=50
tt=1h26

l=3

8

6

8

2
l=3

l=3

l=3

3

6

8
l=3

l=3

8

6
l=3

3

l=3

6

l=3
tet=55
tt=1h52

8
l=4
tet=55
tt=1h37

8

3
l=3

l=3
tet=50
tt=1h11

l=3
tet=55
tt=1h40

8

8

l=3
tet=45
tt=1h10

l=3
tet=50
tt=1h22

8
l=3
tet=55
tt=1h26

8

l= nombre de report modaux
l=4
l=4
l=3
tet=60
tet : temps effectif de transport
tet=60
tet=60
tt=2h05
tt=2h05
tt=1h56
tt : temps de trajet
Nombre d’itinéraires calculés & affichés =
[tableau horaires de passage & combinaison de modalité]
Speed Up SP entre version 2.0 et version.2 : SP =3,18
Le gain relatif GF entre version 2.0 et version1.2 GF=0,68

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

l=3

l=3
tet=55
tt=1h41

8

2

l=2
tet=45

3

l=4

l=4

l=2
tet=40

4
l=3
tet=40
tt=1h10

8

3

8

4

l=2
tet=30

6
l=3
tet=45

l=3
tet=45

l=2
tet=25

1
l=3
tet=40

l=3
tet=40

3
l=2
tet=45

8

l=3
tet=60

l=3
tet=60
tt=1h11

8

l=2
tet=30

6

3

2
l=3
tet=40

1

l=1
tet=15

l=2
tet=35

1

4

l=1
tet=10

0

4
l=1
tet=15

7

l=1
tet=10

l=2
tet=20

7

l=2
tet=35

l=3
tet=55

1

l=1
tet=10

1

l=1
tet=5

l=1
tet=5

l=3
tet=60
tt=1h51

Contributions
37/ 46

Réalisation & Jeux de tests
ADP_CPS_v3.0
Ordonner les stations de réseau selon l’ordre de correspondance.
En cas d’égalité le privilège est donné à la station la plus proche à la destination.

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
38/ 46

APD_CPS_V3.0
Cut_V0 :
Une
station
visité ne
se
répète
pas
deux
fois

5
l=1
tet=5

Parcours des stations selon l’ordre de
l=1
correspondance

1

tet=10

Cut_V & cut V ’ :

l=3
tet=40

8
l=3
tet=45
tt=1h11

6

8
l=3
tet=50
tt=1h37

8
l=3
tet=45
tt=1h26

8

l=3
tet=50
tt=1h26

l= nombre de report modaux
tet : temps effectif de transport
tt : temps de trajet

8
l=3
tet=60
tt=1h10

3

8
l=3
tet=60
tt=1h11

6

8
l=4
tet=65
tt=1h37

8
l=3
tet=60
tt=1h22

2

2

6
3

8
l=3
tet=65
tt=1h26

8

3

l=3
tet=55
tt=1h40

8

l=3
tet=55
tt=1h41

6

6

8

2

l=2
tet=45

l=2
tet=45

3

l=2
tet=40

4

4

2

6

4

l=2
tet=30

l=2
tet=30

l=2
tet=50

l=2
tet=25

1

1

4

1

l=1
tet=15

l=1
tet=15

l=3
tet=40

3

l=3
tet=40
tt=1h10

Price & price ’

2

l=1
tet=10

0

7

l=2
tet=35

7

l=1
tet=10

l=1
tet=10

1

4
l=2
tet=35

8

0

l=2
tet=20

l=3
tet=40

l=1
tet=5

l=1
tet=5

8
l=3
tet=55
tt=1h52

l=4
tet=60
tt=2h05

3

8

l=3
tet=55
tt=1h40

8
l=3
tet=55
tt=1h41

l=3
tet=45
tt=1h10

6

3

8

3

8

6

8
l=4
tet=60
tt=2h05

8
l=3
tet=50
tt=1h22

8
l=3
tet=50
tt=1h11

3

8

6
8

6

3

l=3
tet=50
tt=1h22

8
l=3
tet=55
tt=1h26

8
l=3
tet=55
tt=1h26

l=3
tet=60
tt=1h51

Nombre d’itinéraires calculés & affichés = [tableau horaires de passage &
combinaison de modalité]
Speed Up SP entre version 2.0 et version.2 : SP =1,12
Le gain relatif GF entre version 2.0 et version1.2 GF=0,92

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusions & Perspectives

Contributions
39/ 46

Réalisations & Analyses
Plate-forme & environnement logiciels

Plateforme java 1.8.0

Eclipse IDE version 4.3.2

Python3.4.2

PyCharm4.0.5

Problématique
Introduction
Réalisations & Analyses

L'état de l'art
Contributions
Conclusions & Perspectives

40/ 46

Temps d’exécution en fonction du taille de réseau

Introduction
Problématique
Réalisations & Analyses

L'état de l'art
Contributions
Conclusions & Perspectives

41/ 46

Speed-Up & Gain relatif

42/ 46

Speed-Up & Gain relatif

Problématique
Introduction
Réalisations & Analyses

L'état de l'art
Contributions
Conclusions & Perspectives

43/ 46

Conclusions & Perspectives
Conclusion

Problématique
L'état de l'art
Introduction
Résultats & Analyses
Conclusions & Perspectives

Contributions
44/ 46

Perspectives

Introduction
Problématique
L'état de l'art
Résultats & Analyses
Conclusion & Perspectives

Contribution
45/ 46

Bilan personnel:

Merci de votre attention

46/ 46


Aperçu du document PresentationStage_IdrissHASSINE.pdf - page 1/46

 
PresentationStage_IdrissHASSINE.pdf - page 2/46
PresentationStage_IdrissHASSINE.pdf - page 3/46
PresentationStage_IdrissHASSINE.pdf - page 4/46
PresentationStage_IdrissHASSINE.pdf - page 5/46
PresentationStage_IdrissHASSINE.pdf - page 6/46
 




Télécharger le fichier (PDF)




Sur le même sujet..





Ce fichier a été mis en ligne par un utilisateur du site. Identifiant unique du document: 00366200.
⚠️  Signaler un contenu illicite
Pour plus d'informations sur notre politique de lutte contre la diffusion illicite de contenus protégés par droit d'auteur, consultez notre page dédiée.