#26 Le 25/11/2016, à 00:57
- chris_wafer
Re : Script pour optimiser une tournée
Oui je m'y mettrais un jour... ;-) Mais tu es vraiment trop rapide... ;-)
Hors ligne
#27 Le 25/11/2016, à 20:45
- chris_wafer
Re : Script pour optimiser une tournée
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?
Hors ligne
#28 Le 27/11/2016, à 11:53
- chris_wafer
Re : Script pour optimiser une tournée
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.
Hors ligne
#29 Le 27/11/2016, à 11:59
- chris_wafer
Re : Script pour optimiser une tournée
La librairie GeoPy ne pourrait pas faire l'affaire?
https://geopy.readthedocs.io/en/1.10.0/
Hors ligne
#30 Le 27/11/2016, à 12:26
- Hizoka
Re : Script pour optimiser une tournée
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)
KDE Neon 64bits
Tous mes softs (MKVExtractorQt, HizoSelect, HizoProgress, Qtesseract, Keneric, Services menus...) sont sur github
Hors ligne
#31 Le 27/11/2016, à 17:35
- chris_wafer
Re : Script pour optimiser une tournée
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?
Hors ligne
#32 Le 27/11/2016, à 19:20
- Hizoka
Re : Script pour optimiser une tournée
c'est ce que j'ai compris.
KDE Neon 64bits
Tous mes softs (MKVExtractorQt, HizoSelect, HizoProgress, Qtesseract, Keneric, Services menus...) sont sur github
Hors ligne
#33 Le 27/11/2016, à 19:50
- chris_wafer
Re : Script pour optimiser une tournée
C'est 15000 transactions.
Hors ligne
#34 Le 27/11/2016, à 20:50
- chris_wafer
Re : Script pour optimiser une tournée
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?
Hors ligne
#35 Le 27/11/2016, à 20:55
- chris_wafer
Re : Script pour optimiser une tournée
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?
Hors ligne
#36 Le 27/11/2016, à 21:29
- Hizoka
Re : Script pour optimiser une tournée
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.
KDE Neon 64bits
Tous mes softs (MKVExtractorQt, HizoSelect, HizoProgress, Qtesseract, Keneric, Services menus...) sont sur github
Hors ligne
#37 Le 27/11/2016, à 22:00
- chris_wafer
Re : Script pour optimiser une tournée
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)
Hors ligne
#38 Le 27/11/2016, à 23:39
- Hizoka
Re : Script pour optimiser une tournée
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
KDE Neon 64bits
Tous mes softs (MKVExtractorQt, HizoSelect, HizoProgress, Qtesseract, Keneric, Services menus...) sont sur github
Hors ligne
#39 Le 28/11/2016, à 23:13
- chris_wafer
Re : Script pour optimiser une tournée
Y aurait pas un fort en programmation qui aurait le courage à le programmer?
Car j'avoue que je vais terriblement galéré...
Merci.
Hors ligne
#40 Le 11/01/2017, à 13:31
- Pluton13
Re : Script pour optimiser une tournée
Bravo Hizoka quelle expertise et quelle patience...
Hors ligne
#41 Le 15/07/2020, à 16:29
- Degenesis
Re : Script pour optimiser une tournée
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.
Hors ligne
#42 Le 01/09/2023, à 14:15
- chris_wafer
Re : Script pour optimiser une tournée
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?
Hors ligne
#43 Le 02/08/2024, à 13:46
- chris_wafer
Re : Script pour optimiser une tournée
Bonjour,
Je relance le sujet pour savoir si d'autres personnes ont cogité sur cette problématique?
Merci.
Hors ligne
#44 Le 02/08/2024, à 15:47
- Watael
Re : Script pour optimiser une tournée
tu dois être bien sec maintenant, depuis huit ans que tu sèches sur le sujet.
Connected \o/
Welcome to sHell. · eval is evil.
En ligne
#45 Le 02/08/2024, à 15:53
- xubu1957
Re : Script pour optimiser une tournée
Bonjour,
Et l'Intelligence Artificielle n'aurait-elle pas pondue une réponse ?
Conseils pour les nouveaux demandeurs et pas qu'eux
Important : Pensez à passer vos sujets en [Réso|u] lorsque ceux-ci le sont, au début du titre en cliquant sur Modifier sous le premier message, et un bref récapitulatif de la solution à la fin de celui-ci. Merci. Membre de Linux-Azur
Hors ligne
#46 Le 02/08/2024, à 16:11
- Watael
Re : Script pour optimiser une tournée
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)
Connected \o/
Welcome to sHell. · eval is evil.
En ligne
#47 Le 06/08/2024, à 02:08
- nicolas66
Re : Script pour optimiser une tournée
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.).
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#48 Le 11/08/2024, à 18:53
- chris_wafer
Re : Script pour optimiser une tournée
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...
Hors ligne