Documentation

VRPTW et anonymat

Vehicle Routing Problems With Time Windows

Le problème de routage de véhicules avec fenêtre de temps se démarque principalement par le nombre de combinaisons possible. En effet, pour vérifier toutes les combinaisons de routes, la complexité algorithmique est O(n!). Dans le contexte routier, il est fréquent que le nombre d'endroits total à visiter pour la même entreprise dépasse 10, soit 10! (3628800) possibilités. Après d'innombrables recherches en 2017, aucun service sous forme d'API n’était disponible. Afin de mieux nous outiller envers ce problème, nous avons conçu le premier API de type VRPTW.

Nous ne vous suivons pas

Lorsque l'API est utilisé à des fins de réseaux routiers, nous ne pouvons pas déterminer les emplacements correspondants. En effet, les informations des adresses ne sont pas nécessaires, car les coûts des liens sont préalablement calculés. L'API demende le moins d'information possible pour que vous puissiez conservez votre anonymat.

Example d'utilisation

URL

POST https://www.algorithmesolutions.com/routing

Header: Content-Type application/json

Requête: raw


{
"key":"98C10D89-9FE2-4AE9-A9BE-F149ECE8AD97",
"distanceMatrix":[
[0, 531, 495, 3081,2974,961],
[531, 0, 1104,3521,3408,1222],
[495, 1104,0, 3040,2856,876],
[3081,3521,3040,0, 2847,3147],
[2974,3408,2856,2847,0, 3059],
[961, 1222,876, 3147,3059,0]
],
"weight":[0,7200,10800,28800,12600,10800],
"firstToVisit":[3,4],
"capacity":37800,
"available":4
}


Réponse

"[[4,1],[5,2],[3]]"

Détection des cas connus

Bien comprendre la réponse consitue la première étape de l'analyse paramétrique. En effet, la réponse de la requête dévoile beacuoup d'information sur les paramètres utilisés.

Aller-retour simple

Supposons que la capacité est moindre que celle requise pour visiter les emplacements, alors tous les emplacements seront visités par des aller-retour sans visiter d'autre point.

{
...
"capacity":2,
...
}

Réponse

"[[1],[2],[3],[4],[5]]"
Indice: le nombre de route dépasse le nombre de véhicules disponbile dans la requête.



Aller-retour avec et sans priorisation

La configuration des premiers emplacements à visiter impacte le nombre de véhicules nécessaires.

{
...
"firstToVisit":[3,4],
...
}

Réponse: "[[4],[5,1],[3],[2]]"
{
...
"firstToVisit":[],
...
}

Réponse: "[[2,5],[1,4],[3]]"

Configuration des paramètres

key

Cette valeur est la clé d'API fournis lors de votre adhésion.

distanceMatrix

Cette matrice résume les distances de chacun des emplacements 'i' (rangée) vers chacun des emplacements 'j' (colonne). Il est important de retenir que l'index 0 (première rangée et première colonnne) représente le dépôt. Selon l'example, soit "D" la matrice carré des distances:

0 531 495 30812974961
531 0 1104352134081222
495 11040 30402856876
3081352130400 28473147
29743408285628470 3059
961 1222876 314730590

Note: dans le contexte de réseaux routier, il existe des API qui calcul cette matrice pour vous. En autre, Google Maps Distance Matrix API est un moyen efficace d'obtenir cette matrice.


$$ D_{ij} = \begin{bmatrix} 0 & D_{1,2} & D_{1,3} & ... & D_{1,n-1} & D_{1,n} \\ 0 & 0 & D_{2,3} & ... & D_{2,n-1} & D_{2,n} \\ 0 & 0 & 0 & ... & D_{3,n-1} & D_{3,n} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & ... & 0 & D_{n-1,n} \\ 0 & 0 & 0 & ... & 0 & 0 \\ \end{bmatrix} D_{ij} = \left\{ \begin{array}{ll} 0\ \ si\ \ i=j \\ D_{ij} = D_{ji}\\ (i = 0) = {à\ partir\ du\ dépôt} \\ (j = 0) = vers\ le\ dépôt \\ (i \neq0) = à\ partir\ de\ l'emplacement \\ (j \neq0) = vers\ l'emplacement \\ \end{array} \right.\\ $$

En considérant que le trajet parcouru entre 'i' et 'j’ est approximativement le même qu’entre 'j’ et 'i' (aller = retour), on peut donc utiliser la réflexion matricielle:

$$ D'_{ij} = \begin{bmatrix} 0 & D_{1,2} & D_{1,3} & ... & D_{1,n-1} & D_{1,n} \\ D_{1,2} & 0 & D_{2,3} & ... & D_{2,n-1} & D_{2,n} \\ D_{1,3} & D_{2,3} & 0 & ... & D_{3,n-1} & D_{3,n} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ D_{1,n-1} & D_{2,n-1} & D_{3,n-1} & ... & 0 & D_{n-1,n} \\ D_{1,n} & D_{2,n} & D_{3,n} & ... & D_{n-1,n} & 0 \\ \end{bmatrix} $$

weight

Tableau des coûts pour chacun des emplacements.

$$ E_j = \begin{bmatrix} E_{Depot} & E_{Cons._1} & E_{Cons._2} & ... & E_{Cons.n-1} & E_{Cons.n} \end{bmatrix} $$

firstToVisit (facultatif)

Tableau d'entiers supérieurs à 1 correspondants aux emplacements qui doivent être visités en premier. Par exemple: pour l'emplacement 3 (index 3) et l'emplacement 4 (index 4) on obtient:

$$ C_{f} = \begin{bmatrix} 3, 4 \end{bmatrix} $$

capacity

Valeur entière positive du nombre de véhicules disponibles.

Code source

Le répertoire public suivant est une ébauche pour tester l'API.

Version actuel: 1.1.1

28 mai 2018: version 1.1.1

Renvoi d'erreurs lorsqu'un paramètre est mal utilisé.

30 mars 2018: version 1.1.0

Obtention visuel de la preuve de concept, passage des tests et correctifs mineurs.

4 décembre 2017: version 1.0.0

Mise en ligne de la version stable.

27 juillet 2017: version 0.1.1

Amélioration généralisée sur les trajets calculés.

25 mai 2017: version 0.1.0

Développement et implémentation à haut niveau de la résolution.

2 février 2017: version 0.0.1

Conception et élaboration d'un outil d'optimisation algorithmique.

Communication

Bug

Comme tous les logiciels, cet outil peut comporter des bugs. Si vous détectez un problème concernant l'utilisation, vous pouvez nous en faire part en communicant avec nous par courriel. Le cas échéant, un suivi vous sera envoyé pour vous aviser des démarches entreprises et de la correction du bug en question.

Commentaire

Vos commentaires sont les bienvenus et nous les apprécions tous. En nous faisant part de vos commentaires, vous contribuez à une meilleure optimisation et divulgation de ce produit.

Suggestion

Avec ce genre d'algorithme, il est difficile de considérer tous les facteurs. Toute suggestion provenant des utilisateurs est prise au sérieux.

Envoyer un message

Contraintes

Le nombre d'emplacements maximal à résoudre est 500. Si cette limite n'est pas suffisante pour vos utilisations, prenez contact avec nous.