API Optimisation

Introduction

Open Street est un service d’optimisation d’itinéraires créé à partir de librairies de programmation open-source et d’un moteur développé en interne. En bref, si vous connaissez vos lieux de rendez-vous mais que vous ne savez pas dans quel ordre il est préférable de les parcourir, Open Street peut vous être utile.

Notre application web en ligne utilise les API Open Street, dont notamment celle qui permet d’optimiser des trajets en résolvant le problème du voyageur du commerce

Le lancement d’un calcul par l’API d’optimisation

Protocole utilisé

Cette API utilise la méthode GET implémentée dans le protocole HTTP 1.1. On peut donc l’utiliser depuis un navigateur web standard ou toute autre librairie permettant de télécharger des données depuis un serveur web. Cette API d’optimisation n’est pas susceptible de recevoir de caractères spéciaux ou accentués, mais les URL doivent tout de même être correctement encodées. Les navigateurs récents encodent automatiquement les URL mais pas toujours les librairies HTTP.

Toutes nos API supportent la compression gzip, il est donc fortement conseillé d’activer cette fonctionnalité dans votre client HTTP. Pour vérifier que la compression est active, l’en-tête de la requête du client doit comporter Accept-Encoding : "gzip, deflate" et l’en-tête de la réponse du serveur doit comporter Content-Encoding : "gzip" . Cela permet de diminuer de près de 50% le temps de téléchargement des données.

Le temps de calcul croît en fonction du nombre de points. Plus précisément, il croît au carré du nombre de points. Il faut compter quelques secondes pour une dizaine de points, et quelques minutes pour une centaine. Pour plus d’informations sur la prévision du temps de calcul, cliquez ici.

Il est donc important que le client HTTP utilisé supporte un timeout de plusieurs minutes. Sur demande, nous pouvons fournir la fonction qui donne le temps de calcul estimé en fonction du nombre de points, en vue d’implémenter une barre de progression dans une application.

Notre moteur de résolution tire parti d’un cache interne qui permet d’accélérer une requête à partir du moment où elle a déjà été demandée. Ainsi, en relançant un calcul, ou en ne modifiant que quelques points d’un calcul déjà lancé, le temps de résolution sera sensiblement plus court.

Données d’entrée

Pour fonctionner, cette API a besoin de données qui sont fournies en tant que paramètres d’URL. Dans la tableau ci-dessous, les astérisques* indiquent les paramètres qui sont obligatoires pour lancer un calcul.

Les points géographiques à optimiser doivent obligatoirement être saisis sous la forme de coordonnées latitude,longitude et non pas sous la forme d’adresses postales. L’API de géocodage Open Street permet d’effectuer cette conversion.

Paramètre	Valeur	Explication
pts*	46.2021852,5.2221591	Points de passage séparés par des barres verticales |. Les nombres doivent comporter entre 1 et 10 décimales. L’absence de décimale est refusé car cela n’est pas assez précis pour décrire un lieu.
nb*	de 3 à plusieurs centaines	Nombre de points soumis. Il doit être cohérent avec le paramètre pts, et permet de s’assurer de l’intégrité de la transmission.
mode	driving, walking ou trucking	Mode de transport : voiture, vélo ou piéton. Les distances s’en trouvent modifiées pour utiliser les voies adaptées à chacun de ces modes.
unit	m ou s	Choix de l’unité de travail pour optimiser la distance parcourue en mètres, ou le temps de parcours en secondes.
tour	open ou closed	Choix d’un itinéraire en boucle ouverte sans retour au point de départ ou en boucle fermée avec retour au point de départ.
key*	chaine-de-caracteres	Clé d’authentification de chaque utilisateur.

En ce qui concerne le moyen de transport (mode), de nombreux tests ont été effectués pour les trajets voiture, et moins pour le vélo ou piéton.

L’unité de travail (unit) conseillée est m.

Le type de parcours (tour) modifie profondément l’interprétation qui doit être faite des résultats. Dans le premier cas de boucle fermée, le résultat ne possède pas véritablement de point de départ, et la boucle peut être parcourue dans le sens voulu. Dans le second cas de boucle ouverte, le point de départ est le premier point fourni à l’API tandis que le point d’arrivée est le dernier point fourni à l’API ; l’ordre du résultat doit être considéré en l’état.

Avec le paramètre tour « closed », les résultats de l’API peuvent être présentés dans n’importe quel sens. C’est ce qui explique que vous pouvez trouver une différence entre ce mode et le mode « open » dans lequel vous auriez figé le point de départ identique au point d’arrivé : le sens de parcours de la boucle peut être inversé.

Un exemple concret

Prenons l’exemple simpliste d’un trajet de quatre points dont on souhaite calculer l’ordre de passage optimisé.

Point	Adresse postale	Coordonnée lat,lon
A	135 rue Saint-Leu, 80000, Amiens	49.8998757,2.300284
B	1 rue Marcel Cuny-Cronne, 54039, Baccarat	48.4510104,6.7483327
C	37 rue Bronzac, 94230, Cachan	48.7830011,2.333158
D	1 Boulevard Maréchal Foch, 76200, Dieppe	49.929876,1.078363

Les adresses postales ont préalablement été transformées en coordonnées latitude,longitude grâce à notre API de géocodage. Voici à quoi ressemble la requête formulée pour l’API d’optimisation. Notez qu’une clé d’authentification valide est requise.

 

Le traitement des résultats de l’API d’optimisation

Données de sortie

Le format de données de sortie est un objet json qui peut être téléchargé et traité par une application, ou encore visualisé par un navigateur. La compression liée au protocole HTTP est gérée par le client HTTP de manière transparente pour le développeur. Voici ci-après le tableau des paramètres de sortie.

Paramètre	Explication
DIMENSION	Dimension du problème, chiffre identique au paramètre d’entrée nb.
TOUR	Identique au paramètre d’entrée, et affiché à titre de rappel.
COMPUTE_TIME	Temps de calcul pur en secondes.
TOTAL_TIME	Temps de traitement des données et de calcul en secondes.
OPTIMIZATION	Ordre de passage optimisé des points en utilisant les indexes de la requête initiale.
STEPS_DURATIONS	Temps de parcours par étape (en secondes).
STEPS_DISTANCES	Distance parcourue par étape (en mètres.

Voici l’objet json tel qu’il est renvoyé par l’API.

Conseils d’utilisation

Lorsque vous traitez cet objet json, vous devez impérativement récupérer les valeurs grâce à leur chaîne associée, et non pas par leur position dans le document ou leur numéro de ligne. En effet, d’autres données sont susceptibles de s’intercaler à l’avenir et c’est le seul moyen de respecter la compatibilité. Vous pouvez sans risque transformer l’objet json en tableau de votre langage de programmation avec une librairie spécialisée, à la condition de conserver les chaînes et les valeurs. Pour plus d’informations sur json, consultez le site json.org qui fournit une liste complète de librairies de décodage dans différents langages.

Il faut bien prendre en compte les conseils relatifs à l’interprétation des données selon le paramètre tour utilisé. Dans ce cas de figure précis, le parcours est une boucle et donc on peut le prendre dans le sens voulu, et à partir du point voulu. Par défaut, le premier point de la boucle est le premier point de la requête.

Lors du calcul d’une optimisation de trajet, les lieux de départ et d’arrivée peuvent être des entrepôts, le siège social, le domicile, un hôtel, etc. Il est important d’inclure ces points dans l’optimisation, et pas seulement les points de rendez-vous.

Pour ce calcul très simpliste de quatre points, on remarque que l’ordre optimisé est identique à l’ordre de la requête. Il en serait autrement pour un calcul de 40 points.

Pour les calcul comportant de nombreux points (plusieurs dizaines), on peut constater une certaine variabilité du résultat en multipliant les requêtes. Cela est tout à fait normal car notre algorithme de résolution est initialisé par une variable aléatoire. Vous devez cependant constater que ces résultats ont des longueurs totales proches à plus de 95%. Si vous souhaitez avoir l’absolue certitude de détenir l’optimisation la meilleure possible au kilomètre près, il vous est possible de relancer un calcul plusieurs fois et de prendre le meilleur résultat.

Les codes d’erreur

Il peut arriver que le calcul échoue à cause d’une erreur de requête ou d’une erreur interne de nos serveurs. Voici le type de code qui peut être affiché.

Le tableau ci-dessous décrit la signification des différents codes que vous pouvez rencontrer en utilisant notre API. Toute sortie qui ne contient pas les données de résolution avec la clé « OPTIMIZATION » est à considérer comme une erreur. Les messages d’erreur ci-dessous peuvent évoluer et c’est pourquoi il vaut mieux tester la présence de la clé « OPTIMIZATION » pour déceler une erreur.

Code	Explication
SYNTAX_ERROR	La requête est incoplète ou comporte une erreur.
INVALID_LATLON	Les coordonnées latitude,longitude ne sont pas des décimaux entre 1 et 10 décimales.
WRONG_KEY	Votre clé d’authentification est fausse. Contactez-nous.
NB_IS_INCONSISTENT	Le paramètre nb est faux.
LIMIT_REACHED	Vous avez épuisé vos quotas. En savoir plus.

Les codes ci-dessous sont particulièrment rares, mais il peut être utile d’en prendre connaissance.

Code	Explication
BINARY_NOT_FOUND	Le système de résolution est absent, obsolète ou corrompu. Contactez-nous.
INTMAXDATA_TOO_BIG	Les distances entre les points sont trop grandes, supérieures à la distance Paris-Pékin. Peut signifier une erreur de géocodage sur le mauvais continent.
PRESET_UNKNOWN	Erreur de configuration du système. Contactez-nous.
RESOLVER_HAS_FAILED	La résolution a échouée après normalisation de la matrice. Contactez-nous.
RESULTS_NOT_FOUND	Le problème est insoluble. Contactez-nous.
DISTANCES_TIMEOUT / REQUEST_DENIED	Problème interne sur le composant de calcul de distances. Contactez-nous.
DISTANCES_ERROR	Problème interne sur le composant de calcul de distances. Contactez-nous.
MAX_DIMENSION_REACHED	La formule souscrite ne permet pas d’optimiser un itinéraire avec autant de points.
QUOTA_REACHED	La formule souscrite ne permet pas d’optimiser autant d’itinéraires par jour.
LOW_CREDIT	Le solde du compte client est inférieur au coût de l’opération.

Développements à venir

• D’autres paramètres facultatifs sont susceptibles de voir le jour pour affiner le calcul.
• La méthode GET du protocole HTTP limite la taille des requêtes à 8 Ko, soit environ 200 coordonnées en une seule optimisation. Cette limite sera dépassée à l’avenir par l’utilisation facultative de la méthode POST.