Solution du problème 25 : De la multitude des problématiques de livraison, un cas simple

La première réaction face à ce problème de tournée est de repérer l’ensemble des enchaînements de livraisons possibles par un même véhicule. Par exemple : la livraison 2 peut être réalisée par le camion qui effectue la livraison 6 puisque le ramassage de 6 doit s’effectuer à 10h et que le temps de réalisation de cette livraison suivi du temps de transfert entre le point de déchargement de 6 et le point de ramassage de 2 est de T₆₂ = 1 heures, ce qui permet de charger la livraison 2 à l’heure prévue :11h.

Le tableau suivant caractérise par la présence de 1 (possibilité) ou de 0 (impossibilité) les enchaînements possibles par le même véhicule.

Table des enchaînements possibles

Minimiser le nombre de véhicules consiste donc a faire succéder le plus d’enchaînements possibles, la série d’enchaînements obtenus correspondant au plan de transport d’un véhicule.

On visualise mieux les successions d’enchaînements en dessinant le schéma (les mathématiciens le nomment « graphe ») des possibilités d’enchaînement des différentes livraisons. On peut le représenter comme dans la figure suivante :

Graphe des enchaînements possibles

Les « sommets » du graphe représentant les livraisons à réaliser et les « arcs » (les flèches) traduisant les enchaînements réalisables.

Par exemple, on peut affecter à un premier camion les livraisons 1-6-2, à un deuxième les livraisons 7-4 ; et les livraisons 5-3 à un troisième. Ce plan transport est représenté en rouge sur le graphe les « arcs » (les flèches) en rouge correspondant aux enchaînements sélectionnés.

Minimiser le nombre de camions consiste donc à sélectionner le plus d’enchaînements possibles à condition que deux enchaînements distincts ne partent pas d’un, ou n’arrive à, un sommet commun (puisque deux véhicules distincts ne peuvent effectuer la même livraison).

En effet, si on part de la solution où 7 camions différents réalisent les 7 livraisons, créer un enchaînement diminue le besoin de camions d’une unité, en créer un second réduit encore d’un camion la flotte nécessaire et ainsi de suite. Donc on conclut que le nombre de camions plus le nombre d’enchaînements est égal au nombre de livraisons. Dans l’exemple présenté ci-dessus il y a 3 camions et 4 enchaînements.

Trouver une solution qui minimise le nombre de camions consiste à sélectionner le plus d’enchaînements possibles.

Traduit en termes quantitatifs le problème à résoudre est le suivant :

dans le tableau ci-dessous il faut mettre le maximum de « 1 » dans les cases blanches - qui sont associées aux enchaînements autorisés- à condition de ne mettre qu’un seul « 1 » par ligne et par colonne. Beaucoup plus facile que le « Sudoku » !

Tableau permettant la sélection des enchaînements possibles

Puisqu’on ne peut mettre qu’un seul 1 par ligne et par colonne, au mieux il sera possible d’utiliser 5 enchaînements puisque les colonnes 1 et 7 ne présentent aucunes cases libres.

En conséquence, il est impossible d’utiliser moins de 2 camions (nombre d’enchaînements + nombre de camions = 7)

Pour maximiser le nombre de 1 à placer, une règle heuristique consiste à occuper en priorité les rangées (colonnes ou ligne) présentant le moins de cases disponibles.

Ici, commençons à remplir la colonne 6 (1 en case [1,6]) puis la ligne 2 (1 en case [2,4]), puis la ligne 5 avec la seule case restante [5,3], ensuite la 6^ème ligne avec la seule case restée libre [6,2] et on finit par [7,5].

Remplissage séquentiel du tableau

Cinq enchaînements sont placés donc nous obtenons la solution optimale à 2 camions dont le premier réalise les livraisons :1-6-2-4, le second 7-5-3.

Remarquons que dans un cas réel où les livraisons sont beaucoup plus nombreuses le choix des « 1 » peut s’effectuer facilement avec les « solveurs » de programmation linéaire.