Embed Size (px)
Citation preview
Une approche évolutionniste pour résoudre un problème de plus court chemin intermodal
multicritère
Mounir BOUSSEDJRA, Christelle BLOCH et Abdellah EL MOUDNI
Université de Technologie de Belfort-MontbéliardLaboratoire Systèmes et Transports (S.e.T)
90010 Belfort – FranceMèl : [email protected]
Journée de Travail
Groupe “Bermudes”
13 juin 2003 – Clermont-Ferrand (France)
2
Introduction
Domaine transport terrestre
Méthodes d’optimisation
Des modèles simplifiés
Loin de la complexité de la pratique
Problème plus court chemin
Différentes variantes
En particulier temps de trajet dynamiques
3
Plan
Définitions
Problématique
Modélisation
Algorithme de résolution
Conclusion et Perspectives
4
Définitions
Intermodal
Transbordement
Temps d’attente
1. Date de départ2. Date d ’arrivée3. Moyen de transport choisi
Temps de trajet
Temps d’attente
Aspect Dynamique
5
Problématique
Deux points source et destination «One to One»
La date de départ « DD »et la date d’arrivée « DA »
Intermodal, dynamique avec temps d’attente
hj
l
S
i
kD
mTemps, Coût & Nombre de transbordements
6
Modélisation du réseau Urbain
Réseau Intermodal
Bus Train
Voiture
Points de connexion
Modélisation
Modélisation d’un sous réseau
} )(),...,(),({)(21
ixixixiX v
k
vvv
),( ztij
ji
k
h
)(tΨ zy
ikh
)(iX v
V est l’ensemble des points successeurs du nœud courant
(i)xT v
j (i)x,...,t(i)xt(i)xT vim
vi
vi 1{
)(),( iXTtiXx j
i
j ),( xtij
C(i,k)
7
Approche de résolution
Formulation mathématique
)(.)(.)(.)( xhxgxfxZ
D
jSi
iji
i
Ψxf )()( Temps de trajet
D
jSi
ij
i
cxg ,)( Coût de trajet
D
Sii
Trxh ,)( Nombre de transbordements
Minimiser ?
hj
l
S
i
k Dm
)(tΨ zy
Sli
),( ztSl
),( miC
mTr
8
Approche de résolution
Formulation mathématique
, et
)()(
)()()('
minmax
min
xfxf
xfxfxf
)()(
)()()('
minmax
min
xgxg
xgxgxg
)()(
)()()('
minmax
min
yhyh
yhyhxh
et
Tel que :
,
.
9
Outil de résolution
Algorithmes Evolutionnistes
Approche de résolution
Réseau Intermodal
Bus Train
Voiture
Points de connexion
10
Approche de résolution
Population initiale
Génération aléatoire.
Heuristique (premier mode, première date).
11
Approche de résolution
Codage
Réseau Intermodal
Bus Train
Voiture
Points de connexion
Codage
Evaluation
Eval(path) fit(path)
1
12
Approche de résolution
SélectionLa roue de la fortune.
CroisementInter réseaux
Intra réseaux
Réseau busRéseau trainPoint de connexion
P1
P2
O1
O2O1
O2
Mutation
)3(vx )3(vxt
)(135
tzx ),(35
tx
)(135
tzx ),(35
tx
13
Approche de résolution
Réinsertion
Parents Fils
Nouvelle population
14
Conclusion & Perspectives
Réorganiser des réseaux de transport intermodaux
Améliorer l'interaction entre les différents modes
Temps, coût et nombre de transbordements
Travaux futurs
Comparaison de résultats avec des méthodes exactes.
Parallèlisation de l’approche.
15
Une approche évolutionniste pour résoudre un problème de plus court chemin intermodal
multicritère
Mounir BOUSSEDJRA, Christelle BLOCH et Abdellah EL MOUDNI
Université de Technologie de Belfort-MontbéliardLaboratoire Systèmes et Transports (S.e.T)
90010 Belfort – FranceMèl : [email protected]
Journée de Travail
Groupe “Bermudes”
13 juin 2003 – Clermont-Ferrand (France)
