Motivation

L'autre jour, je voyageais dans la ville avec les transports en commun et j'ai inventé un problème de graphique intéressant modélisant le problème de trouver la connexion la plus courte entre deux endroits.

Nous connaissons tous le "problème du chemin le plus court" classique: étant donné un graphe orienté avec des longueurs de bord w e ∈ R + 0$G=(V,E)$ et deux sommets s , t ∈ V , trouvent le chemin le plus court entre s et t (c'est-à-dire le chemin minimisant la longueur totale des bords). En supposant des longueurs de bord non négatives, il existe différents algorithmes et le problème est facile.$w_e\in\mathbb{R}_0^+,\,e\in E$$s,t\in V$$s$$t$

C'est un bon modèle pour le cas où nous marchons, par exemple. Les sommets sont des carrefours dans notre réseau de routes et chaque bord a une longueur fixe - en mètres, par exemple. Une autre interprétation possible des poids de bord est le temps qu'il nous faut pour passer d'un de ses sommets à l'autre. C'est l'interprétation qui m'intéresse maintenant.$w_e$

Problème

Je veux maintenant modéliser la situation suivante. Je veux voyager d'un point A à un point B dans une ville via les transports en commun et minimiser le temps . Le réseau de transports en commun peut être facilement modélisé sous forme de graphique orienté comme vous vous en doutez. La partie intéressante est le poids des bords (ce modèle de temps) - les transports publics (bus, par exemple) ne partent qu'à certains intervalles, qui sont différents pour chaque arrêt (sommet dans le graphique). En d'autres termes - les poids des bords ne sont pas constants, ils changent en fonction du temps que nous voulons utiliser le bord.

Comment modéliser cette situation: Nous avons un graphe orienté et une fonction de poids de bord w : E × R + 0 → R + 0 qui prend du temps comme argument et renvoie le temps qu'il faut pour utiliser le bord sur notre chemin. Par exemple, si le bus du sommet v au sommet u part à t = 10 et cela prend 5 fois et nous arrivons au sommet v à t = $G=(V,E)$ $w\colon E\times \mathbb{R}_0^+\rightarrow\mathbb{R}_0^+$$v$$u$$t=10$$5$$v$$t=8$, alors est l'épaisseur du bord. Clairement, w ( v u , 10 ) = 5 .$w(vu,8)=7$$w(vu,10)=5$

Il est légèrement délicat de définir le poids total du chemin, mais nous pouvons le faire récursivement. Soit un chemin dirigé. Si k = 1 alors w ( P ) = 0 . Sinon, w ( P ) = w ( P ′ ) + w ( v k - 1 v k , w ( P ′ ) $P=v_1v_2\ldots v_{k-1} v_k$$k=1$$w(P)=0$$w(P)=w(P')+w(v_{k-1}v_k,w(P'))$, où est le sous-chemin de P sans v k . Il s'agit d'une définition naturelle correspondant à la situation réelle.$P'$$P$$v_k$

Nous pouvons maintenant étudier le problème sous différentes hypothèses sur la fonction . L'hypothèse naturelle est w ( e , t ) ≤ w ( e , t + Δ ) + Δ  pour tout  e ∈ E , Δ ≥ 0 , qui modélise "l'attente du temps Δ ".$w$

Si la fonction "se comporte bien", il peut être possible de réduire ce problème au problème classique du chemin le plus court. Mais on pourrait se demander ce qui se passe lorsque les fonctions de poids deviennent sauvages. Et si nous abandonnions l'hypothèse de l'attente?

Des questions

Mes questions sont les suivantes.

• Ce problème a-t-il déjà été posé? Cela semble plutôt naturel.
• Y a-t-il des recherches à ce sujet? Il me semble qu'il existe différents sous-problèmes à poser et à étudier - principalement en ce qui concerne les propriétés de la fonction poids.
• Pouvons-nous réduire ce problème (éventuellement sous certaines hypothèses) au problème classique du plus court chemin?

$n^{\Theta(\log n)}$

L'algorithme de Dijkstra peut en effet être utilisé pour ce problème, lorsque la politique d'attente est imposée, c'est-à-dire attendre à un nœud si cela réduit le temps d'arrivée final. Sans la politique d'attente, la situation est beaucoup plus sauvage: le chemin le plus court peut ne pas être simple, le sous-chemin d'un chemin le plus court peut ne pas être le plus court entre les deux extrémités du sous-chemin, les chemins traversant un nombre infini d'arêtes peuvent avoir un temps d'arrivée fini, etc. Voir à nouveau le document d'Orda et Rom pour plus de discussion.

Connaissez-vous le problème des "chemins non décroissants les plus courts"? Il a été défini pour modéliser des situations comme celles-ci. Bien qu'il soit un peu moins expressif par rapport à votre formulation, il existe des algues rapides pour cela.

Si vous supposez que les heures sont intégrales (ce qui est logique dans le cas des transports en commun), vous pouvez créer un réseau étendu dans le temps, similaire à celui suggéré par Ford-Fulkerson pour le débit maximal dans le temps (ou le débit le plus rapide) et recherchez plutôt le chemin le plus court dans ce graphique.