Discussion :

[icl1c]

Bonjour,

Je souhaite adapter le voyageur de commerce pour un problème contenant des zones, avec pour chaque zones, n villes. De plus, il y a une priorité de passage qui doit être appliquée sur chaque zone (prioritaire, normal, non prioritaire). Et plusieurs zones peuvent avoir la même priorité de passage. Autre contrainte, la ville de départ n'est pas identique à la ville d'arrivée.

Chaque zone commencée, doit être entièrement terminée avant d'attaquer une nouvelle zone.

Actuellement, j'utilise l'algorithme 2-opt pour résoudre le problème sans prendre en compte les zones. Mais je ne trouve pas de solution tendant vers l'optimal pour adapter cet algorithme à la gestion des zones et des priorités.

Si vous pouviez m'aider un petit peu à avancer ça serait sympa.

Merci d'avance.

ps : langage de dev : PHP

[Acrim]

La contrainte qui impose que toute zone commencée doit être entièrement terminée avant de passer à une autre devrait "simplifier" ton problème puisque a priori cela devrait pouvoir te permettre de te limiter à un sous-problème par zone au lieu d'avoir à considérer toutes les villes à la fois. Qu'en penses tu ?

Quant au fait que tu ne trouves pas de solution tendant vers l'optimal. Je ne comprends pas ce que tu veux dire : tu tentes de résoudre un TSP classique et rien ne se passe ? Qu'elle est ton approche ?

[icl1c]

Bonjour,

On peut pas considérer que des sous-problèmes. En effet, même si la solution est optimale localement (pour une zone), cela n'implique pas que la solution sera optimale globalement. C'était ma première idée, mais on s'aperçoit très rapidement qu'il y a des absurdités lors de l'affichage du parcours.

Actuellement, j'ai réussi à implémenter mon TSP classique avec 2-opt mais ça ne prend pas en compte les zones. Je sais dans quelle zone se trouve une ville sans problème, j'arrive à bien représenter mes zones mais je n'arrive pas à faire une zone l'une après l'autre avec le TSP.

[Acrim]

Si tu optimises chaque sous problème et que tu optimises l'ordre dans lequel tes sous problèmes (zones) sont visités, tu n'obtiens pas une solution "globalement" optimisée ?

Le fait qu'une zone doit être visitée entièrement fait que beaucoup de solutions "classiques" du TSP sont non-valides. Lorsque tu fais ton 2-opt, prends tu en compte tes zones dans la sélection des arrêtes que tu supprimes (et plus généralement utilises tu une heuristiques pour guider tes choix) ? Par exemple, si tu supprimes deux arcs à l’intérieur de 2 zones différentes tu n'auras aucun moyen de trouver une "reconnexion" qui respecte ta contrainte.

En espérant que cela t'aidera un peu.

[Branch]

Bonjour,

Je souhaite adapter le voyageur de commerce pour un problème contenant des zones, avec pour chaque zones, n villes. De plus, il y a une priorité de passage qui doit être appliquée sur chaque zone (prioritaire, normal, non prioritaire). Et plusieurs zones peuvent avoir la même priorité de passage. Autre contrainte, la ville de départ n'est pas identique à la ville d'arrivée.

Chaque zone commencée, doit être entièrement terminée avant d'attaquer une nouvelle zone.

Actuellement, j'utilise l'algorithme 2-opt pour résoudre le problème sans prendre en compte les zones. Mais je ne trouve pas de solution tendant vers l'optimal pour adapter cet algorithme à la gestion des zones et des priorités.

Si vous pouviez m'aider un petit peu à avancer ça serait sympa.

Merci d'avance.

ps : langage de dev : PHP

Salut,

pour t'aider au mieux il pourrait être interessant de connaitre la taille des problèmes que tu souhaites résoudre (nombre de zones, nombre de clients par zone) ainsi que le temps dont tu disposes pour la résolution (tu souhaites une solution au bout de 1s, 1min, 1h ?)