Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Boite à outils PDF Recherche Aide Contact



a imprimer .pdf



Nom original: a imprimer.pdf

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.13, et a été envoyé sur fichier-pdf.fr le 14/08/2013 à 11:22, depuis l'adresse IP 88.162.x.x. La présente page de téléchargement du fichier a été vue 1296 fois.
Taille du document: 4.8 Mo (92 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Institut Supérieur d'Informatique
de Modélisation et de leurs
Applications.

Université de Technologie de
Troyes

24 Avenue des Landais
BP 10 125
63 173 AUBIERE CEDEX.

12 rue Marie Curie
CS 42060
10004 TROYES CEDEX

Rapport de stage de troisième Année
Filière Systèmes d'Information et Aide à la Décision

Problèmes de tournées de véhicules avec profits dépendants
de la période de service

Présenté par : Ludovic DRUGBERT
Responsables UTT : Monsieur Murat Afsar et Madame Nacima Labadie
Responsable ISIMA : Monsieur Philippe Lacomme

Durée 5 mois

Institut Supérieur d'Informatique
de Modélisation et de leurs
Applications.

Université de Technologie de
Troyes

24 Avenue des Landais
BP 10 125
63 173 AUBIERE CEDEX.

12 rue Marie Curie
CS 42060
10004 TROYES CEDEX

Rapport de stage de troisième Année
Filière Systèmes d'Information et Aide à la Décision

Problèmes de tournées de véhicules avec profits dépendants
de la période de service

Présenté par : Ludovic DRUGBERT
Responsables UTT : Monsieur Murat Afsar et Madame Nacima Labadie
Responsable ISIMA : Monsieur Philippe Lacomme

Durée 5 mois

Remerciements
Avant tout développement sur mon travail, je souhaite commencer ce rapport par des remerciements et tiens à assurer de toute ma gratitude ceux qui m'ont aidé pour ce stage de troisième
année.
C'est dans ce cadre que je tiens à remercier très sincèrement,

M. Murat Afsar et Mme

Nacima Labadie, responsables UTT, pour l'accueil qu'ils m'ont o ert, pour m'avoir suivi tout
au long de ces cinq mois ainsi que pour m'avoir proposé ce sujet et donné toutes les informations
nécessaires pour le réaliser. Je les remercie aussi pour leur présence et leur disponibilité tout au
long du stage.
Je tiens également à remercier M.

Philippe Lacomme, mon tuteur ISIMA, qui s'est assuré

que mon stage se déroulait dans de bonnes conditions.
Je leur suis très reconnaissant de m'avoir toujours accompagné à chaque fois dont j'ai eu
besoin. Leurs remarques, leur disponibilité ainsi que leurs conseils m'ont été très béné ques.
En n, je tiens à remercier les chercheurs, les enseignants et les doctorants que j'ai eu l'occasion
de fréquenter tout au long du stage pour leur patience et leur disponibilité.

DRUGBERT Ludovic

5

2013

TABLE DES FIGURES

Table des gures
1

Planning prévisionnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2

Exemple du T SP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3

Exemple du V RP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

4

Exemple d'une solution de l'OP . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

5

Exemple d'une solution du T OP . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

6

Exemple d'une solution du T OP tw . . . . . . . . . . . . . . . . . . . . . . . . . .

28

7

Exemple d'une solution du T OP twP DP sur une instance de 100 clients et un
horizon de temps composé de 4 périodes . . . . . . . . . . . . . . . . . . . . . . .

31

8

Exemple 2OP T Interne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

9

Exemple 2OP T Externe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

10

Exemple Relocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

11

Exemple Exhange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

12

Exemple Forward OrExchange . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

13

Schéma des deux espaces de travail . . . . . . . . . . . . . . . . . . . . . . . . . .

50

14

Exemple d'un croisement sur deux parents P1 et P2 . . . . . . . . . . . . . . . . .

52

15

Exemple d'une sélection par Roulette de Casino sur 7 individus . . . . . . . . . .

52

16

Exemple d'une sélection N/2 Elitisme et par Tournoi . . . . . . . . . . . . . . . .

53

17

Exemple d'un résultat du Split sur un tour géant composé de 9 Clients . . . . . .

54

18

Exemple d'un Split ou les périodes sont ordonnées . . . . . . . . . . . . . . . . .

56

19

Exemple d'une solution composée de deux tournées . . . . . . . . . . . . . . . . .

57

20

Exemple d'un Split sur tournée saturée avec périodes ordonnées . . . . . . . . . .

58

21

Exemple d'un Split sur tournée non saturée avec périodes ordonnées . . . . . . .

58

22

Exemple d'un Split sur tournée non saturées . . . . . . . . . . . . . . . . . . . . .

58

23

Exemple de concaténation d'une solution composée de deux tournées . . . . . . .

59

24

Schéma global du GRASP xELS . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

25

Exemple Split . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

26

Exemple Split avec Fenêtres di érentes sur tournées saturées . . . . . . . . . . . .

68

27

Exemple Split avec Fenêtres di érentes sur tournées non saturées . . . . . . . . .

69

28

In uence du paramètre n sur l'heuritisque d'insertion . . . . . . . . . . . . . . . .

70

29

In uence du paramètre m sur l'heuritisque d'insertion . . . . . . . . . . . . . . .

70

30

In uence du paramètre q sur l'heuritisque d'insertion . . . . . . . . . . . . . . . .

71

DRUGBERT Ludovic

6

2013

TABLE DES FIGURES
31

Exemple graphique d'une solution au T OP twP DP sur une période donnée . . .

72

32

Exemple graphique d'une solution au T OP twP DP sur une période donnée . . .

73

DRUGBERT Ludovic

7

2013

LISTE DES TABLEAUX

Liste des tableaux
1

Méthodes Exactes pour l'OP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2

Méthodes Heuristiques pour l'OP . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3

Méthodes Métha-Heuristiques pour l'OP . . . . . . . . . . . . . . . . . . . . . . .

26

4

Liste des pro ts pour les clients de la solution H . . . . . . . . . . . . . . . . . .

57

5

Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

6

Comparaisons sur l'instance r201 . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

7

Comparaisons avec le T OP tw . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

8

Liste des pro ts pour le tour géant π avec une période . . . . . . . . . . . . . . .

67

9

Liste des pro ts pour le tour géant π avec deux périodes . . . . . . . . . . . . . .

68

DRUGBERT Ludovic

8

2013

1 RÉSUMÉ ET ABSTRACT

1 Résumé et Abstract
Résumé

Ce stage explore le problème du Team Orienteering Problem with Time Windows and

Period Dependant Pro ts (T OP twP DP) qui lui-même est une extension du Multi-period
Orienteering Problem with Time Windows (M uP OP tw) et du Team Orienteering Problem with Time Windows (T OP tw). Pour résoudre ce nouveau problème de tournées de véhicules, j'ai implémenté plusieurs méta-heuristiques, tel qu'un algorithme Mémétique, un GRASP,
un GRASPxELS ou encore une ILS sur des instances modi ées du T OP tw.
Dans un premier temps, j'ai fait un état de l'art sur des problèmes connexes en regroupant
les articles les plus pertinents. Ensuite, j'ai conçu de nouvelles instances de tests adaptées à mon
problème et basées sur des instances connues du T OP tw. J'ai tenté de les résoudre grâce à un
solveur de programmation linéaire. Les temps d'attentes n'étant pas raisonnables, je suis partie
sur un algorithme mémétique constitué d'une procédure de découpage nommée Split et d'une
recherche locale basée sur des mouvements fréquemment utilisés dans les problèmes de tournées
de véhicules. J'ai aussi implémenté un GRASP (Greedy randomized adaptive search procedure),
dans sa version la plus simple, un GRASP xELS (GRASP hybridé par une méthode ELS ou
Evolutionary Local Search) et en n une ILS (Iterated Local Search), tous constitués de la même
recherche locale.
Les résultats sont encourageants. Nous utilisons, pour comparer les méta-heuristiques, un
système de budget autorisant chacune d'entre elle à un nombre limité de recherche locale. On
montre alors un léger avantage pour le Mémétique en terme de fonction objective.

Mot-clés : Multi Period Team Orienteering, Period Dependent Pro ts, Time Windows, Algorithme Mémétique, GRASP , GRASP xELS , ILS , Variable Neighborhood Descent.

DRUGBERT Ludovic

9

2013

1 RÉSUMÉ ET ABSTRACT
Abstract

Team Orienteering Problem with Time Windows
and Period Pro t Dependent (T OP twP DP ), which itself is an extension of Multi-period
Orienteering Problem with Time Windows (M uP OP tw) and Team Orienteering Problem with Time Windows (T OP tw). To solve this new vehicle routing problem, I implemenThis course explores the problem of

ted several meta-heuristics, such as Memetics, a GRASP , a GRASP xELS or a ILS on modi ed
instances of T OP tw.
At rst, I was a state of the art related problems by combining the most relevant articles.
Then I created new instances of tests adapted to my problem and based on the known T OP tw
instances. I tried to solve through a linear programming solver. The waiting time is not reasonable, I went on a memetic algorithm consisting of a cutting procedure called Split and a
local search based on commonly utiliss movements in routing problems vehicles. I also implemented a GRASP (greedy randomized adaptive search procedure), in its simplest version, a
GRASP xELS (GRASP hybridized by Evolutionary Local Search method) and nally an ILS

(Iterated Local Search), all made from the same local search.
The results are encouraging. We use to compare the meta-heuristics, a budget system each
allowing a limited number of local search. A slight advantage for the Memetics is then shown in
terms of objective function.

Keywords : Multi Period Team Orienteering, Period Dependent Pro ts, Time Windows, Memetic algorithm, GRASP , GRASP xELS , ILS , Variable Neighborhood Descent.

DRUGBERT Ludovic

10

2013

TABLE DES MATIÈRES

Table des matières
1 Résumé et Abstract

9

2 Introduction

14

3 Contexte

15

3.1 Le laboratoire LOSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.2 Intérêt du stage dans le cadre de la formation ingénieur . . . . . . . . . . . . . .

16

3.3 Planning prévisionnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.4 Organisation du rapport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

4 Les di érents problèmes de tournées de véhicules

19

4.1 Le T SP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

4.2 Le V RP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.3 Les problèmes d'orienteering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

4.3.1

Orienteering Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

4.3.2

Team Orienteering Problem . . . . . . . . . . . . . . . . . . . . . . . . . .

26

4.3.3

Team Orienteering Problem with Time Windows . . . . . . . . . . . . . .

28

4.3.4

Multi Period Orienteering Problem with multi Time Windows . . . . . . .

30

5 Le Team Orienteering Problem with Time Windows and Period Dependent
Pro t
31
5.1 Formalisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

5.2 Modèle mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

5.2.1

Données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

5.2.2

Variables de décisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

5.2.3

Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

5.3 Programme linéaire en nombre entiers . . . . . . . . . . . . . . . . . . . . . . . .

34

5.4 Heuristique d'insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

5.5 Les accélérateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

5.6 La Recherche Locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

5.6.1

2OPT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

DRUGBERT Ludovic

42

5.6.1.a

2OPT Interne . . . . . . . . . . . . . . . . . . . . . . . . .

42

5.6.1.b

2OPT Externe . . . . . . . . . . . . . . . . . . . . . . . .

43

11

2013

TABLE DES MATIÈRES
5.6.2

Relocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

5.6.3

Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

5.6.4

Forward OrExchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

5.6.5

Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

5.6.6

Suppression Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

5.6.7

Structure algorithmiques . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

6 Approches méta-heuristiques pour le T OP twP DP
6.1 Algorithme Mémétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49
49

6.1.1

Population Initiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

6.1.2

Croisement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

6.1.3

La sélection des parents . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

6.1.4

Split . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

6.1.4.a

Split avec tournée saturée et période imposée . . . . . . .

56

Concaténation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

6.2 ILS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

6.3 GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

6.4 GRASP xELS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

6.1.5

7 Résultats

63

7.1 Les instances utilisées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

7.2 Utilisation d'un solveur du commerce CPLEX . . . . . . . . . . . . . . . . . . . .

63

7.3 Les méta-heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

7.4 Comparaisons avec le T OP tw . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

8 Prolongement

67

8.1 Fenêtre dépendante de la période . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

8.2 Heuristique d'insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

8.3 Parallélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

9 Utilisation de Qt et interface graphique

72

10 Conclusion

74

11 Lexique

75

DRUGBERT Ludovic

12

2013

TABLE DES MATIÈRES

12 Annexes

DRUGBERT Ludovic

79

13

2013

2 INTRODUCTION

2 Introduction
Dans le cadre de la troisième année du cursus ingénieur ISIMA, j'ai e ectué mon stage au sein
du laboratoire LOSI de l'Université technologique de Troyes. J'ai développé, sous la direction de

Mme Nacima labadie et Mr Murat Afsar et sur une période s'étendant du 01 avril au 30
août 2013, plusieurs méta-heuristiques permettant de résoudre des instances du T OP twP DP .
Ce stage s'inscrit dans ma formation d'ingénieur informaticien dans le domaine de la Recherche
Opérationnelle et de l'Aide à la décision.
Les algorithmes de calcul de tournées sont utilisés dans les moteurs des logiciels d'optimisation
de tournées. Ces solutions sont utilisées par des entreprises qui souhaitent rationaliser leur otte
de véhicules, réduire leurs coûts ou encore optimiser l'occupation de leur personnel mobile. La
fonction d'optimisation de tournée peut aussi être intégrée dans des solutions de plani cation de
ressources mobiles. Ces solutions ont pour vocation de plani er des tâches ou missions avec ou
sans prise de rendez-vous, et de les répartir entre les ressources en fonction de leurs contraintes
(disponibilité, localisation, compétences requises, durées d'interventions, etc.)
Ce rapport présente tout d'abord le contexte du stage et l'état de l'art sur des problèmes
connexes au mien. Ensuite, je détaille les di érentes étapes du stage. Après présentation des
di érentes méthodes de résolutions développées dans le cadre de ce stage, une comparaison
détaillée des résultats obtenus a été e ectuée a n de mesurer la pertinence et l'e cacité de ces
dernières.

DRUGBERT Ludovic

14

2013

3 CONTEXTE

3 Contexte
3.1

Le laboratoire LOSI

Le Laboratoire d'Optimisation des Systèmes Industriels (LOSI) a été créé en septembre 1997
comme équipe universitaire. Il est devenu en 2000 Jeune équipe (JE 2304) du Ministère de la
recherche. En 2004, il s'est regroupé avec le LM2S et le Tech-CICO pour former l'Institut de
Sciences et Technologies de l'Information de Troyes, unité de recherche associée au CNRS avec
le statut FRE (FRE 2732). Depuis le 1er janvier 2006, l'équipe Optimisation des Systèmes
Indusriels est une équipe de recherche de l'Institut Charles Delaunay.
L'objectif de l'équipe est de développer des outils d'aide à la décision dans le domaine de la
gestion de systèmes logistiques et de production pour optimiser les performances de ces systèmes,
en terme de compétitivité et de niveau de service aux clients, en tenant compte de toutes les
contraintes sociales, réglementaires, techniques, nancières, etc. A partir d'une description du
système à étudier, qu'il soit en phase de conception ou en phase opérationnelle, et du ou des
critères (mesures de performances) à optimiser, il s'agit de construire des modèles mathématiques,
qui sont ensuite analysés pour identi er des ensembles de solutions prometteuses, en fonction des
paramètres et/ou des données d'entrée. Des algorithmes de résolution sont ensuite développés
pour trouver des solutions optimales ou satisfaisantes parmi ces ensembles prometteurs. Ces
algorithmes sont implémentés sous forme de programmes informatiques qui permettent d'assister
les décideurs à trouver une solution qui leur convient. Ces décisions peuvent concerner aussi bien
le niveau stratégique, comme la conception de réseaux de transport ou l'implantation de sites
ou de plate-formes logistiques, que les niveaux tactiques et opérationnels, comme la plani cation
d'approvisionnement ou de production, l'ordonnancement de la production ou les tournées de
véhicules.
L'équipe développe sa recherche selon deux axes principaux :


Système logistique : Prise en compte des relations entre les entreprises et leurs environnements logistiques, notamment avec les fournisseurs, les clients et les prestataires de
service, avec une place particulière pour le transport : conception de réseaux de transport
et de distribution, implantation de sites de production et/ou de plate-formes logistiques,
plani cation de l'approvisionnement et de production, optimisation des tournées.



Système de production : Optimisation de fonctionnement interne d'une entreprise :
plani cation et ordonnancement de la production, agencement d'atelier, conception de

DRUGBERT Ludovic

15

2013

3 CONTEXTE
systèmes de production ou de lignes de fabrication, optimisation de découpe à une ou deux
dimensions, chargement de moyens de transport dans la distribution, aménagement des
zones de stockage.
Pour la résolution de problèmes d'optimisation qui se posent dans les systèmes logistiques
et de production (de biens ou de services), l'équipe rassemble des spécialistes en modélisation,
analyse, optimisation, évaluation et simulation des systèmes, et développe de nombreuses collaborations avec le monde académique international et le monde socio-économique. De nombreux
logiciels ont été développés en interne pour les systèmes logistiques ou de production.
3.2

Intérêt du stage dans le cadre de la formation ingénieur

La Recherche Opérationnelle est une composante importante dans la formation d'ingénieur
en informatique décisionelle. S'intégrer à un groupe de travail dans ce domaine permet de mettre
en oeuvre les connaissances théoriques et d'acquérir les compétences dans le développement de
programmes et l'analyse de données. De plus, travailler dans le monde de la recherche donne
accès aux connaissances et techniques les plus récentes. Cela constitue une valeur ajoutée réelle
à notre cursus de formation ingénieur.
3.3

Planning prévisionnel

La plani cation du projet doit bien entourer toutes les étapes d'étude et de réalisation. Le
projet étant réparti sur plusieurs domaines, il m'a fallu adopter une plani cation pour bien cerner
les étapes de réalisation. Avant même de me lancer dans la programmation, j'ai commencé par
dresser un planning prévisionnel du déroulement de mon stage.
Cette plani cation est conforme aux phases du projet ainsi qu'aux objectifs attendus. Au
cours de cette période, un ensemble de points de contrôle sont mis en place pour établir un suivi
du déroulement des di érentes étapes. Cependant, la plani cation du début n'était pas aussi
détaillée que le diagramme représenté en gure 1, où j'ai ajouté, au fur et à mesure, les détails
et les fonctions pour chaque étape.
3.4

Organisation du rapport

Le rapport est organisée comme suit : Je vais d'abord dresser une présentation des problèmes
de tournées de véhicules suivi d'un état de l'art sur les problèmes d'orienteering (OP pour Orienteering Problem). Je présente ensuite le nouveau problème du
DRUGBERT Ludovic

16

Team Orienteering Problem
2013

3 CONTEXTE

with Time windows And Period Dependant Pro t (T OP twP DP ) étudié dans ce stage, sa
formulation mathématique et les méthodes de résolution que nous avons conçues. Il s'agit d'une
heuristique constructive simple et de quatre méta-heuristiques : un algorithme mémétique, une
recherche adaptive randomisée (GRASP ) ainsi qu'une méthode hybride de type GRASP xELS
et en n une ILS . Ces méthodes ont fait l'objet de comparaisons minutieuses sur un ensemble
d'instances issues de la littérature.

DRUGBERT Ludovic

17

2013

3 CONTEXTE

Figure 1 Planning prévisionnel
DRUGBERT Ludovic

18

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES

4 Les di érents problèmes de tournées de véhicules
Les problèmes de tournées de véhicules constituent une classe de problèmes de recherche
opérationnelle et d'optimisation combinatoire. Il s'agit de déterminer les tournées d'une otte de
véhicules a n de livrer une liste de clients, ou de réaliser des tournées d'interventions (maintenance, réparation, contrôles) ou de visites (visites médicales, commerciales, etc.). Le but est de
minimiser le coût de livraison (ou de collecte) des biens des entreprises concernées par l'optimisation de tournées qui peuvent couvrir les secteurs d'activités suivants :
Livraison (ou collectes) de biens à des entreprises ou à des particuliers : transporteurs, messageries (distribution de presse), grandes surfaces (livraison de marchandises des entrepôts
aux magasins, livraison et installation d'équipement à domicile), etc.
Réparation et maintenance d'équipements de particuliers (électroménager, chaudières),
d'équipements collectifs (ascenseurs, tapis roulants) ou d'entreprises (distributeurs automatiques, équipements industriels, informatique, etc).
Interventions d'expertises, de contrôle, d'audit (certi cation, prélèvements, etc.)
Les problèmes de tournée sont des extensions classiques du problème du voyageur de commerce (T SP ), et font partie de la classe des problèmes NP-complets. Comme pour la plupart
des problèmes NP-complets il est di cile de résoudre des instances de grande taille de façon
optimale. On se contente alors de trouver des solutions de bonne qualité . A n d'obtenir des
solutions dans des temps de calculs raisonnables, on se tourne généralement vers des méthodes
approchées à base d'heuristique pour construire une première solution que l'on améliore ensuite
avec d'autres heuristiques ou des méthodes de recherche locale. La programmation linéaire en
nombre entiers permet de résoudre de façon exacte certains problèmes de tournées de véhicules de taille relativement réduite (jusque environ 200 clients à l'heure actuelle). Les méthodes
développées sont des applications de Branch and cut, ou plus récemment des générations de
colonnes. De nombreuses méta-heuristiques ont également été appliquées à ce problème, comme
la recherche tabou, mais aussi les algorithmes génétiques, recherches à voisinage variable etc...
Certains problèmes possédant jusque 20000 clients ont ainsi pu être traités de façon e cace.
4.1

Le

T SP

Le T SP ou Traveling Saleman Problem est un problème classique de la littérature en
Recherche Opérationelle. L'énoncé peut être le suivant : étant donné N points (ou villes) et les
distances les séparant, trouver un chemin de longueur totale minimale qui passe exactement une
DRUGBERT Ludovic

19

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES
fois par chaque point et revienne au départ. Le problème est de type NP-complet, c'est-à-dire
qu'il n'existe pas d'algorithme de résolution exacte pouvant résoudre n'importe quelle instance du
problème en un temps raisonnable . La plupart de ces problèmes sont tellement combinatoires
que la simple énumération des solutions est impossible dès que la taille des données augmente.
L'approche de résolution la plus naïve serait l'énumération de tous les chemins possibles,
l'algorithme serait alors en O (n!), ce qui devient vite impraticable même pour de petites instances. Held et Karp [1] ont montré que la programmation dynamique permettait de résoudre le
problème en O n2 2n .


Les méthodes d'optimisation linéaire sont à ce jour parmi les plus e caces pour la résolution
du problème de voyageur de commerce et permettent désormais de résoudre des problèmes de
grandes tailles (à l'échelle d'un pays), moyennant éventuellement un temps de calcul important.
Lorsque le temps alloué à la résolution est faible on utilisera plutôt des heuristiques tel que
l'Algorithme de Lin-Kernighan [2] et des méta-heuristiques. Toutefois les méthodes heuristiques
ne donnent en général aucune preuve justi ant qu'elles obtiennent la meilleure solution, et même
si elles peuvent en pratique être très bonnes, en toute généralité elles ne fournissent qu'une
solution approchée.
Les algorithmes génétiques peuvent aussi être adaptés au problème du voyageur de commerce.
L'idée a été proposée la première fois par John Holland [3] au début des années 1970.

Figure 2 Exemple du T SP
Formalisation : Formellement, le problème du voyageur de commerce peut s'écrire comme un
programme linéaire. Soit le graphe G = (V, E) où V est l'ensemble des sommets représentant les
villes et E = (i, j) | (i, j) ∈ V 2 , i 6= j l'ensemble des arcs. On note dsij la durée du trajet de i




vers i, (i, j) ∈ V 2 .
Ci-dessous, on retrouve le programme linéaire du T SP où xij est une variable binaire de
DRUGBERT Ludovic

20

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES
décision indiquant si l'arc (i, j) fait partie de la solution.
Le programme linéaire du T SP :
min

X

(1)

dsij xij

(i,j)∈E

Sous contraintes :
X

xij =

(i,j)∈E

X

xji = 1

∀i ∈ V

(2)

(j,i)∈E

xij ∈ {0, 1}

∀ (i, j) ∈ E

(3)

La fonction objectif (1) minimise la durée totale du trajet. Les contraintes (2) permettent de
s'assurer que toutes les villes sont visitées exactement une fois. (3) xent la nature des variables
de décisions.
4.2

Le

V RP

Le problème de routage de véhicules (V RP ou Vehicle Routing Problem) est une extension
du problème du voyageur du commerce. Il a été introduit pour la première fois par Dantzig et
al. [4] sous le nom de Truck Dispatching Problem et a depuis fait l'objet d'études intensives pour
le modéliser et le résoudre.
Dans sa version la plus basique dite Capacitated V RP (CV RP) ou V RP avec contraintes de
capacité, une otte de véhicules de capacité nie, basée dans un dépôt, doit assurer des tournées
entre plusieurs clients (ou villes) ayant demandé chacun une certaine quantité de marchandises.
L'ensemble des clients visités par un véhicule désigne la tournée de celui-ci. Chaque client doit
être desservi une et une seule fois et chaque tournée commence et se termine au dépôt. L'objectif
du CV RP est de minimiser le coût total, qui peut être la somme des distances, ou des temps de
parcours des tournées ou une valeur monétaire, tout en respectant la contrainte de capacité des
véhicules : la quantité de marchandises livrées sur une tournée ne doit pas dépasser la capacité
du véhicule qui l'assure. La gure 3 représente un exemple de problème de V RP résolu avec 3
véhicules.

Formalisation : Formellement, le

V RP peut s'écrire comme un programme linéaire. Soit le

graphe G = (V, E) où V = C ∪ D est l'ensemble des sommets représentant les clients (C )
et les dépôts (D = {de , ds }, où de représente le dépôt départ et ds le dépôt d'arrivé) et E =
{(i, j) | i ∈ C ∪ {de } , j ∈ C ∪ {ds } , i 6= j} l'ensemble des arcs. Soit ci la demande du client i ∈ C .

DRUGBERT Ludovic

21

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES

Figure 3 Exemple du V RP
Soit m le nombre de véhicules qui compose la otte et Q la capacité d'un véhicule. On note dsij
la durée du trajet de i vers i, (i, j) ∈ V 2 .
Ci-dessous, on retrouve le programme linéaire du V RP où xnij est une variable binaire de
décision indiquant si l'arc (i, j) est emprunté par le n-ième véhicule.
Le programme linéaire du V RP :
min

m
X
X

(4)

dsij xnij

n=1 (i,j)∈E

Sous contraintes :
X

X

xnij =

(i,j)∈E

xnji

∀i ∈ C,

∀n = 1...m

(5)

(j,i)∈E
m
X
X

xnij = 1

∀i ∈ C

(6)

n=1 (i,j)∈E

X

xnde j =

(de ,j)∈E

X

xnjds = 1

∀n = 1...m

(7)

(j,ds )∈E

X

ci xnij ≤ Q

∀n = 1...m

(8)

(i,j)∈E
i6=de

xnij ∈ {0, 1}

∀ (i, j) ∈ E,

∀n = 1...m

(9)

La fonction objectif (4) minimise la durée totale des trajets. Les contraintes (5) assurent la
conservation du ot. Les contraintes (6) s'assurent que tous les clients sont servis. (7) obligent
DRUGBERT Ludovic

22

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES
tous les véhicules à être utilisés. Les contraintes (8) assurent le respect des capacités de chaque
véhicules. (9) xent la nature des variables de décisions.
4.3

Les problèmes d'orienteering

Au cours de la dernière décennie, un certain nombre d'applications exigeantes en matière
de logistique et de tourisme ont été modélisés comme des problèmes d'orientation (en anglais
orienteering). Les problèmes de tournées de véhicules avec pro ts se distinguent des problèmes
classiques du fait que la visite de chaque client n'est plus obligatoire. Cependant, lorsqu'un sommet (client) est visité, un pro t (gain ou score) non-négatif est collecté. Le but est de construire
un nombre de routes visitant les clients, telles que la somme des pro ts collectés soit maximale.
Tous les problèmes avec pro t sont une extension de l'OP et chacun d'entre eux se traduit par
l'ajout d'une combinaison de nouvelles contraintes sur celui-ci.

4.3.1 Orienteering Problem
Le nom Orienteering Problem (OP) provient d'un jeu de course d'orientation. Dans ce
jeu, les concurrents commencent à un point de départ spéci é et doivent ensuite visiter autant
de points de contrôle que possible avant de retourner au point de départ dans un laps de temps
donné (cf. gure 4). A chaque point de contrôle est associé un score. L'objectif est de maximiser
le score total collecté. L'OP peut être considéré comme une combinaison entre le problème du sac
à dos (KP ) et le problème du voyageur de commerce (T SP ). En outre, du fait de la limitation
de la durée du chemin, tous les sommets n'ont pas à être visités.

Figure 4 Exemple d'une solution de l'OP
Formalisation : Formellement, le problème de l'OP peut s'écrire comme un programme linéaire.
Soit le graphe G = (V, E) où V = C ∪ D est l'ensemble des sommets représentant les clients
(C ) et les dépôts (D = {de , ds }, où de représente le dépôt départ et ds le dépôt d'arrivé) et
E = {(i, j) | i ∈ C ∪ {de } , j ∈ C ∪ {ds } , i 6= j} l'ensemble des arcs. Soit pi le gain du client

DRUGBERT Ludovic

23

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES
i ∈ C . Soit λ la durée maximale du tour. On note dsij la durée du trajet de i vers i, (i, j) ∈ V 2 .

Ci-dessous, on retrouve le programme linéaire de l'OP où xij est une variable binaire de
décision indiquant si l'arc (i, j) fait partie de la solution. La variable binaire yi indique si le client
i est sélectionné ou non.

Le programme linéaire de l'OP :
max

X

(10)

pi yi

i∈C

Sous contraintes :
X

xij =

X

xji = yi

∀i ∈ C

(11)

(j,i)∈E

(i,j)∈E

X

X

xde j =

(de ,j)∈E

xjds = 1

(12)

(j,ds )∈E

X

dsij xij ≤ λ

(13)

(i,j)∈E

xij ∈ {0, 1}

yi ∈ {0, 1}

∀ (i, j) ∈ E

(14)

∀i ∈ C

(15)

La fonction objectif (10) maximise le pro t collecté. (11) et (12) assurent la connectivé du
chemin dans la solution. Le respect de la durée maximale d'un voyage est assuré par (13). (14)
et (15) xent la nature des variables de décisions.
Il existe un certain nombre de méthodes exactes pour l'OP telles que résumées dans le tableau 1. En utilisant ces méthodes exactes, des instances de petites tailles peuvent être résolues
en un laps de temps raisonnable. Toutefois, lorsque la taille du problème augmente (plusieurs
centaine de sommets), le temps de calcul augmente de façon exponentielle et ces méthodes deviennent impraticables. Par conséquent, de nombreux chercheurs se concentrent sur des méthodes
heuristiques.

DRUGBERT Ludovic

24

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES
Référence

Stratégie de Solution

Année

Hayes and Norman [6]

Dynamic Programming

1984

Kataoka and Morito [7]

Branch and Bound

1988

Laporte and Martello [8]

Branch and Bound

1990

Ramesh et al. [9]

Branch and Bound

1992

Leifer and Rosenwein [10] 0-1 Integer Programming 1993
Fishetti et al. [11]

Branch and cut

1998

Table 1 Méthodes Exactes pour l'OP
Les méthodes heuristiques résolvent généralement l'OP en deux étapes : la

construction

d'un chemin et l'amélioration de celui-ci. Plusieurs approches de construction sont proposées
dans la littérature. Le tableau 2 résume les approches de type heuristiques pour la résolution de
l'OP .
Référence

Stratégie de Solution

Année

Tsiligirides [13]

greedy insertion

1984

Tsiligirides [13]

sweep-based insertion

1984

Golden et al. [5]

greedy insertion, path improvement

1987

Keller [14]

random insertion, path improvement 1989

Keller [14]

greedy insertion, path improvement

1989

Ramesh and Brown [15] random insertion, path improvement 1991
Chao et al. [16]

random insertion, path improvement 1996

Table 2 Méthodes Heuristiques pour l'OP
Une première manière de procéder consiste à attribuer à chaque point, un poids calculé à
partir de formules basées sur le pro t et les durées des di érents trajets [5, 14, 13]. Les points
sont ensuite selectionnés les uns après les autres en utilisant une stratégie gloutonne puis ils sont
insérés dans un chemin de la solution courante. On itère alors jusqu'à ce que plus aucune insertion
ne soit possible. De fait, il est aussi possible de sélectionner aléatoirement le point choisi pour
l'insertion [14, 15]. Tsiligrides [13] présente une autre approche de construction nommé

sweep-

based insertion. Dans cette approche, l'espace de recherche est divisé en secteurs. Les chemins
sont alors construits dynamiquement sur la base de ces secteurs.
L'étape d'amélioration, quant à elle, utilise généralement des algorithmes de types 2OPT ou
3OPT pour diminuer la durée totale et des algorithmes de types suppression/insertion, relocation
DRUGBERT Ludovic

25

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES
ou exchange, pour augmenter le pro t total collecté.
En plus des méthodes heuristiques, plusieurs méta-heuristiques sont appliquées à l'OP . Wang
et al. [17] utilise le réseau de neurones arti ciels. Tasgetiren et Smith [18] utilisent eux, un
algorithme génétique. Récemment, l'algorithme de colonie de fourmis et celui de recherche tabou
ont été utilisés par Liang et al. [19]. Les heuristiques proposées par Ramesh et Brown [15], et
Chao et al. [16] peuvent également être considérés comme les approches méta-heuristiques. Les
résultats de Tasgetiren et Liang sont proches des meilleurs résultats connus, bien que le temps de
calcul de Tasgetiren soit relativement élevé. Le tableau 3 résume les approches Méta-heuristiques
pour la résolution de l'OP .
Référence

Stratégie de Solution Année

Wang et al [17]

Neural Network

1995

Tasgetiren and Smith [18] Genetic algorithm

2000

Liang et al. [19]

Ant Colony

2001

Liang et al. [19]

Tabu search

2001

Table 3 Méthodes Métha-Heuristiques pour l'OP
Golden et al. [5] ont prouvé que l'OP est NP-di cile, c'est-à-dire qu'il n'existe pas d'algorithme de résolution exacte en un temps raisonnable capable de résoudre n'importe quelle
instance du problème. Intuitivement, cela revient à dire qu'il faut tester toutes les solutions
réalisables.

4.3.2 Team Orienteering Problem
Team Orienttering Problem (T OP ) est apparu en premier dans Butt And Cavalier
(1994) sous le nom de Multiple Tour Maximum Collection Problem. Il s'agit d'une extenLe

sion de l'OP qui consiste à trouver un ensemble de chemins disjoints maximisant un gain, et ce,
en repectant une limite de temps. Les chemins dans ce problème partagent tous le même point
de départ et d'arrivée. Ce problème rajoutant des contraintes à celui de l'OP qui est NP-di cile
il est lui même NP-di cile.

Formalisation : Formellement, le

T OP peut s'écrire comme un programme linéaire. Soit le

graphe G = (V, E) où V = C ∪ D est l'ensemble des sommets représentant les clients (C )
et les dépôts (D = {de , ds }, où de représente le dépôt départ et ds le dépôt d'arrivé) et E =
{(i, j) | i ∈ C ∪ {de } , j ∈ C ∪ {ds } , i 6= j} l'ensemble des arcs. Soit pi le gain du client i ∈ C . Soit

DRUGBERT Ludovic

26

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES

Figure 5 Exemple d'une solution du T OP
λ la durée maximale de chaque tournée. On note dsij la durée du trajet de i vers i, (i, j) ∈ V 2 .

Soit m le nombre de véhicules composant la otte.
Ci-dessous, on retrouve le programme linéaire du T OP où xnij est une variable binaire de
décision indiquant si l'arc (i, j) est emprunté par le n-ième véhicule. La variable binaire yin
indique si le client i est visité par le n-ième véhicule.
Le programme linéaire du T OP :
max

m X
X

pi yin

(16)

∀i ∈ C

(17)

n=1 i∈C

Sous contraintes :
m
X

yin ≤ 1

n=1

X

xnij =

(i,j)∈E

X

xnji = yin

∀i ∈ C,

∀n = 1...m

(18)

(j,i)∈E

X

X

xnde j =

(de ,j)∈E

xnjds = 1

∀n = 1...m

(19)

(j,ds )∈E

X

dsij xnij ≤ λ

∀n = 1...m

(20)

(i,j)∈E

xnij ∈ {0, 1}

yin ∈ {0, 1}

∀ (i, j) ∈ E,

∀i ∈ C,

∀n = 1...m

∀n = 1...m

(21)

(22)

Chao et al. [16] proposa une première heuristique pour résoudre ce problème. Cette heuristique
DRUGBERT Ludovic

27

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES
construit un ensemble de chemins entre lesquels des échanges de points vont être réalisés, et
auxquels vont être appliqué un algorithme de reséquencement 2OPT.
Depuis, de nombreuses méthodes ont vu le jour pour tenter de résoudre au mieux ce problème.
Certaines sont l'adaptation de méta-heuristiques, comme par exemple les adaptations de colonies
de fourmis proposées par Liangjun Ke [20] qui fournit de bons résultats en un temps très court,
l'adaptation d'un algorithme génétique proposée par Bouly [21], algorithme tabou par Tang [22]
ou Archetti [23]. D'autres encore ont proposé des méthodes de résolutions di érentes comme par
exemple Butt [24] qui utilise un algorithme basé sur la génération de colonnes ou encore Boussier
[12] qui propose une méthode de branch and prize. D'autres en n comme Feillet [25] ont préféré
voir le T OP comme une extension du problème du voyageur de commerce.

4.3.3 Team Orienteering Problem with Time Windows
Le

Team Orienteering Problem with Time Windows (T OP tw) est une extension du

T OP . A chaque point de contrôle est associé une fenêtre de temps indiquant la disponiblité

du point. L'objectif est de construire un ensemble de chemin visitant les di érents clients et
respectant les fenêtres de temps, tout en maximisant le pro t collecté.

Figure 6 Exemple d'une solution du T OP tw
Formalisation : Formellement, le

T OP tw peut s'écrire comme un programme linéaire. Soit

le graphe G = (V, E) où V = C ∪ D est l'ensemble des sommets représentant les clients (C )
et les dépôts (D = {de , ds }, où de représente le dépôt départ et ds le dépôt d'arrivé) et E =
{(i, j) | i ∈ C ∪ {de } , j ∈ C ∪ {ds } , i 6= j} l'ensemble des arcs. Soit pi le gain du client i ∈ C .

Soit γi = [ei , li ] la fenêtre de temps de l'élément i ∈ V . Soit λ la durée maximale de chaque
tournée. On note dsij la durée du trajet de i vers i, (i, j) ∈ V 2 . Soit m le nombre de véhicules
composant la otte.
Ci-dessous, on retrouve le programme linéaire du T OP où xnij est une variable binaire de
DRUGBERT Ludovic

28

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES
décision indiquant si l'arc (i, j) est emprunté par le n-ième véhicule. La variable binaire yin
indique si le client i est visité par le n-ième véhicule. On pose ani = dani + win , avec dani l'instant
d'arrivée du n-ième véhicule sur le sommet i et win le temps d'attente.
Le programme linéaire du T OP tw :
max

m X
X

pi yin

(23)

∀i ∈ C

(24)

n=1 i∈C

Sous contraintes :
m
X

yin ≤ 1

n=1

X

xnij =

X

xnji = yin

∀i ∈ C,

∀n = 1...m

(25)

(j,i)∈E

(i,j)∈E

X

X

xnde j =

(de ,j)∈E

xnjds = 1

(26)

∀n = 1...m

(j,ds )∈E

ei yin ≤ ani ≤ li yin

ani + dsij + M xnij ≤ anj + M

∀i ∈ V,

∀ (i, j) ∈ E,

ands − ande ≤ λ

xnij ∈ {0, 1}

yin ∈ {0, 1}

ani ∈ R+

∀n = 1...m,

M = lds − ede

∀n = 1...m

∀ (i, j) ∈ E,

∀i ∈ C,

∀i ∈ V,

(27)

∀n = 1...m

∀n = 1...m

∀n = 1...m

∀n = 1...m

(28)

(29)

(30)

(31)

(32)

Récemment, une certaine attention a été accordée au T OP tw. Un algorithme de Colonie de
fourmis a été proposé par Montemanni et Gambardella [29]. Un algorithme de type ILS (Iterated
Local Search) est proposé par Vansteenwegen et al. [26]. En n, un algorithme de recherche locale
évolutionnaire hybridé et un VNS Granulaire est proposé par Labadie et al. [30].
DRUGBERT Ludovic

29

2013

4 LES DIFFÉRENTS PROBLÈMES DE TOURNÉES DE VÉHICULES

4.3.4 Multi Period Orienteering Problem with multi Time Windows
Le Multi

Period Orienteering Problem with multi Time Windows (M uP OP tw) est

une extension de l'Orienteering Problem with Time Windows (OP tw). On considère ici, en plus
des fenêtres multiples, un horizon de temps composé d'un nombre ni de période pour pouvoir
visiter les clients. Tricoire et Al. [35] propose un algorithme exact et une méthode de VNSAA
pour résoudre ce problème.
Le M uP OP tw fait partie de la classe de problème dit multi-période , ou un client doit être
visité une fois sur l'horizon de temps. Contrairement aux problèmes périodiques dans lesquel les
clients peuvent être visités plusieurs fois sur le long d'un horizon de temps. Une fois le problème
résolu, la même plani cation est reproduite sur un horizon plus long.

DRUGBERT Ludovic

30

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT

5 Le Team Orienteering Problem with Time Windows and Period
Dependent Pro t
Mon stage s'intéresse au nouveau problème du Team

Orienteering Problem with Time

Windows and Period Dependent Pro ts (T OP twP DP ) qui est une extension du T OP tw
et du M uP OP tw. On considère ici que le pro t apporté par la visite d'un client dépend de
la période de service. La gure 7 montre un exemple d'une solution du T OP twP DP sur une
instance de 100 clients, une otte composée de 3 véhicules et un horizon de temps constituté de
4 périodes.

Figure 7 Exemple d'une solution du T OP twP DP sur une instance de 100 clients et un horizon
de temps composé de 4 périodes

Le but est de proposer des plans de transports tactiques optimisés en sélectionnant un portefeuille de clients, en a ectant chaque client retenu à une période et en construisant les tournées
optimales de chaque période. Le T OP twP DP peut-être vu comme étant p problèmes de type
T OP tw, ou p est le nombre de période, une fois les clients a ectés aux périodes.

DRUGBERT Ludovic

31

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
5.1

Formalisations

On considère ici la notion de séquence, au sens mathématique du terme. Soit une séquence
X = (xi )i∈IX , d'éléments xi d'un ensemble VX , indexée par l'ensemble IX = J1, |VX |K. On note

alors, par abus de language, l'application X dé nie sur IX et à valeur dans VX , qui pour un
indice i ∈ IX donne l'élément xi ∈ VX associé :
X : IX
i

−→ VX
7−→ X (i) = xi

ainsi que l'application inverse X −1 , qui pour xi ∈ VX donne l'élément i ∈ IX associé :
X −1 : VX
xi

−→ IX
7−→ X −1 (xi ) = i

On notera l'ensemble EX des couples (i, j), i, j ∈ VX , tel que X −1 (j) = X −1 (i) + 1. On
représentera la séquence X = (xi )i∈IX sous forme d'un vecteur de dimension |VX | :
X = x1 , x2 , ..., x|VX |

5.2



Modèle mathématique

5.2.1 Données
Considérons un horizon de temps Ψ comme un ensemble composé d'un nombre ni de périodes
βi , i ∈ {x ∈ N | x < |Ψ|}, tel que Ψ =




β1 , β2 , ..., β|Ψ| . Pour la suite, on considèrera qu'une

période est un intervalle de R+ et que toutes les périodes sont idendiques.
∀t ∈ Ψ : βt = A = [eA , lA ] , (eA , lA ) ∈ R2

Soit λ ∈ [0, lA − eA ] la durée maximale d'un voyage pour chaque période. On note m ∈ N,
le nombre de véhicules disponibles sur l'horizon de temps.
Considérons un ensemble ni de clients C = c1 , c2 , ..., c|C| ainsi qu'un ensemble constitué




de deux dépôts notés D = {de , ds }, xe sur l'horizon de temps, avec de le dépôt de départ et
ds le dépôt d'arrivé. On note alors V = C ∪ D. Chaque élement i de V a une position dans



− −

l'espace R2 dé nie par le vecteur Ui = (xi , yi ). On note alors, ∀ (i, j) ∈ V 2 , dij = Ui − Uj =
p
(xi − xj )2 + (yi − yj )2 , représentant la distance euclidienne entre les deux sommets i et j . A

DRUGBERT Ludovic

32

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
chaque élément i ∈ V , on associe la durée de service si ∈ R+ et la fenêtre de temps γi = [ei , li ] ⊆
A, ou ei est la date de visite au plus tôt et li la date de visite au plus tard, et pour chaque client
i ∈ C et chaque période t ∈ Ψ, on dé nit le pro t pti ∈ R+ . Pour la suite, on considère que
∀i ∈ D, ∀t ∈ Ψ : pti = 0, si = 0, γi = A. Le problème peut être dé ni par l'application :
ξV,Ψ : V × Ψ −→ R+ × R+ × Γ × R2 × [0, lβ − eβ ]



(i, t) 7−→ ξV,Ψ (i, t) = pti , si , γi , Ui , λ

avec Γ = [x, y] | (x, y) ∈ β 2 , x ≤ y .




Pour la suite, et pour simpli er le problème, on considère la somme dsij = dij + si , ∀(i, j) ∈
(V \ {ds }) × (V \ {de }). Soit le graphe orienté et pondéré G = (V, E), ou V = C ∪ D repré-

sente l'ensemble des sommets et E = {(i, j) | i ∈ C ∪ {de } , j ∈ C ∪ {ds } , ei + dsij ≤ lj , i 6= j}
l'ensemble des arcs (Par abus de language, on assimilera les clients et le dépôt aux sommets les
représentants). dsij représente alors la durée du trajet sur l'arc (i, j) ∈ E .

5.2.2 Variables de décisions
Soit at,n
la variable indiquant l'instant où le service du n-ième véhicule commence chez le
i
sommet i ∈ V pour la période t ∈ Ψ.
Soit la variable binaire xt,n
ij égale à 1 si l'arc (i, j) ∈ E est emprunté par le n-ième véhicule à
la période t ∈ Ψ, 0 sinon.
Soit la variable binaire yit,n égale à 1 si le client i ∈ C est visité par le n-ième véhicule à la
période t ∈ Ψ, 0 sinon.

5.2.3 Notations
Soit T une séquence représentant une tournée. Chaque tournée commence au dépôt de et
se termine au dépôt ds et contient un ensemble de clients à visiter notés CT , on a donc VT =
CT ∪ D. Les éléments de VT représentent les sommets du tour et ceux de ET les arcs. On notera
P
βT la période auquel appartient la tournée T , dT =
dsij la durée totale du tour T et
(i,j)∈ET

pT =

P
i∈CT

pβi T

le pro t total collecté.

On note ΩξV,Ψ l'espace des solutions réalisable du problème ξV,Ψ . Une solution H ∈ ΩξV,Ψ est
composée de |Ψ| sous-ensembles composés de m tournées, représentant une solution du T OP tw
sur chaque période. On note pH le pro t collecté par la solution H . Pour un problème ξV,Ψ
donné et une solution H ∈ ΩξV,Ψ , on note ht , avec ht ∈ H , la solution sur la période t ∈ Ψ.
DRUGBERT Ludovic

33

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
On notera(l'ensemble GH , représentant
les clients non visités par la solution H , on a donc
)
GH = C \

i∈

S
T ∈ht

CT | t ∈ Ψ .

On note, pour une tournée T donnée et un élément i ∈ VT , dai indiquant la date d'arrivée
sur le sommet i, wi indiquant le temps d'attente au sommet i et ai la date de début de début de
service chez i. On a alors wde = wds = 0 et ∀(i, j) ∈ ET , wj = max {ej − (ai + dsij ) , 0}.
En n, on note pour une tournée T et pour (i, j) ∈ ET , la durée supplémentaire ∆ir =
dsir + wr + dsrj − dsij engendrée par l'ajout du client r après le sommet i dans le tour T .
5.3

Programme linéaire en nombre entiers

Le programme linéaire du T OP twP DP est donné ci-dessous :
max

m XX
X

pti yit,n

(33)

∀i ∈ C

(34)

n=1 i∈C t∈Ψ

Sous contraintes :
m X
X

yit,n ≤ 1

n=1 t∈Ψ

xt,n
ij =

X
(i,j)∈E

X

t,n
xt,n
ji = yi

∀i ∈ C,

∀t ∈ Ψ,

∀n = 1...m

(35)

(j,i)∈E

X

xt,n
de j =

(de ,j)∈E

X

xt,n
jds = 1

∀t ∈ Ψ,

∀n = 1...m

(36)

∀i ∈ V,

∀t ∈ Ψ,

∀n = 1...m

(37)

(j,ds )∈E

t,n
ei yit,n ≤ at,n
i ≤ li yi
t,n
t,n
at,n
i + dsij + M xij ≤ aj + M

∀ (i, j) ∈ E,

t,n
at,n
ds − ade ≤ λ

xt,n
ij ∈ {0, 1}

yit,n ∈ {0, 1}

DRUGBERT Ludovic

∀t ∈ Ψ,

∀t ∈ Ψ,

∀ (i, j) ∈ E,

∀i ∈ C,

∀n = 1...m

∀t ∈ Ψ,

∀t ∈ Ψ,

34

∀n = 1...m,

∀n = 1...m

∀n = 1...m

M = lA − eA (38)

(39)

(40)

(41)

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT

+
at,n
i ∈R

∀i ∈ V,

∀t ∈ Ψ,

∀n = 1...m

(42)

La fonction objectif (33) maximise le pro t total des clients sélectionnés pour chaque période.
Les contraintes (34) permettent de s'assurer que chaque client est visité au plus une fois sur
l'horizon de temps. (35) et (36) permettent de garantir la connectivité pour chaque chemin dans
la solution. Les fenêtres de temps sont gérées de manière classique par les contraintes (37). (38)
implique que si l'arc (i, j) est sélectionné dans la solution, alors le début de service chez j doit
être supérieur ou égale au début de service de i plus le temps de voyage entre i et j . Le respect
de la durée maximale d'un voyage sur une période est assuré par (39) et la durée maximale
sur l'horizon de temps est donnée par (40). (40), (41) et (42) xent la nature des variables de
décisions.

DRUGBERT Ludovic

35

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
5.4

Heuristique d'insertion

Une heuristique d'insertion est utilisée pour construire une solution initiale réalisable. L'idée
principale repose sur la construction de |Ψ| solutions de type T OP tw. Dans chaque itération, la
procédure évalue toutes les insertions possibles parmis les clients non visités et choisit la meilleure
d'entre elles. Le critère d'insertion est le suivant : pour un sommet i d'une tournée T donnée
i,T
(i 6= ds ) et un candidat r pour l'insertion après i, on note Sr,g
l'ensemble des clients atteignables

à partir de r parmis g , si r est visité après i dans T . La meilleure insertion est déterminée par le




i,T ptr
couple (i, r) pour lequel ρir = Sr,g
∆ir est maximal. Dans la suite de cette section, j'explique

en détail l'implémentation de l'heuristique d'insertion.
Considèrons un problème de type T OP twP DP dé ni par l'application ξV,Ψ . Dans un premier
temps, on construit l'ensemble F = f 1 , f 2 , ..., f |Ψ| ∈ φξV,Ψ , tel que f t représente l'ensemble




des clients a ectés à la période t ∈ Ψ et φξV,Ψ l'ensemble des a ectations possibles. On résoud
ensuite un T OP tw pour chaque période de l'horizon de temps. Le résultat nal est l'ensemble
des |Ψ| solutions construites grâce à l'heuristique d'insertion. L'algorithme 1 décrit la résolution
d'un T OP twP DP :

Algorithm 1 InsertionMultiPeriode
Entrées: Un problème de type T OP twP DP dé ni par ξV,Ψ . ALEA, paramètre permettant de
randomiser l'heuristique.

Sorties: Une solution H ∈ ΩξV,Ψ .

1: H ← {} ;
2: F ← A ecterClientsPeriodes(ξV,Ψ , ALEA) ;
3: Pour chaque période t ∈ Ψ faire
4:
h ← InsertionPeriode(ξV,Ψ , f t , t) ;
5:
H ← H ∪ {h} ;
6: n Pour
7: return H ;

On initialise une solution H de type T OP twP DP . On appelle ensuite la fonction A ecter-

ClientsPeriodes avec le paramètre ALEA. Ce paramètre permet de randomiser notre heuristique
d'insertion et donc de parcourir l'espace φξV,Ψ . Dans le meilleur des cas, on a ecte chaque client à
une période de manière à maximiser le pro t espéré. On a ensuite une boucle sur chaque période
de l'horizon. On y construit alors les solutions de type T OP tw pour les ajouter à la solution
H . Chaque solution est construite sur la base des di érentes a ectations réalisées précedement.

En n on retourne la solution ainsi créée.
Les algorithmes 2 et 3 décrivent la construction d'une solution de type T OP tw sur une
période donnée. L'idée est de construire m tournées, les unes après les autres, en insérant des
DRUGBERT Ludovic

36

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
clients libres tout en suivant le critère de sélection décrit plus en détail par la suite.

Algorithm 2 InsertionPeriode
Entrées: Un problème de type
servis. Une période t ∈ Ψ.

T OP twP DP dé ni par ξV,Ψ . Un ensemble de clients g non

Sorties: Un ensemble de tournées h sur la période t.
1: h ← {} ;
2: Pour n = 1 à m faire
3:
T ← N ouvelleT ournee(ξV,Ψ , g, t) ;
4:
h ← h ∪ {T } ;
5:
g ← g \ CT ;
6:
n ← n + 1;
7: n Pour
8: return h ;

On initialise une solution h de type T OP tw. On cherche alors à construire m tournées à
partir de l'ensemble g . Chaque fois qu'une tournée est créée, on l'ajoute à la solution courante
et les clients sont supprimés de g pour ne pas les réutiliser.
Une tournée est construite en deux temps. Premièrement, on appelle la fonction Initialise-

Tournee, qui permet d'initialiser une nouvelle tournée en insérant un premier client et en a ectant la tournée à une période (βT ← t). Ensuite la fonction InsererClientT our permet, à partir
d'une tournée donnée et d'un ensemble de clients non servis, d'insérer les meilleurs d'entre-eux
aux meilleures positions. En n on retourne la solution créée.

Algorithm 3 NouvelleTournee
Entrées: Un problème de type

T OP twP DP dé ni par ξV,Ψ . Un ensemble de clients g non
servis. Une période t ∈ Ψ.
Sorties: Une nouvelle tournée T construite avec l'heuristique d'insertion.
1: T ← InitialiserT ournee(ξV,Ψ , g, t) ;
2: g ← g \ CT ;
3: T ← InsererClientT our(ξV,Ψ , T, g) ;
4: return T ;

L'algorithme 4 permet de remplir une tournée donnée en paramètre. On insère des clients
dans celle-ci tant que possible. A chaque tour de boucle, on cherche un client à insérer grâce à
l'algorithme 5. Si on trouve un nouveau client, on l'insére, sinon on s'arrête. A chaque fois qu'un
client est inséré, on le supprime de l'ensemble des clients libres pour qu'il ne puisse plus être
choisi.
L'algorithme 5 consiste, pour une tournée donnée, à trouver le meilleur client à insérer et dans
quelle position. On cherche alors, pour chaque arc de la tournée, à trouver le meilleur candidat
pour l'insertion grâce à l'algorithme 6. On sélectionne alors le meilleur de tous les candidats
DRUGBERT Ludovic

37

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT

Algorithm 4 InsererClientTour
Entrées: Un problème de type T OP twP DP dé ni par ξV,Ψ . Une tournée T . Un ensemble de

clients g non servis.
Sorties: La tournée T avec de nouveaux clients de l'ensemble g.
1: stop ← f alse ;
2:
3:
4:
5:
6:
7:
8:
9:

Tant que

stop = f alse faire
(c, idxc , stop) ← MeilleurInsertionTour(ξV,Ψ , T, g ) ;
Si stop = f alse alors
T ← InsererClient(T, c, idxc ) ;
g ← g \ {c} ;

n Si
n Tant que
return T ;

pour l'insertion. L'algorithme retourne le client à inserer ainsi que la position d'insertion et une
variable booléen indiquant si un client a été trouvé ou non.

Algorithm 5 MeilleurInsertionTour
Entrées: Un problème de type T OP twP DP dé ni par ξV,Ψ . Une tournée T . Un ensemble de

clients g non servis.
Sorties: Le meilleur client c à inserer dans le tour T à l'indice idxc ∈ IT . La variable booléen
stop indiquant si un client a été trouvé ou non.
1: ρmax ← −1 ; idxc ← null ; c ← null ; stop ← f alse ;
2: Pour chaque arc (i, j) ∈ ET faire
3:
(ctemp , ρtemp ) ← MeilleurInsertionArc(ξV,Ψ , T , (i, j), g ) ;
4:
5:
6:
7:
8:
9:
10:
11:

Si

ρtemp > ρmax alors
ρmax ← ρtemp ; c ← ctemp ; idxc ← T −1 (i) + 1 ;

n Si
n Pour
Si ρmax = −1 alors
stop ← true ;

n Si
return (c, idxc , stop) ;
L'algorithme 6 permet de choisir le meilleur client à inserer entre deux clients donnés en

paramètre. On note alors, pour une T donnée, un sommet i ∈ VT \ {ds } et un ensemble de clients
i,T
g ⊆ C non servis, l'ensemble Sr,g
des clients s ∈ g qui peuvent être visités après le sommet r

dans T , et si r est inséré après i, tout en respectant les fenêtres de temps (cf. algorithme 8) :
i,T
Sr,g
= {s ∈ g | ar,temp + dsrs ≤ ls } , avec ar,temp = max {er , ai + dsir }

Le critère de sélection est le suivant : Pour une tournée T donnée et un sommet i ∈ VT \ {ds },
le meilleur client à inserer après i dans T , parmi un ensemble de clients libres g , est le client r




βT

i,T pr
tel que ρir = Sr,g
∆ir soit maximal.

DRUGBERT Ludovic

38

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT

Algorithm 6 MeilleurInsertionArc
Entrées: Un problème de type T OP twP DP dé ni par ξV,Ψ . Une tournée T . Un arc (i, j) ∈ ET .
Un ensemble de clients g non servis.
Sorties: Le client c à insérer après i et la valeur ρirmax associée.
1: ρirmax ← 0 ; c ← null ;
2: Pour chaque client r ∈ g faire

Si

3:
4:
5:
6:
7:

T estInsertion(ξV,Ψ , T, r, T −1 (i)) = true
ρirmax ← ρir ; c ← r ;

et alors

ρir > ρirmax

alors

n Si
n Pour
return (c, ρirmax ) ;

On a alors une boucle principale qui parcourt tous les clients de g . Pour chacun d'entre eux,
on véri e si l'insertion est possible grâce aux accélérateurs (cf. section 5.5). Ensuite on calcule
la valeur ρir associée. On mémorise à chaque itération le meilleur client. L'algorithme retourne
alors le meilleur client trouvé.

Algorithm 7 calculSr
Entrées: Un problème de type

T OP twP DP dé ni par ξV,Ψ . Une tournée T et un client i ∈
VT \ {ds }. Un ensemble de clients g . Un candidat r pour l'insertion après i.
Sorties: L'ensemble S des clients qui peuvent être visité après r dans T parmis g.
1: S ← {} ;
2: ar,temp = max {er , ai + dsir } ;
3: Pour chaque client s ∈ g faire
4:
Si s 6= r et alors ar,temp + dsrs ≤ ls alors
5:
S ← S ∪ {s} ;

n Si
n Pour
return S ;

6:
7:
8:

i,T
Le calcul de Sr,g
est réalisé comme ceci : on initialise l'ensemble à vide. Pour chaque client

s ∈ g , on regarde si il est atteignable à partir de r, c'est-à-dire que ar,temp + dsrs ≤ ls , avec
ar,temp = max {er , ai + dsir }. Si oui, alors on l'ajoute à l'ensemble. En n on retourne l'ensemble

comme résultat.
Il est possible de prendre en compte la contrainte suivante : ar,temp + dsrs ≤ lA . On s'assure
alors en plus que la visite du client permet le retour au dépôt dans les temps.
5.5

Les accélérateurs

Les fenêtres de temps sur chaque client imposent parfois des temps d'attente. Ainsi, lorsque
l'on fait une modi cation dans une tournée, la date de début de service au niveau de chaque
client peut être modifée ou décalée. Cela peut conduire à modi er les délais d'attente de plusieurs
DRUGBERT Ludovic

39

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
clients successifs, ce qui nous oblige à calculer la propagation des dates d'arrivée a n de connaître
le gain avant chaque modi cation de tournée. Le coût est bien trop important pour que nous
puissions envisager cette méthode. L'ajout des accélérateurs au niveau de chaque client permet
de résoudre cette di culté.
max et Qabs dé nies par
On note alors, pour une tournée T donnée, les applications Qmin
T , QT
T

récurence :



Qmin :


 T

ET

−→ R



(i, j) 7−→ Qmin
(i) = max Qmin
(j) − dsij , ei
T
T




 Qmin (ds ) = eA
T
Qmin
représente la date d'arrivée au plus tôt sur un client sans que cela n'occasionne d'attente
T

supplémentaire. Au niveau d'un client i d'une tournée T , on calcule la nouvelle date de début de
service. Si elle est inférieure à Qmin
(i) alors on sait qu'il y a une augmentation du délai d'attente
T
dans la tournée sans que cela n'in uence sa durée.



Qmax :


 T

−→ R

ET

(i, j) 7−→ Qmax
(i) = min {Qmax
(j) − dsij , li }
T
T




 Qmax (ds ) = lA
T
Qmax
représente la date d'arrivée au plus tard sur un client sans que cela viole le respect des
T

fenêtres de temps sur le reste de la tournée. Au niveau d'un client, si la nouvelle date d'arrivée
est supérieure à cette valeur alors on sait qu'il y a une violation d'une fenêtre de temps sur ce
client ou sur les clients qui le suivent.



Qabs :


 T




 Qabs (ds )
T

ET

−→ R

abs
(i, j) 7−→ Qabs
T (i) = QT (j) + wi

=0

Qabs
T modélise la capacité du reste de la tournée à résister à du retard supplémentaire sans

modi er sa durée totale. Au niveau d'un client i d'une tournée T , si la nouvelle date d'arrivée est
supérieure à l'ancienne et cette di érence est supérieure à Qabs
T (i) alors la durée de la tournée
est augmentée, sinon elle n'est pas modi ée.
Ces accélérateurs, au niveau de chaque client, permettent de tenir compte du comportement
de la suite de la tournée en fonction de la date d'arrivée sur le client courant. Cela permet de

DRUGBERT Ludovic

40

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
connaître instantanément l'in uence d'un changement de la date d'arrivée sur un client sur le
reste de la tournée. Le calcul de ces variables se fait à l'initialisation des tournées et après chaque
modi cation. Pour se faire, on parcourt la tournée depuis le dépôt nal vers le dépôt initial.
Par exemple, soit une tournée T et un client j ∈ CT . Considérons maintenant une nouvelle
T
date d'arrivée sur ce client notée daj,new = aβj,new
−wj,new , tel que daj,new ≤ Qmax
(j). La nouvelle
T

date d'arrivée au dépôt ds , notée ads ,new , est alors donnée par :

ads ,new

5.6




 ad + max 0, daj,new − daj − Qabs (j)
s
T
=


 a + min 0, max da
min (j) − da
j,new , QT
j
ds

Si daj,new > daj
Sinon

La Recherche Locale

L'objectif de cette étape est l'amélioration de la solution obtenue dans l'étape antérieure a n
d'obtenir un optimum local. L'amélioration se fait par l'application d'un algorithme de recherche
local sur la solution. La qualité de la solution résultante dépend de la structure du voisinage, la
technique de recherche, et la solution de départ elle-même.
La recherche locale est un algorithme itératif qui va remplacer la solution actuelle par une
meilleure solution dans le voisinage, l'algorithme s'arrête lorsqu'on ne trouve aucune meilleure
solution (optimum local), deux stratégies de recherche sont envisagées :


Best-improving : on examine tous les voisins, et on remplace la solution par le meilleur
voisin.



First-improving : on remplace la solution initiale par le premier meilleur voisin qu'on
trouve.

A partir d'une solution réalisable, on applique plusieurs mouvements intra et extra tournée
pour trouver le minimum local des solutions initiales et des nouvelles solutions générées par
les méta-heuristiques. Ici, on utilisera plusieurs types de mouvements connus : le 2OPT, la
relocation, l'exchange, le Forward OrExchange ainsi qu'un algorithme de suppression et insertion.
On distinguera les mouvements internes qui ne modi ent qu'une tournée et les mouvements
externes qui nécessitent deux tournées. Lorsque ces mouvements sont appliqués sur des tournées
appartenant à une même période, ils visent uniquement à réduire la durée totale des tournées,
étant donné que le pro t reste inchangé. Lorsqu'ils sont appliqués sur des tournées n'appartenant
pas à une même période, on regarde en premier le pro t puis la distance totale.

DRUGBERT Ludovic

41

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT

5.6.1 2OPT
2OPT est un algorithme de recherche locale proposé par Croes en 1958 pour résoudre le
problème du voyageur de commerce en améliorant une solution initiale. 2OPT est un algorithme
itératif : à chaque étape, on supprime deux arêtes de la solution courante et on reconnecte les
deux tours ainsi formés. Cette méthode permet soit d'améliorer le pro t total collecté (2OPT
Externe), soit de réduire la durée d'une même tournée (2OPT Interne).

5.6.1.a 2OPT Interne

Figure 8 Exemple 2OP T

Interne

Le 2OPT interne ( gure 8) permet, lorsqu'on l'applique sur une même tournée, de réduire la
durée totale de celle-ci. En e et, les clients visités demeurent inchangés, le pro t reste constant
sur une période donnée. L'algorithme 8 illustre le déroulement du 2OPT sur une même tournée.
On supprime deux arcs d'une même tournée et on reconstruit la tournée di éremment. Les 2 arcs
supprimés sont sélectionnés par l'intermédiaire de 2 boucles imbriquées et toutes les possibilités
peuvent être envisagées : la première améliorante est acceptée. On continue tant que l'on trouve
une améliorante.
A n de véri er les contraintes de fenêtres de temps, nous calculons les nouvelles dates d'arrivées sur les clients (T [j], T [j − 1], ..., T [i + 1], T [j + 1]). Grâce aux accélérateurs et à la nouvelle
date d'arrivée en T [j +1], nous pouvons déduire la faisabilité de la tournée ainsi que de la nouvelle
durée de celle-ci.

DRUGBERT Ludovic

42

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT

Algorithm 8 2OP TInterne
Entrées: Un problème de type T OP twP DP dé ni par ξV,Ψ . Une tournée T .
Sorties: La tournée T améliorée par le 2OP TInterne .
1: amelioration ← true ;
2: Tant que amelioration = true faire
3:
amelioration ← f alse ;
4:
Pour i = 0 à |CT | faire
5:
j ← i + 2 ; continuer ← true ;
6:
Tant que j ≤ |CT | et alors continuer = true faire
7:
(realisable, gainDistance ) ← T est2OP TInterne (ξV,Ψ , T, i, j) ;
8:
Si gainDistance > 0 et alors realisable = true alors
9:
T ← Construire2OP TInterne (T, i, j) ;
10:
amelioration ← true ; continuer ← f alse ;
11:
n Si
12:
n Tant que
13:
n Pour
14: n Tant que
15: return T ;

5.6.1.b 2OPT Externe

Figure 9 Exemple 2OP T

Externe

Le 2OP T externe permet, lorsqu'on l'applique sur deux tournées di érentes, d'améliorer soit
le pro t collecté si les tournées appartienent à une période di érente, soit de réduire la durée
totale de celles-ci. L'algorithme 17 illustre le déroulement du 2OPT sur deux tournées di érentes.
On supprime deux arcs de deux tournées di érentes (cf.fgure 9) et on permute la n de chaque
tournée. Les deux arcs supprimés sont sélectionnés par l'intermédiaire de 2 boucles imbriquées et
toutes les possibilités peuvent être envisagées. La première améliorante est acceptée. On continue
tant que l'on trouve une amélioration.
Le gain espéré par le 2OPExterne est donné par :

gainP rof it =

|C2 |
X

βT1
pT2 [k]



βT2
pT2 [k]

k=j+1



+

|C1 |
X

βT

βT

2
1
pT1 [k]
− pT1 [k]



k=i+1

Si celui-ci est supérieur ou égale à 0, alors on cherche à véri er la faisabilité du croisement. Pour
DRUGBERT Ludovic

43

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT

Algorithm 9 2OP TExterne
Entrées: Un problème de type T OP twP DP dé ni par ξV,Ψ . Deux tournées T1 et T2 di érentes.
Sorties: Les tournées T1 et T2 améliorée par le 2OP TExterne .
1: amelioration ← true ;
2: Tant que amelioration = true faire
3:
amelioration ← f alse ;
4:
Pour i = 0 à |CT1 | faire
5:
j ← 0 ; continuer ← true ;
6:
Tant que j ≤ |CT2 | et alors continuer = true faire
7:
(realisable, gainDistance , gainP rof it ) ← T est2OP TExterne (ξV,Ψ , T1 , T2 , i, j) ;
8:
Si gainP rof it ≥ 0 et alors realisable = true alors
9:
Si gainP rof it > 0 ou alors gainDistance > 0 alors
10:
(T1 , T2 ) ← Construire2OP TExterne (T1 , T2 , i, j) ;
11:
amelioration ← true ; continuer ← f alse ;
12:
n Si
13:
n Si
14:
n Tant que
15:
n Pour
16: n Tant que
17: return (T1 , T2 ) ;

cela, nous calculons les nouvelles dates d'arrivées pour les clients T [i + 1] et T [j + 1] et grâce aux
accélérateurs nous pouvons déduire la faisabilité des deux nouvelles tournées ainsi que le gain
sur la distance.

5.6.2 Relocation

Figure 10 Exemple Relocation
Le mouvement de Relocation tente de déplacer un client d'une tournée vers une autre (cf.
gure 10). L'algorithme 17 illustre la Relocation sur deux tournées di érentes. Les arcs (i − 1, i),
(i, i + 1) et (j, j + 1) sont remplacés par les arcs (i − 1, i + 1), (j, i) et (i, j + 1). La première amé-

liorante est acceptée. On continue tant que l'on trouve une améliorante. Ce mouvement permet
d'améliorer en premier le pro t lorsque les tournées appartiennent à deux périodes distinctes.

DRUGBERT Ludovic

44

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT

Algorithm 10 Relocation
Entrées: Un problème de type T OP twP DP dé ni par ξV,Ψ . Deux tournées T1 et T2 .
Sorties: Les tournées T1 et T2 améliorée par la Relocation.

1: amelioration ← true ;
2: Tant que amelioration = true faire
3:
amelioration ← f alse ;
4:
Pour i = 1 à |CT1 | faire
5:
j ← 0 ; continuer ← true ;
6:
Tant que j ≤ |CT2 | à continuer = true faire
7:
(realisable, gainDistance , gainP rof it ) ← T estRelocation (ξV,Ψ , T1 , T2 , i, j) ;
8:
Si gainP rof it ≥ 0 et alors realisable = true alors
9:
Si gainP rof it > 0 ou alors gainDistance > 0 alors
10:
(T1 , T2 ) ← ConstruireRelocation(T1 , T2 , i, j) ;
11:
amelioration ← true ; continuer ← f alse
12:
n Si
13:
n Si
14:
n Tant que
15:
n Pour
16: n Tant que
17: return (T1 , T2 ) ;

Le gain espéré par la Relocation est donné par :
βT

βT

2
1
gainP rof it = pT1 [i]
− pT1 [i]

Si celui-ci est supérieur ou égale à 0, alors on cherche à véri er la faisabilité de la relocation.
Pour cela, nous calculons la nouvelle date d'arrivée pour le client T [j+1] et grâce aux accélérateurs
nous pouvons déduire de la faisabilité de la nouvelle tournée ainsi que le gain sur la distance.

5.6.3 Exchange

Figure 11 Exemple Exhange
L'idée consiste à échanger deux clients de tournées di érentes. Pour un client xé dans la
tournée 1, on envisage successivement l'échange avec tous les clients de la tournée 2. La première
améliorante est acceptée. L'algorithme ressemble sensiblement à celui de la Relocation, seul les
DRUGBERT Ludovic

45

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
fonctions de test et de reconstruction changent. Le gain espéré par le Exchange est donné par :
βT

βT

βT

βT

2
1
1
2
gainP rof it = pT1 [i]
− pT1 [i]
+ pT2 [j]
− pT2 [j]

5.6.4 Forward OrExchange

Figure 12 Exemple Forward OrExchange
On essaye d'améliorer la tournée en avancant un client dans la tournée. Il existe aussi le
Backward OrEchange qui consiste à reculer un client dans une tournée.

5.6.5 Insertion
L'algorithme d'insertion consiste, pour chaque client non visité, à trouver la position d'insertion qui maximise son pro t. On parcourt alors toutes les tournées et on insére dans la meilleure
tournée au premier emplacement disponible. L'algorithme 11 décrit l'algorithme d'insertion.

Algorithm 11 SuppressionInsertion
Entrées: Un problème de type T OP twP DP dé ni par ξΨ,C . Une solution H .
Sorties: La solution H améliorée.
1: Pour chaque client i ∈ GH faire
2:
3:
4:

Insérer i dans la tournée qui maximise sont pro t

n Pour
return H ;

5.6.6 Suppression Insertion
Ce mouvement consiste à remplacer une séquence consécutive de clients par des clients non
visités. L'idée est de supprimer q clients consécutifs dans une tournée et de les remplacer par des
clients qui ne sont pas dans la solution. L'algorithme 12 décrit le mouvement.
La première boucle répétée sert de critère d'arrêt. L'algorithme s'arrête lorsque aucune amélioration n'a été trouvée. La deuxième boucle permet de prendre en compte toutes les tailles de
DRUGBERT Ludovic

46

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
séquence à supprimer. En général, on supprime des séquences de 2 à 3 clients. Les deux boucles
suivantes permettent de parcourir toutes les tournées de la solution. La 4ème permet de considérer toutes les séquences XOut de clients sortant. On utilise alors la fonction InsererClientT our
de l'heuristique d'insertion pour déterminer les nouveaux clients (le critière de sélection restant
inchangé). La première améliorante est acceptée.

Algorithm 12 SuppressionInsertion
Entrées: Un problème de type T OP twP DP dé nie par ξV,Ψ . Une solution H .
Sorties: La solution H améliorée.
1: Répéter
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

F ound ← f alse ; best ← 0 ; q ← 1 ;

Tant que q ≤ qmax faire
Pour chaque ht ∈ H faire
Pour chaque tournée T ∈ ht faire
Si CT ≤ q alors
TIn ← NouvelleTournee(ξV,Ψ , GH ) ;
gain ← pTIn − pT ;
Si gain > 0 alors
T ← TIn ;
F ound ← T rue ;

n Si
Sinon
Pour chaque séquence XOut de q clients consécutif dans le tour T faire
TOut ← T \ XOut ;
TIn ← InsererClientTour(ξV,Ψ , TOut , GH ) ;
gain ← pTIn − pTOut ;
Si gain > 0 alors
T ← TIn ;
F ound ← T rue ;

n Si
n Pour
n Si
n Pour
n Pour
q ← q + 1;

n Tant que
Jusqu'à F ound = f alse
return H ;

5.6.7 Structure algorithmiques
Nous proposons deux manières d'utiliser les mouvements présentés précedement notées R1
et R2 . La première méthode consiste à les appliquer les uns après les autres avec un ordre choisi
de manière arbitraire.
La deuxième méthode est inspirée du V N D (Variable Neighborhood Descend), qui est une
DRUGBERT Ludovic

47

2013

5 LE TEAM ORIENTEERING PROBLEM WITH TIME WINDOWS AND PERIOD
DEPENDENT PROFIT
composante de la métaheuristique V N S (Variable Neighborhood Search). Proposée par Hansen
et al. [34] [33], l'idée générale est de changer systématiquement de système de voisinage au cours
de la recherche locale. La V N S découle des observations suivantes :
Un minimum local selon un type de voisinage v1 n'est pas forcément un minimum local
pour le type de voisinage v2 .
Un minimum global est un minimum local, et ce quelque soit le voisinage.
Pour nombre de problèmes, des minima locaux sur un ou plusieurs voisinages sont relativement proches les uns des autres.
Cette dernière remarque, faite de manière empirique, implique qu'un minimum local est
susceptible de donner des informations sur le minimum global. Ainsi, en approfondissant la
recherche d'un minimum local à plusieurs types de voisinage, on améliore nos connaissances sur
le minimum global.
Dans la V N D le parcourt des systèmes de voisinages se fait de manière déterministe. L'algorithme 1 illustre l'enchainement des systèmes de voisinage. On note alors v1 , v2 , v3 , ..., v6 les
algorithmes Insertion, SupressionInsertion, F wdOrExchangeH , ExchangeH , RelocationH ,
2OP TH qui prennent en paramètre une solution H et qui retourne l'amélioration de ceux-ci

grâce aux algorithmes précédents. Toutes les combinaisons entre les tournées sont envisagées
pour les mouvements extra.

Algorithm 13 R2
Entrées: Un problème de type T OP twP DP dé nie par ξV,Ψ . Une solution H .
Sorties: La solution H améliorée par la récherche locale.
1: Répéter
2:
Répéter
3:
Répéter
4:
Répéter
5:
Répéter
6:
Répéter
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

(gainv1 , H) ← v1 (ξV,Ψ , H) ;
Jusqu'à gainv1 = 0
(gainv2 , H) ← v2 (ξV,Ψ , H) ;
Jusqu'à gainv2 = 0
(gainv3 , H) ← v3 (ξV,Ψ , H) ;
Jusqu'à gainv3 = 0
(gainv4 , H) ← v4 (ξV,Ψ , H) ;
Jusqu'à gainv4 = 0
(gainv5 , H) ← v5 (ξV,Ψ , H) ;
Jusqu'à gainv5 = 0
(gainv6 , H) ← v6 (ξV,Ψ , H) ;
Jusqu'à gainv6 = 0
return H ;

DRUGBERT Ludovic

48

2013

6 APPROCHES MÉTA-HEURISTIQUES POUR LE T OP T W P DP

6 Approches méta-heuristiques pour le T OP twP DP
Il existe de nombreuses métaheuristiques et autant de méthodes pour traiter les problèmes
de tournées de véhicules :
L'approche évolutionniste (algorithme génétique / mémétique) s'inspire de la théorie de
l'évolution par des processus de mutation et de sélection.
Le recuit-simulé est un algorithme qui s'inspire des cycles de refroidissement en métallurgie
pour explorer les voisinages d'une solution
La recherche tabou est la première méta-heuristique à intégrer une mémoire des opérations récentes et donc des opérations interdites, d'où son nom
La colonie de fourmis est une autre approche qui trouve son origine dans l'observation de
l'exploitation alimentaire des fourmis et la matière dont elles utilisent leur phéromone pour
faire apparaître le plus court chemin.
Le GRASP ou Greedy Randomized Adaptative Search Procedure, est une méta heuristique
basé qui ombine les méthodes gloutonnes et aléatoires.
Nous nous proposons d'appliquer un algorithme Mémétique, un GRASP et un GRASPxELS.
Les méta-heuristiques utilisent la même recherche locale expliqué précedement. On utilisera alors,
pour pouvoir les comparer, un système de budget qui limite le nombre de recherches locales
autorisées pour chacun des algorithmes.
6.1

Algorithme Mémétique

Étant donné la nature complexe du problème, pour être en mesure de résoudre des instances
de petites et de grandes tailles, nous proposons une méta-heuristique de type mémétique. Le
concept des algorithmes mémétique a été introduit par Moscato [28]. Cette approche est une
combinaison entre un algorithme évolutionnaire et une recherche locale.
La recherche s'e ectue alors dans deux espaces : l'espace des tournées et l'espace des tours
géants (obtenue par concaténation des tournées). Les heuristiques donnent des solutions initiales
sous forme de tournées. Elles sont concaténées pour donner un tour géant a n d'appliquer les
permutations. Le passage ensuite dans l'espace des tournées permet d'e ectuer la recherche locale.
Ainsi, pour passer d'un espace à un autre, nous avons deux fonctions :


SPLIT, un algorithme de programmation dynamique qui permet une projection optimale
de l'espace des tours géants vers l'espace des tournées.



CONCATENATION, qui permet une projection de l'espace des tournées vers l'espace

DRUGBERT Ludovic

49

2013


Documents similaires


Fichier PDF modele 1
Fichier PDF chapitre 2 info
Fichier PDF 1cours algorithme 1
Fichier PDF vdc
Fichier PDF 3cours algorithme 3
Fichier PDF a imprimer 1


Sur le même sujet..