Le problème du voyageur de commerce (PVC)

Trouver le trajet le plus court pour passer par un certain nombre de villes et revenir à la ville de départ : voila le problème posé ! 

Problème apparemment simple, en fait très complexe ! Pourriez-vous imaginer qu'il faudrait environ 30 ans pour traiter le parcours ci-contre en explorant  un milliard de trajets par seconde ?

Malgré tout, il existe des méthodes de résolution et j'en présenterai quelques unes dans cet article. Vous pourrez trouver en particulier :

• la méthode simple que j'utilise pour atteindre rapidement la solution du défi des 250 villes proposé sur Internet depuis quelques années.
• des exemples d'utilisation pédagogique pour des élèves de collège ou de lycée.

Des animations illustrant les algorithmes utilisés.

Introduction

Méthodes de résolution

La méthode de la colonie de fourmis

Le 2-opt amélioré que j'utilise pour le problème des 250 villes.

150 villes (Churitz) : méthode 2 opt optimisé