Algorithme pour le DARP (Dial A Ride Problem)

Bonjour à tous !

Je suis à la recherche d'un algorithme pour résoudre des DARP,

J'ai déjà fait un petit programme Python qui simule un bus d'une capacité n, qui doit aller chercher et déposer x clients.
Cependant la méthode utilisée est le plus proche voisin et comme vous le savez elle est loin d'être le plus optimale.

Je viens donc vers vous pour savoir si vous n'auriez pas des sources où je peux trouver un algorithme assez détaillé où même un code qui utiliserait des méthodes plus complexes comme des méthodes heuristiques ou méta-heuristique par exemple. Cela pourrait m'avancer grandement dans mes recherches

Merci d'avance, en vous souhaitant une bonne journée !

Stabilo.

:salut:

En fait, quelle est la différence avec le voyageur de commerce (TSP) ? Il y a énormément de littérature sur le sujet, un gros solveur (http://www.math.uwaterloo.ca/tsp/concorde.html), etc.

(Sinon, "optimal" est un superlatif : une solution est optimale ou elle ne l'est pas, on ne peut pas être "plus optimal", tout comme tu n'es pas "plus meilleur" que quelqu'un d'autre ;).)

Salut !

Merci de ta réponse,

Alors en effet c'est assez similaire avec un TSP, cependant il y a des contraintes supplémentaires notamment celle de la capacité et de multiples points de dépôts donc ce n'est pas non plus tout à fait un VRP (Véhicules Routing Problem).

(Bien sur, ce que je voulais dire par là c'est de trouver une solution qui s'approche de la solution optimale dans un temps limité sachant que ce sont des problèmes complexes :D)

L'algorithme de Dijkstra semble assez indiqué : https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
Utilisé pour le trafic routier ou internet…

Sauf que Dijkstra oubliera une bonne partie des contraintes !

Sinon, ce genre de problème se résout "assez bien" par des techniques d'optimisation mathématique (une bonne vieille formulation MILP). Pour toute la famille de problèmes avec des chemins, on utilise très souvent une résolution par génération de colonnes. Un article qui fait les deux, justement : https://www.math.u-bordeaux.fr/~rsad...tall_ILS16.pdf

C'est vrai qu'il faut l'arranger un peu, mais apparemment on peut s'en sortir : https://www.researchgate.net/publica...39;s_algorithm
Je ne connais pas assez ces thèmes-là pour bien argumenter j'avoue, mais des extensions de Dijkstra me semblent pouvoir répondre à ce type de problème (il y a aussi l'algorithme A* par exemple : https://en.wikipedia.org/wiki/A*_search_algorithm)

A* et Dijkstra, c'est pour ainsi dire du pareil au même : ça ne fait qu'un plus court chemin (A* ne considère qu'une partie du graphe selon une fonction heuristique). Ici, on parle plutôt d'aller chercher des gens sans exploser la capacité du bus : certes, il y a des plus courts chemins pour aller d'un utilisateur à l'autre, mais ça ne suffit pas à résoudre le problème. L'article que tu cites ne fait effectivement "que" des plus courts chemins, mais dans un graphe "multimodal" (un réseau de bus, un réseau de tram, etc., avec des interconnexions et des coûts pour passer de l'un à l'autre).

Oui, c'est vrai, ça n'intègre pas toutes les contraintes, et ça n'a pas l'air évident pour les intégrer facilement / efficacement en fait.
Mauvaise piste ou incomplète en tout cas, désolé :oops:

Merci pour l’intérêt que vous portez au sujet.

Le problème des articles sur le Dial a Ride Problem, est que l'algo n'est pas tout à fait représenté. Enfin de façon mathématique si, cependant je suis honnêtement incapable de le programmer par moi même ou même d'abord, le transformer en solution algorithmique.

Après quelques recherches, j'ai trouvé un module python CPLEX qui semble résoudre pas mal de problèmes.

Il semble qu'en lui donnant des inputs, il soit capable de résoudre le problème qu'on lui demande en respectant les contraintes imposées. Il me reste, par ailleurs, à comprendre vraiment comment il fonctionne pour que je puisse peut être l'adapter à mon problème.

Bonne journée à vous,

Stabilo