Capacitated Vehicle Routing Problem - Heuristique

[sikin1989]

Bonjour,


Je dois réaliser un programme en C++ permettant de résoudre le problème du CVRP (Capacitated Vehicle Routing Problem) via des heuristiques. Je ne vais pas développer le problème ici puisqu'il s'agit d'un problème classique. Si quelqu'un pense pouvoir me répondre en ayant plus d'information, je lui en fournirais volontiers :-)

Pour l'instant j'ai appliqué l'algorithme de Clarke and Wright. Le problème est que cet algorithme me fournis un nombre de chemin non fixé. Hors, on me demande de n'avoir que x trajets.

J'ai essayé de me renseigner sur des méthodes heuristiques pouvant, à partir de ma résolution partielle, "rectifier" le tire en imposant un certain nombre de trajet, mais je n'ai rien trouvé de concluant.

Est-ce que quelqu'un pourrait donc me renseigner sur des algorithmes pouvant me permettre de faire cela ? Ou me donner un lien qui pourrait m'intéresser ?


Merci d'avance et bonne soirée !