VRPTW expliqué : optimiser une tournée avec fenêtres horaires

Si vous avez lu l'article sur le TSP, vous savez déjà comment ordonner des livraisons pour minimiser la distance. Mais en pratique, vos clients ne vous attendent pas à n'importe quelle heure. Un mariage à 14h, un déjeuner d'affaires à 12h pile, un cabinet médical fermé entre 12h30 et 14h. C'est précisément le rôle du VRPTW, le Vehicle Routing Problem with Time Windows. C'est lui qui prend le relais quand le TSP atteint sa limite.

Du TSP au VRPTW : l'évolution naturelle

Le TSP minimise la distance, point. Il suppose que toutes les adresses sont accessibles à tout moment. C'est une simplification utile pour comprendre le problème, mais qui ne reflète pas votre réalité quotidienne.

Le VRPTW ajoute deux ingrédients essentiels :

1. Plusieurs véhicules potentiels (le V de VRP) : vous pouvez avoir 1, 2, 5 livreurs en simultané
2. Des fenêtres horaires par client (le TW de Time Windows) : chaque adresse a une plage [ouverture, fermeture]

Et soudain, ce qui était un problème de géométrie pure devient un problème temporel. L'ordre optimal n'est plus juste « le plus court », c'est « le plus court qui respecte tous les créneaux ».

Un exemple concret

Imaginons une journée typique de traiteur : 6 livraisons à effectuer, départ du dépôt à 10h00.

Le TSP vous dirait peut-être : « passez par A, B, C, D, E, F dans cet ordre, c'est le plus court ». Mais si vous arrivez chez A à 12h05 alors qu'il fallait être là entre 11h45 et 12h00, vous êtes en retard. Le client n'est pas content. Vous perdez le contrat.

Le VRPTW trouve un ordre qui :

1. Visite chaque adresse dans sa fenêtre
2. Minimise la distance et le temps total parmi tous les ordres faisables
3. Vous prévient à l'avance si certaines fenêtres ne sont pas atteignables (auquel cas, il faut un véhicule de plus, ou décaler le départ)

Le résultat EDF sur cet exemple

OptiRoad classe les arrêts par fenêtre de fermeture croissante, puis simule la journée à partir du départ à 10h00. L'ordre obtenu est : B (Bastille), puis E (Étoile), A (République), C (Châtelet), D (Montparnasse) et enfin F (Pigalle). Voici le planning détaillé que vous obtenez à l'écran :

Chez B, vous arrivez très en avance (10h18) : le véhicule patiente jusqu'à l'ouverture à 11h00, puis livre. Chaque fenêtre est respectée du premier au dernier arrêt. Un ordre purement « plus courte distance » à la TSP ne garantirait jamais ce résultat.

Pourquoi c'est plus dur que le TSP

Le TSP est déjà NP-difficile (cf. l'article TSP). Le VRPTW l'est encore plus, car il faut simuler le déroulement temporel de la tournée pour valider chaque solution candidate :

• À chaque arrêt, on calcule l'heure d'arrivée prévue
• Si on arrive avant l'ouverture, on attend (perte de temps)
• Si on arrive après la fermeture, la solution est invalide (rejetée)
• Le serviceTime (durée sur place) s'ajoute à l'heure de départ vers le suivant

Le solveur ne peut pas se contenter d'optimiser sur la distance brute. Il doit construire le planning détaillé de la journée pour chaque ordre testé.

Fenêtre dure ou fenêtre souple ?

En théorie, il existe deux familles de fenêtres horaires. Une fenêtre dure doit être respectée : une solution qui la rate est purement et simplement rejetée, comme un créneau médical ou une cérémonie qui ne se décalent pas. Une fenêtre souple tolère un retard, mais au prix d'une pénalité que le solveur cherche à minimiser.

OptiRoad traite les fenêtres comme dures pour juger la faisabilité d'une tournée. La différence, c'est qu'au lieu de casser silencieusement un créneau pour gagner quelques kilomètres, OptiRoad signale l'arrêt en retard avant même le départ. Vous décidez : prévenir le client, ajouter un véhicule ou décaler l'heure de départ. À noter : le drapeau strict posé sur une fenêtre est une donnée sémantique visible dans le planning (une gestion plus avancée arrivera plus tard).

Les approches pour résoudre le VRPTW

1. Earliest Deadline First (EDF)

À chaque étape, on choisit le client dont la fenêtre se ferme le plus tôt parmi ceux qu'on peut encore atteindre. Simple, rapide, donne d'excellents résultats en pratique. C'est l'approche utilisée par OptiRoad.

2. Insertion heuristics

On part d'une tournée vide, on insère les clients un par un en cherchant la position qui minimise le coût total tout en respectant les fenêtres. Bonne qualité, calcul plus long.

3. Métaheuristiques (recuit simulé, tabou, génétique)

Pour les très grosses instances (centaines de stops, multi-véhicules complexes). Donnent des solutions près de l'optimum mais demandent du temps de calcul.

4. Programmation par contraintes

Approche académique très puissante mais lourde à mettre en œuvre, réservée à des cas spécifiques.

Le temps de service change tout

On l'oublie souvent, mais le temps passé à chaque arrêt (le serviceTime) décale toutes les arrivées suivantes. Cinq minutes multipliées par quinze livraisons, c'est plus d'une heure qui recule sur la journée. Ignorer ce temps donne un planning qui tient sur le papier mais prend du retard dans la vraie vie.

OptiRoad résout donc le temps de service arrêt par arrêt, selon une priorité claire : la valeur saisie manuellement sur l'arrêt l'emporte, sinon celle du contact correspondant dans votre carnet d'adresses (matché par coordonnées), sinon le réglage par défaut du compte (5 minutes). Chaque ETA affichée intègre ainsi le temps réellement passé sur place.

Comment OptiRoad implémente le VRPTW

Quand vous activez « Fenêtres horaires » dans le dashboard (plan Pro ou Business), voici ce qu'OptiRoad fait :

1. Tri des clients par fenêtre de fermeture croissante (avec une priorité spéciale pour les arrêts marqués priority: high)
2. Construction de la tournée par insertion EDF : à chaque étape, on prend le client suivant qui respecte la fenêtre courante et minimise le détour
3. Simulation du planning : à partir de l'heure de départ, on calcule pour chaque arrêt :
   • heure d'arrivée prévue (en tenant compte de la distance)
   • heure de début de service (= max(arrivée, ouverture))
   • heure de départ (= début + serviceTime)
4. Détection des retards : si l'arrivée prévue dépasse la fermeture, le stop est marqué late: true dans la réponse, vous êtes prévenu avant de partir
5. Pas de 2-opt quand VRPTW est actif : l'ordre EDF prime sur l'optimisation distance, pour ne pas casser les contraintes temporelles

Le résultat dans l'app : un tableau récapitulatif clair montrant l'heure d'arrivée prévue à chaque client, les éventuels retards en rouge, et la durée totale réelle de la journée (avec les temps d'attente compris).

Quand utiliser le VRPTW vs le TSP simple

• TSP : tournée de livraison classique sans contrainte horaire forte (e-commerce, courrier, etc.). Vous arrivez quand vous arrivez.
• VRPTW : dès qu'au moins quelques clients ont une plage horaire imposée. Traiteurs, fleuristes (cérémonies), aides à domicile (créneaux médicaux), interventions techniques sur RDV.

OptiRoad bascule automatiquement sur le VRPTW dès que vous renseignez au moins une fenêtre horaire dans votre tournée.

Et le multi-véhicules ?

Le VRPTW peut être combiné avec du multi-véhicules : plusieurs livreurs en parallèle, chacun avec sa propre tournée optimisée. OptiRoad gère ce cas en plan Business avec l'algorithme Clarke-Wright Savings pour répartir les arrêts entre véhicules, puis EDF et simulation par véhicule. Ce sera l'objet d'un futur article.

En pratique : ce que ça change pour vous

Sur une tournée typique avec fenêtres horaires (livraisons traiteur, par exemple) :

• Sans VRPTW : 30 à 50 % des livraisons risquent d'être hors fenêtre, vous appelez les clients pour décaler, vous stressez.
• Avec VRPTW : 100 % des livraisons dans les fenêtres ou alerte avant départ. La journée se déroule comme prévu.

Et quand vous savez à l'avance qu'une livraison sera en retard, vous pouvez agir. Le simple fait de savoir à l'avance vaut souvent plus que l'économie de kilomètres.

Pour aller plus loin

Le VRPTW est disponible en plan Pro et Business. Le plan Free inclut le TSP simple (sans fenêtres horaires), suffisant pour valider la qualité de l'algorithme. Pour activer les fenêtres, passez en Pro et activez le toggle « Fenêtres horaires » dans OptimizePanel.

Vous voulez creuser le multi-véhicules (VRP avec Clarke-Wright Savings) ? C'est le prochain article.

Questions fréquentes

Que se passe-t-il si une fenêtre ne peut pas être tenue ?

L'arrêt concerné est signalé en retard avant le départ, jamais découvert sur la route. Vous gardez la main : prévenir le client, ajouter un véhicule pour répartir la charge, ou décaler l'heure de départ pour que le créneau redevienne atteignable.

Puis-je mélanger des arrêts avec et sans fenêtre ?

Oui. Les arrêts sans fenêtre ne sont contraints par aucune heure : OptiRoad les place librement autour des arrêts contraints, là où ils s'insèrent le mieux sans perturber les créneaux imposés. Vous n'êtes donc pas obligé de renseigner une fenêtre pour chaque livraison.

Le VRPTW gère-t-il plusieurs véhicules ?

Oui, en plan Business. OptiRoad répartit d'abord les arrêts entre les véhicules avec l'algorithme Clarke-Wright Savings, puis applique l'EDF et la simulation de planning sur chaque tournée prise séparément. Chaque livreur obtient ainsi son propre itinéraire optimisé et respectueux des fenêtres.

Quel plan inclut les fenêtres horaires ?

Les fenêtres horaires sont disponibles en plan Pro et Business. Le plan Free se limite au TSP simple, sans contrainte temporelle : parfait pour tester la qualité de l'optimisation sur de petites tournées, mais pas adapté aux métiers à créneaux imposés.