View
8
Download
0
Category
Preview:
Citation preview
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Une approche interdisciplinaire pourl’ordonnancement des transports
Bernat GACIAS
Université Toulouse III - Paul SabatierLAAS-CNRS
25 Novembre 2010
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 1 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Contexte
Forte compétitivité entre entreprisesObjectifs :
Satisfaire les requêtes des clients → RéactivitéMinimisation des coûts
Organisation des transports :Planification de la flotteOptimisation des tournées
Problème très complexe :Contraintes : techniques, réglementaires, environnementaleset socialesGrande complexité algorithmique
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 2 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Objectifs de l’étude
Système d’aide à la décision (SAD) pour l’ordonnancementdes transports
Approche interdisciplinaire :Ingénierie CognitiveRecherche Opérationnelle
Caractéristiques du système :L’humain se situe au centre du processus de prise dedécisionsDynamique du domaineAssister l’humain dans chaque tâche
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 3 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Plan
1 Description du problème
2 Contexte de travail
3 Mécanisme de résolution
4 Assistance à l’opérateur dans la phase de résolution
5 Interfaces homme-machine
6 Conclusion et perspectives
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 4 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
1 Description du problème
2 Contexte de travail
3 Mécanisme de résolution
4 Assistance à l’opérateur dans la phase de résolution
5 Interfaces homme-machine
6 Conclusion et perspectives
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 5 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Problème de tournées de véhicules (VRP)
Déterminer les itinéraires à suivre par une flotte de véhicules detransport de manière à satisfaire un ensemble de requêtes clients
Problème NP-completContraintes des problèmes réels : contraintes de capacité desvéhicules, contraintes temporelles,. . .
routes
clientsdépôt
dépôt
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 6 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Architecture du Système d’Aide à la Décision
1 Une interface homme-machine basée sur une hiérarchied’abstraction issue d’une analyse du domaine
2 Un mécanisme de résolution avec des algorithmes efficaces
CSPInterface
EcologiqueVRPalgo.
Prise dedécisions
Propagationde contraintes
de résolutionMécanisme
Analysedu domainede travail
modèle
solution
dedonnées
Base
Homme
(WDA)
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 7 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
1 Description du problème
2 Contexte de travailAnalyse du domaine de travail (WDA)Analyse de tâches
3 Mécanisme de résolution
4 Assistance à l’opérateur dans la phase de résolution
5 Interfaces homme-machine
6 Conclusion et perspectives
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 8 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Analyse du domaine de travail (WDA)
Etape du Cognitive Work Analysis [Rasmussen et al.(1994) ;Vicente (1999)]
WDA : A travers une Hiérarchie d’Abstraction
Caractéristiques :Indépendance vis-à-vis des moyens et des événementsPertinence du point de vue psychologique du modèle obtenu
Approche proposée : Enumération des variantes du problèmede tournées de véhicules
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 9 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Processus
objetsliés aux
Objetsphysiques
Fonctionsliées auxobjectifs
Valeurset mesuresprioritaires
Objectifsfonctionnels
Disponibilité Demandes
Véhicules Conducteurs Marchandises Dépôts Clients
Fenêtres
clientsde temps
service
Temps de
conducteursde tempsFenêtres
Réseau
routier
Minimisation
des coûts de service
Qualité
la capacité
Gestion de
du temps
Gestion
du poids
Satisfaction Satisfaction
du volume itinéraires
Sélection Satisfaction de
contraintes
entre objets
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 10 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Analyse de tâches
Entretien avec deux planificateurs (entreprises de transportsécurisé)
Problème d’ordonnancement des transports
Sélectionde la
solution en temps réeldes tournées
GestionModélisation
du problème
Spécification
des
contraintes
Sélection
véhicules
des
Résolution
du problème
des clients
véhicules
Affectation
aux
Sélection
des
itinéraires
caractéristiques
et leurs
Spécification
des objets
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 11 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Répartition de fonctionsProcédure pour la répartition des fonctions dans les SAD [vanWezel et al. (2010)]
Humain
Manuel Consultatif Interactif Supervision Automatique
HumainHumain
Algorithme
AlgorithmeAlgorithme
Algorithme
Humain
Modélisation du problème → InteractifRésolution du problème → Consultatif, interactif ou desupervisionSélection de la solution finale → ManuelGestion des tournées en temps réel → Consultatif, interactifou de supervision
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 12 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
1 Description du problème
2 Contexte de travail
3 Mécanisme de résolutionProgrammation par contraintesAlgorithmes spécifiquesRésultats expérimentaux
4 Assistance à l’opérateur dans la phase de résolution
5 Interfaces homme-machine
6 Conclusion et perspectives
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 13 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Programmation par contraintes
Caractéristiques :Séparation des mécanismes d’analyse et de résolution1 contrainte - 1 algorithme (propagation et inversion)Contraintes secondaires et préférences
Contraintes initiales
(dynamique)
Nouvelles contraintes
Nouvelles situations
Prise dedécision
Propagationde contraintes
Problème desatisfaction
de contraintes
Définition
du problème
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 14 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Algorithmes spécifiques
Algorithmes pour la sélection de véhicules
1 Vérification de la faisabilité d’une solutionSatisfaction des contraintes de capacitéBorne inférieure (FTC, FTDe,. . .) → Evaluation
2 Minimisation du nombre de véhicules à utiliser1 type de contrainte de capacité : Algorithme en O(n)2 (ou plus) types de contraintes : Pb. NP-difficile ? ? ?
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 15 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Algorithmes spécifiques
Algorithmes pour l’affectation des clients
1 Vérification de la faisabilité après chaque affectation1 Vérification qu’il n’existe pas d’incompatibilité avec les
autres clients (O(n))2 Raisonnement énergétique (O(n3))3 Solution réalisable : Recherche arborescente basée sur les
divergences (LDS)2 Algorithme d’affectation
Sélection du client à affecter : Algorithme de “sweep” [Gillet
et Miller (1974)]
Sélection du véhicule : minimisation de la distance moyenneentre le client et les clients déjà affectés au véhicule
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 16 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Algorithmes spécifiques
Algorithmes pour la sélection des itinéraires
1 Algorithme de sélection des itinérairesMécanismes d’insertion “savings” et “regrets”
2 Optimisation des tournées de manière indépendanteLDS vs. CDS → Comparaison
3 Optimisation de la solution complète“Relocation” et “Exchange” [Savelsbergh (1992)]
Critères géographiques pour la sélection des voisinages
g2
g1
si d(Ci , g1) > d(Ci , g2) {Ci , R1, R2}
g2
g1
si d(Ci , g1) > d(Ci , Cj) {Ci , R1, R2}
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 17 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Borne inférieure pour le nombre de véhicules
C++ (Linux), 2 GHz, Ram 2 GoBornes très proches de la valeur optimaleTemps de calcul faibles
Instances NbOpt NVMoy NVMoyBI TCPU (s)C1-100 9 (9) 10 10 0.02C2-100 8 (8) 3 3 0.01R1-100 3 (12) 11.83 10 0.03R2-100 5 (11) 2.64 2 0.00RC1-100 0 (8) 11.5 9.38 0.02RC2-100 0 (8) 3.25 2 0.00C1-200 7 (10) 18.8 18.2 0.1C2-200 10 (10) 6 6 0.03R1-200 9 (10) 18.1 18 0.13R2-200 10 (10) 4 4 0.03RC1-200 10 (10) 18 18 0.13RC2-200 8 (10) 4.3 4 0.03C1-400 6 (10) 37.6 36.4 1.41C2-400 3 (10) 11.7 11 0.11R1-400 9 (10) 36.2 36 1.91R2-400 10 (10) 8 8 0.12RC1-400 10 (10) 36 36 3.43RC2-400 7 (10) 8.5 8 0.12Total 124 (176)
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 18 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Comparaison entre LDS, CDS-V1 et CDS-V2
CDS est plus performante que LDSCDS-V2 est la méthode la plus efficace → exploite les aspectsphysiques du problème
10 stournee LDS CDS-V1 CDS-V2
Instances NbMeilleure EMoy NbMeilleure EMoy NbMeilleure EMoyC1-25 8 (9) 1.65 % 8 (9) 2.12 % 9 (9) 0.00 %C2-25 2 (8) 15.98 % 4 (8) 7.28 % 6 (8) 12.55 %R1-25 12 (12) 0.00 % 12 (12) 0.00 % 12 (12) 0.00 %R2-25 1 (11) 14.99 % 3 (11) 10.20 % 10 (11) 7.79 %RC1-25 8 (8) 0.00 % 8 (8) 0.00 % 8 (8) 0.00 %RC2-25 1 (8) 11.87 % 1 (11) 9.58 % 8 (8) 0.00 %C1-50 8 (9) 2.43 % 8 (9) 1.32 % 9 (9) 0.00 %C2-50 1 (8) 6.94 % 5 (8) 4.37 % 7 (8) 8.52 %R1-50 11 (12) 0.78 % 12 (12) 0.00 % 12 (12) 0.00 %R2-50 0 (11) 9.78 % 3 (11) 3.15 % 9 (11) 0.86 %RC1-50 7 (8) 0.53 % 7 (8) 0.53 % 8 (8) 0.00 %RC2-50 0 (8) 5.64 % 3 (8) 4.73 % 7 (8) 2.83 %C1-100 7 (9) 0.31 % 8 (9) 0.02 % 9 (9) 0.00 %C2-100 2 (8) 4.18 % 5 (8) 2.77 % 6 (8) 1.97 %R1-100 8 (12) 0.44 % 10 (12) 0.52 % 12 (12) 0.00 %R2-100 0 (11) 7.13 % 6 (11) 1.64 % 5 (11) 2.86 %RC1-100 6 (8) 0.17 % 6 (8) 0.18 % 8 (8) 0.0 %RC2-100 0 (7) 7.53 % 3 (7) 2.76 % 4 (7) 3.02 %
Total 82 (167) 6.58 % 112 (167) 5.21 % 149 (167) 4.23 %
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 19 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Optimisation de la solution complète
Algorithme d’optimisation locale d’une solution
Bonnes solutions obtenues assez rapidement (instances de type 1)
120 s, 300 s Sol. Opt. ou MSC RL+CDSInstances NV DIST NV DIST EMoy TMeilleureC1-25 3 190.59 3 190.59 0.00 % 0.81C2-25 2 214.45 1.63 231.89 8.13 % 33.15R1-25 4.92 463.37 4.92 472.43 1.12 % 2.37R2-25 2.73 382.15 2.09 411.47 7.62 % 64.59RC1-25 3.25 350.24 3.25 354.99 9.24 % 0.55RC2-25 2.88 319.28 2.38 384.5 20.32 % 62.3C1-50 5 361.69 5 368.99 9.05 % 21.48C2-50 2.75 339.75 2.13 560.23 69.56 % 65.89R1-50 7.75 766.13 8.42 821.32 7.02 % 35.2R2-50 3.82 615.41 2.27 895.87 45.03 % 60.01RC1-50 6.5 730.31 7.25 807.43 11.83 % 11.07RC2-50 3.88 571.68 2.5 904.66 58.07 % 55.16C1-100 10 826.7 10.44 936.18 13.24 % 97.49R1-100 13.25 1173.61 14.17 1329.17 14.31 % 264.05RC1-100 11.13 1341.33 13.25 1411.05 5.45 % 128.51
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 20 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
1 Description du problème
2 Contexte de travail
3 Mécanisme de résolution
4 Assistance à l’opérateur dans la phase de résolutionInversion de modèle
5 Interfaces homme-machine
6 Conclusion et perspectives
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 21 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Problèmes non-réalisables
Comment peut-on faire face à ces problèmes ?
Problème
sur−contraint
Problème non−réalisable
Relaxation
de contraintes
solutions trop vaste
Problème: Objectifs contradictoires
Modèle
simplifié
Algorithmed’optimisation:
Forte: Espace de
Evaluation
Sélectionà partir
des objectifs
complexité, critères,...
Légère: choix de l’ensemble
de contraintes à relâcher
Inversion de modèle : variables de décision → paramètresparamètres → variables de décision
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 22 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Problèmes non-réalisables
Comment peut-on faire face à ces problèmes ?
Problème
sur−contraint
Problème non−réalisable
Relaxation
de contraintes
solutions trop vaste
Problème: Objectifs contradictoires
Modèle
simplifié
Algorithme
complexité, critères,...d’optimisation:
Forte: Espace de Légère: choix de l’ensemble
de contraintes à relâcher
Evaluation
Sélectionà partir
des objectifs
paramètres → variables de décisionInversion de modèle : variables de décision → paramètres
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 22 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Mécanismes d’inversionMéthodologie
Phase de conception du système : Analyse des paramètres quiinterviennent dans les contraintes
Phase de résolution du problème : Chaque contrainte disposed’une procédure d’inversion du modèle
1 Identification des possibles paramètres à relâcher2 Application des méthodes de classification :
Critère géographiqueCritère temporel
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 23 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Méthodes de classificationCritère géographique (CG)
Construire des groupes de clients homogènes (variablescaractéristiques)Algorithme des centres mobiles (2D ; xi et yi) [Forgy (1965)]
Exemple
Dépôt
Etablir un critère de sélection selon la contrainte violéeBernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 24 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Méthodes de classificationCritère géographique (CG)
Construire des groupes de clients homogènes (variablescaractéristiques)Algorithme des centres mobiles (2D ; xi et yi) [Forgy (1965)]
G
Fixer Centres
Dépôt
g 12g 1
1
Etablir un critère de sélection selon la contrainte violéeBernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 24 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Méthodes de classificationCritère géographique (CG)
Construire des groupes de clients homogènes (variablescaractéristiques)Algorithme des centres mobiles (2D ; xi et yi) [Forgy (1965)]
Itération 1
G
Dépôt
g 11
g 12
Etablir un critère de sélection selon la contrainte violéeBernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 24 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Méthodes de classificationCritère géographique (CG)
Construire des groupes de clients homogènes (variablescaractéristiques)Algorithme des centres mobiles (2D ; xi et yi) [Forgy (1965)]
Itération 2
Dépôt
g 21
g 11
g 12
g 22
Etablir un critère de sélection selon la contrainte violéeBernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 24 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Méthodes de classificationCritère géographique (CG)
Construire des groupes de clients homogènes (variablescaractéristiques)Algorithme des centres mobiles (2D ; xi et yi) [Forgy (1965)]
Itération 2
Dépôt
g 11
g 12
g 21
g 22
Etablir un critère de sélection selon la contrainte violéeBernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 24 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Méthodes de classificationCritère géographique (CG)
Construire des groupes de clients homogènes (variablescaractéristiques)Algorithme des centres mobiles (2D ; xi et yi) [Forgy (1965)]
Itération 2
Dépôt
g 11
g 12
g 21
g 22
Etablir un critère de sélection selon la contrainte violéeBernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 24 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Méthodes de classificationCritère temporel (CT)
Indice dissimilarité (δ) : Mesurer le degré de centrage des FTAlgorithme des nuées dynamiques [Diday (1971)]
Groupes de clients dont les FT sont très prochesEtablir un critère de sélection selon la contrainte violée
0 1
disjointesnon inclusesinclusescentrées
δ(i , j)
i
−min(dj − ri , di − rj)di − rjdi − rjdi − rj
dj − ridj − ri dj − ri
i i i i
j j j j j
contigües
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 25 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
Problème à 7 clients Ci avec FT [ri , di ]
BInv = 3 dû aux FTV (C3) 6= V (C4)V (C3) 6= V (C6)V (C4) 6= V (C6)
L’utilisateur propose une solution avec 2 véhicules → nonréalisable
C1
C5
C7
Dépôt
C2
C3C4
C6
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 26 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
1 Identification des contraintes à relâcher2 Critère géographique3 Critère temporel4 L’opérateur humain choisit la décision la plus pertinente
C1
C5
C7
Dépôt
C2
C3C4
C6
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 27 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
1 Identification des contraintes à relâcherAnnulation de service pour C3, C4 ou C6Modification des fenêtres de temps de C3, C4 ou C6
C1
C5
C7
Dépôt
C2
C3C4
C6
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 27 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
1 Identification des contraintes à relâcherAnnulation de service pour C3, C4 ou C6
2 CG : Algorithme des centres mobiles
C1
C5
C7
Dépôt
C2
C3C4
C6
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 27 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
1 Identification des contraintes à relâcherAnnulation de service pour C3, C4 ou C6
2 CG : Algorithme des centres mobilesCalcul de la distance moyenne entre chaque client et les autresclients du cluster (dmi )Les valeurs de dmi donnent une liste de clients à supprimer duproblème → C6 (dm6 > dm4 > dm3)
C1
C5
C7
Dépôt
C2
C3C4
C6
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 27 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
1 Identification des contraintes à relâcherAnnulation de service pour C3, C4 ou C6
2 CG : Algorithme des centres mobilesCalcul de la distance moyenne entre chaque client et les autresclients du cluster (dmi )Les valeurs de dmi donnent une liste de clients à supprimer duproblème → C6 (dm6 > dm4 > dm3)
C1
C5
C7
Dépôt
C2
C3C4
C6
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 27 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
1 Identification des contraintes à relâcherAnnulation de service pour C3, C4 ou C6
2 Critère géographique → C6
3 CT : Algorithme des nuées dynamiques
7 Clients3 Groupes
1
3
2
2
2
3
t
2
d1
d5
r1
r2
r3 d3
d4
d2
r4
r5
r7 d7
r6 d6
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 27 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
1 Identification des contraintes à relâcherAnnulation de service pour C3, C4 ou C6
2 Critère géographique → C63 CT : Algorithme des nuées dynamiques
1 Identification des ensembles de clients les plus conflictuels(|Pk | ≥ 2× nv) → Groupe 2 (C2, C3, C4 et C6)
7 Clients3 Groupes
1
3
2
2
2
3
t
2
d1
d5
r1
r2
r3 d3
d4
d2
r4
r5
r7 d7
r6 d6
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 27 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
1 Identification des contraintes à relâcherAnnulation de service pour C3, C4 ou C6
2 Critère géographique → C63 CT : Algorithme des nuées dynamiques
1 Identification des ensembles de clients les plus conflictuels(|Pk | ≥ 2× nv) → Groupe 2 (C2, C3, C4 et C6)
2 Centres mobiles pour les clients du Groupe 2 → C4
(dm4 > dm3 > dm6)
C2
Depot
C3C4
C6
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 27 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Scénario
1 Identification des contraintes à relâcherAnnulation de service pour C3, C4 ou C6
2 Critère géographique → C6
3 Critère temporel → C4
4 L’opérateur humain choisit le client à supprimer du problème
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 27 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Résultats expérimentaux
56 instancesnc = 9 NbOptDist DevMoy MoyPos NbSolCG-C 13 (17) 8.73 % 2.7 6CG-R 9 (23) 5.99 % 3.5 17CG-RC 9 (16) 5.01 % 3.2 5CT-C 5 (17) 14.98 % 4.5 7CT-R 3 (23) 11.46 % 5.4 7CT-RC 4 (16) 9.30 % 5.3 7DD-C 8 (17) 15.76 % 4.3 8DD-R 5 (23) 10.97 % 4.7 11DD-RC 3 (16) 9.12 % 4.5 4CS 32 6.83 % 3.54 30Total (3 critères) 37 38
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 28 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
1 Description du problème
2 Contexte de travail
3 Mécanisme de résolution
4 Assistance à l’opérateur dans la phase de résolution
5 Interfaces homme-machineInterfaces du système d’aide à la décisionEvaluation de l’interface pour la sélection de la solution finale
6 Conclusion et perspectives
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 29 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Interfaces du système d’aide à la décision
Interfaces pour la modélisation du problèmeLangage naturel et compréhensibleFlexibles et d’utilisation facile (définition, suppression,modification)
Interfaces pour la résolution du problèmeAffichage de l’information nécessaire pour la résolutionL’opérateur humain peut participer directement à laconstruction de la solutionTrois modes de contrôle
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 30 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Interfaces pour la résolution du problème
Sélection desvéhicules
Information sur lescontraintes decapacitéProposition dedifférentes solutions
Affectation desclients aux véhicules
Information sur objetset contraintesOutils d’interactionarticulés avec lesalgorithmes
Sélection desitinéraires
Information sur lestournéesInterface pour lacomparaison destournées
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 31 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Interfaces pour la sélection de la solution finale
Conception écologique d’interfaces :Favorise un traitement de l’information basé sur le couplageperception-actionPertinence psychologique : une HA est affichée de manièreperceptivement évidente pour aider l’opérateur humain dansson analyse
Interface de manipulation directe
Interface perceptive et abrégée :solutions affichées de manière simultanéeles différences entre solutions (information fonctionnelle)sont perceptivement évidentes pour l’opérateur
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 32 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Interfaces pour la sélection de la solution finale
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 33 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Interfaces pour la sélection de la solution finale
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 33 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Interfaces pour la sélection de la solution finale
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 33 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Interfaces pour la sélection de la solution finale
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 33 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Présentation de l’expérience
Les participants (12) doivent sélectionner la meilleure solution
Scénarios :Contrainte objectifsContrainte moyens
Comparaison d’interfaces :Analytique vs. PerceptiveIntégrale vs. Abrégée
Paramètres de mesureTemps nécessaire pour sélectionner la meilleure solutionCharge Mentale : NASA-TLXQualité de la solution
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 34 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Résultats de l’expérienceAnalytique vs. Perceptive
(a) Temps (b) Charge Mentale (c) Performance
L’interface perceptive favorise le processus de résolution :réduction du tempset de la charge mentale ? → les résultats sont moins évidentsmeilleure performance (même pour les scénarios aveccontraintes liées aux moyens)
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 35 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Résultats de l’expérienceIntégrale vs. Abrégée
(d) Temps (e) Charge mentale (f) Performance
L’interface abrégée est plus efficiente1 seule l’information fonctionnelle est nécessaire pour la
sélection des solutions2 l’information physique n’est pas affichée de manière
perceptivement évidente
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 36 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
1 Description du problème
2 Contexte de travail
3 Mécanisme de résolution
4 Assistance à l’opérateur dans la phase de résolution
5 Interfaces homme-machine
6 Conclusion et perspectives
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 37 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Conclusion
Approche interdisciplinaire pour la conception d’un SAD pourl’ordonnancement des transports
L’opérateur humain participe à la modélisation et à larésolution du problèmeLe SAD est bien adapté au contexte dynamique du problèmeDes outils spécifiques ont été proposés pour aiderl’opérateur dans la réalisation de chaque sous-tâche
Inversion du modèle : cadre de travail pour le guidage del’opérateur lorsque le problème est non-réalisable
Evaluation d’une des interfaces proposées au travers d’uneexpérience
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 38 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Perspectives
Evaluer le SAD dans un contexte de coopération H-M
Finaliser le mécanisme d’inversion de modèle
Finaliser la réalisation du système d’aide à la décision :Gestion des tournées en temps réel (algorithmes etinterfaces)
Evaluer la pertinence de l’approche pour la conception duSAD dans d’autres domaines : ordonnancement d’atelier,timetabling,. . .
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 39 / 40
Problème Contexte de travail Mécanisme de résolution Assistance à l’opérateur Interfaces homme-machine Conclusion
Merci pour votre attention
Bernat GACIAS Une approche interdisciplinaire pour l’ordonnancement des transports 40 / 40
Recommended