Problème du plus court chemin

[invite2ed02f7e]

Bonjour,

Je vous écris pour savoir quels sont les algorithmes de plus court chemin les plus efficaces, désirant résoudre un problème de ce type. Mon objectif final est d'optimiser des emplois du temps, je vais essayer de l'illustrer au travers d'un exemple. Je pense que cela ressemble d'assez près au problème du voyageur du commerce, sauf qu'il y en a plusieurs d'une certaine manière.

On considère une entreprise de dépannage.

Position du problème :
-Chaque jour j il y a N_j dépanneurs disponibles qui partent d'une base.
-Chaque technicien dispose d'une feuille de route qui le fait intervenir dans quelques villes.
-Pour chaque ville i il peut intervenir k fois. Et pour chaque intervention k, on peut estimer la durée t_k d'une intervention.
-La distance de la base à une ville quelconque D_b est connue.
-La distance entre deux villes D_i1i2 est connue.
-Toutes les adresses et villes pour intervention sont connues avant le départ de la base le matin (donc toutes les distances le sont).

Contraintes :
-La feuille de route ne peut-être établie que du jour pour le lendemain (optimisation au jour le jour).
-Il y a un nombre maximal m d'interventions par demi-journée.
-Il y a un nombre d'heures de travail hebdomadaire h à respecter le plus possible.

Objectifs :
-Minimiser la distance totale parcourue dans la journée, sachant que le midi, de nombreux dépanneurs viennent se réapprovisionner en matériel livré à la base.
-Minimiser la distance totale parcourue individuellement.
-Minimiser pour une période de temps donnée au maximum la distance entre deux voire trois dépanneurs, pour que ceux-ci puissent s'entraider ou s'échanger du matériel si nécessaire.
-Minimiser la distance à la base en cas de besoin de matériel supplémentaire. On pourra aussi ajouter d'autres points où récupérer du matériel.
-Maximiser le nombre d'interventions total par jour.
-Essayer de rendre l'emploi du temps individuel le plus régulier possible (par exemple sur 37h de travail hebdomadaires, tenter d'attribuer 7h25 par jour ouvré).

Alors je ne demande pas du tout de résolution complète vu que c'est ce que je cherche à m'amuser à faire. Mais j'ai quelques questions pour prendre une bonne direction :

L'algorithme de Floyd-Warshall (utilisé pour réduire la distance à la base et la distance entre dépanneurs) est-il le plus adapté à cette situation?
J'ai regardé par curiosité Dijkstra (que je connaissais déjà un peu), et Christofides, mais intuitivement, Floyd-Warshall me semble être le plus adapté. Vaudrait-il mieux le coupler avec un autre? En utiliser un autre? Utiliser une méthode naïve/exhaustive?
-----

[Dlzlogic]

Bonjour,
D'abord à propos du plus court chemin.
C'est un problème qui n'est pas très difficile avec les hypothèses qui m'étaient données : un centre de secours (pompiers) doit trouver le plus court chemin depuis la caserne jusqu'au lieu du sinistre. Il y avait une condition intéressante : la région est vallonnée et les véhicules roulent moins vite sur certaines routes que sur d'autres.
J'ai utilisé l'algorithme de Dijkstra, et je n'ai pas eu l'occasion d'en essayer d'autres.
Tel que vous le présentez votre problème est beaucoup plus compliqué, puisqu'il s'agit s'étudier les suites des chemins parcourus par un dépanneur, là c'est le problème du voyageur de commerce, et que vous voulez aussi que l'optimisation se fasse pour un certain nombre de dépanneurs, les uns par rapport aux autres.
Si j'avais un conseil à vous donner, ce serait de dissocier soigneusement les différentes conditions. Je m'explique : si le dépanneur à un instant donné doit se rendre d'un point A à un point B, il n'y a qu'une seule condition à étudier : le plus court chemin. Si le problème en est à la phase "gestion du personnel" les problèmes de choix de plus court chemin doivent être laissés de côté.
Votre problème est intéressant.