Optimisation d'itinéraire pour plusieurs véhicules

12

J'ai 100 destinations et 5 véhicules et je dois coder une solution qui achemine efficacement les véhicules vers chaque destination, de sorte que chaque destination est visitée par 1 des véhicules. Certaines de ces destinations pourraient également avoir des fenêtres horaires à visiter.

J'utilise PostgreSQL et PostGIS, et je cherchais à utiliser le pgrouting mais je ne suis pas sûr qu'il convient à plusieurs véhicules - de ma connaissance limitée de Dijkstra, etc., je pense qu'ils sont conçus pour un seul véhicule.

Avez-vous des idées pour savoir si le pgrouting peut résoudre ce problème, et si oui, des exemples de code? Sinon, existe-t-il des alternatives open source qui peuvent le faire?

routing pgrouting RichW
la source
Il se trouve que j'ai un besoin similaire au vôtre. J'exploite une entreprise NPO NEMT (transport médical non urgent). nous devons transporter les patients à leurs rendez-vous avec des plages horaires pour les cueillettes ou les livraisons. La plupart des demandes sont reçues à l'avance, d'autres sont sur place. DARP semble être un bon algorithme. Avez-vous besoin d'un solveur DARP pour la même raison? Nick
Nick Bazzi

Réponses:

10

pgRouting a une fonction appelée solveur DARP (Dial-a-Ride Problem) :

Le solveur Dial-a-Ride Problem (DARP) essaie de minimiser les coûts de transport tout en satisfaisant les contraintes de niveau de service client (violation des fenêtres horaires, temps d'attente et de déplacement) et les contraintes de la flotte (nombre de voitures et capacité, ainsi que l'emplacement du dépôt).

Plus d'informations sur DARP et pgRouting:

Pour utiliser cette nouvelle fonction, vous devez installer la branche darp de pgRouting .

Les réponses à cette question sur stackexchange peuvent fournir des informations supplémentaires: algorithme de routage pour plusieurs véhicules avec plusieurs largages .

obscur
la source
J'ai d'abord vu l'algorithme DARP, mais je l'ai effleuré car je ne savais pas qu'il pouvait être utilisé pour les coursiers. On dirait que ça fera bien l'affaire! Il est dommage que la page de documentation ne contienne aucun exemple d'utilisation, il pourrait s'agir de rechercher dans le code source pour voir comment cela fonctionne.
RichW
1

Bien qu'ESRI ArcLogistics ne corresponde manifestement pas à vos besoins particuliers d'utilisation de PostGIS ou de l'open source, pour ceux qui n'ont pas les compétences en programmation ou le temps de mettre en œuvre leurs propres solutions, il s'agit d'une bonne extension standardisée et payante pour ArcGIS conçu pour accomplir les tâches que vous avez décrites.

Actuellement, ils offrent également un essai gratuit de 30 jours si vous souhaitez le tester.

RyanKDalton
la source
Je suis descendu au siège ESRI la semaine dernière pour discuter de ce logiciel pour eux, mais il ne semble pas répondre à nos besoins (doit fonctionner sur un serveur et est également assez cher). Excellent morceau de kit cependant!
RichW
Notre produit FleetEngine fonctionne comme un serveur avec une interface SOAP. 100 destinations, 5 véhicules et créneaux horaires sont définitivement à la portée des capacités. Il est très proche d'être prêt pour la production, contactez-moi pour une licence de test. Ce n'est pas open source ou gratuit, mais d'un autre côté, pas aussi cher qu'ArcLogistics.
Uffe Kousgaard
1
Salut Uffe, peut-il prendre en compte les restrictions des véhicules (poids et dimensions) et trier les colis sur les véhicules en conséquence? En outre, cela fonctionne-t-il au Royaume-Uni et utilise-t-il les données d'historique routier pour calculer les vitesses, etc.?
RichW
Oui à toutes vos questions. Il utilise de simples additions de poids / volumes. Il ne peut pas faire trop d'emballage 3D, ce serait trop à espérer. Prise en charge complète des réseaux routiers dans tous les pays également, mais vous devez fournir le réseau routier. Malheureusement, je n'ai pas vu la réponse plus tôt, je pensais que cette discussion était terminée. Envoyez-moi un ping à [email protected] si vous souhaitez en discuter davantage.
Uffe Kousgaard