Comment utiliser l'API VRPTW?

Interface de programmation (API) VRPTW

Vehicle Routing Problem With Time Windows (VRPTW)

Le problème de routage de véhicules avec fenêtre de temps est caractérisé par le nombre de combinaisons possibles. 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 dépasse 10, soit 10! (3628800) possibilités. Afin de mieux nous outiller envers ce problème, nous avons conçu le premier API de type VRPTW.

Nous ne vous pistons pas

Lorsque l’interface de programmation (API) est utilisée, 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 doivent être préalablement calculés. Ainsi vous 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]]"

Configuration des paramètres

key

Cette valeur est requise seulement si vous dépassez 500 emplacements.

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.

Interprétation de la réponse

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 sans optimistaion

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]]"
Le nombre de route dépasse le nombre de véhicules disponbile dans la requête.



Priorisation (facultatif)

La configuration des premiers emplacements à visiter impacte la solution.

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

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

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

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

Publication de la preuve de concept, ajout des tests pour l'assurance qualité 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éliorations sur les trajets.

25 mai 2017: version 0.1.0

Développement et implémentation de la solution.

2 février 2017: version 0.0.1

Conception et design préliminaire.

Code source

Un code d'example d'utilisation de l'API est disponible:

Une suggestion?

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 l'éventuel correction du bug en question.

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

Envoyer un message

Contraintes

Si le nombre d'emplacements à résoudre est supérieur à 500, contactez-nous.

2021-05-11: 11/05/2021