Script pour optimiser une tournée

chris_wafer · Le 25/11/2016, à 00:57

Oui je m'y mettrais un jour... ;-) Mais tu es vraiment trop rapide... ;-)

chris_wafer · Le 25/11/2016, à 20:45

Attention : il faut avoir une clés pour utiliser de manière illimité l'API de Google.
On peu l'avoir ici : https://console.developers.google.com/apis/credentials

Il faudrait peut-être rajouté en paramètre de ce script un clés?

chris_wafer · Le 27/11/2016, à 11:53

Par contre on est limité à 2500 requêtes par jour avec l'API google.
Ainsi, il sera pas possible de splitter le script pour d'abord sauver dans un fichier tous les résultats de distance que l'on peut relancer chaque jour pour qu'ils viennent se compléter astucieusement.
Et ensuite, une fois que tout est rempli le script viendrait lire ce fichier pour faire l'algortihme des distances?

Merci d'avance.

chris_wafer · Le 27/11/2016, à 11:59

La librairie GeoPy ne pourrait pas faire l'affaire?
https://geopy.readthedocs.io/en/1.10.0/

Hizoka · Le 27/11/2016, à 12:26

Y a ça aussi qui semble pas mal : https://developer.mapquest.com/document … tions-api/

https://developer.mapquest.com/document … trix/post/ semble complétement adapté mais je n'ai qu'un message d'erreur quand j'essaie de l'utiliser...

http://www.mapquestapi.com/directions/v2/routematrix?json{"locations":["Rouen","Rennes","Paris","Nantes"],"options":{"allToAll":true}}&outFormat=xml&key=KEY
Error parsing JSON from Request: A JSONObject text must begin with '{' at character 0 of ,  Please see the documentation for the Directions Service at http://www.mapquestapi.com/directions/ for details on correctly formatting requests.

je ne sais pas si ça vient de moi ou pas...

Pourtant

https://www.mapquestapi.com/directions/v2/optimizedRoute?json={"locations":["Rouen","Caen","Rennes","Paris"]}&outFormat=xml&key=KEY

fonctionne bien lui...

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

chris_wafer · Le 27/11/2016, à 17:35

C'est quand même limitée à 150 000 transactions?
Pour 100 lieu, ça va puisque ça va faire 100*100=10000 transactions si j'ai bien compris?

Hizoka · Le 27/11/2016, à 19:20

c'est ce que j'ai compris.

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

C'est 15000 transactions.

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

Je viens d'essayer des trucs mais je ne comprends pas pourquoi ta requête marche pas.
Quelqu'un d'autres auraient une idée?

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

Si je tape ceci ça marche en ligne de commande :

curl -X POST -H "Content-Type: application/json" -v -d '{"locations":["Rouen","Rennes","Paris","Nantes"],"options":{"allToAll":true}}' http://www.mapquestapi.com/directions/v2/routematrix?key=KEY

On pourrait l'intégrer?

Hizoka · Le 27/11/2016, à 21:29

c'est assez compliqué car on ne peut les mettre que par paquets de 25...
donc franchement ca va prendre du temps à mettre en place et je n'ai pas trop ce temps là...

si on veut garder le système de la double boucle, il faut pas faire du allToAll mais du direct, ce qui permet de faire des paquets de 100 d'après ce que j'ai lu.

chris_wafer · Le 27/11/2016, à 22:00

En fait pour 100 villes, il suffit juste de faire combien de requêtes?

Dernière modification par chris_wafer (Le 27/11/2016, à 22:19)

Hizoka · Le 27/11/2016, à 23:39

Si on veut etre precis : 100 * 99 = 9900

et si on evite de calculer les aller retour, ça fait bien moins puisque que, si je dis pas de connerie :
1ere ville : 99 (les 99 autres villes)
2e : 98 (les 99 moins la 1ere)
3e : 97 (les 99 moins les 2 premieres)
...
99e : 1
100 : 0

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

Y aurait pas un fort en programmation qui aurait le courage à le programmer?
Car j'avoue que je vais terriblement galéré...

Merci.

Pluton13 · Le 11/01/2017, à 13:31

Bravo Hizoka quelle expertise et quelle patience...

Degenesis · Le 15/07/2020, à 16:29

Bonjour,
Je vais me permettre d'intervenir, et de déterrer le topic (veuillez m'en excusez), mais je me dis que l'info que je partage pourrait relancer, voir intéresser certaines personnes. Je suis tombé sur cette page, parlant de l'algorithme de Dijkstra et je me demande si cela ne pourrait pas être une aide précieuse pour ce projet.

Il suffirait tout d'abord de proposer, dans le script, le type itinéraire (si possible): "Rapide" ou "Court", préciser également s'il est souhaitable d'éviter l'autoroute et/ou les sections à péage ; ensuite, l’algorithme s'occuperait de calculer les distances dans un ordre précis, en reprenant l'idée de la ville de départ en 1re position dans la liste.

Concernant l'API, à voir s'il est intéressant d'utiliser Google ou un autre service.

chris_wafer · Le 01/09/2023, à 14:15

Bonjour,

Je relance le sujet pour savoir s'il y en a qui connaisse des algorithmes optimisées "open source" pour trouver la tournée avec le moins de km? Afin que cela soit hyper rapide à calculer?
Y a pas un truc avec les graphes?

chris_wafer · Le 02/08/2024, à 13:46

Bonjour,

Je relance le sujet pour savoir si d'autres personnes ont cogité sur cette problématique?

Merci.

Watael · Le 02/08/2024, à 15:47

tu dois être bien sec maintenant, depuis huit ans que tu sèches sur le sujet.

xubu1957 · Le 02/08/2024, à 15:53

Bonjour,

Et l'Intelligence Artificielle n'aurait-elle pas pondue une réponse ?

Watael · Le 02/08/2024, à 16:11

est-ce bien nécessaire de déranger le chat qu'j'ai pété ?

j'ai croisé "le problème (de la tournée) du commis voyageur" il y a longtemps, et je me souviens que c'est documenté, et que j'avais trouvé des algorithmes avec le "simple" moteur de recherche de l'époque.
mais, n'en ayant pas l'usage, je n'ai pas développé plus de curiosité que ça.

Dernière modification par Watael (Le 02/08/2024, à 16:11)

nicolas66 · Le 06/08/2024, à 02:08

J'abonde dans le sens de Watael : le problème du voyageur de commerce (traveling salesman problem) est ancien (première formulation dans les années 30), bien étudié mais difficile à résoudre de manière optimale dans un temps raisonnable sur un ordinateur. La bonne nouvelle est qu'il existe des algorithmes (appelés heuristiques) permettant de fournir une solution, certes sous-optimale, mais souvent de qualité suffisante pour les besoins courants, comme c'est le cas ici. Une heuristique courante et simple à implémenter est de commencer avec une solution tirée aléatoirement puis d'accepter des modifications avec une probabilité qui décroît au fil du temps. Je t'invite à consulter la page Wikipédia pour avoir plus d'infos à ce sujet (historique, algorithmiques, complexités, etc.).

chris_wafer · Le 11/08/2024, à 18:53

Et voilà ce qu'a donné chat G PT :

<?php

function getCoordinates($address) {
    $address = urlencode($address);
    $url = "https://nominatim.openstreetmap.org/search?q={$address}&format=json&addressdetails=1&limit=1";
    $opts = [
        "http" => [
            "header" => "User-Agent: Nominatim-Test/1.0\r\n"
        ]
    ];
    $context = stream_context_create($opts);
    $response = file_get_contents($url, false, $context);
    $response = json_decode($response, true);
    
    if (!empty($response)) {
        $location = $response[0];
        return ['lat' => $location['lat'], 'lon' => $location['lon']];
    } else {
        return null;
    }
}

function calculateDistance($coord1, $coord2) {
    $earthRadius = 6371; // Earth's radius in kilometers

    $latFrom = deg2rad($coord1['lat']);
    $lonFrom = deg2rad($coord1['lon']);
    $latTo = deg2rad($coord2['lat']);
    $lonTo = deg2rad($coord2['lon']);

    $latDelta = $latTo - $latFrom;
    $lonDelta = $lonTo - $lonFrom;

    $angle = 2 * asin(sqrt(pow(sin($latDelta / 2), 2) + cos($latFrom) * cos($latTo) * pow(sin($lonDelta / 2), 2)));
    return $angle * $earthRadius;
}

function findNearestClient($currentLocation, $clients, $availableClients) {
    $closestClient = null;
    $closestDistance = PHP_INT_MAX;
    foreach ($availableClients as $clientIndex) {
        $distance = calculateDistance($currentLocation, $clients[$clientIndex]['coordinates']);
        if ($distance < $closestDistance) {
            $closestDistance = $distance;
            $closestClient = $clientIndex;
        }
    }
    return $closestClient;
}

function twoOptSwap($route, $i, $k) {
    $newRoute = array_slice($route, 0, $i);
    $newRoute = array_merge($newRoute, array_reverse(array_slice($route, $i, $k - $i + 1)));
    $newRoute = array_merge($newRoute, array_slice($route, $k + 1));
    return $newRoute;
}

function twoOpt($clients, $route) {
    $improved = true;
    while ($improved) {
        $improved = false;
        $bestDistance = calculateTotalDistance($clients, $route);
        for ($i = 1; $i < count($route) - 1; $i++) {
            for ($k = $i + 1; $k < count($route); $k++) {
                $newRoute = twoOptSwap($route, $i, $k);
                $newDistance = calculateTotalDistance($clients, $newRoute);
                if ($newDistance < $bestDistance) {
                    $route = $newRoute;
                    $bestDistance = $newDistance;
                    $improved = true;
                }
            }
        }
    }
    return $route;
}

function calculateTotalDistance($clients, $route) {
    $totalDistance = 0;
    for ($i = 0; $i < count($route) - 1; $i++) {
        $totalDistance += calculateDistance($clients[$route[$i]]['coordinates'], $clients[$route[$i + 1]]['coordinates']);
    }
    return $totalDistance;
}

function findNextAvailableSlot($currentTime, $availability, $duration) {
    foreach ($availability as $slot) {
        $startTime = strtotime($slot['start']);
        $endTime = strtotime($slot['end']);
        if ($currentTime <= $startTime && ($startTime + $duration) <= $endTime) {
            return $startTime;
        }
    }
    return null;
}

function organizeWeeklyTour($home, $clients, $workingHours, $weekDays) {
    $tour = [];
    $currentLocation = $home;
    $currentTime = strtotime($workingHours['start']);
    $endTime = strtotime($workingHours['end']);
    
    foreach ($weekDays as $day) {
        $tour[$day] = [];
        $availableClients = array_filter(array_keys($clients), function($index) use ($clients, $day) {
            return isset($clients[$index]['availability'][$day]);
        });
        
        while ($currentTime < $endTime && !empty($availableClients)) {
            $nearestClient = findNearestClient($currentLocation, $clients, $availableClients);
            if ($nearestClient === null) {
                break;
            }

            $clientAvailability = $clients[$nearestClient]['availability'][$day];
            $visitDuration = $clients[$nearestClient]['duration'] * 3600; // Convert hours to seconds
            $visitStartTime = findNextAvailableSlot($currentTime, $clientAvailability, $visitDuration);
            if ($visitStartTime === null) {
                unset($availableClients[array_search($nearestClient, $availableClients)]);
                continue;
            }
            $visitEndTime = strtotime($clientAvailability[array_search(['start' => date('H:i', $visitStartTime), 'end' => date('H:i', strtotime('+1 hour', $visitStartTime))], $clientAvailability)]['end']);

            if ($visitStartTime + (calculateDistance($currentLocation, $clients[$nearestClient]['coordinates']) * 60 / 50 * 3600) > $visitEndTime) {
                unset($availableClients[array_search($nearestClient, $availableClients)]);
                continue;
            }

            $currentTime = $visitStartTime + (calculateDistance($currentLocation, $clients[$nearestClient]['coordinates']) * 60 / 50 * 3600);
            if ($currentTime > $endTime) {
                break;
            }

            $tour[$day][] = $nearestClient;
            unset($availableClients[array_search($nearestClient, $availableClients)]);
            $currentLocation = $clients[$nearestClient]['coordinates'];
            $currentTime += $visitDuration; // Adjust for visit duration
        }

        $tour[$day] = twoOpt($clients, $tour[$day]);
        $currentLocation = $home;
        $currentTime = strtotime($workingHours['start']);
    }

    return $tour;
}

// Adresse de domicile (doit être convertie en coordonnées)
$homeAddress = '47000 Agen';
$home = getCoordinates($homeAddress);
//echo "Home\n";
//print_r ($home);

// Clients avec adresses postales
$clients = [
    ['name' => 'Client1', 'address' => '47310 Moirax', 'duration' => 0.5, 'availability' => ['Monday' => [['start' => '10:00', 'end' => '12:00'], ['start' => '14:00', 'end' => '16:00']]]],
    ['name' => 'Client2', 'address' => '47520 Le Passage', 'duration' => 0.5, 'availability' => ['Tuesday' => [['start' => '09:00', 'end' => '12:00'], ['start' => '15:00', 'end' => '18:00']]]],
    ['name' => 'Client3', 'address' => '47510 Foulayronnes', 'duration' => 0.5, 'availability' => ['Wednesday' => [['start' => '13:00', 'end' => '15:00'], ['start' => '17:00', 'end' => '19:00']]]],
    // Ajoutez plus de clients ici...
];

// Convertir les adresses des clients en coordonnées
foreach ($clients as &$client) {
	//echo "Client : " . $client['name'] . "\n";
    $client['coordinates'] = getCoordinates($client['address']);
    //print_r ($client['coordinates']);
}

//exit;

$weekDays = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday'];
$workingHours = ['start' => '09:00', 'end' => '21:00'];

$tour = organizeWeeklyTour($home, $clients, $workingHours, $weekDays);

foreach ($tour as $day => $clientsForDay) {
    echo $day . ":\n";
    foreach ($clientsForDay as $clientIndex) {
        echo "  Visit " . $clients[$clientIndex]['name'] . " for " . $clients[$clientIndex]['duration'] . " hours\n";
    }
}
?>

Mais il y a encore des bugs... Je suis en train de les chercher...

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#26 Le 25/11/2016, à 00:57

Re : Script pour optimiser une tournée

#27 Le 25/11/2016, à 20:45

Re : Script pour optimiser une tournée

#28 Le 27/11/2016, à 11:53

Re : Script pour optimiser une tournée

#29 Le 27/11/2016, à 11:59

Re : Script pour optimiser une tournée

#30 Le 27/11/2016, à 12:26

Re : Script pour optimiser une tournée

#31 Le 27/11/2016, à 17:35

Re : Script pour optimiser une tournée

#32 Le 27/11/2016, à 19:20

Re : Script pour optimiser une tournée

#33 Le 27/11/2016, à 19:50

Re : Script pour optimiser une tournée

#34 Le 27/11/2016, à 20:50

Re : Script pour optimiser une tournée

#35 Le 27/11/2016, à 20:55

Re : Script pour optimiser une tournée

#36 Le 27/11/2016, à 21:29

Re : Script pour optimiser une tournée

#37 Le 27/11/2016, à 22:00

Re : Script pour optimiser une tournée

#38 Le 27/11/2016, à 23:39

Re : Script pour optimiser une tournée

#39 Le 28/11/2016, à 23:13

Re : Script pour optimiser une tournée

#40 Le 11/01/2017, à 13:31

Re : Script pour optimiser une tournée

#41 Le 15/07/2020, à 16:29

Re : Script pour optimiser une tournée

#42 Le 01/09/2023, à 14:15

Re : Script pour optimiser une tournée

#43 Le 02/08/2024, à 13:46

Re : Script pour optimiser une tournée

#44 Le 02/08/2024, à 15:47

Re : Script pour optimiser une tournée

#45 Le 02/08/2024, à 15:53

Re : Script pour optimiser une tournée

#46 Le 02/08/2024, à 16:11

Re : Script pour optimiser une tournée

#47 Le 06/08/2024, à 02:08

Re : Script pour optimiser une tournée

#48 Le 11/08/2024, à 18:53

Re : Script pour optimiser une tournée

Pied de page des forums