Constitution du graphe

Les étapes essentielles de la constitution du graphe sont les suivantes.

1. Insertion d’un nœud pour chaque départ et chaque arrivée d’une section de service (ou d’une succession de sections de service associées par des chaînages forcés) et raccordement des deux nœuds par une arête. Ces nœuds sont appelés vrais événements ci après. Par départ et arrivée, on entend le temps respectif en incluant les temps de préparation Pré et Post éventuels s’ils doivent être pris en considération (Utilisation : Paramètres du calcul des rotations).

Illustration 198 : Insertion des nœuds et des arêtes pour les sections de service

2. Pour chaque dépôt autorisé pour la combinaison de véhicules ainsi que pour chaque point d’arrêt étant le début d’une section de service de la partition actuelle (services à vide entre points d’arrêt), insertion d’un événement d’arrivée à l’instant d’arrivée à cet élément et insertion d’une arête pour le service à vide de l’événement de départ du service à l’événement d’arrivée au point d’arrêt ou dans le dépôt (il en résulte des événements d’arrivée dit faux événements d’arrivée). Les dépôts sont des points d’arrêt particuliers. Dans le graphe, on distingue les événements au point d’arrêt et dans le dépôt, ce qui signifie qu’il existe dans le graphe un nœud pour le point d’arrêt et un nœud supplémentaire pour le dépôt, bien que le dépôt soit représenté par le même point d’arrêt dans le réseau.

Illustration 199 : Insertion des arêtes pour le trajet de retour aux dépôts et pour les services à vide entre points d’arrêt

3. De manière analogue, insertion d’un événement de sortie et d’une arête de l’élément à l’événement de départ du service, mais uniquement pour chaque dépôt autorisé, pas pour les autres points d’arrêt (ils représentent le trajet depuis les dépôts, il en résulte des événements de départ dits faux événements de départ).

Illustration 200 : Insertion des arêtes pour les trajets depuis des dépôts

Nota : Lorsque les transferts sont interdits (Utilisation : Paramètres du calcul des rotations), seules des arêtes vers le et depuis le dépôt représenté par le même point d’arrêt dans le réseau sont insérées. Dans ce cas, aucun transfert n’est possible, mais la combinaison peut effectuer un trajet de retour au dépôt et ensuite revenir au même point d’arrêt pour le début du prochain service.

4. Insertion d’une arête supplémentaire entre deux événements consécutifs d’un point d’arrêt ou d’un dépôt (arête dite de ligne de temps ou d’attente). À l’aide de cette arête, on peut modéliser l’attente à un point d’arrêt ou dans un dépôt. Avec les arêtes de ligne de temps, une rotation peut être poursuivie avec un nouveau service au même point d’arrêt.

Lors du calcul de rotations, vous pouvez choisir de calculer des rotations ouvertes ou fermées. Lors du calcul de rotations fermées, chaque ligne de temps, c.-à-d. chaque succession d’arêtes de ligne de temps pour un point d’arrêt ou un dépôt, constitue une boucle fermée. Des arêtes de service et de service à vide peuvent également franchir la transition du dernier jour de l’intervalle de calcul des rotations au premier jour. Une rotation présente autant de jours de rotation que le nombre de boucles effectuées dans la période de calendrier jusqu’au retour au point de départ.

On ne peut exiger que les rotations commencent et finissent dans un dépôt que dans le cas des rotations ouvertes. Dans ce cas, des arêtes de liaison sont insérées d’un nœud auxiliaire à tous les dépôts avant le premier et après le dernier nœud de chaque ligne de temps. L’afflux et l’écoulement se font alors uniquement via ces nœuds auxiliaires. Dans ce cas, il peut arriver qu’aucun flux ne puisse être déterminé. C’est ce qui se produit lorsque la capacité totale de tous les dépôts est inférieure au nombre de véhicules requis pour assurer toutes les actions. Dans un tel cas, le calcul des rotations est interrompu avec un message d’erreur.

En ce qui concerne les rotations ouvertes et fermées, vous trouverez aussi la note dans l’exemple introductif (Rotations ouvertes et fermées).

5. Le graphe est ensuite simplifié par regroupement des nœuds avec une accessibilité identique et par suppression d’arêtes de services à vide équivalentes, c.-à-d. que les mêmes départs sont accessibles (Réduction des arêtes). Le graphe après la réduction des arêtes figure dans l’Illustration 201.

Illustration 201 : Graphe exemple après l’insertion des arêtes de ligne de temps et la réduction des arêtes

6. Pour la formulation sous forme de problème de flux, il est nécessaire d’assigner aux arêtes un seuil inférieur et un seuil supérieur pour leur capacité (c.-à-d. le nombre de véhicules minimal ou maximal pouvant circuler sur une arête). Le constant suivant s’applique :

Le seuil inférieur de la capacité sur les sections de service est de 1 (car il est indispensable que chaque section de service soit réellement assurée).
Toutes les autres arêtes présentent un seuil inférieur de capacité de 0 (car il n’est par exemple pas indispensable d’assurer les services à vide).
Le seuil supérieur est également de 1 pour les arêtes des sections de service (car chaque section de service doit être assurée une seule fois et non plusieurs).
Le seuil supérieur pour les arêtes de services à vide est le nombre de services à vide qu’elles représentent (ce nombre est uniquement supérieur à 1 lorsque des arêtes ont été regroupées dans le cadre de la réduction des arêtes).
Les arêtes le long des arêtes de ligne de temps présentent la capacité du dépôt comme seuil supérieur s’il s’agit d’un dépôt. Pour toutes les autres arêtes de ligne de temps, le seuil supérieur est infini.

7. Afin de déterminer un flux au coût le plus faible, les arêtes doivent être évaluées avec un coût dans la dernière étape. Celui-ci est décrit par une fonction de coût de manière analogue au temps de déplacement perçu dans les affectations TC (Temps de déplacement perçu). Cette fonction de coût se compose de termes qui multiplient chacun une propriété de l’arête (c.-à-d. l’activité décrite par l’arête) par un coefficient et un coût. La fonction de coût est la suivante :

Coût	= besoin en véhicules • coefficient • coût unité de véhicules total
	+ temps de service • coefficient • coût heure service
	+ Km/MiService • coefficient • coût km/mi service
	+ temps à vide • coefficient • coût heure à vide
	+ Km/MiÀVide • coefficient • coût km/mi à vide
	+ Nb services à vide • coefficient
	+ temps d’arrêt • coefficient • coût par heure temps d’arrêt
	+ temps de service en dépôt • coefficient • coût heure dépôt
	+temps de chargement • coefficient • coût heure de charge

Nota : Les coefficients s’appliquent aussi au coût pour « aucune combinaison ».

Les composantes du coût intervenant sur une arête dépendent du type de l’arête. Les composantes du coût pour les différents types d’arêtes sont les suivantes.

Arêtes de service
Le temps de service décrit la durée de la section de service (le coût du service lui-même n’est pas pertinent pour la résolution du problème, car un flux de 1 est appliqué à chacune de ces arêtes et aucune valeur alternative n’est donc appliquée. Pour l’affichage du résultat, les arêtes de service sont tout de même évaluées avec le coût de service de la combinaison de véhicules pour la durée et la distance)
Km/Mi Service décrit la distance parcourue par le service
Le temps d’arrêt technique décrit la durée de l’instant du NoeudOrig jusqu’au départ du NoeudOrig plus la durée de l’arrivée au NoeudDest jusqu’à l’instant du NoeudDest
Arêtes de service à vide
Le temps à vide décrit la durée du service à vide
Km/Mi à vide décrit la distance parcourue par le service à vide
Le temps d’arrêt technique décrit la durée de l’instant du NoeudOrig jusqu’au départ plus la durée de l’arrivée à l’instant du NoeudDest s’il s’agit d’un point d’arrêt ordinaire
Le temps d’arrêt technique en dépôt décrit la durée de l’instant du NoeudOrig jusqu’au départ plus la durée de l’arrivée à l’instant du NoeudDest s’il s’agit d’un dépôt
Arêtes de ligne de temps
Le temps d’arrêt technique et le temps d’arrêt technique en dépôt décrivent la durée entre les instants des nœuds reliés par des arêtes
Afin d’évaluer le besoin en véhicules, le coût pour la combinaison de véhicules est ajouté à l’évaluation pour chaque arête qui franchit un instant quelconque choisi. Dans la mesure où chaque combinaison de véhicules doit franchir cet instant d’évaluation une fois, le besoin en véhicules est comptabilisé et évalué.

Le résultat intermédiaire est un graphe évalué pour lequel un flux au coût le plus faible est déterminé dans l’étape suivante.