Méthodologie de Développement Objet

Méthodologie de Développement ObjetQuatrième partie : Présentation du projet

Christine Solnon

INSA de Lyon - 4IF

2014 - 2015

1/32

Optimisation de tournées de livraison Le projet Optimod’Lyon

Plan du cours

1 Optimisation de tournées de livraisonLe projet Optimod’LyonLe projet DevOO

2 Le voyageur de commerce en programmation par contraintes

2/32


Le projet Optimod’Lyon

Réponse à un appel à projets de l’ADEME sur la mobilité urbaine

Porteur : Grand Lyon

13 partenaires :

2 collectivités : Lyon etGrand Lyon8 industriels : IBM,Renault Trucks, Orange,CityWay, Phoenix ISI,Parkeon, AutoroutesTrafic, Geoloc Systems3 laboratoires derecherche : LIRIS,CETE, LET

Durée : 3 ans (2012-2015)

Budget : 7 M Euros

IN THE CITYSUSTAINABLE MOBILITYOPTIMIZE

3/32


Objectifs d’Optimod’Lyon

mobility portal

in real−time

mobility data

for collecting

New systems

networks by a 1 hour prediction

of traffic conditions

Optimize the exploitation of urban

Provide real−time and multi−modal

Optimize urban deliveries by informing

drivers and optimizing tours

information, available at any time, every

where and for every body

warehouse

Data

Mobility

Grand Lyon

4/32

Optimisation de tournées de livraison Le projet DevOO

Plan du cours

1 Optimisation de tournées de livraisonLe projet Optimod’LyonLe projet DevOO

2 Le voyageur de commerce en programmation par contraintes

5/32


Vue générale du projet (IHM + DevOO)

Sous-système “Demande de livraison” :Utilisé par les clients pour

Demander une nouvelle livraisonSuivre une livraison en cours

Sous-système “Préparation et supervision des livraisons” :Utilisé par les sociétés de livraison pour

Planifier les tournées de livraisonModifier une tournée planifiéeSuperviser le bon déroulement des tournées en cours

Sous-système “Réalisation des livraisons” :Utilisé par les livreurs pour

Connaître les livraisons à effectuer et l’itinéraire à suivreIndiquer les livraisons effectuées

Sous-système “Relations clientèles” :Utilisé par les sociétés de livraison pour gérer ses relations clients

6/32


Périmètre du projet DevOO

Préparation des feuilles de route :

Charger un plan à partir d’un fichier XMLCharger une demande de livraisons à partir d’un fichier XMLCalculer une tournée pour une demande de livraisonsModifier interactivement une tournéeGénérer une feuille de route pour le livreur

Points reliés pardes tronçons

Chaque tronçon aune longueur etune vitessemoyenne

Entrepot en bleuclair 7/32





3 plages de livraison :

8h-10h (bleu) :4 livraisons

10h-12h (rose) :4 livraisons

12h-14h (vert) :5 livraisons

7/32





Tournée la pluscourte partant de (etrevenant sur) l’entrepotet passantsuccessivement par

1 les points bleus

2 les points roses

3 les points verts7/32





Possibilité de

Supprimer deslivraisons

Insérer deslivraisons

7/32





Description textuellede la tournée indiquantl’itinéraire et leshoraires de passage

7/32


Formalisation du problème de calcul de tournée

Données fournies en entrée :

Un graphe G = (V ,A) tel que V = points et A = tronçons

Un entrepôt e ∈ V

Une fonction d : A→ R+ telle que dij = durée de l’arc (i , j)

Un ensemble de points de livraison L ⊆ V

Une fonction p : L→ N telle que pi est la plage de livraison de i

Données à calculer en sortie :Un circuit c dans G tel que

c part de e, passe par chaque point de L et revient sur e

pour tout couple de points (i , j) ∈ L× L, si pi < pj alors c passe par iavant de passer par j

la somme des durées des arcs de c est minimale

8/32


Reformulation du problème de calcul de tournée

Calcul du graphe des plus courts chemins G′ :Entrée : G = (V ,A), L ⊆ V , e ∈ V , p : L→ N et d : A→ R+

Sortie : G′ = (V ′,A′) et d ′ : A′ → R+ tels que

V ′ = L ∪ {e}A′ = {(e, i)|i ∈ L,pi est minimal}

∪ {(i , j) ∈ L× L|pi = pj ∨ pj = pi + 1}∪ {(i ,e)|i ∈ L,pi est maximal}

d ′ij = longueur du plus court chemin

de i à j dans G

e

1

2

3

4

5

6

7

8

9

Recherche du plus court circuit hamiltonien dans GEntrée : un graphe G′ = (V ′,A′) et une fonction coût d ′ : A′ → R+

Sortie : un circuit c dans G′ tel queChaque sommet de V ′ apparaît exactement une fois dans cLa somme des coûts des arcs de c est minimale

; Problème NP-difficile bien connu : le voyageur de commerce !9/32


Reformulation du problème de calcul de tournée

Calcul du graphe des plus courts chemins G′ :Entrée : G = (V ,A), L ⊆ V , e ∈ V , p : L→ N et d : A→ R+

Sortie : G′ = (V ′,A′) et d ′ : A′ → R+ tels que

V ′ = L ∪ {e}A′ = {(e, i)|i ∈ L,pi est minimal}

∪ {(i , j) ∈ L× L|pi = pj ∨ pj = pi + 1}∪ {(i ,e)|i ∈ L,pi est maximal}

d ′ij = longueur du plus court chemin

de i à j dans G

e

1

2

3

4

5

6

7

8

9

Recherche du plus court circuit hamiltonien dans GEntrée : un graphe G′ = (V ′,A′) et une fonction coût d ′ : A′ → R+

Sortie : un circuit c dans G′ tel queChaque sommet de V ′ apparaît exactement une fois dans cLa somme des coûts des arcs de c est minimale

; Problème NP-difficile bien connu : le voyageur de commerce !9/32

Le voyageur de commerce en programmation par contraintes Problèmes d’optimisation sous contraintes

Plan du cours

1 Optimisation de tournées de livraison

2 Le voyageur de commerce en programmation par contraintesProblèmes d’optimisation sous contraintesProgrammation par contraintesCode Choco fourni pour le projet

10/32


Rappels (cf Aide à la décision / M. Miquel)

Modèle mathématique d’un problème d’optimisation sous contraintes :

; Quadruplet (X ,D,C,F ) tel queX = ensemble de variables (inconnues du problème)D = fonction associant à chaque variable un ensemble de valeurs; D(xi) = domaine de xi = ensemble des valeurs que xi peut prendreC = contraintes du problème; Contrainte = relation entre des variables de X; Restreint les valeurs pouvant être affectées à ces variablesF : X → R = fonction objectif

But du jeu :

Affecter une valeur à chaque variable de sorte queChaque variable soit affectée à une valeur de son domaineToutes les contraintes de C soient satisfaitesF soit maximisée (ou minimisée)

11/32


Quelques cas particuliers

Pas de contraintes : C = ∅; Problème d’optimisation

Pas de fonction objectif : F = 0; Problème de satisfaction de contraintes (CSP)

Domaines de D discrets (énumérables); Problème combinatoire

F linéaire, D = R et C = ensemble d’inéquations linéaires; Problème d’optimisation linéaire (programmation linéaire)

F linéaire, D = Z et C = ensemble d’inéquations linéaires; Problème d’optimisation linéaire en nombres entiers

F linéaire, D = {0,1} et C = ensemble d’inéquations linéaires; Problème de sac-à-dos multidimensionnel

F quadratique, D = R et C = ensemble d’inéquations linéaires; Problème d’optimisation quadratique (programmation quadratique)

...12/32


Très très nombreuses applications

Conception d’emplois du temps, affectation de ressources

Ordonnancement de tâches

Tournées de véhicules, voyageur de commerce

Découpe de pièces, chargement de véhicules

Optimisation du trafic (avions, trains, voitures, frêt, ...)

...

et développement durable !

cf Cours de M. Miquel pour des exemples...

13/32


Complexité

Certains cas particuliers ont des complexités polynomiales :Programmation linéaire (domaines continus)2-SATProblème d’affectation / couplage maximalQuelques problèmes dans les graphes :ACM, Plus courts chemins, Coupure minimale/Flot maximal, ......

Ils sont bien souvent NP-difficiles :Programmation linéaire en nombres entiers, Sac-à-dosSAT, 3-SAT, Planar-3-SAT, ...Nombreux problèmes dans les graphes :Coloriage, Voyageur de commerce, Cliques/Stables, ...CSP finis (contraintes quelconques)...

Dans certains cas, ils sont indécidables :Equations diophantiennesCSP continus (contraintes quelconques)...

14/32


Difficulté des problèmes NP-difficiles ?

Croissance exponentielle :

n 2n Temps (si 109 instr/seconde)30 ≈ 109 ≈ 1 seconde40 ≈ 1012 ≈ 16 minutes50 ≈ 1015 ≈ 11 jours60 ≈ 1018 ≈ 32 ans70 ≈ 1021 ≈ 317 siècles

15/32


Et en pratique ?

Certaines instances de problèmes NP-complets peuvent être faciles; Notion de transition de phase

Certains problèmes NP-difficiles admettent des cas particuliers qui ontdes complexités polynomiales

Certains problèmes NP-difficiles sont approximables en tempspolynomial (avec garantie sur l’erreur)

Sinon, on peut explorer l’espace de recherche de façon “intelligente" :

Contenir l’explosion en structurant et filtrant l’espaceContourner l’explosion en faisant des impasses

16/32


Méthodes complètes : Contenir l’explosion combinatoire

Branch & Bound & Propagate

Branch : Structurer l’espace derecherche en arbreElaguer les branches de l’arbre :

Bound : Calcul de bornes sur lafonction objectifEx. : Solution sur R en prog.linéairePropagate : Propagation descontraintes pour réduire lesdomaines

Utiliser des heuristiques d’ordreChoix de la prochaine variable àinstancierChoix de la valeur à affecter àcette variable

Ex : pb des 4 reines

=> élagage

D(x3) vide

D(x4) vide

=> élagage

17/32


Méthodes incomplètes : Contourner l’explosion combinatoire

Exploration guidée par des heuristiquesIntensification de la recherche autour des zones “prometteuses"Diversification pour découvrir de nouvelles zones

Deux familles d’approches incomplètesPerturbatives : modification de combinaisons existantes

Ex : Recherche locale (LS), Algorithmes génétiques (GA),Optimisation par essaims de particules (PSO), ...

Constructives : construction de nouvelles combinaisonsEx : Optimisation par colonies de fourmis (ACO), Algorithmes parestimation de distribution (EDA), ...

Exemple de recherche locale pour le problème des 8 reines :

18/32

Le voyageur de commerce en programmation par contraintes Programmation par contraintes

Plan du cours



19/32


La programmation par Contraintes (CP)

"Constraint programming represents one of the closest approaches computerscience has yet made to the Holy Grail of programming : the user states theproblem, the computer solves it."

Eugene C. Freuder

En pratique : “CP = Model + Search"

Model = Description du problème

Déclaration des variables et de leurs domainesDéclaration des contraintesEventuellement : Déclaration d’une fonction objectif

Search = Exploration de l’espace de recherche

Utilisation d’algorithmes intégrésPossibilité de guider la recherche par des heuristiquesPossibilité de définir de nouvelles stratégies

Pas toujours aussi efficace qu’un programme « cousu main »... mais tellement plus vite développé !

20/32


Langages et environnements de programmationpar Contraintes

ALICE [Jean-Louis Laurière, 1976]; Premier système à base de contraintes

CHIP, Prolog V, Gnu-Prolog; Extensions de Prolog

CHOCO (Java), Gecode (C++), OR-Tools (C++); Bibliothèques open source

OPL Development Studio (IBM); Langage de modélisation + CP + MIP

Comet (Dynadec); Langage de modélisation + CP + CBLS + MIP

...

21/32


Exemple de programme linéaire en OPL

[Programme extrait du manuel utilisateur d’OPL (www.ibm.com)]22/32


Exemple de sac-à-dos en OPL

[Programme extrait du manuel utilisateur d’OPL (www.ibm.com)]23/32


Exemple de programme CBLS : les reines en Comet

[Programme extrait du tutoriel Comet (dynadec.com)]24/32


Le voyageur de commerce en CP

Variables : X = {nexti , costi | i ∈ V ′} de sorte que :La variable nexti donne le sommet visité après le sommet iLa variable costi donne le cout de l’arc (i ,nexti)

Domaines :D(nexti) = {j ∈ V ′ | (i , j) ∈ A′}

D(costi) = [minCosti ,maxCosti ]

Contraintes :Le cout associé à i est égal au coût de l’arc entre i et nexti :

∀i ∈ V , costi = di,nexti

Next doit définir un circuit :

circuit(next ,0)

Fonction objectif : F = min∑

i∈V ′ costi

25/32

Le voyageur de commerce en programmation par contraintes Code Choco fourni pour le projet

Plan du cours



26/32


Diagramme de classes

27/32


Code Choco : Déclaration des variables et contraintes

28/32


Code Choco : Résolution

29/32


Code de test : Comparaison avec Branch & Bound

Résultat de l’exécution du test :testBestSol: 3377 ms for Choco and 69303 ms for Branch and Bound

30/32


Code de test : Exécution sur une instance plus grosse

31/32


Résultat de l’exécution du test

32/32

Documents

Méthodologie de Développement Objet