Script pour optimiser une tournée

chris_wafer · Le 22/11/2016, à 08:47

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 · Le 22/11/2016, à 09:04

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 ?

Dernière modification par pingouinux (Le 22/11/2016, à 09:10)

chris_wafer · Le 22/11/2016, à 09:17

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

pingouinux · Le 22/11/2016, à 09:22

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 · Le 22/11/2016, à 09:55

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

chris_wafer · Le 22/11/2016, à 09:59

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

jean bono · Le 22/11/2016, à 11:42

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

chris_wafer · Le 22/11/2016, à 12:23

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

Merci.

Hizoka · Le 22/11/2016, à 12:54

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

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...

Dernière modification par Hizoka (Le 22/11/2016, à 13:09)

chris_wafer · Le 22/11/2016, à 14:11

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 · Le 22/11/2016, à 19:44

En fait je n'ai pas lu les pages

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])

en

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 · Le 22/11/2016, à 19:52

Merci beaucoup.

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

Hizoka · Le 22/11/2016, à 20:00

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

Dernière modification par Hizoka (Le 22/11/2016, à 21:51)

chris_wafer · Le 23/11/2016, à 05:45

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 · Le 23/11/2016, à 18:39

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"

Dernière modification par Hizoka (Le 23/11/2016, à 18:42)

chris_wafer · Le 23/11/2016, à 19:28

ç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 · Le 23/11/2016, à 19:37

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 · Le 23/11/2016, à 20:06

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 · Le 23/11/2016, à 20:19

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

from multiprocessing import cpu_count

chris_wafer · Le 23/11/2016, à 20:27

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

Hizoka · Le 24/11/2016, à 15:24

Une version un peu crados :

#!/bin/python3
from urllib.request import urlopen
from concurrent.futures import ThreadPoolExecutor # Permet de le multi calcul
from multiprocessing import cpu_count # Indique le nombre de cpu


def Internet(Arrive):
    global Depart

    if Depart in VillesInconnues or Arrive in VillesInconnues:
        return

    # 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])

        elif '"destination_addresses" : [ "" ],' in Ligne:
            VillesInconnues.add(Arrive)

        elif '"origin_addresses" : [ "" ],' in Ligne:
            VillesInconnues.add(Depart)


# Fonction qui regarde la ville la plus proche en temps
def Tri(Depart, VillesVisitees):
    try:
        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])

    except:
        pass

# Villes à visiter
TotalDistance = 0
TotalTemps = 0
Villes = []
VillesInconnues = set()
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.strip())

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:
        for City in Caca:
            executor.submit(Internet, City)


# Supprime les villes iconnues
for Ville in VillesInconnues:
    print("Impossible de trouver la ville", Ville)

    try:
        del(BigDico[Ville])
    except:
        pass

    popo = dict(BigDico)

    for MiniDict in popo:
        try:
            del(BigDico[MiniDict][Ville])
        except:
            pass


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

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

# Boucle traitant toutes les villes
while len(Villes) != len(VillesVisitees) + len(VillesInconnues):
    NextVille = Tri(NextVille, VillesVisitees)
    Trajet.append(NextVille)
    VillesVisitees.append(NextVille)


# Écriture dans le fichier de sortie
with open(Sortie, "w") as VillesTriees:
    for Ville in Trajet:
        if Ville:
            VillesTriees.write(Ville + '\n')


# informations
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 :

Impossible de trouver la ville Kakakokikokukp
Impossible de trouver la ville Salololollope
Les trajets les plus rapides seraient : Rouen => Le Havre => Paris => Berlin
Cela fait un total de 1340km et 13 heures de trajet

chris_wafer · Le 24/11/2016, à 18:44

Si j'ai un fichier avec ça :

Bordeaux
Paris
Lille
Toulouse
Narbonne
Marseille
Léognan

Ca me met cette erreur :

Traceback (most recent call last):
  File "/home/chris/bin/CDCalulDistance.py", line 135, in <module>
    print("Les trajets les plus rapides seraient :", " => ".join(Trajet))
TypeError: sequence item 1: expected str instance, NoneType found

Hizoka · Le 24/11/2016, à 19:00

les accents semblent poser probleme...
sans, ça fonctionne...

chris_wafer · Le 24/11/2016, à 19:27

Une idée pour gérer les accents?

Hizoka · Le 24/11/2016, à 19:57

#!/bin/python3
from urllib.request import urlopen
from urllib.parse import quote
from concurrent.futures import ThreadPoolExecutor # Permet de le multi calcul
from multiprocessing import cpu_count # Indique le nombre de cpu



# Variables
TotalDistance = 0
TotalTemps = 0
Villes = []
VillesInconnues = set()
Stop=False
StopMessage=""
Cle="AIzaSyD5UNZCB4zhybm0f8Kf1vxOhsprKCFVIyE"
#Cle="AIzaSyB3mt5IkwuxFVS2H7pcdy4aqrkDGhsi_ao"
Fichier = "ListeVilles.txt" # La 1ere ville est celle de départ
Sortie = "VillesTriees.txt"


def Internet(Arrive):
    global Depart
    global Stop

    if Depart in VillesInconnues or Arrive in VillesInconnues or Stop:
        return

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

        elif '"destination_addresses" : [ "" ],' in Ligne:
            VillesInconnues.add(Arrive)

        elif '"origin_addresses" : [ "" ],' in Ligne:
            VillesInconnues.add(Depart)

        elif '"error_message" :' in Ligne:
            Stop=True

            global StopMessage
            StopMessage = ":".join(Ligne.split(":")[1:])



# Fonction qui regarde la ville la plus proche en temps
def Tri(Depart, VillesVisitees):
    try:
        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])
    except:
        print("La fonction tri n'a pas bien fonctionnée avec", Depart, VillesVisitees)
        print(BigDico[Depart])



with open(Fichier, "r") as ListeVilles:
    for Ville in ListeVilles:
        Villes.append(Ville.strip())

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:
        for City in Caca:
            executor.submit(Internet, City)


# Supprime les villes iconnues
for Ville in VillesInconnues:
    print("Impossible de trouver la ville", Ville)

    try:
        del(BigDico[Ville])
    except:
        pass

    popo = dict(BigDico)

    for MiniDict in popo:
        try:
            del(BigDico[MiniDict][Ville])
        except:
            pass


if Stop:
    print("Une erreur est survenue :", StopMessage)
    exit()


for Ville, Values in BigDico[Depart].items():
    print(Ville, Values)

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

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

# Boucle traitant toutes les villes
while len(Villes) != len(VillesVisitees) + len(VillesInconnues):
    NextVille = Tri(NextVille, VillesVisitees)
    Trajet.append(NextVille)
    VillesVisitees.append(NextVille)


# Écriture dans le fichier de sortie
with open(Sortie, "w") as VillesTriees:
    for Ville in Trajet:
        if Ville:
            VillesTriees.write(Ville + '\n')


# informations
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)))

Les trajets les plus rapides seraient : Bordeaux => Léognan => Toulouse => Narbonne => Marseille => Paris => Lille
Cela fait un total de 1668km et 16 heures de trajet

Va te falloir te mettre à python

Dernière modification par Hizoka (Le 26/11/2016, à 14:57)

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 22/11/2016, à 08:47

Script pour optimiser une tournée

#2 Le 22/11/2016, à 09:04

Re : Script pour optimiser une tournée

#3 Le 22/11/2016, à 09:17

Re : Script pour optimiser une tournée

#4 Le 22/11/2016, à 09:22

Re : Script pour optimiser une tournée

#5 Le 22/11/2016, à 09:55

Re : Script pour optimiser une tournée

#6 Le 22/11/2016, à 09:59

Re : Script pour optimiser une tournée

#7 Le 22/11/2016, à 11:42

Re : Script pour optimiser une tournée

#8 Le 22/11/2016, à 12:23

Re : Script pour optimiser une tournée

#9 Le 22/11/2016, à 12:54

Re : Script pour optimiser une tournée

#10 Le 22/11/2016, à 14:11

Re : Script pour optimiser une tournée

#11 Le 22/11/2016, à 19:44

Re : Script pour optimiser une tournée

#12 Le 22/11/2016, à 19:52

Re : Script pour optimiser une tournée

#13 Le 22/11/2016, à 20:00

Re : Script pour optimiser une tournée

#14 Le 23/11/2016, à 05:45

Re : Script pour optimiser une tournée

#15 Le 23/11/2016, à 18:39

Re : Script pour optimiser une tournée

#16 Le 23/11/2016, à 19:28

Re : Script pour optimiser une tournée

#17 Le 23/11/2016, à 19:37

Re : Script pour optimiser une tournée

#18 Le 23/11/2016, à 20:06

Re : Script pour optimiser une tournée

#19 Le 23/11/2016, à 20:19

Re : Script pour optimiser une tournée

#20 Le 23/11/2016, à 20:27

Re : Script pour optimiser une tournée

#21 Le 24/11/2016, à 15:24

Re : Script pour optimiser une tournée

#22 Le 24/11/2016, à 18:44

Re : Script pour optimiser une tournée

#23 Le 24/11/2016, à 19:00

Re : Script pour optimiser une tournée

#24 Le 24/11/2016, à 19:27

Re : Script pour optimiser une tournée

#25 Le 24/11/2016, à 19:57

Re : Script pour optimiser une tournée

Pied de page des forums