Prioriser les visites à proximité avec les attributs de transition

Cet exemple montre comment utiliser les attributs de transition pour privilégier les itinéraires où les collectes et les livraisons à proximité sont effectuées par le même véhicule au cours d'un même créneau horaire. Pour en savoir plus sur les attributs de transition, consultez Modéliser la logique métier avec les attributs de transition.

Dans cet exemple :

• Les livraisons des colis A, B et C sont proches les unes des autres sur la même route.
• D'autres livraisons sont prévues.
• Aucun délai de livraison n'est spécifié pour les livraisons.
• Quel que soit le programme de visites, le véhicule doit emprunter cette route deux fois : une fois le matin en partant du dépôt et une fois le soir au retour.
• La distance et la durée totales du trajet sont toujours les mêmes, quelle que soit la date à laquelle les étapes A, B et C sont effectuées.

Dans ce cas, et pour une requête qui n'utilise que le coût par heure et le coût par kilomètre, l'itinéraire optimisé pourrait prévoir de traiter A et B le matin, et C le soir. Le coût de la solution serait le même que si les trois étaient traités en même temps.

Important : Pour obtenir un itinéraire où les trois livraisons sont effectuées ensemble, vous devez ajouter des contraintes qui augmentent le coût des itinéraires où les colis ne sont pas livrés ensemble.

Coût par kilomètre avec un seuil

Pour regrouper les visites à proximité, vous devez d'abord sélectionner une distance seuil. Il s'agit de la distance maximale entre deux visites que vous considérez comme proches. Cet exemple utilise un seuil de 100 mètres, ce qui correspond à peu près à un pâté de maisons dans une zone urbaine. Vous pouvez augmenter ou diminuer le seuil pour l'adapter aux besoins de votre entreprise et aux préférences de vos conducteurs.

Pour regrouper les visites à proximité (à moins de 100 mètres les unes des autres), vous définissez un coût élevé pour les 100 premiers mètres de chaque transition et un coût inférieur pour les mètres supplémentaires. Étant donné que les 100 premiers mètres sont les plus coûteux, l'optimiseur réalise les plus grandes économies en utilisant des transitions plus courtes que le seuil de 100 mètres, même si cela signifie rallonger la longueur totale de l'itinéraire.

Pour configurer les coûts, ajoutez une entrée à ShipmentModel.transition_attributes avec les propriétés suivantes :

• Pour faire correspondre toutes les transitions possibles, choisissez un tag qui n'est utilisé nulle part dans le modèle, par exemple UNUSED_TAG. Définissez TransitionAttributes.excluded_src_tag et TransitionAttributes.excluded_dst_tag sur ce tag.
• Configurez TransitionAttributes.distance_limit avec la distance et les coûts du seuil :
  • Définissez DistanceLimit.soft_max_meters sur le seuil sélectionné.
  • Définissez DistanceLimit.cost_per_kilometer_below_soft_max sur le coût par kilomètre inférieur au seuil.
  • Définissez DistanceLimit.cost_per_kilometer_above_soft_max sur le coût par kilomètre au-dessus du seuil.

{
  "model": {
    "transitionAttributes": [
      {
        "excluded_dst_tag": "UNUSED_TAG",
        "excluded_src_tag": "UNUSED_TAG",
        "distanceLimit": {
          "softMaxMeters": 100,
          "costPerKilometerBelowSoftMax": 50,
          "costPerKilometerAboveSoftMax": 1,
        }
      }
    ]
  }
}

Le tag #unused_tag# ne doit être utilisé par aucun envoi ni aucun véhicule pour correspondre à toutes les transitions possibles. Pour en savoir plus, consultez Associer toutes les demandes de visite.

Fonctionnement d'un coût élevé inférieur au seuil

Cette section montre comment le coût inférieur et supérieur au seuil affecte le coût global des différentes solutions du scénario d'exemple.

Solution 1 : Effectuer A et B à l'aller, C au retour

Dans cette solution, les expéditions sont divisées en deux traversées de cette route. Deux d'entre eux sont fournis lors de la première traversée et le dernier lors de la seconde. Il existe cinq transitions :

Transition	Distance	En-dessous du seuil		Au-dessus du seuil
		Distance	Coût	Distance	Coût
dépôt →A	1 000 m	100 m	5	900 m	0,9
A→B	50 m	50 m	2.5	0 m	0
B→other	1 030 m	100 m	5	930 m	0,93
autre→C	1 000 m	100 m	5	900 m	0,9
C→depot	1080 m	100 m	5	980 m	0.98
Total		450 m	22,5	3 710 m	3.71

Le coût global est calculé en additionnant les deux coûts par kilomètre :

• le coût par kilomètre en dessous du seuil (50) multiplié par la distance totale parcourue en dessous du seuil (450 m = 0,45 km) ;
• le coût par kilomètre au-dessus du seuil (1) multiplié par la distance totale parcourue au-dessus du seuil (3 710 m = 3,71 km).

Le coût global est donc de 0,45 * 50 + 3,71 * 1 = 22,5 + 3,71 = 26,21.

Solution 2 : Effectuez A, B et C à l'aller, mais rien au retour

Dans cette solution, contrairement à la solution 1, les trois expéditions sont livrées "en groupe" lors d'un seul trajet. Lors de l'autre traversée, le véhicule ne s'arrête pas du tout. Là encore, il y a cinq transitions, mais leurs durées et leurs compositions sont différentes :

Transition	Distance	En-dessous du seuil		Au-dessus du seuil
		Distance	Coût	Distance	Coût
dépôt →A	1 000 m	100 m	5	900 m	0,9
A→B	50 m	50 m	2.5	0 m	0
B→C	30 m	30 m	1,5	0 m	0
C→other	1 000 m	100 m	5	900 m	0,9
other→depot	2 080 m	100 m	5	1 980 m	1,98
Total		380 m	19	3 780 m	3,78

En utilisant le même calcul que dans la solution 1, le coût global est de 0,38 * 50 + 3,78 * 1 = 19 + 3,78 = 22,78. Effectuer toutes les visites en un seul créneau horaire est donc moins coûteux que de les effectuer en deux groupes. Vous pouvez renforcer cet effet en augmentant DistanceLimit.cost_per_kilometer_below_soft_max.

Pourquoi un coût par kilomètre inférieur au seuil ne fonctionne pas

Comme vous souhaitez privilégier les transitions courtes plutôt que les transitions longues, vous pouvez être tenté d'attribuer un coût élevé par kilomètre aux transitions longues et de conserver un coût faible par kilomètre pour les transitions courtes. Mais cela a en fait un effet inverse : comme les 100 premiers mètres de la transition sont les moins chers, l'optimiseur utilise ces mètres "bon marché" au maximum en privilégiant les transitions qui font près de 100 mètres ou plus.

Vous pouvez voir cet effet sur les deux exemples de solutions. Si vous inversez le coût par kilomètre au-dessus et en dessous du seuil, les coûts d'itinéraire changent :

	Coût élevé au-dessus du seuil		Coût élevé en dessous du seuil
	Solution 1	Solution 2	Solution 1	Solution 2
KM en dessous du seuil	0,45	0,38	0,45	0,38
Coût par kilomètre en dessous du seuil	1,00	1,00	50,00	50,00
KM au-dessus du seuil	3.71	3,78	3.71	3,78
Coût par kilomètre au-delà du seuil	50,00	50,00	1,00	1,00
Coût total	185,95	189.38	26.21	22.78

Pour chaque version, le coût total le plus faible des deux solutions est mis en gras. Vous pouvez constater que lorsque vous utilisez un coût élevé au-dessus du seuil, le coût total de l'itinéraire est désormais plus élevé pour l'itinéraire où les visites sont regroupées, ce qui est le contraire de ce que vous vouliez obtenir.