Conception d'algorithme de routage des véhicules / des ressources

Question

Mon premier post ici - en espérant que vous pourrez m'aider à concevoir un algorithme que j'envisage depuis un petit moment maintenant - je ne sais pas quelle approche adopter (VRPTW ou planification des ressources ou autre chose !?)

Pour le mettre dans un vrai exemple de mot, nous avons beaucoup de déchets de jardin à un petit nombre d'emplacements (généralement moins de 5). Les déchets doivent tous être transportés vers d'autres endroits dans les délais donnés. Pour déplacer les déchets de jardin, nous avons des remorques, qui doivent être remorquées par des voitures. Les déchets de jardin ne peuvent être abandonnés qu'au dépôt de déchets à certains moments (fenêtres de temps). Sur certains sites, nous pouvons déposer la remorque pour être rempli ou vidé par des gens là-bas, mais à d'autres endroits, le conducteur de la voiture doit le faire lui-même et la voiture doit y rester. Tous les horaires peuvent être calculés (c.-à-d. Temps de chargement / déchargement, heures de transit, etc.). Les voitures peuvent se déplacer entre les sites sans remorque, les remorques peuvent être remorquées vides, mais les remorques ne peuvent pas se déplacer entre les emplacements.

Notre objectif est de s'assurer que toutes les charges de déchets de remorque sont transportées pendant que

• Minimiser le nombre de remorques et de voitures utilisées
• Rencontrez toutes les fenêtres de toutes les déchets pour déposer les déchets
• «Équilibrer» les bandes-annonces - c'est-à-dire qu'à la fin de la journée, nous avons autant de bandes-annonces à chaque endroit que là au début de la journée

J'ai pensé à aborder cela comme un algorithme de planification des ressources, mais je ne sais pas comment gérer «l'équilibrage» des bandes-annonces.

Une autre méthode que j'ai considérée était de considérer d'abord les voitures. Je pouvais ensuite sélectionner la première tâche et construire un graphique de toutes les tâches réalisables après cela. Si je choisissais ensuite le chemin le plus long à travers le graphique qui servirait le nombre maximum de charges de remorque. Je pouvais ensuite retirer ces tâches de la liste des tâches et répéter jusqu'à ce que toutes les tâches soient entretenues. J'aurais alors besoin de parcourir ces charges de remorque pour déterminer le nombre de bandes-annonces requises.

Toute pensée quant à l'approche serait appréciée!

Answer 1

Je suis d'accord avec Jiri ... vous voulez un algorithme heuristique qui se rapproche raisonnablement d'une solution acceptable et affine ensuite à partir de là.

J'ai travaillé dans des entreprises auparavant qui avaient un logiciel de routage de livraison et l'approche qu'elles ont adoptée était d'utiliser un algorithme génétique pour résoudre un problème très similaire, mais beaucoup plus grande. Prendre un regarder ici Si vous n'êtes pas familier avec l'approche. De ce site:

1. Démarrer] Générer une population aléatoire de N chromosomes (solutions appropriées pour le problème)
2. Fitness] Évaluez la fitness f (x) de chaque chromosome x dans la population

3. Nouvelle population] Créez une nouvelle population en répétant les étapes suivantes jusqu'à ce que la nouvelle population soit terminée

   Sélection] Sélectionnez deux chromosomes parents dans une population en fonction de leur forme physique (le meilleur fitness, plus la chance d'être sélectionnée)

   Crossover] avec une probabilité de croisement se croiser sur les parents pour former une nouvelle progéniture (enfants). Si aucun croisement n'a été effectué, la progéniture est une copie exacte des parents.

   Mutation] avec une probabilité de mutation mute une nouvelle progéniture à chaque locus (position dans le chromosome).

   Accepter] Placer une nouvelle progéniture dans une nouvelle population

4. Remplacer] Utilisez une nouvelle population générée pour une nouvelle série d'algorithmes
5. Test] Si la condition finale est satisfaite, arrêtez et renvoyez la meilleure solution dans la population actuelle
6. Loop] Passez à l'étape 2

L'astuce est de coder vos contraintes dans un "chromosome" et d'écrire la fonction "fitness". La fonction de fitness doit prendre les entrées des résultats d'une solution potentielle et cracher une score de la qualité d'une solution ou de le jeter si elle viole l'une des contraintes.

Comme mentionné par Jiri, l'avantage de cette solution est qu'il propose une réponse réalisable, mais peut-être pas la meilleure, très rapidement et plus vous le laissez longtemps, meilleur est la solution.

Answer 2

Nous parlons ici un algorithme complet NP, au-delà de certains voitures et remorques, ce ne sera pas une tâche où vous obtiendrez une meilleure solution de toutes les solutions possible le plus long chemin comme vous le suggérez. Si vous concevez votre algorithme de cette façon, il est très probable qu'un jour vous ajoutez un peu plus de voitures et de bandes-annonces et il ne finira jamais de calculer la solution.

Vous voulez probablement aller avec un algorithme qui peut raisonnablement générer rapidement une solution suffisamment bonne du problème. Assurez-vous de créer une métrique pour la qualité de la solution, vous obtenez un bon moyen d'estimer la valeur de la métrique pour une solution idéale, puis définissez-vous un% dans lequel vous souhaitez que votre solution soit à partir d'une solution idéale et simplement Prenez la première solution qui a une métrique dans les limites. Cela a l'avantage supplémentaire de si cet algorithme prend trop de temps à calculer et que vous l'avordez, vous pouvez toujours utiliser la solution avec la métrique calculée la plus basse, même si elle n'est pas dans vos limites attendues.

Je ne sais pas quelle approche pour résoudre le problème lui-même. Je suggère de lire quelques articles après avoir cherché portail ACM. Je suppose que UPS et FedEx ont probablement des problèmes similaires, si vous les ajoutez en tant que mots clés à une recherche dans Google, vous pourriez obtenir des résultats plus utiles.

Answer 3

J'ai tendance à être d'accord avec Robert. Cela me ressemble à un très grand candidat pour une technique d'optimisation évolutive comme la mise en œuvre de l'algorithme génétique qu'il décrit.

J'ai également eu un très bon succès sur certains problèmes avec l'optimisation des essaims de particules (PSO) .Bastiquement, vous pouvez considérer chaque génome comme une particule dans un espace multidimensionnel. Les coordonnées de la particule sont les paramètres de votre calcul (fonction de fitness). Chaque particule est lancée au hasard avec une vitesse aléatoire. Pour chaque itération de la simulation, vous mettez à jour la position de chaque particule avec son vecteur de voyage actuel, puis vous ajoutez des composants d'autres vecteurs comme: Direction à la meilleure particule jusqu'à présent, direction à la meilleure particule de tous les temps, direction à un groupe local Meilleur etc ...

Il peut sembler assez intimidant au début d'implémenter un GA ou un PSO, mais je vous assure qu'il est facile d'écrire un petit cadre qui résume l'algorithme (GA / PSO) du domaine de problème réel que vous essayez d'optimiser. Vous pouvez toujours retomber à Wikipedia pour plus de détails sur les algorithmes.

Une fois que j'ai un framework, je commence normalement par un problème de paramètre 2 (probablement une simplification de votre problème, ou des emplacements X et Y sur une image), afin que je puisse facilement visualiser et modifier l'algorithme afin d'obtenir un bon comportement d'essaimage. Ensuite, je le remets à plus de dimensions.

J'aime cette approche car elle me permet d'optimiser facilement pour les problèmes qui ont des pièces assez complexes et complexes à l'énoncé du problème réel (comme les voitures et les remorques).

De plus, pourquoi les techniques évolutives sont attrayantes, c'est parce que vous pouvez consacrer une partie fixe du temps à la simulation et prendre la meilleure réponse jusqu'à présent lorsque vous décidez de vous arrêter.

D'après mon expérience, vous avez tendance à prendre autant de temps à peaufiner les paramètres du GA ou du PSO (une fois que vous avez une implémentation) que vous pourriez écrire une solution heuristique codée, mais l'avantage est que pour changer la stratégie pour trouver la solution généralement Nécessite des changements de paramètres uniquement ou échangeant des algorithmes très bien définis avec une autre implémentation, au lieu de coder une stratégie complètement différente pour résoudre le problème heuristiquement à partir de zéro.

Veuillez me donner un cri si vous avez besoin de conseils sur la conception des frameworks génériques pour l'un des deux algorithmes. Je dois souligner que vous obtenez également plusieurs bons cadres gratuits de tiers. J'aime parfois coder le mien parce que je comprends alors tous les aspects de l'algorithme et je sais où je peux ajuster la stratégie.

Answer 4

Approche générale:

Étant donné que le problème est petit, je suggère une approche où vous ajoutez des voitures et des remorques jusqu'à ce que vous obteniez une solution réalisable plutôt que d'essayer de minimiser les voitures et les remorques.

Solving:

J'ai eu moins de succès sur le gaz avec des contraintes et encore moins de succès sur le gaz avec des contraintes sur les variables entières (par exemple, le nombre de bandes-annonces dans un emplacement). Il se peut que la programmation de contraintes soit une meilleure approche, car vous voulez simplement générer une solution réalisable pour un nombre donné de voitures et de remorques plutôt que d'essayer de minimiser la distance parcourue.

Observation:

Vous résolvez le problème sur un réseau où les derniers mouvements peuvent être de déplacer une bande-annonce vide.

Bonne chance !

Answer 5

Recherche locale sont une alternative aux algorithmes génétiques. Dans le Concours international du horaire 2007, les algorithmes de recherche locaux (tels que la recherche tabu et le recuit simulé) ont clairement battu les entrées d'algorithme génétique (1 à la 4e place pour LS contre 5e place pour GA dans la piste 1 sur environ 80 concurrents IIRC).

Jetez également un œil à certaines bibliothèques, comme Optaplanner (Recherche tabu, recuit simulé, acceptation tardive, open source, java), JGAP (algorithmes génétiques, open source, java), optents (recherche tabu, ...