1

Approches primale et duale pour la conception optimale

de réseaux de transport en commun

Julien Antunes Mendes

Université catholique de LouvainEcole Polytechnique de Louvain

28 juin 2010

2

3

4

5

6

Modélisation, données et objectifModélisation d’un réseau à l’aide d’un graphe orientéNœuds = arrêts de busArêtes = routes entre 2 nœuds

7

Modélisation, données et objectif

Données :Demandes entre les paires origine-destination (par exemple, demande

de A à B : 30 personnes/heure)Capacités des busTemps de parcours des arêtesVariables :Flux sur les arêtesFlux sur les routesObjectif :Recherche d’un équilibreen régime stationnaire

Modélisation d’un réseau à l’aide d’un graphe orientéNœuds = arrêts de busArêtes = routes entre 2 nœuds

8

Recherche d’un équilibre

Les passagers choisissent une route plutôt qu’une autre

pour 2 raisons

Ils veulent une route rapide (temps de parcours petit)

Ils veulent un faible flux sur la route pour éviter

l’encombrement dans le bus, pour ne pas être trop serrés

Désutilité : inconfort, mécontentement

9

• Présentation du problème Désutilité, problème général, optimalité

• Passage au dual Problème dual, comparaison, résolution

• Problème design Décider des capacités, problème dual,

choix des lignes de bus

10

• Présentation du problème Désutilité, problème général, optimalité

• Passage au dual Problème dual, comparaison, résolution

• Problème design Décider des capacités, problème dual,

choix des lignes de bus

11

Fonction de désutilité par unité de temps

Le volume du moyen de locomotion doit être supérieur à la somme des volumes des personnes

12

Fonction de désutilité par unité de temps

13

Problème de minimisationNotations

Données

Variables

14

Problème de minimisation

Minimiser somme des désutilités sur les arêtes : équilibre socialMinimiser somme des intégrales des désutilités : équilibre égoïste

15

Problème de minimisation

16

Conditions d’optimalité

Désutilité sur la kème

route entre r et s

17

Conditions d’optimalité

Désutilité minimale sur les routes utilisées Désutilité supérieure sur les routes non utilisées

Désutilité sur la kème

route entre r et s

18

Résolution du problème primal via SDPT3 (Matlab)

SDPT3 permet de résoudre des problèmes de minimisation convexe où apparaissent des logarithmes de variables dans l’objectif

Les nombres sur le dessin représentent les capacitésLes temps de parcours sont unitairesLes demandes sont les suivantes :

AB : 3AD : 4BA : 2CB : 5DC : 1

19

Résolution du problème primal via SDPT3 (Matlab)

SDPT3 permet de résoudre des problèmes de minimisation convexe où apparaissent des logarithmes de variables dans l’objectif

Les nombres sur le dessin représentent les capacitésLes temps de parcours sont unitairesLes demandes sont les suivantes :

AB : 3AD : 4BA : 2CB : 5DC : 1

20

• Présentation du problème Désutilité, problème général, optimalité

• Passage au dual Problème dual, comparaison, résolution

• Problème design Décider des capacités, problème dual,

choix des lignes de bus

21

Pourquoi passer au dual ?

Temps de calcul augmente :

Nombre de chemins

Nombre de paires origine-destination

22

Un réseau de bus

# nœuds : 25

# arêtes : 80

23

Un réseau de bus

Nombre de chemins sans boucle entre le nœud

supérieur gauche et le nœud

inférieur droit : 8512

Avec 600 paires origine-destination,

environ 3.000.000 de chemins

24

Passage au dual

25

Passage au dual

Application dans notre cas :

26

Passage au dual

27

Passage au dual

28

Plus court chemin et choix des chemins

On va prendre les chemins de taille minimale en termes de nombre d’arêtesou avec un certain écart par rapport à cette taille

Ecart=0

Ecart=2

29Augmentation du nombre de chemins

Résultats pour un réseau de bus, obtenus via SDPT3

30

Méthodes de résolution du problème dual

• SDPT3 (problèmes de mémoire vive avec un réseau de bus 8x8 : 4032 paires OD et 224 arêtes)

• Plus forte pente

• Méthode «  moyenne des itérés »

• Méthode de l’ellipsoïde

Obtention d’un sous-gradient

31

Obtention d’un sous-gradient

A partir d’une solution optimale du problème de plus court chemin, on en trouve son gradient :

Gradient :

Mais il peut y avoir plusieurs plus courts chemins et la fonction n’est alors pas différentiable.

On prend un sous-gradient.

32

Justification

Méthode «  moyenne des itérés »

+ pénalité par rapport à l’itéré initial pour que le problème soit borné

y est solution d’une équation du second degré

33

Comparaison des résultats

La méthode «  moyenne des itérés » donne les meilleurs résultats

34

• Présentation du problème Désutilité, problème général, optimalité

• Passage au dual Problème dual, comparaison, résolution

• Problème design Décider des capacités, problème dual,

choix des lignes de bus

35

Données et objectif

Données :Demandes entre les paires origine-destination (par

exemple, demande de A à B : 30 personnes/heure)Capacités des busTemps de parcours des arêtesVariables :Flux sur les arêtesFlux sur les routesCapacités (+coût)Objectif :Recherche d’un équilibre

36

Présentation du problème design, conjointement convexe en les flux

et les capacités

1) Chaque arête est considérée de manière indépendante2) Un réseau est constitué de lignes et la capacité va être égale sur une ligne car un véhicule va suivre exclusivement celle-ci

37

Passage au dual

Pour plus de concision

m* vaut soit zéro soit moins l’infini. On contraint les variables duales à

appartenir au domaine effectif de la fonction.

38

Passage au dual

La dernière contrainte impose que m*(y)=0

39

Flux optimauxEn annulant la dérivée partielle

de p(x,f) par rapport à x

Capacités fixes et capacités variables

40

Résultats

Réseau de bus

Autre réseau

41

Données et objectif

Données :Demandes entre les paires origine-destination (par

exemple, demande de A à B : 30 personnes/heure)Temps de parcours des arêtesLignesVariables :Flux sur les arêtesFlux sur les routesCapacités# chauffeurs sur les lignesObjectif :Recherche d’un équilibre

42

Flux égaux pour les lignesAjout contrainte : capacité sur une arête =

somme des capacités des lignes traversant cette arête

s : nombre de chauffeurs

sur les lignes

F(a,l) : capacité supplémentaire

sur l’arête a par l’ajout d’un

chauffeur sur la ligne l

43

Passage au dual

Si F=I, même problème que précédemment où chaque arête était considérée de manière indépendante

44

RésultatsOn considère un réseau de bus avec 5 lignes verticales et 5 horizontales.Un chauffeur en plus sur une ligne fait augmenter la capacité de 300 surchaque arête de la ligne. Les coûts sont unitaires.

Le nombre optimal de chauffeurs de bus sur chaque ligne est :

45

Compromis coût-désutilité

représentel’importancedu coût parrapport à ladésutilité

46

Conclusion• Problème primal• Passage au dual inévitable pour les grands

réseaux - Résolution avec SDPT3 (problèmes de mémoire vive) - « Moyenne des itérés » donne les meilleurs résultats

• Problème design convexe - Décider des capacités - Méthode de l’ellipsoïde pour un problème contraint

• Extensions : - Régime non stationnaire - Résolution en nombres entiers