Après des

LA R.O. à MONTRÉAL Succès en planification

Nouveaux défis en temps réel

François Soumis

GERAD

1 Journées de la recherche 2013

SUCCÈS EN PLANIFICATION

• Trois entreprises issues de l’université

– INRO

– AD OPT

– GIRO

• Les problèmes, la science, les marchés


INRO – LE PROBLÈME

• Planification de réseaux routiers et de

transport en commun

Demande estimée

Réseaux de transport

Modèles de flot de passagers

- Utilisation du réseau - Qualité de service

Modification du scénario


INRO – LES SYSTÈMES

• Optimiseurs puissants déterminant les flots de voitures et/ou de passagers dans les réseaux • Interfaces graphiques

- Visualiser les flots

- Modifier le réseau

• Implanté dans 80 pays


LES OPTIMISEURS • Multi-flots à coûts convexes

LIMITE DE CAPACITÉ

SUR UN ARC

TEMPS QUI AUGMENTE

AVEC LA CONGESTION

Temps de parcours

Flot Capacité ?


AUTRES APPLICATIONS

• Flot de passagers aériens

Espérance clients refusés

Demande moyenne

Capacité

Capacité d’un avion Demande


AUTRES APPLICATIONS • Flot de passagers aériens


Demande moyenne

Capacité



AUTRES APPLICATIONS

• Flot de passagers aériens

• Acheminement du trafic en télécom

- Espérance du trafic perdu (lignes)

- Espérance de l’attente (paquets)

• Transport des marchandises: camion, trains,…


Demande moyenne

Capacité



AUTRES APPLICATIONS • Flot de passagers aériens

• Acheminement du trafic en télécom - Espérance du trafic perdu (lignes) - Espérance de l’attente (paquets)

• Transport des marchandises: camion, trains,…

• École de Montréal Remplacer les contraintes de capacités par des coûts N-L - Représente mieux la réalité - Plus facile à résoudre


Demande moyenne

Capacité


9

AD OPT –LES PROBLÈMES

TRANSPORT AÉRIEN

1 2 3 4 5 ... 31 1 2 . .

HORAIRE

DE VOLS

AVIONS

BLOCS

MENSUELS

ROTATIONS

D’ÉQUIPAGES

PLANIFICATION

A 320

DC-9

PERSONNES

BASE

VOL

JOURS

CONGÉ ROTATION

MTL TOR 7:00 8:00 8:00 9:00

... SDV SDV

PÉRIODE

DE REPOS SERVICE DE VOL

VOL


PROBLÈME GÉNÉRIQUE

COUVRIR À COÛT MINIMUM UN ENSEMBLE DE TÂCHES

AVEC DES CHEMINS RÉALISABLES

COMMODITÉ

TÂCHE

TÂCHE


AD OPT – LA SCIENCE 1980- …

GÉNÉRATION DE COLONNES

= 1

BASE COLONNES INCONNUES

PROBLÈME

RÉDUIT SOUS-

PROBLÈME

COÛT RÉDUIT

NOUVELLES

COLONNES

VARIABLES

DUALES

COÛT

RÉDUIT = 0 OPTIMAL

AJOUTER LES

COLONNES

NON OUI

1- RÉSOUDRE LE PROBLÈME RÉDUIT

2- GÉNÉRER DE NOUVELLES COLONNES EN RÉSOLVANT LE

SOUS-PROBLÈME (MINIMISER LE COÛT RÉDUIT)


AD OPT – LES SYSTÈMES

• Optimiseurs

• Interfaces graphiques

– Valider les donnés

– Visualiser les solutions, les modifier

• Implantés dans une vingtaine de compagnies

– Plusieurs systèmes par compagnies

• (Pilotes, Copilotes, Agents de bord) X (Rotations, Blocs),

Avions

Journées de la recherche 2013 13

ROTATIONS

BLOCS

MENSUELS

OPTIMISATION

INTÉGRÉE

COUVRIR LES VOLS AVEC DES ROTATIONS

COUVRIR LES ROTATIONS AVEC DES BLOCS

NOUVEAUX PROBLÈMES: OPTIMISATION INTÉGRÉE

COUVRIR LES VOLS AVEC DES BLOCS

- 10 000 À 30 000 VOLS / MOIS

- UN BLOC CONTIENT JUSQU’À 100 VOLS

- LE PROBLÈME DE PARTITIONNEMENT

EST TRÈS DÉGÉNÉRÉ



AD OPT – LA SCIENCE 2005-…

AGREGATION DES TACHES

• AGGRÉGER LES VOLS EN CLUSTERS

vol Rotation




• AGGRÉGER LES VOLS EN CLUSTERS (ex: équipage suit l’avion)

• REOPTIMISER

- OPTIMISATION RAPIDE SUR LES CLUSTERS (arcs bleus seulement)

• Petits problèmes (une contrainte par cluster)

vol Rotation




• AGGRÉGER LES VOLS EN CLUSTERS (ex: équipage suit l’avion)

• REOPTIMISER

- OPTIMISATION RAPIDE SUR LES CLUSTERS (arcs bleus seulement)

• Petits problèmes (une contrainte par cluster)

- MODIFIER LES CLUSTERS POUR ATTEINDRE L’OPTIMALITÉ

• Ajouter des arcs rouges (choisit avec les coûts réduits)

vol Rotation

AGRÉGATION DES TÂCHES • PROBLÈME MAÎTRE

• PROBLÈME AGRÉGÉ

1100

1100 0011

0011 1010

1010

… …..

0 0

=1

=1

=1

=1

=1

=1

TÂCHES

BASE HORS BASE

1100

1100 0011

0011 1010

1010

… ….. TÂCHES

1100

0011

1010

COLONNES

HORS BASE

COMPATIBLES

COLONNES

INCOMPATI

-BLES

PIVOTS

RAPIDES

PIVOTS NÉCESSITANT UNE

MODIFICATION DE L’AGRÉGATION 18

OPTIMISATION INTÉGRÉE AVEC

L’AGRÉGATION DE CONTRAINTES

1100

0011

1010

COLONNES

HORS BASE

COMPATIBLES

COLONNES

INCOMPATIBLES

• RÉSOUDRE LE PROBLÈME DES ROTATIONS

• AGRÉGER LES VOLS D’UNE MÊME ROTATION

• OPTIMISER LES BLOCS SANS DÉSAGRÉGATION

PROBLÈME CLASIQUE DE BLOCS

• RÉOPTIMISER LES BLOCS EN MODIFIANT L’AGRÉGATION

• (ATTEINT LA SOLUTION OPTIMALE EN RÉSOLVANT SEULEMENT DE

PETITS PROBLÈMES)

19

AGRÉGATION DES TÂCHES

et GÉNÉRATION de COLONNES

• PROBLÈME AGRÉGÉ

• FAVORISER LES COLONNES COMPATIBLES

1100

0011

1010

COLONNES

HORS BASE

COMPATIBLES

COLONNES

INCOMPATI

-BLES

PIVOTS

RAPIDES

PIVOTS NÉCESSITANT UNE

MODIFICATION DE L’AGRÉGATION

20

SOUS

PROBLÈME

GÉNÉRANT

DES

COLONNES

DANS UN

RÉSEAU

Journées de la recherche 2013

GÉN. DE COL. + AGRÉGATION

MILLIONS DE MILLIONS DE VARIABLES

30 000

CONTRAINTES

• ON RÉSOUD SEULEMENT LE NOYAU DU PROBLÈME PLUSIEURS FOIS

• RÉDUIT LE NOMBRE DE VARIABLES AVEC LA GÉNÉRATION DE COLONNES

• RÉDUIT LE NOMBRE DE CONTRAINTES AVEC L’AGRÉGATION

• LE NOYAU EST AJUSTÉ DYNAMIQUEMENT POUR ATTEINDRE L’OPTIMALITÉ

NOYAU

ON PEUT RÉSOUDRE DES PROBLÈMES IMMENSES


1 2 3 4 ... 31 1 ─ ─ ─ ─ 2 ─ ─ ─ ─ . . .

PARCOURS

ROUTES

D’AUTOBUS

BLOCS

MENSUELS

JOURNÉES DE

CHAUFFEURS

STATIONS

GARAGE

GARAGE ?

CHAUFFEURS

PARCOURS PARCOURS ...

PARCOURS

POINT DE RELÈVE

ROUTE 1

JOURS

CONGÉ JOURNÉE

ROUTE 2

1 2 3 ... 1 7:00 7:30 7:40 2 7:05 7:35 7:45 . . .

GIRO – LES PROBLÈMES

GESTION DES AUTOBUS

CRÉATION D’HORAIRES DIVISÉE EN 3 ÉTAPES


TRANSPORT EN COMMUN

• Défis semblables

• Implanté dans 300 villes: New York, Chicago,

Los Angeles, Tokyo, Singapore, Sydney, ….


DES DÉFIS DE DÉCISION EN TEMPS RÉEL

• Système d’opération en temps réel

– Processus de décision léger et rapide ???

– Algorithmes d’optimisation

• (1% d’erreur peut coûter 10 millions par an)

• Planifier en tenant compte de l’incertitude

– Créer des situations plus favorables à l’opération

• Coupler la planification et l’opération

– La planification augmente fortement l’efficacité

– L’opération ne doit pas trop la réduire


SYSTÈME D’OPÉRATION EN TRANSPORT AÉRIEN

• Mise à jour du plan suite aux perturbations: météo,

pannes, absences, …

• Décisions intégrés et rapides

– Rotations + Blocs (pour réalisabilité )

– Intégrer avions (pour les coûts)

• Interconnexion avec les autres systèmes

– Détecter les perturbations

– Identifier les ressources disponibles

– Interaction avec les décideurs

– Implantation des décisions: avions, personnels,

passagers services au sol,…


AVIONS

ÉQUIPAGES

Rotations + Blocs

COUPLER LA PLANIFICATION ET L’OPÉRATION

• La planification optimise avec une vue d’ensemble du système dans l’espace et le temps

• L’opération doit décider rapidement

– Décision avec vue locale

– Tenir compte du plan pour profiter de la vue d’ensemble

• Identifier quand le plan est hors cible et le mettre à jour


DISPATCHING DE CAMIONS MINIERS

Communication

Balise camion ordinateur

Décisions • Prévision de l’heure à laquelle chaque pelle sera libre

(positions des camions, temps de trajets et de chargements, ...)

• Affectation des camions

Objectifs • Qualité de mélange

• Productivité

position

affectation

ordinateur

Concentrateur ?

?

LE SYSTÈME DÉVELOPPÉ Planification d’équipements • Équilibre : nb. camions – nb. pelles – obj. production

• Localisation des pelles (qualité de mélange)

Programmation linéaire + système interactif

Plan d’opération • Débit par pelle

• Itinéraires des camions

• Équilibre : qualité – quantité (temps d’attente)

Lagrangiens + Flot à coûts convexes (10 sec.)

Affectation des camions • Suit le plan (reproduit les attentes du plan et non les flots)

• Considère 10-15 prochains camions

Problème d’affectation

Implanté dans 6 mines (Canada, U.S.A., Brésil, Inde)

AUTRES PROBLÈMES

• Camions de livraisons

• Chaine logistique

• Systèmes de production

• Systèmes de distribution de service

• ……

On ne manquera pas de défis

dans le cadre de la chaire


Documents

Après des