The sweep algorithm :

Explication de l'algorithme

L'algorithme du balayage (Sweep Algorithm) est une méthode heuristique utilisée pour
résoudre le problème de tournée de véhicules (VRP). Cet algorithme est particulièrement
efficace pour les problèmes de VRP où les clients sont géographiquement dispersés autour
d'un dépôt central.

Étapes de l'algorithme

1. Ordonnancement radial :
• Positionnez tous les clients sur un plan en coordonnées polaires en utilisant le
dépôt comme origine.
• Calculez l'angle de chaque client par rapport à l'axe horizontal (ou vertical), en
balayant dans un sens horaire ou anti-horaire.
2. Tri des clients :
• Triez les clients en fonction de leurs angles polaires, créant ainsi une séquence
ordonnée des clients à visiter.
3. Construction des routes :
• Parcourez les clients dans l'ordre des angles polaires et affectez-les
successivement à des véhicules jusqu'à ce que la capacité du véhicule soit
atteinte.
• Une fois la capacité atteinte, commencez une nouvelle tournée avec un
nouveau véhicule.
4. Optimisation locale (optionnel) :
• Appliquez des techniques d'optimisation locale comme l'échange 2-opt ou 3-
opt pour améliorer la qualité des tournées.

Prenons un exemple de la tournée de la Véhicule :

Dépôt → Client 1 → Client 2 → Dépôt.

1. Sélectionnons les arcs [Dépôt, Client 1] et [Client 2, Dépôt].

2. Inversons l'ordre des clients entre ces deux arcs, ce qui donne la nouvelle tournée :
Dépôt → Client 2 → Client 1 → Dépôt.
3. Calculons la distance totale parcourue dans cette nouvelle tournée.
4. Comparons la nouvelle distance avec l'ancienne distance.
5. Si la nouvelle distance est plus courte, nous conservons cette nouvelle tournée
comme solution actuelle.
Exemple

Supposons que nous ayons un dépôt situé à la position (0,0) et quatre clients avec les positions
suivantes :

Étape 1 : Convertir en coordonnées polaires

Étape 2 : Tri des clients par angle

Les clients triés par angle polaire sont :

Étape 3 : Construction des routes

Supposons que chaque véhicule ait une capacité de 5.

Étape 4 : Optimisation locale (optionnelle)

par exemple :
Nous pouvons utiliser la distance euclidienne pour calculer la distance entre les différents
points dans notre exemple. La formule de la distance euclidienne entre deux points.

Aucune amélioration possible.

 The nearest neighbor
L'algorithme du "plus proche voisin" (nearest neighbor) est une heuristique simple utilisée
pour résoudre le problème de tournée de véhicules (VRP). Cet algorithme construit une
tournée en sélectionnant à chaque étape le client non encore visité le plus proche du dernier
client visité. L'idée est de minimiser la distance totale parcourue par le véhicule en choisissant
des chemins courts à chaque étape.

Étapes de l'algorithme du plus proche voisin :

1. Sélection du point de départ : Choisir un point de départ (généralement le dépôt)

pour commencer la tournée.
2. Initialisation : Marquer tous les clients comme non visités et initialiser la tournée
avec le point de départ.
3. Sélection du client suivant : À chaque étape, sélectionner le client non visité le plus
proche du dernier client visité.
4. Ajout du client à la tournée : Ajouter le client sélectionné à la tournée.
5. Marquage du client comme visité : Marquer le client sélectionné comme visité.
6. Répétition : Répéter les étapes 3 à 5 jusqu'à ce que tous les clients aient été visités.
7. Retour au point de départ : Une fois tous les clients visités, retourner au point de
départ pour terminer la tournée.

Soit A le dépôt et le tableau suivant des distances :

A B C D
A -- 45 34 20
B 45 -- 56 10
C 34 56 --- 24
D 20 10 24 --

1. Sélection du point de départ : Choisir un point de départ (généralement le dépôt) pour

commencer la tournée.

• Dépôt (A) est le point de départ.

• Tous les clients sont non visités.

• Nous commençons par le dépôt.

2. Initialisation : Marquer tous les clients comme non visités et sélectionner le dépôt comme
point de départ de la tournée.
3. Sélection du client suivant : À chaque étape, sélectionner le client non visité le plus proche
du dernier client visité.
 A B C D
A -- 45 34 21
B 45 -- 56 10
C 34 56 --- 24
D 21 10 24 --

• Nous examinons les distances entre le dépôt et tous les clients non visités.
• Nous choisissons le client le plus proche du dépôt, qui est le Client D.
• Le Client D est sélectionné comme prochain client à visiter.
• A→ D

A B C D
A -- 45 34 21
B 45 -- 56 40
C 34 56 --- 24
D 21 40 20 --

• Nous examinons maintenant les distances entre le Client D et tous les autres clients non
visités (B et C).
• Le Client C est le plus proche du Client D, avec une distance de 20 unités.
• Le client C sélectionné comme prochain client à visiter
• A→ D → C

A B C D
A -- 45 34 21
B 45 -- 56 40
C 34 56 --- 24
D 21 40 20 --

Il reste B à visiter :
• À ce stade, tous les clients ont été visités une fois, et il n'y a plus de clients non visités.
• Nous retournons donc au dépôt (A) pour terminer la tournée.

A→ D → C → B → A
The clarke and wright
L'algorithme de Clark et Wright est une heuristique populaire utilisée pour résoudre le problème
de tournée de véhicules (VRP). Il combine les tournées des véhicules pour réduire le nombre
total de véhicules nécessaires et/ou la distance totale parcourue, en exploitant les économies
réalisées en regroupant les livraisons.

Etapes :

• Construction de la tournée initiale : Pour chaque client, calculer le coût d'envoi depuis le
dépôt et le coût de retour au dépôt, puis classer les clients en fonction de ces coûts.

• Création des tournées : Commencer avec une tournée vide pour chaque véhicule. Pour
chaque paire de clients, connecter les clients avec une nouvelle arête et calculer l'économie
réalisée en utilisant cette arête au lieu d'envoyer deux véhicules différents.

• Combinaison des tournées : Fusionner les tournées lorsque cela est possible pour réduire
le nombre total de véhicules nécessaires tout en respectant les contraintes de capacité.

• Optimisation locale (optionnelle) : Appliquer des techniques d'optimisation locale, telles

que l'algorithme 2-opt, pour améliorer la solution initiale.
Exemple :
The brunch and bound

Le "branch and bound" (ou "séparation et évaluation" en français) est une technique
algorithmique utilisée pour résoudre des problèmes d'optimisation combinatoire, tels que le
problème du voyageur de commerce (TSP) ou le problème de sac à dos. Cette méthode divise
l'espace de recherche en sous-espaces plus petits (branches), les évalue pour éliminer
certaines d'entre elles, et utilise des bornes (bounds) pour guider la recherche vers la solution
optimale.

L'algorithme de branch and bound peut être appliqué à divers problèmes d'optimisation
combinatoire, tels que le TSP, le problème du sac à dos, le problème de découpage de
binaires, etc. Son utilisation permet de garantir la recherche d'une solution optimale, même si
cela peut être coûteux en termes de temps de calcul.

Principes de base du branch and bound :

1. Branching (Séparation) :
• L'algorithme commence par une solution initiale.
• Il explore l'espace de recherche en générant des solutions voisines (branches) à
partir de la solution actuelle.
• Chaque branche représente une décision prise à un nœud de l'arbre de
recherche.
2. Bounding (Évaluation) :
• Pour chaque branche générée, une borne est calculée pour estimer la qualité de
la solution associée à cette branche.
• Les bornes servent à éliminer certaines branches de l'arbre de recherche sans
les explorer plus en détail.
• Il existe deux types de bornes : les bornes supérieures (upper bounds) qui
définissent une limite maximale pour la valeur de la solution, et les bornes
inférieures (lower bounds) qui définissent une limite minimale pour la valeur
de la solution.
3. Élagage (Pruning) :
• Les branches dont la borne est pire que la meilleure solution déjà trouvée sont
élaguées (coupées) de l'arbre de recherche.
• Cela réduit l'espace de recherche en éliminant les branches qui ne peuvent pas
conduire à une solution optimale.
4. Backtracking (Retour en arrière) :
• L'algorithme explore récursivement les branches restantes jusqu'à ce que toutes
les solutions possibles aient été explorées.
• Il retient la meilleure solution trouvée jusqu'à présent.
5. Arrêt :
• L'algorithme s'arrête lorsque toutes les branches ont été explorées ou lorsque
les bornes des branches restantes sont moins bonnes que la meilleure solution
trouvée jusqu'à présent.
 • Commencez à la ville A.
• Distance totale initiale = 0 km.

• Générer les branches :

o A→B
o A→C
o A→D

À partir de B, nous pouvons aller vers C ou D, et de la même manière pour les autres nœuds.
Calculer la borne inférieure pour chaque branche

Meilleure solution est A→B→D→C→A ou A→C→D→B→A

The fisher and jaikumar algorithm

L'algorithme de Fisher et Jaikumar est une méthode heuristique pour résoudre le problème de
tournée de véhicules (VRP). Il utilise une approche de cluster-first, route-second (regrouper
d'abord, router ensuite), où les clients sont d'abord regroupés en clusters basés sur la proximité
géographique et les contraintes de capacité des véhicules, puis une tournée est construite pour
chaque cluster.

Étapes de l'algorithme de Fisher et Jaikumar :

1. Construction des clusters :

• Les clients sont regroupés en clusters basés sur leur proximité géographique et
les contraintes de capacité des véhicules.
• Un algorithme de partitionnement, comme l'algorithme de k-moyennes ou une
heuristique de construction de clusters, est utilisé pour former des clusters de
clients.
2. Construction des tournées :
• Pour chaque cluster, une tournée est construite en utilisant une heuristique de
construction de tournées, comme l'algorithme du plus proche voisin ou
l'algorithme de Christofides.
• La tournée commence et se termine au dépôt.
3. Optimisation des tournées :
• Des techniques d'optimisation locale, comme l'algorithme 2-opt ou 3-opt, sont
appliquées pour améliorer les tournées individuelles.
4. Évaluation de la solution :
• La solution est évaluée en termes de coût total (distance parcourue) et de
satisfaction des contraintes de capacité.

Exemple d'application de l'algorithme de Fisher et Jaikumar :

Supposons que nous ayons un dépôt et cinq clients, chacun avec une demande de livraison
spécifique. Les distances entre le dépôt et les clients, ainsi qu'entre chaque paire de clients,
sont connues. L'objectif est de minimiser la distance totale parcourue par les véhicules tout en
respectant les contraintes de capacité.

Données :

• Capacité maximale des véhicules : 100 unités

• Demandes de livraison des clients : C1 = 20, C2 = 30, C3 = 25, C4 = 15, C5 = 35
• Distances entre les clients (en kilomètres) :
The brunch and cut
L'algorithme Branch-and-Cut est une méthode heuristique utilisée pour résoudre des problèmes
d'optimisation combinatoire complexes, tels que le problème de tournées de véhicules (VRP).
L'algorithme fonctionne en divisant récursivement le problème en sous-problèmes plus petits
et plus faciles à résoudre, puis en éliminant les solutions qui ne sont pas optimales.

Étapes de l'algorithme Branch-and-Cut :

1. Initialisation :
• Créer une solution initiale, par exemple en utilisant la méthode de l'insertion la
plus proche.
• Calculer la distance totale parcourue par la solution initiale.
2. Branchement :
• Sélectionner une variable de décision non encore fixée, par exemple
l'affectation d'un client à un véhicule.
• Créer deux nouveaux sous-problèmes en fixant la variable de décision à deux
valeurs différentes.
3. Coupe :
• Ajouter des contraintes au problème afin d'éliminer les solutions qui ne sont
pas optimales.
• Les contraintes peuvent être basées sur des bornes inférieures et supérieures
pour la distance totale parcourue.
4. Résoudre les sous-problèmes :
• Résoudre les sous-problèmes créés à l'étape 2.
• Si un sous-problème a une solution meilleure que la solution actuelle, mettre à
jour la solution actuelle.
5. Répéter les étapes 2 à 4 jusqu'à ce qu'il n'y ait plus de sous-problèmes à résoudre.
Insertion séquentielle
L'algorithme d'insertion séquentielle est une heuristique couramment utilisée pour résoudre le
problème de tournées de véhicules (VRP). Il s'agit d'une méthode constructive qui commence
par une solution vide et insère progressivement les clients dans les tournées existantes jusqu'à
ce que tous les clients soient visités.

Fonctionnement de l'algorithme :

1. Initialisation :
o Créer une tournée vide pour chaque véhicule.
o Calculer la distance entre le dépôt et chaque client.
2. Insertion des clients :
o Pour chaque client non encore attribué:
▪ Identifier la tournée et la position d'insertion qui minimisent
l'augmentation totale de la distance.
▪ Insérer le client dans la tournée et la position sélectionnées.
▪ Mettre à jour les distances entre le dépôt et les clients restants.
3. Répéter l'étape 2 jusqu'à ce que tous les clients soient insérés.

Exemple d'application :

Considérons un problème VRP avec 5 clients et 1 véhicule. Les distances entre les points sont
représentées par la matrice suivante :

Dépôt Client 1 Client 2 Client 3 Client 4

Dépôt 0 10 15 20 25
Client 1 10 0 5 10 15
Client 2 15 5 0 15 20
Client 3 20 10 15 0 10
Client 4 25 15 20 10 0

Initialisation :

• Tournées vides : [T1 = [], T2 = []]

• Distances au dépôt : [Client 1: 10, Client 2: 15, Client 3: 20, Client 4: 25]

Première insertion :

• Choisir le client avec la distance minimale au dépôt (Client 1).

• Insérer Client 1 dans la première tournée (T1) à la première position.
• Mettre à jour les distances: [Client 2: 5, Client 3: 10, Client 4: 15]

Deuxième insertion :
 • • Identifier la tournée et la position qui minimisent l'augmentation de distance en
insérant Client 2.
• • Insérer Client 2 dans T1 à la deuxième position (T1 = [Client 1, Client 2]).
• • Augmentation de distance: 5 (distance entre Client 1 et Client 2).
• • Autres options:
• Insérer Client 2 dans T1 à la première position: Augmentation de distance = 10.
• Insérer Client 2 dans une nouvelle tournée: Augmentation de distance = 20 (distance
du dépôt à Client 2).
• Mettre à jour les distances : [Client 3 : 15, Client 4: 20]

Troisième insertion :

• Insérer Client 3 dans T1 à la troisième position (T1 = [Client 1, Client 2 ,Client 3]).
• Mettre à jour les distances : [Client 4: 10]

Quatrième insertion :

• Insérer Client 4 dans T1 à la quatrième position (T1 = [Client 1, Client 3, Client 2,

Client 4]).

Solution finale :

• Tournée unique T1 : [Dépôt - Client 1 - Client 3 - Client 2 - Client 4 - Dépôt]

• Distance totale : 40(10+ 5 + 15 + 10)