Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme pour le DARP (Dial A Ride Problem)


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2016
    Messages
    124
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Indre et Loire (Centre)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : juillet 2016
    Messages : 124
    Points : 118
    Points
    118
    Par défaut 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.

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 189
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 189
    Points : 179 039
    Points
    179 039
    Par défaut


    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 .)
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2016
    Messages
    124
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Indre et Loire (Centre)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : juillet 2016
    Messages : 124
    Points : 118
    Points
    118
    Par défaut
    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 )

  4. #4
    Membre averti Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    132
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 132
    Points : 372
    Points
    372
    Par défaut
    L'algorithme de Dijkstra semble assez indiqué : https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
    Utilisé pour le trafic routier ou internet…

  5. #5
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 189
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 189
    Points : 179 039
    Points
    179 039
    Par défaut
    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
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  6. #6
    Membre averti Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    132
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 132
    Points : 372
    Points
    372
    Par défaut
    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)

  7. #7
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 189
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 189
    Points : 179 039
    Points
    179 039
    Par défaut
    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).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  8. #8
    Membre averti Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    132
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 132
    Points : 372
    Points
    372
    Par défaut
    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é

  9. #9
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2016
    Messages
    124
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Indre et Loire (Centre)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : juillet 2016
    Messages : 124
    Points : 118
    Points
    118
    Par défaut
    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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. probleme d'algorithme pour une fonction puissance
    Par john_evrest dans le forum Caml
    Réponses: 10
    Dernier message: 25/10/2011, 16h58
  2. algorithme pour calcul de probabilité
    Par filsdugrand dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 14/12/2005, 15h11
  3. Quel algorithme pour insertion d'objets "triés" da
    Par phplive dans le forum Langage
    Réponses: 3
    Dernier message: 04/08/2005, 10h27
  4. Algorithme pour trier trois nombres
    Par legosam dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 17/01/2005, 22h47
  5. Algorithme pour chiffres significatifs en Assembleur
    Par lutin2003 dans le forum Assembleur
    Réponses: 5
    Dernier message: 09/09/2004, 11h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo