Comment prouver que la technologie d’optimisation Quintiq est la plus performante ?

Nous avons résolu quelques-uns des défis d'optimisation les plus complexes au monde. Voici nos dernières victoires :

Le problème de tournées de véhicules avec fenêtre de temps

Quel est l'enjeu ?
Communément appelé VRPTW, ce problème d'optimisation combinatoire est l'un des plus étudiés. Il s'agit d'une variante du problème de tournées de véhicules initialement défini par Dantzig et Ramser en 1959. L'une des solutions possibles à ce problème est la création d'une série de tournées correspondant chacune à une livraison. Chaque tournée est attribuée à un véhicule et chaque client est livré dans la fenêtre de temps exigée. Le volume total assigné à chaque tournée ne doit pas dépasser la capacité du véhicule. Le défi consiste à trouver une solution qui permette de réduire le nombre de véhicules utilisés et la distance totale parcourue.

La communauté scientifique s'intéresse au problème VRPTW de tournées de véhicules avec fenêtre de temps depuis les années 1970. Des centaines d'articles proposant des solutions au problème ont été publiés depuis. Des scientifiques comme Gehring & Homberger ou encore Solomon ont défini un ensemble de références permettant de comparer de manière équitable les divers résultats, quelle que soit la méthode utilisée.

Il existe plusieurs versions reconnues des références Solomon et Gehring & Homberger. Gehring et Homberger ont établi plusieurs références, dont chacune implique un nombre de clients allant de 200 à 1 000. D'autres valeurs, telles que les caractéristiques des commandes et les distances, varient également d'une référence à l'autre.

Les caractéristiques communes aux différentes variantes du problème sont les suivantes :
  • Vous disposez d'un dépôt central et d'un portefeuille de clients à livrer.
  • Chaque client exige que lui soit livré un volume spécifique dans une certaine fenêtre de temps. Ces contraintes varient d'un client à l'autre.
  • Les distances séparant les clients du dépôt sont définies. Pour chacun de ces voyages, un temps de trajet est spécifié.
  • Vous disposez d'un groupe de véhicules, chacun présentant une capacité maximale.
  • Une commande ne peut être répartie entre plusieurs véhicules.

Quintiq bat des records

Quintiq s'est d'abord attelé à la résolution du problème de référence Gehring & Homberger pour 1 000 clients - le cas C1_10_4 -, et a résolu depuis de nombreuses autres references. Quintiq a ciblé la référence pour 1 000 clients, c'est à dire la plus complexe, parce qu'elle se rapproche le plus des difficultés de planification rencontrées par les entreprises logistiques à grande échelle.

Voici nos dernières victoires :

Précédent record du monde Quintiq nouveau record
Date Record Number of routes Record précédent Number of routes Record précédent
26 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_10_109043896.789043865.86
24 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_10_19046272.079046270.17
24 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_10_29044129.429044098.92
24 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_10_59045564.819045540.07
24 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_10_69045303.679045290.05
24 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_10_89044366.019044299.25
24 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_10_99044280.849044240.32
11 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, C2_6_9177958.26177941.57
07 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, C2_6_8177547.67177539.73
07 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, C2_10_102815944.722815943.34
05 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, C2_8_1023109812310977.36
04 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, C2_8_92311645.222311605.35
01 Juillet, 2016Problème de tournées de véhicules avec fenêtre de temps, C1_8_27227058.997226752.87
22 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_4_1368576.97368573.96
22 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_4_2367905.66367898.97
22 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_4_3367540.59367537.47
22 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_4_4367310.35367308.55
22 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_4_5368185.21368182.04
22 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, RC1_4_10367609.21367601.2
22 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, R1_10_59151830.369151792.49
22 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, R1_10_69147849.059147764.96
22 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, R1_10_99150490.499150288.99
01 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, R1_4_2368926.7368923.5
01 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, R1_4_5369242.43369226.21
01 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, R1_4_6368373.71368372.91
01 Juin, 2016Problème de tournées de véhicules avec fenêtre de temps, R1_4_9368719.19368717.26
13 Janvier, 2016Problème de tournées de véhicules avec fenêtre de temps, R1_4_10368113.93368107.82
13 Janvier, 2016Problème de tournées de véhicules avec fenêtre de temps, R1_10_39145237.299145235.85
31 Décembre, 2015Problème de tournées de véhicules avec fenêtre de temps, R1_10_69147849.059147832.22
31 Décembre, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_6_65516632.035516630.25
31 Décembre, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_6_55516693.265516662.35
31 Décembre, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_6_85515978.75515963.37
31 Décembre, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_4_9367752.77367751.63
31 Décembre, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_6_105515740.265515719.46
31 Décembre, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_6_25516044.935515980.93
31 Décembre, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_8_17231710.687231601.57
31 Décembre, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_8_77229862.447229783.63
25 Novembre, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_8_77726492.647726486.14
23 Novembre, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_10_29042278.459042247.05
18 Novembre, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_10_109039933.069039923.41
18 Novembre, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_8_27227189.167227138.28
18 Novembre, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_6_65916345.445915905.66
18 Novembre, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_10_99040570.69040546.6
18 Novembre, 2015Problème de tournées de véhicules avec fenêtre de temps, R1_4_3367821.95367819.09
17 Septembre, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_10_39040239.239040101.36
04 Septembre, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_8_107224090.17224070.17
06 Juillet, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_4_7367957.64367953.49
30 Juin, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_4_6368177.8368177.46
29 Juin, 2015Problème de tournées de véhicules avec fenêtre de temps, R1_4_8367275.13367263.07
27 Mai, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_8_37224278.187224257.32
25 Mai, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_6_95515922.65515891.18
07 Mai, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_4_9367043.74367043.37
06 Mai, 2015Problème de tournées de véhicules avec fenêtre de temps, R1_4_7367641.22367619.04
13 Avril, 2015Problème de tournées de véhicules avec fenêtre de temps, RC1_6_75516145.645516105.68
13 Avril, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_10_39040239.239040187.99
18 Mars, 2015Problème de tournées de véhicules avec fenêtre de temps, C2_6_4176911.35176909.58
18 Mars, 2015Problème de tournées de véhicules avec fenêtre de temps, C2_8_82311292.12311288.01
09 Mars, 2015Problème de tournées de véhicules avec fenêtre de temps, C2_8_62313150.632312551.09
17 Février, 2015Problème de tournées de véhicules avec fenêtre de temps, C2_8_62313150.632312728.62
16 Janvier, 2015Problème de tournées de véhicules avec fenêtre de temps, C1_10_39040239.239040207.71
12 Décembre, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_10_39040239.239040221.66
28 Novembre, 2014Problème de tournées de véhicules avec fenêtre de temps, RC1_6_15517118.75517031.33
28 Novembre, 2014Problème de tournées de véhicules avec fenêtre de temps, RC1_6_35515273.985515236.75
18 Novembre, 2014Problème de tournées de véhicules avec fenêtre de temps, RC1_6_45514839.615514811.21
10 Novembre, 2014Problème de tournées de véhicules avec fenêtre de temps, R1_6_75416615.135416611.86
10 Novembre, 2014Problème de tournées de véhicules avec fenêtre de temps, R1_6_85415696.585415650.58
28 Octobre, 2014Problème de tournées de véhicules avec fenêtre de temps, R1_6_45415819.625415801.04
28 Octobre, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_8_47223841.117223824.17
28 Octobre, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_8_97224389.57224342.07
09 Octobre, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_8_87425293.097326684.02
15 Septembre, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_8_97224389.57224349.32
15 Septembre, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_8_67928665.577927202.7
05 Septembre, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_10_69944108.349943830.21
22 Août, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_8_87425293.097425250.78
21 Août, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_10_79744806.739743453.92
28 Juillet, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_8_37224278.187224267.08
24 Juin, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_6_85614429.485614422.48
16 Mai, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_6_65916345.445916039.29
14 Avril, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_6_75814816.555715927.17
11 Avril, 2014Problème de tournées de véhicules avec fenêtre de temps, C1_10_79744806.739743772.66
13 Septembre, 2013Problème de tournées de véhicules avec fenêtre de temps, C1_6_45613563.175613558.93
08 Juillet, 2013Problème de tournées de véhicules avec fenêtre de temps, C1_8_47223840.327223827.02
01 Avril, 2013Problème de tournées de véhicules avec fenêtre de temps, C1_10_49039641.469039468.6
Tout voir

Découvrez comment notre équipe Optimisation a résolu le problème de tournées de véhicules avec fenêtre de temps (VRPTW)
SINTEF est un organisme de recherche indépendant qui référence les solutions les plus connues apportées aux problèmes de référence Solomon et Gehring & Homberger. Les records du monde sont vérifiés et publiés par SINTEF sur son portail Web dédié aux solutions d'optimisation des transports.

Quintiq consacre continuellement du temps et des ressources aux problèmes d'optimisation, avec l'objectif de battre de nouveaux records du monde. Sans doute remporterons-nous prochainement d'autres victoires. Consultez régulièrement cette page !