Une approche évolutionniste pour résoudre un problème de plus court chemin intermodal...

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 : mounir.boussedjra@utbm.fr

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 : mounir.boussedjra@utbm.fr

Journée de Travail

Groupe “Bermudes”

13 juin 2003 – Clermont-Ferrand (France)