Je travaille sur un problème d'acheminement de véhicule avec un seul dépôt. La définition du problème est la suivante. Il y a n vechiles qui doivent se rendre sur un certain nombre de sites. Chaque site a ses contraintes spécifiques comme seuls les véhicules de capacité certaine peuvent desservir le site, certains sites doivent être desservis à une heure précise de la journée. De plus, les véhicules auront des capacités différentes et auront des heures de départ et d'arrivée différentes.Utilisation de la théorie des graphes dans le routage d'un véhicule Problème
L'idée est de minimiser le temps de déplacement des véhicules depuis le dépôt.
Je suis en train de construire la matrice de coût pour le problème. Bien que n'étant pas un expert en théorie des graphes, je sais que je pourrais utiliser le cycle hamiltonien pour résoudre le problème si celui-ci tombait dans un problème classique de vendeur itinérant. Cependant, comme il s'agit d'un problème de vendeurs itinérants multiples, je veux savoir comment résoudre le problème en utilisant les cycles hamiltoniens ou s'il existe un autre processus spécifiquement conçu pour cibler les problèmes en tant que tels.
Toute aide serait grandement appréciée.
Combien de véhicules et de sites avez-vous? Une heuristique forte pourrait permettre d'utiliser un backtracking quelque peu stupide. Oui, c'est NP complet, et seulement plusieurs parties peuvent être résolues de façon plus intelligente, comme certains chemins trouvés avec Dijkstra. –
J'ai décomposé le problème en bits. La première partie correspond aux sites avec les véhicules les plus exigeants sur le site, après quoi elle inclut tous les autres sites jusqu'à l'heure d'expiration du véhicule. Ensuite, je trouve le cycle hamiltonien le plus court à partir du graphique obtenu. Je le fais en itération pour tous les véhicules disponibles jusqu'à ce que tous les sites aient été assignés. Comme vous l'aurez deviné, la route générée n'est pas optimale. – Purusartha