Ce site est optimisé pour être consulté depuis un navigateur moderne dans lequel JavaScript est activé.

Script pour optimiser une tournée

chris_wafer

Bonjour,

J'ai une liste d'adresse dans un fichier, et je voudrais faire un script qui me permettent de me réorganiser la liste afin que je parcoure toutes les adresses dans le moins de temps possible.
C'est en fait pour optimiser une tournée.

Quelqu'un aurait une idée?

Merci.

pingouinux

Bonjour,
C'est le fameux problème du voyageur de commerce. Pour chaque couple d'adresses, il faut connaître le temps pour aller de l'une à l'autre. Une recherche exhaustive ne peut se faire que pour un petit nombre d'adresses, car le temps de calcul augmente très vite avec ce nombre.
Il existe peut-être des algorithmes donnant une solution approchée.

Édité : Quel est le nombre d'adresses ?

chris_wafer

Il y a environ une centaine d'adresse.
Où trouver un algorithme et comment faire?
Ça me serait vraiment très utile.

pingouinux

Voici un article qui peut t'aiguiller, mais je ne sais pas faire : Le problème du voyageur de commerce : introduction
Tu trouveras de nombreux articles à ce sujet sur internet.

chris_wafer

Il n'y aurait pas des scripts existant sur quoi ce baser?

chris_wafer

En fait, c'est surtout comment lister la distance entre chaque adresse automatiquement?

jean bono

Salut,
Si tu comprends l'anglais, ceci peut t'aider
http://analystcave.com/excel-calculate-distances-between-addresses/

chris_wafer

Merci.
Et comment on pourrait appeler ça dans un un script? L'API de google où on lui donne deux adresses?

Merci.

Hizoka

Salut, petite contribution 🙂

function CalculDistance
{
depart="${1}"
arrive="${2}"
distance=""
temps=""

while read ligne
do
  if [[ ${ligne} =~ '"text" :' ]]
  then
    if [[ -z ${distance} ]]
    then
      distance="${ligne##*: ?}"
      distance="${distance/%?,}"
    else
      temps="${ligne##*: ?}"
      temps="${temps/%?,}"
    fi
  fi
done < <(curl https://maps.googleapis.com/maps/api/distancematrix/json?origins=${depart}\&destinations=${arrive}\&language=fr)
echo "la distance entre ${depart} et ${arrive} est de ${distance} et il faut compter ${temps} pour la parcourir en voiture"
}

exemple :

CalculDistance Rouen Paris
=> la distance entre Rouen et Paris est de 136 km et il faut compter 1 heure 45 min pour la parcourir en voiture

Pour la suite, il est imaginable de boucler sur un fichier avec les adresses, de comparer toutes les adresses une à une.
Pour la suite faut reflechir un peu plus :p

Perso je me dis qu'il vaudrait mieux faire ça en python mais bon...
genre un dico par adresse qu'il faut classer par ordre,
le trajet le plus court est utilisé,
on charge à ce moment là le dico de nouvelle destination en y supprimant les adresses déjà visitées
et ainsi de suite...

Une idée comme une autre je pense...

chris_wafer

Merci beaucoup, c'est super!!!

Et pour l'implémentation de l'Algorithme génétique? Car après faudra faire ça?

Merci d'"avance pour votre aide.

Hizoka

En fait je n'ai pas lu les pages :p

je suis parti sur un truc un peu perso du genre en python3:

from urllib.request import urlopen

# Fonction qui regarde la ville la plus proche en temps
def Tri(Depart, VillesVisitees):
    x = []
    for Ville, Values in BigDico[Depart].items():
        if Ville not in VillesVisitees:
            x.append((int(Values[1]), Values[0], Ville))
    x.sort()
    return(x[0][2])


# Villes à visiter
Villes = ["Rouen", "Paris", "Rennes", "Lyon", "Strasbourg"] # Liste des villes
VillesVisitees = ["Rouen"] # Ville de départ

# Dictionnaire qui contiendra les infos
BigDico = {}

# 1ere boucle travaillant sur les villes
for Depart in Villes:
    # Ajoute la ville à la liste
    BigDico[Depart] = {}
    # 2e boucle traitant les villes
    for Arrive in Villes:
        # Si les 2 villes sont les mêmes, on saute ce calcul
        if Depart == Arrive:
            continue
        # On ajoute la nouvelle destination à la ville de départ
        BigDico[Depart][Arrive] = []
        # On ajoute les infos sur le trajet
        for Ligne in urlopen("https://maps.googleapis.com/maps/api/distancematrix/json?origins={}&destinations={}&language=fr".format(Depart, Arrive)).read().decode('UTF-8').split("\n"):
            if '"value" :' in Ligne:
                BigDico[Depart][Arrive].append(Ligne.split(' : ')[1])

# Tri les temps d'acces par ordre
Trajet = [Villes[0]]
VillesVisitees.append(Villes[0])

NextVille = Tri(Villes[0], VillesVisitees)
Trajet.append(NextVille)

while len(Villes) != len(VillesVisitees):
    VillesVisitees.append(NextVille)
    NextVille = Tri(NextVille, VillesVisitees)
    Trajet.append(NextVille)

ça donne ça :

['Rouen', 'Paris', 'Rennes', 'Lyon', 'Strasbourg']

et ça semble en effet être à chaque fois le trajet le plus rapide...

Après il y a surement une meilleur logique...

Pour travailler sur la distance au lieu du temps, il suffit de changer ça :

def Tri(Depart, VillesVisitees):
    x = []
    for Ville, Values in BigDico[Depart].items():
        if Ville not in VillesVisitees:
            x.append((int(Values[1]), Values[0], Ville))
    x.sort()
    return(x[0][2])

def Tri(Depart, VillesVisitees):
    x = []
    for Ville, Values in BigDico[Depart].items():
        if Ville not in VillesVisitees:
            x.append((int(Values[0]), Values[1], Ville))
    x.sort()
    return(x[0][2])

chris_wafer

Merci beaucoup.

Mais l’algorithme risque d'être long pour 120 villes, non?

Hizoka

Je regarde pour éviter les récupérations doublons des infos, mais oui ça va prendre un peu de temps enfin bon, il suffit d'attendre...

EDIT, version un chouille plus rapide :

from urllib.request import urlopen

# Fonction qui regarde la ville la plus proche en temps
def Tri(Depart, VillesVisitees):
    x = []
    
    for Ville, Values in BigDico[Depart].items():
        if Ville not in VillesVisitees:
            x.append((int(Values[1]), Values[0], Ville))
            
    x.sort()
    
    return(x[0][2])


# Villes à visiter
Villes = ["Rouen", "Paris", "Rennes", "Lyon", "Strasbourg", "Le Havre", "Sotteville les Rouen", "Quimper", "Londres", "Brest", "Berlin"] # Liste des villes
VillesVisitees = ["Rouen"] # Ville de départ

# Dictionnaire qui contiendra les infos
BigDico = {}

# 1ere boucle travaillant sur les villes
for Depart in Villes:
    # Ajoute la ville à la liste
    if Depart not in BigDico.keys():
        BigDico[Depart] = {}
    
    # 2e boucle traitant les villes
    for Arrive in Villes:
        # Si les 2 villes sont les mêmes, on saute ce calcul
        if Depart == Arrive:
            continue
            
        # Pour eviter de calculer plusieurs fois les mêmes trajets
        if Arrive not in BigDico.keys():
            BigDico[Arrive] = {}
            
        # On ajoute la nouvelle destination à la ville de départ
        if Arrive not in BigDico[Depart].keys():
            BigDico[Depart][Arrive] = []
            BigDico[Arrive][Depart] = []
        
            # On ajoute les infos sur le trajet
            for Ligne in urlopen("https://maps.googleapis.com/maps/api/distancematrix/json?origins={}&destinations={}&language=fr".format(Depart.replace(" ", "+"), Arrive.replace(" ", "+"))).read().decode('UTF-8').split("\n"):
                if '"value" :' in Ligne:
                    BigDico[Depart][Arrive].append(Ligne.split(' : ')[1])
                    BigDico[Arrive][Depart].append(Ligne.split(' : ')[1])

                
# Tri les temps d'acces par ordre
Trajet = [Villes[0]]

NextVille = Tri(Villes[0], VillesVisitees)
Trajet.append(NextVille)
VillesVisitees.append(NextVille)

while len(Villes) != len(VillesVisitees):
    print("ville de depart", NextVille)
    NextVille = Tri(NextVille, VillesVisitees)
    Trajet.append(NextVille)
    VillesVisitees.append(NextVille)

print("Les trajets les plus rapides seraient :", " => ".join(Trajet))

Il est évident qu'on peut améliorer le code et que ça doit être un chouille long (le temps de réponse du serveur) mais l'avantage c'est que c'est automatique...
Il est possible dans l'idée de faire du multi thread sur la récup des infos, ça ferait une très grosse différence si tu as plusieurs core.
EDIT : code modifié pour prendre en compte les espaces

chris_wafer

Bonjour,

Merci merci c'est trop sympa.
L'idéal serait maintenant de lire un fichier où chaque ligne contient une adresse; et ensuite de gérer un fichier qui contient les adresses dans l'ordre de la tournée.
Et aussi, écrire à la fin de la génération le temps ou la distance parcouru.

Merci d'avance.

Hizoka

V'la un code un peu cracra mais qui va bien plus vite si tu as plusieurs coeurs :

#!/bin/python3

from urllib.request import urlopen
from concurrent.futures import ThreadPoolExecutor # Permet de le multi calcul
from psutil import cpu_count # Indique le nombre de cpu


def Internet(Arrive):
    global Depart

    # On ajoute les infos sur le trajet
    for Ligne in urlopen("https://maps.googleapis.com/maps/api/distancematrix/json?origins={}&destinations={}&language=fr".format(Depart.replace(" ", "+"), Arrive.replace(" ", "+"))).read().decode('UTF-8').split("\n"):
        if '"value" :' in Ligne:
            BigDico[Depart][Arrive].append(Ligne.split(' : ')[1])
            BigDico[Arrive][Depart].append(Ligne.split(' : ')[1])



# Fonction qui regarde la ville la plus proche en temps
def Tri(Depart, VillesVisitees):
    x = []

    for Ville, Values in BigDico[Depart].items():
        if Ville not in VillesVisitees:
            x.append((int(Values[1]), int(Values[0]), Ville))

    x.sort()

    global TotalDistance
    TotalDistance += x[0][1]
    global TotalTemps
    TotalTemps += x[0][0]

    return(x[0][2])


# Villes à visiter
TotalDistance = 0
TotalTemps = 0
Villes = []
Fichier = "ListeVilles.txt" # La 1ere ville est celle de départ
Sortie = "VillesTriees.txt"

with open(Fichier, "r") as ListeVilles:
    for Ville in ListeVilles:
        Villes.append(Ville.replace('\n', ''))

VillesVisitees = [Villes[0]] # Ville de départ

# Dictionnaire qui contiendra les infos
BigDico = {}


# 1ere boucle travaillant sur les villes
for Depart in Villes:
    # Ajoute la ville à la liste
    if Depart not in BigDico.keys():
        BigDico[Depart] = {}

    Caca = []

    # 2e boucle traitant les villes
    for Arrive in Villes:
        # Si les 2 villes sont les mêmes, on saute ce calcul
        if Depart == Arrive:
            continue

        # Pour eviter de calculer plusieurs fois les mêmes trajets
        if Arrive not in BigDico.keys():
            BigDico[Arrive] = {}

        # On ajoute la nouvelle destination à la ville de départ
        if Arrive not in BigDico[Depart].keys():
            BigDico[Depart][Arrive] = []
            BigDico[Arrive][Depart] = []

            Caca.append(Arrive)

    with ThreadPoolExecutor(max_workers=cpu_count()) as executor:
        print("Traitement des distances en partant de", Depart)
        for City in Caca:
            executor.submit(Internet, City)



# Tri les temps d'acces par ordre
Trajet = [Villes[0]]

NextVille = Tri(Villes[0], VillesVisitees)
Trajet.append(NextVille)
VillesVisitees.append(NextVille)

while len(Villes) != len(VillesVisitees):
    NextVille = Tri(NextVille, VillesVisitees)
    Trajet.append(NextVille)
    VillesVisitees.append(NextVille)

with open(Sortie, "w") as VillesTriees:
    for Ville in Trajet:
        VillesTriees.write(Ville + '\n')


print("Les trajets les plus rapides seraient :", " => ".join(Trajet))
print("Cela fait un total de {}km et {} heures de trajet".format(int(TotalDistance/1000), int(TotalTemps/3600)))

ex :

Traitement des distances en partant de Rouen
Traitement des distances en partant de Caen
Traitement des distances en partant de Amiens
Traitement des distances en partant de Paris
Traitement des distances en partant de Brest
Traitement des distances en partant de Marseille
Traitement des distances en partant de Grenoble
Traitement des distances en partant de Berlin
Traitement des distances en partant de Moscou
Traitement des distances en partant de Londres
Traitement des distances en partant de Rome
Traitement des distances en partant de Venise
Les trajets les plus rapides seraient : Rouen => Amiens => Paris => Caen => Brest => Londres => Grenoble => Marseille => Venise => Rome => Berlin => Moscou
Cela fait un total de 7723km et 77 heures de trajet

Pour le fichier d'entré :

Fichier = "ListeVilles.txt" # La 1ere ville est celle de départ

Pour le fichier de sortie :

Sortie = "VillesTriees.txt"

chris_wafer

ça me marque :

Traceback (most recent call last):
  File "/home/chris/bin/CDCalulDistance.py", line 5, in <module>
    from psutil import cpu_count # Indique le nombre de cpu
ImportError: cannot import name 'cpu_count'

Hizoka

vla une version ou tu indiques le nombre de core à utiliser :

#!/bin/python3

from urllib.request import urlopen
from concurrent.futures import ThreadPoolExecutor # Permet de le multi calcul


def Internet(Arrive):
    global Depart

    # On ajoute les infos sur le trajet
    for Ligne in urlopen("https://maps.googleapis.com/maps/api/distancematrix/json?origins={}&destinations={}&language=fr".format(Depart.replace(" ", "+"), Arrive.replace(" ", "+"))).read().decode('UTF-8').split("\n"):
        if '"value" :' in Ligne:
            BigDico[Depart][Arrive].append(Ligne.split(' : ')[1])
            BigDico[Arrive][Depart].append(Ligne.split(' : ')[1])



# Fonction qui regarde la ville la plus proche en temps
def Tri(Depart, VillesVisitees):
    x = []

    for Ville, Values in BigDico[Depart].items():
        if Ville not in VillesVisitees:
            x.append((int(Values[1]), int(Values[0]), Ville))

    x.sort()

    global TotalDistance
    TotalDistance += x[0][1]
    global TotalTemps
    TotalTemps += x[0][0]

    return(x[0][2])


NombreDeCoeur = 4
TotalDistance = 0
TotalTemps = 0
Villes = []
Fichier = "ListeVilles.txt" # La 1ere ville est celle de départ
Sortie = "VillesTriees.txt"

with open(Fichier, "r") as ListeVilles:
    for Ville in ListeVilles:
        Villes.append(Ville.replace('\n', ''))

VillesVisitees = [Villes[0]] # Ville de départ

# Dictionnaire qui contiendra les infos
BigDico = {}


# 1ere boucle travaillant sur les villes
for Depart in Villes:
    # Ajoute la ville à la liste
    if Depart not in BigDico.keys():
        BigDico[Depart] = {}

    Caca = []

    # 2e boucle traitant les villes
    for Arrive in Villes:
        # Si les 2 villes sont les mêmes, on saute ce calcul
        if Depart == Arrive:
            continue

        # Pour eviter de calculer plusieurs fois les mêmes trajets
        if Arrive not in BigDico.keys():
            BigDico[Arrive] = {}

        # On ajoute la nouvelle destination à la ville de départ
        if Arrive not in BigDico[Depart].keys():
            BigDico[Depart][Arrive] = []
            BigDico[Arrive][Depart] = []

            Caca.append(Arrive)

    with ThreadPoolExecutor(max_workers=NombreDeCoeur) as executor:
        print("Traitement des distances en partant de", Depart)
        for City in Caca:
            executor.submit(Internet, City)



# Tri les temps d'acces par ordre
Trajet = [Villes[0]]

NextVille = Tri(Villes[0], VillesVisitees)
Trajet.append(NextVille)
VillesVisitees.append(NextVille)

while len(Villes) != len(VillesVisitees):
    NextVille = Tri(NextVille, VillesVisitees)
    Trajet.append(NextVille)
    VillesVisitees.append(NextVille)

with open(Sortie, "w") as VillesTriees:
    for Ville in Trajet:
        VillesTriees.write(Ville + '\n')


print("Les trajets les plus rapides seraient :", " => ".join(Trajet))
print("Cela fait un total de {}km et {} heures de trajet".format(int(TotalDistance/1000), int(TotalTemps/3600)))

tu modifies

NombreDeCoeur = 4

tu lances bien le logiciel en utilisant python3 ?

chris_wafer

Je tape :

 python3 <MonScript>

Une idée?
Je pensais aussi que tu pourrais rajouter un message d'erreur lorsque les villes sont erronées (qu'on ne trouve pas)?

Merci encore pour ton superbe travail!

chris_wafer

J'ai remplacé par ça et ça marche :

from multiprocessing import cpu_count

chris_wafer

Une version pour afficher une erreur et ignorer lorsque l'adresse est pas valide?

Page suivante »