PARTIE I : Déterminer les tournées de véhicules

L'étude porte sur la livraison de produits à des clients, via des tournées de véhicules (des camions par exemple). Nous résumons ci-dessous la modélisation par un graphe pondéré, non orienté \(G = (V, E)\) :

• chaque somment \(v\) représente un lieu : le sommet \(v_0\) est l'entrepôt quand les autres \(v_i\) sont les clients ;
• chaque \(v_i\) est accessible à partir de \(v_0\) ; \(G\) est donc connexe ;
• chaque arête \(e_{ij}\) est pondérée par la distance \(d_{ij}\) entre les sommets \(v_i\) et \(v_j\) ;
• chaque client \(v_i\), \(i\gt 0\), commande \(w_i\) produits ;
• enfin, chaque camion a une capacité maximale \(C\).

Exemple 1

Le sujet travaille avec des graphes pondérés que l'on peut construire avec pygraph. Un nœud est identifié par une variable \(v_i\) dans le sujet (avec comme convention que \(v_0\) représente l'entrepôt), dans notre modélisation, nous n'utiliserons que les numéros \(0, 1...\)

Le graphe des distances

Le graphe \(G_1\) du sujet

\(G_1\)Le code

G1 = pg.Graph(5)
G1.add_edges_from([(0, 1, 2), (0, 2, 1), (1, 2, 1), (0, 3, 4.5), (0, 4, 5), (3, 4, 4)])
G1.position([(4, 1, 0), (3, 0, 1), (0, 1.5, 1.5), (2, 2.5, 2.5), (1, 3.5, 1.5)], ech=0.8)

Les autres informations

Les demandes des clientsLa matrice d'adjacence du grapheLe tableaux dist des plus courtes distances

Donné en Figure 1b du sujet.

clients	\(1\)	\(2\)	\(3\)	\(4\)
demandes	\(5\)	\(6\)	\(4\)	\(3\)

Donné en Figure 1c du sujet.

\[\mathnormal{adjacence} = \left( \begin{array}{lllll} 0 & 2 & 1 & 4,5 & 5\\ 2 & 0 & 1 & \infty & \infty\\ 1 & 1 & 0 & \infty & \infty\\ 4,5 & \infty & \infty & 0 & 4\\ 5 & \infty & \infty & 4 & 0\\ \end{array} \right)\]

Donné en Figure 1d du sujet.

\[\mathnormal{dist} = \left( \begin{array}{lllll} 0 & 2 & 1 & 4,5 & 5\\ 2 & 0 & 1 & 6,5 & 7\\ 1 & 1 & 0 & 5,5 & 6\\ 4,5 & 6,5 & 5,5 & 0 & 4\\ 5 & 7 & 6 & 4 & 0\\ \end{array} \right)\]

Génération des informations

La matrice d'adjacence

À partir du graphe \(G_1\), on peut construire sa matrice d'ajacence c'est-à-dire la matrice qui donne pour un couple \((i, j)\) la valeur du poids de l'arête associée ou \(\infty\) si l'arête n'existe pas.

Nous allons donner la fonction Python adjacence qui prend un graphe au sens de pygraph et qui renvoie cette matrice sous la forme d'un tableau de tableaux. C'est ici l'occasion de voir que pygraph n'est pas que un outil de visualisation, mais permet aussi de manipuler le graphe comme structure.

La constante \(\infty\)

INF = float('inf')

La matrice d'adjacence d'un graphe

Dans pygraph, le poids d'une arête \((u, v)\) d'un graphe \(g\) est donné par g.edge_view(u, v).weight. node_ids() et edges() sont les deux méthodes pour parcourir les sommets et les arêtes.

def adjacence(g):
    """Crée la matrice d'adjacence à partir du graphe g"""
    adj = [[0 if v == s else INF for v in g.node_ids()] for s in g.node_ids()]
    for s, v in g.edges():
        poids = g.edge_view(s, v).weight
        adj[s][v] = poids
        adj[v][s] = poids
    return adj 

Calcul de la matrice d'adjacence de \(G_1\)

>>> A1 = adjacence(G1)
>>> A1
[[0, 2, 1, 4.5, 5],
[2, 0, 1, inf, inf],
[1, 1, 0, inf, inf],
[4.5, inf, inf, 0, 4],
[5, inf, inf, 4, 0]]

Le tableau des plus courtes distances

Question 1

Le sujet donne, en pseudo-langage, l'algorithme de Floyd-Warshall pour ce calcul dont l'entrée est la matrice d'adjacence \(A\) :

Floyd-Warshall

dist <- A
foreach vertex z in V do
    foreach vertex x in V do
        foreach vertex y in V do
            if dist(x, z) ≠ ∞ and dist(z, y) ≠ ∞ and
            dist(x, z) + dist(z, y) < dist(x, y) then
                dist(x, y) <- dist(x, z) + dist(z, y)
return dist

Avertissements

1. Nul besoin de parler de np.inf pour l'infini, float('inf') fourni un infini.
2. L'affectation de tableau de tableaux dist <- A est une vraie difficulté si on souhaite étudier ce sujet en Terminale NSI ; en effet il faut veiller à effectuer correctement la copie profonde.
3. Pas besoin non plus de tester que les distances sont différentes de l'infini.

Traduire en Python l'algorithme précédent.

Réponse

def floyd_warshall(adj):
    dist = [ligne.copy() for ligne in adj]
    noeuds = list(range(len(adj)))
    for z in noeuds:
        for x in noeuds:
            for y in noeuds:
                d = dist[x][z] + dist[z][y]
                if d < dist[x][y]:
                    dist[x][y] = d
    return dist

Tableau des distances de l'exemple

>>> DIST1 = floyd_warshall(A1)
>>> DIST1
[[0, 2, 1, 4.5, 5],
[2, 0, 1, 6.5, 7],
[1, 1, 0, 5.5, 6],
[4.5, 6.5, 5.5, 0, 4],
[5, 7, 6, 4, 0]]

Calcul des tournées : algorithme naïf

Gestion des tournées

Dans la suite, on s'intéresse aux livraisons. Il s'agit d'attribuer à un certain nombre de camions, une liste de clients à livrer, dans un certain ordre, en partant de l'entrepôt (le nœud \(0\) du graphe) et en y revenant. Les questions \(2\) à \(4\) s'intéressent à un algorithme naïf et ses limitations. Voici la description de cet algorithme dont l'entrée est le tableau des distances, le tableau des demandes des clients et la capacité maximale des camions.

1. on prend un premier camion et on lui affecte le client de plus proche qui n'a pas encore été planifié,
2. si la demande de ce client ne met pas le camion en surcharge alors on procède effectivement à l'affectation,
3. sinon on essaie le \(2^e\) client le plus proche etc.
4. on continue ainsi jusqu'à atteindre la capacité du camion,
5. on recommence avec un autre camion, jusqu'à ce que tous les clients soient affectés à une tournée

Modéliser

Il nous faut modéliser deux choses : les tournées de tous les clients et la tournée d'un camion.

• une tournée : une liste Python de clients
• les tournées : une liste de tournée

Question 2

2.1

Appliquer l'algorithme naïf sur les données de l'exemple 1.

Réponse

• On initialise une première tournée avec le client le plus proche de l'entrepôt (il s'agit du client \(2\)) : [2] ; la charge du camion est alors de \(6\) (la demande du client \(2\)),
• on continue : le client le plus proche de \(2\) est \(1\) avec une demande à \(5\) ce qui porterait la charge totale du camion à \(11\) on est en-dessous de la capacité max qui est \(12\) ; on a donc [2, 1]
• le client suivant le plus proche de \(2\) est \(3\) mais la demande viendrait surcharger le camion, on doit donc initier un nouveau camion, avec le client le plus proche de l'entrepôt (il se trouve que c'est toujours le client \(3\)) : [3]
• le dernier client est pris en charge par le \(2^e\) camion : [3, 4]

Les tournées sont donc, avec leurs couts respectifs :

• [2, 1] pour un cout de \(4\) (\(0 \rightarrow 2 : 1\), \(2 \rightarrow 1 : 1\), \(1 \rightarrow 0 : 2\)) ;
• [3, 4] pour un cout de \(13.5\).

On peut d'ailleurs écrire une fonction cout qui, étant donnés un tableau de distances et une tournée, renvoie le cout :

Une fonction pour le calcul du cout

def cout(dist, tournee):
    km = dist[0][tournee[0]]
    for i in range(1, len(tournee)):
        km += dist[tournee[i-1]][tournee[i]]
    km += dist[tournee[-1]][0]
    return km

Par exemple :

>>> cout(DIST, [2, 1])
4
>>> cout(DIST, [3, 4])
13.5

Le cout total peut alors se calculer ainsi :

def cout_total(dist, tournees):
    return sum(cout(dist, t) for t in tournees)

2.2

En considérant l'objectif de minimiser la distance totale parcourus par tous les véhicules, peut-on trouver une autre solution ? Si oui, laquelle ?

Réponse

Il ne semble pas possible d'améliorer sur ce petit exemple.

Question 3

On nous demande l'impact de la suppression du client \(v_2\) sur le reste de la gestion. Alors sans le client \(v_2\) une seule tournée suffit : \(1 \rightarrow 3 \rightarrow 4\) pour une charge totale à \(12\).

Question 4

La question

Il s'agit d'écrire la fonction algo_naif qui code la méthode de génération de tournées.

Avertissements

On regrettera dans un sujet de l'agrégation le nom respect PEP8 sur le nommage de la fonction ainsi que l'indication constante entière pour le paramètre c (C dans le sujet) : si c'est une constante ça n'est pas un paramètre.

Avant d'écrire la fonction algo_naif, nous allons présenter quelques fonction auxiliaires.

Quelques fonctions annexes

Commençons par trier les voisins d'un nœud \(s\) du plus proche au plus éloigné. C'est ce que réalise la fonction voisins_proches ci-dessous.

def voisins_proches(dist, s, visites):
    return sorted((v for v in range(1, len(dist)) if v not in visites), key=lambda x: dist[s][x])

Nous aurons aussi besoin de calculer la charge d'un véhicule :

def charge(tournee, demandes):
    return sum(demandes[c] for c in tournee)

Réponse

Notre fonction commence par :

• préciser que l'entrepôt a été planifié (ce qui permet de ne pas le considérer dans les tournées qui vont être créées) (ligne 3)
• trouver les clients proche de l'entrepôt (ligne 4) et
• initialiser la liste des tournées avec une première tournée qui ne contient que le client le plus proche (ligne 5)
• ensuite il reste à faire \(n\) tours de boucle (où \(n\) est le nombre de vrais clients moins \(1\), c'est-à-dire nb_clients - 2 dans notre modèle qui comptabilise l'entrepôt parmi les clients)

def algo_naif(dist, demandes, capacite):
    nb_clients = len(dist)
    planifies = {0}
    clients = voisins_proches(dist, 0, planifies)
    tournees = [[clients[0]]]
    for _ in range(nb_clients - 2):
        trouve = False
        tournee = tournees[-1]
        charge_courante = charge(tournee, demandes)
        dernier_client = tournee[-1]
        planifies.add(dernier_client)
        voisins = voisins_proches(dist, dernier_client, planifies)
        for suivant in voisins:
            charge_a_ajouter = demandes[suivant]
            if charge(tournee, demandes) + charge_a_ajouter <= capacite:
                tournee.append(suivant)
                trouve = True
                break
        if not trouve:
            voisins = voisins_proches(dist, 0, planifies)
            nlle_tournee = [voisins[0]]
            tournees.append(nlle_tournee)
    return tournees

Appliquons sur l'exemple...

>>> DEMANDES = [None, 5, 6, 4, 3]
>>> C = 12
>>> T1 = algo_naif(DIST, DEMANDES, C)
>>> T1
[[2, 1], [3, 4]]

La fin du sujet consistera à :

• montrer qu'il existe des situations où l'algorithme naïf ne donne pas la solution optimale
• coder un autre algorithme

Calcul des tournées : algorithme de Clarke et Wright (I)

Question 5

Il faut exhiber deux configurations qui trompent l'algorithme naïf. Voyons déjà un :

Construction d'un exemple 2

Un \(2^e\) exemple

\(G_2\)Le codeLes autres informations

G2 = pg.Graph(7)
G2.add_edges_from([(0, 1, 2), (0, 4, 4), (0, 6, 3), (1, 2, 7), (1, 3, 5),
                   (2, 3, 2), (2, 6, 1), (3, 5, 1), (4, 5, 1)])
G2.position([(0, 3, 2), (1, 2, 1), (2, 3, 0), (3, 1, 0), (4, 1, 2),  (5, 0, 1), (6, 4, 1)], ech=0.6)

>>> A2 = adjacence(G2)
>>> DIST2 = floyd_warshall(A2)
>>> D2 = [None, 5, 5, 4, 3, 4, 2] # les demandes

On peut alors lancer l'algorithme naïf pour obtenir des tournées.

Solution naïve

La solutionLe code

Voici la solution naïve, donnant \(3\) tournées pour un cout total de \(25\). Grâce à une fonction de colorisation du graphe pour mettre en avant les tournées :

la fonction de colorisation

def colorise(g, tournees):
    for color_id, tournee in enumerate(tournees):
        for c in tournee:
            g.color_on(c, color_id)

>>> S2 = algo_naif(DIST2, D2)
>>> colorise(G2, S2)
>>> cout_total(DIST2, S2)
25

Une meilleure solution

Une autre solution

La solutionLe code

Les deux tournées ci-dessous offrent un meilleur cout :

>>> S2b = [[1, 2, 6], [3, 5, 4]]
>>> cout_total(DIST2, S2b)
24

L'algorithme de Clarke et Wright

Description de l'algorithme

1. on commence par \(n\) tournées : \(v_0 \rightarrow v_i \rightarrow v_0\), pour tout \(i \lt 0\) (chaque client par 1 véhicule différent)
2. on calcule les économies \(s(i, j)\) pour fusionner deux clients \(v_i\) et \(v_j\) en une même tournée, pour tout \(i, j \lt 0\) et \(i \neq j\) : \(s(i, j) = d(i, 0) + d(0, j) - d(i, j)\)
3. on trie les économies par ordre décroissant ;
4. en parcourant la liste des économies, on fusionne les deux tournées associées si :
   1. les deux clients ne sont pas déjà dans la même tournée,
   2. aucun des deux clients n'est à l'intérieur de la tournée (donc soit 1er soit dernier),
   3. la somme des demandes des deux tournées ne dépasse pas la limite de capacité

À noter que les points 4a et 4b peuvent être testés en même temps pour plus d'efficacité : en effet, si on note \(i\) et \(j\) les deux clients, \(i\) est l'une des extrémités d'une des tournées et \(j\) de l'autre.

La fonction savings

Il s'agit d'une des idées à la base de cet algorithme : lorsqu'on considère deux sommets \(i\) et \(j\) est-ce qu'il est préférable de faire les allers-retour depuis l'entrepôt ou une boucle incluant les deux sommets ? Dit autrement, veut-on remplacer un aller depuis l'entrepôt vers chacun des sommets par le trajet entre les sommets ? Voyons sur un petit exemple :

Illustration du concept d'économie

Dans le graphe ci-dessous, il est plus rentable de parcourir la boucle \(0\rightarrow 1\rightarrow 2\rightarrow 0\) (cout total \(11\)) que les allers-retour \(0\leftrightarrow 1\) et \(0\leftrightarrow 2\) (cout total \(16\)).

La fonction savings

def savings(dist):
n = len(dist)
sav = [[0] * n for _ in range(n)]
for i in range(1, n):
    for j in range(i+1, n):
        sav[i][j] = sav[j][i] = dist[i][0] + dist[0][j] - dist[i][j]
return sav

La fusion de tournées

La seconde idée de l'algorithme est le concept de fusion de tournées. Voyons voir cela sur des exemples.

Fusion de tournées

Cas n°1Cas n°2Cas n°3Cas n°4

Dans le schéma ci-dessous, nous avons deux tournées :

• la bleue qui commence par le client \(i\) et en inclus \(3\) autres
• la jaune qui commence par le cliant \(j\)

Si la somme des charges ne dépasse pas la capacité maximale, on peut fusionner ces deux tournées par leurs extrémités \(i\) et \(j\) pour obtenir une seule (à condition que l'économie sur le couple \((i, j)\) soit effective) :

Nous avons au total \(4\) cas suivant que \(i\) (resp. \(j\)) se trouve en tête ou en queue de sa tournée.

Similaire au cas n°1 : \(i\) est en tête de sa tournée mais cette fois \(j\) est à la fin de la sienne. On obtient la même fusion que le cas n°1 à condition de renverser la tournée jaune (ou ajouter les sommets jaune en commençant par la fin).

Similaire au cas n°1 : \(j\) est bien en tête de sa tournée mais cette fois \(i\) est à la fin ; la fusion se fera alors par la droite de la tournée bleue.

À vous de le dessiner !

Réponse

Similaire au cas n°2 : \(j\) est bien en fin de sa tournée mais cette fois \(i\) est aussi à la fin ; la fusion se fera alors par la droite de la tournée bleue en renversant le parcours de la tournée jaune.

Question 6

Cette question aborde la modélisation d'une tournée en POO. Mais bizarrement, l'énoncé parle de la classe Tournee et nous donne \(4\) de ses méthodes, mais aucune propriété :

• distance : cette méthode calcule le cout total de la tournée ; elle a donc besoin du tableau des distances. Pour nous, ce tableau pourrait être l'une des propriétés de la tournée,
• affiche : affiche au format texte la tournée ie la liste ordonnée des clients visités, en commençant et en finissant par \(0\), le code de l'entrepôt ; la méthode donne aussi le chargement total de la tournée (la somme des demandes des différents clients),
• fusionnable : doit permettre de déterminer si la tournée courante (celle qui appelle la méthode) peut fusionner avec une autre tournée via un couple de clients (il s'agit là de vérifier les contraintes a, b et c du point 4 de l'algorithme de Clarke et Wright),
• enfin fusion : réalise effectivement la fusion si celle-ci a été déclarée possible.

Nous allons voir que les méthodes fusionnables et fusion ne sont pas simples, notamment, fusionnable ne peut pas se contenter de renvoyer un booléen : fusion (qui va appeler fusionnable) a besoin de plus d'informations. Comme nous l'avons vu, la fusion se fait selon plusieurs cas de figures et il nous faut savoir lequel est concerné au moment de fusionner.

La bonne structure pour les clients

Les différents cas de fusion nous font choisir une structure de type file à double entrée pour modéliser les clients. En effet, on doit pouvoir ajouter au début et à la fin ; la simple liste Python n'est donc pas efficace.

Nous pouvons utiliser la structure deque (double ended queue) du module collections :

>>> from collections import deque
>>> test = deque([])  # création d'une file vide
>>> test.append('quelque chose')  # ajout à droite
>>> test.appendleft('autre chose')  # ajout à gauche
>>> test.pop()  # retrait d'un élément à droite
>>> test.popleft()  # retrait d'un élément à gauche

Toutes ces opérations sont en \(O(1)\).

Commençons par une définition de la classe Tournee, son initialiseur qui donne les propriétés :

Définition de Tournee

class Tournee:

    def __init__(self, client, distances, demandes, capacite_max=12):
        self.id = client  # le client initial sert d'identifiant pour la tournée
        self.dist = distances
        self.demandes = demandes
        self.limite = capacite_max
        self.clients = deque([client])
        self.ptc = demandes[client]  # ptc pour poids total en charge

Réponse à la question 6 : distance et affiche

ces deux petites méthodes ne posent pas de difficulté :

class Tournee:
    ...

    def distance(self):
        clients = self.clients
        dist = self.dist
        km = dist[0][clients[0]]
        for i in range(1, len(clients)):
            km += dist[clients[i-1]][clients[i]]
        km += dist[clients[-1]][0]
        return km

    def affiche(self):
        str_tournee = ' '.join(str(c) for c in self.clients)
        print(f'tournée 0 {str_tournee} 0, chargement {self.ptc}')

La méthode fusionnable

Voilà ce que notre méthode fusionnable doit réaliser :

• vérifier les points 4a et 4b de l'algorithme,
• mémoriser l'information de quel cas de figure de fusion doit être mis en œuvre dans le cas où effectivement la fusion est possible ; appelons \(P\) (comme positions) cette information,
• vérifier que la fusion ne provoque pas de surcharge et transmettre dans ce cas l'information \(P\)

Deux petites méthodes auxiliaires

Pour vérifier les points 4a et 4b, nous avons besoin d'une autre tournée et de deux clients (ceux de la fusion potentielle). Il nous faut déterminer si les clients sont bien des extrémités de nos deux tournées mises en œuvre et, si oui, de quelles extrémités (gauche ou droite) :

class Tournee:
    ...

    def extremite(self, client):
        """renvoie 0 si le client est en tête de la tournée -1 s'il est dernier
        et None sinon
        """
        if self.clients[0] == client:
            return 0
        elif self.clients[-1] == client:
            return -1

    def points_4a_4b(self, autre_tournee, deux_clients):
        """renvoie None si les contraintes ne sont pas vérifiées
        - 0, 0 si on est dans le cas 1 de fusion
        - 0, -1 s'il s'agit du cas 2
        - -1, 0 pour le cas 3
        - -1, -1 enfin pour le cas 4
        """
        if self.id != autre_tournee.id:
            i, j = deux_clients
            for u, v in ((i, j), (j, i)):
                position_u, position_v = self.extremite(u), autre_tournee.extremite(v)
                if position_u is not None and position_v is not None:
                    return position_u, position_v

Tout est en place pour la méthode fusionnable :

Réponse à la question 6 : fusionnable

class Tournee:
    ...

    def fusionnable(self, autre_tournee, deux_clients):
        positions = self.points_4a_4b(autre_tournee, deux_clients)
        if positions is not None and self.ptc + autre_tournee.ptc <= self.limite:
            return positions

Si la fusion est possible, on récupère de fusionnable un couple \((p_1, p_2)\) parmi les quatre possibilités : \((0, 0)\), \((0, -1)\), \((-1, 0)\) et \((-1, -1)\). Dans les cas \(2\) et \(4\), lorsque \(p_2\) vaut \(-1\), nous devons parcourir à rebours les clients de la tournée correspondante ; nous utiliserons simplement la méthode reverse disponible sur la deque. Dans les cas \(1\) et \(2\), lorsque \(p_1\) vaut \(0\), nous devons insérer par la gauche. Et au final, cette méthode renvoie True si la fusion a eu lieu, False sinon. Ces considérations nous amènent à cette solution pour la méthode fusion :

Réponse à la question 6 : fusion

class Tournee:
    ...

    def fusion(self, autre_tournee, deux_clients):
        positions = self.fusionnable(autre_tournee, deux_clients)
        if positions is not None:
            p1, p2 = positions
            if p2 == -1:
                autre_tournee.clients.reverse()
            for c in autre_tournee.clients:
                self.ajout(c, gauche=p1 == 0)
            return True
        return False

La petite méthode ajout qui permet d'ajouter un client à une tournée :

• ajouter du bon côté le client à la file des clients,
• augmenter le poids total en charge de la valeur de la demande du client.

Ajouter un client

class Tournee:
    ...

    def ajout(self, client, gauche=False):
        if gauche:
            self.clients.appendleft(client)
        else:
            self.clients.append(client)
        self.ptc += self.demandes[client]

L'ensemble de la définition de la classe Tournee est disponible ici : tournee.py. Le script intègre aussi la mise en œuvre de l'algorithme de Clarke et Wright.

Calcul des tournées : algorithme de Clarke et Wright (II)

Question 7

Enfin, nous sommes en mesure de coder l'algorithme de Clarke et Wright.

Avant de voir le code Python, voici un autre énoncé de la méthode :

Reformulation de l'algorithme

1. Initialiser ce qui va être le résultat de notre fonction une collection de tournées ; dans l'implémentation Python, nous choisissons un dictionnaire car lors des opérations de fusion, nous supprimerons des tournées
2. Calculer les économies et les trier par ordre décroissant
3. Tant qu'il y des fusions possibles :
   1. on récupère le couple de clients de la première économie
   2. on trouve les tournées impliquées
   3. on essaie de fusionner ; si la fusion est effective on retire la tournée qui a été absorbée

Voici la traduction en Python :

Réponse

def clarke_wright(dist, demandes, capacite=12):
    nb_clients = len(demandes)
    tournees = {c: Tournee(c, dist, demandes, capacite) for c in range(1, nb_clients)}
    sav = savings(dist)
    sorted_savings = sorted(((sav[i][j], i, j) for i in range(len(sav)) for j in range(i+1, len(sav))), reverse=True)
    fini = False
    while not fini:
        fini = True
        for _, i, j in sorted_savings:
            id_de_i, tournee_de_i = quelle_tournee(tournees, i)
            id_de_j, tournee_de_j = quelle_tournee(tournees, j)
            if tournee_de_i is not None and tournee_de_j is not None\
               and tournee_de_i.fusion(tournee_de_j, (i, j)):
                del tournees[id_de_j]
                fini = False
    return tournees

Nous pouvons essayer notre algorithme :

Tournées de l'exemple 2

On retrouve les tournées S2b déjà illustrée :

>>> S3 = clarke_wright(DIST2, D2)
>>> S3[1].affiche()
tournée 0 2 6 1 0, chargement 12
>>> S3[4].affiche()
tournée 0 3 5 4 0, chargement 11

Fin et conclusion

L'article étant déjà très long, nous ne traitons pas les dernières questions (8, 9, 10 et 11) qui sont des questionnements d'extension sur la modélisation POO avec une séparation de la gestion des véhicules de la partie tournée via une interface abstraite nommée transport.

Comme pour les autres sujets traités dans cet article en quatre sections, le but était avant tout d'explorer les graphes (thème de notre groupe de recherche IREM) avec l'idée d'en tirer des activités faisables dans d'autres niveaux que les classes préparatoires.

Enfin, pour terminer, nous avons voulu tester sur un exemple trouvé sur internet. Cette vidéo sur youtube montre la résolution du problème de tournées de véhicule en utilisant l'outil d'optimisation Gurobi et son extension Python gurobipy :

Génération du graphe

En utilisant le module numpy, l'auteur génère un graphe de 11 nœuds (le nœud \(0\) représentant toujours l'entrepôt) par leurs coordonnées dans le plan, coordonnées comprises entre \(0\) et \(200\) pour les abscisses et \(0\) et \(100\) pour les ordonnées. Chaque point est (virtuellement) relié à chacun des autres par une arête dont le poids est la distance euclidienne entre les points. Voici sa représentation avec le module matplotlib (5:30 de la vidéo) :

G10 : un exemple tiré du net

Construisons cet exemple à l'aide de nos outils :

G10 à l'aide pygraph

G10Le code

Il a fallu générer les points via leurs coordonnées dans le plan. Pour obtenir les mêmes positions, nous avons utilisé la même technique que l'auteur mais avons divisé par \(10\) toutes les coordonnées.

import numpy as np

NB = 10
np.random.seed(0)  # pour initialiser la séquence pseudo aléatoire
XC = [np.random.rand() * 20 for _ in range(NB + 1)]
YC = [np.random.rand() * 10 for _ in range(NB + 1)]

Puis créer le graphe :

G10 = pg.DiGraph(NB + 1)
G10.position([(i, XC[i], YC[i]) for i in range(NB + 1)], ech=0.4)

Pourquoi un graphe orienté ? Nous représentons le graphe initial des clients sans arêtes puisque toutes les arêtes sont possibles, ce qui rend le graphe difficile à lire. Nous ne ferons apparaitre à la fin que les arcs pour représenter les tournées.

Les autres informations

• La matrice d'adjacence A10 créée à partir des distances euclidiennes (appelée aussi hypot dans numpy) :

  def hypot(x1, y1, x2, y2):
      return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
  
  A10 = [[hypot(XC[i], YC[i], XC[j], YC[j]) for j in range(NB + 1)] for i in range(NB + 1)]
  

• Le tableau des distances DIST10 est identique à la matrice d'adjacence
• La capacité maximale choisie par l'auteur est \(20\)
• Le tableau des demandes : D10 = [None, 4, 4, 4, 8, 1, 2, 1, 5, 8, 4]

La solution

Notre solutionLe codeLa solution de l'auteur

Les tournées calculées par l'algorithme de Clarke et Wright :

S10 = clarke_wright(DIST10, D10, 20)

On peut alors écrire une petite fonction qui prend un graphe orienté et une collection de tournées en paramètres et qui va créer les arcs des différentes tournées et colorier les sommets :

def add_path(g, d_tournees):
    for color_id, tid in enumerate(d_tournees):
        sommets = d_tournees[tid].clients
        g.add_edge(0, sommets[0])
        g.add_edge(sommets[-1], 0)
        for i in range(len(sommets) - 1):
            noeud, suivant = sommets[i], sommets[i+1]
            g.add_edge(noeud, suivant)
            g.color_on(noeud, color_id)
        g.color_on(suivant, color_id)

Et l'appliquer :

add_path(G10, S10)

(à 21:17 environ sur la vidéo)

la tournée en haut à droite est la même ; mais il semble y avoir une différence pour le reste des clients. La représentation de l'auteur n'est pas très lisible puisqu'on ne sait pas exactement combien il y a de tournées. Mais, à cause de la capacité maximale de \(20\), il n'est pas possible de grouper dans une seule tournée les clients \(5, 3, 4, 9, 6\). La tournée \(5, 3, 4\) d'une charge de \(13\) pourrait éventuellement intégrer le client \(6\) qui a une demande à \(2\) (mais pas \(9\) dont la demande est à \(8\)).

Mais la tournée résultante intègre le trajet \(4\rightarrow 6\) très couteux (on le voit sur le graphe). En calculant le cout total de cette solution (trois tournées \((1, 7, 8, 10, 2)\), \((5, 3, 4, 6)\) et \((9)\)) on obtient \(49\) (arrondi à l'entier le plus proche) contre \(47\) pour la solution S10.