Hoe kunnen we bewijzen dat Quintiqs optimalisatie technologie op nummer één staat?

We hebben een aantal van de moeilijkste optimalisatievraagstukken opgelost. Onze meest recente overwinningen:

Vehicle Routing probleem met tijdvensters

Wat is het probleem?
Het VRPTW is een van de meest bestudeerde problemen op het gebied van combinatorische optimalisatie. Het is een variant van het Vehicle Routing Problem (VRP), dat in 1959 voor het eerst werd gedefinieerd door Dantzig & Ramser. Een oplossing voor het VRPTW is een reeks routes bestaande uit een volgorde van bezoeken aan klanten, waarbij elke route aan een voertuig is toegewezen en alle klanten worden bezocht binnen hun tijdsramen. Het totale volume dat aan elke route wordt toegewezen, mag de capaciteit van het voertuig niet overstijgen. De uitdaging is een oplossing te vinden die de reisafstand en het het totaal aantal voertuigen minimaliseert.

Het VRPTW is al sinds de jaren 70 van de vorige eeuw een aandachtspunt voor wetenschappers. Honderden papers zijn gepubliceerd over de methoden om tot een oplossing te komen. Om een eerlijke vergelijking te kunnen maken tussen deze uiteenlopende methoden hebben wetenschappers als Gehring & Homberger en Solomon benchmarkreeksen vastgesteld die het mogelijk maken de resultaten met elkaar te vergelijken, ongeacht de toegepaste methode.

Er zijn verschillende erkende variaties op de benchmarks van Solomon en Gehring & Homberger. Gehring & Homberger kent verschillende versies, elk met een aantal klanten variërend van 200 tot 1000. Ook andere waarden, zoals orderspecificaties en afstanden, variëren afhankelijk van de versie van het probleem. We kozen de 1000-klanten-benchmark (de grootste en daarmee de moeilijkste om op te lossen), omdat die qua schaal het dichtst in de buurt komt van de werkelijke planningsproblemen van onze klanten.

Het heeft de volgende kenmerken:
  • U hebt een centraal depot en een vast klantenbestand.
  • Elke klant vereist levering van een gespecificeerde hoeveelheid binnen een specifiek tijdsraam, dit varieert van klant tot klant.
  • De afstanden tussen de klanten en het depot zijn bekend. Voor elk van deze ritten is een reistijd bekend.
  • U hebt een reeks voertuigen met elk een maximumcapaciteit.
  • Het is niet mogelijk een order te verdelen over meerdere voertuigen.

Het wereldrecord verbreken

Quintiq werkte eerst aan Gehring & Hombergers 1000-klanten-benchmark, versie C1_10_4, en heeft sindsdien ook veel andere versies opgelost. We hebben gekozen voor de 1000-klanten benchmark. Deze is het grootste en daarom een gecompliceerd groep om op te lossen, omdat dit het meest nauwkeurig is in vergelijking met real-life planning problemen van onze klanten.

Hier zijn een aantal van onze laatste en meest indrukwekkende successen:

Voormalig wereldrecord Quintiq’s wereldrecord
Datum Record Number of routes Total distance Number of routes Total distance
Jul 26, 2016Vehicle Routing Problem with Time Windows, RC1_10_109043896.789043865.86
Jul 24, 2016Vehicle Routing Problem with Time Windows, RC1_10_19046272.079046270.17
Jul 24, 2016Vehicle Routing Problem with Time Windows, RC1_10_29044129.429044098.92
Jul 24, 2016Vehicle Routing Problem with Time Windows, RC1_10_59045564.819045540.07
Jul 24, 2016Vehicle Routing Problem with Time Windows, RC1_10_69045303.679045290.05
Jul 24, 2016Vehicle Routing Problem with Time Windows, RC1_10_89044366.019044299.25
Jul 24, 2016Vehicle Routing Problem with Time Windows, RC1_10_99044280.849044240.32
Jul 11, 2016Vehicle Routing Problem with Time Windows, C2_6_9177958.26177941.57
Jul 07, 2016Vehicle Routing Problem with Time Windows, C2_6_8177547.67177539.73
Jul 07, 2016Vehicle Routing Problem with Time Windows, C2_10_102815944.722815943.34
Jul 05, 2016Vehicle Routing Problem with Time Windows, C2_8_1023109812310977.36
Jul 04, 2016Vehicle Routing Problem with Time Windows, C2_8_92311645.222311605.35
Jul 01, 2016Vehicle Routing Problem with Time Windows, C1_8_27227058.997226752.87
Jun 22, 2016Vehicle Routing Problem with Time Windows, RC1_4_1368576.97368573.96
Jun 22, 2016Vehicle Routing Problem with Time Windows, RC1_4_2367905.66367898.97
Jun 22, 2016Vehicle Routing Problem with Time Windows, RC1_4_3367540.59367537.47
Jun 22, 2016Vehicle Routing Problem with Time Windows, RC1_4_4367310.35367308.55
Jun 22, 2016Vehicle Routing Problem with Time Windows, RC1_4_5368185.21368182.04
Jun 22, 2016Vehicle Routing Problem with Time Windows, RC1_4_10367609.21367601.2
Jun 22, 2016Vehicle Routing Problem with Time Windows, R1_10_59151830.369151792.49
Jun 22, 2016Vehicle Routing Problem with Time Windows, R1_10_69147849.059147764.96
Jun 22, 2016Vehicle Routing Problem with Time Windows, R1_10_99150490.499150288.99
Jun 01, 2016Vehicle Routing Problem with Time Windows, R1_4_2368926.7368923.5
Jun 01, 2016Vehicle Routing Problem with Time Windows, R1_4_5369242.43369226.21
Jun 01, 2016Vehicle Routing Problem with Time Windows, R1_4_6368373.71368372.91
Jun 01, 2016Vehicle Routing Problem with Time Windows, R1_4_9368719.19368717.26
Jan 13, 2016Vehicle Routing Problem with Time Windows, R1_4_10368113.93368107.82
Jan 13, 2016Vehicle Routing Problem with Time Windows, R1_10_39145237.299145235.85
Dec 31, 2015Vehicle Routing Problem with Time Windows, R1_10_69147849.059147832.22
Dec 31, 2015Vehicle Routing Problem with Time Windows, RC1_6_65516632.035516630.25
Dec 31, 2015Vehicle Routing Problem with Time Windows, RC1_6_55516693.265516662.35
Dec 31, 2015Vehicle Routing Problem with Time Windows, RC1_6_85515978.75515963.37
Dec 31, 2015Vehicle Routing Problem with Time Windows, RC1_4_9367752.77367751.63
Dec 31, 2015Vehicle Routing Problem with Time Windows, RC1_6_105515740.265515719.46
Dec 31, 2015Vehicle Routing Problem with Time Windows, RC1_6_25516044.935515980.93
Dec 31, 2015Vehicle Routing Problem with Time Windows, RC1_8_17231710.687231601.57
Dec 31, 2015Vehicle Routing Problem with Time Windows, RC1_8_77229862.447229783.63
Nov 25, 2015Vehicle Routing Problem with Time Windows, C1_8_77726492.647726486.14
Nov 23, 2015Vehicle Routing Problem with Time Windows, C1_10_29042278.459042247.05
Nov 18, 2015Vehicle Routing Problem with Time Windows, C1_10_109039933.069039923.41
Nov 18, 2015Vehicle Routing Problem with Time Windows, C1_8_27227189.167227138.28
Nov 18, 2015Vehicle Routing Problem with Time Windows, C1_6_65916345.445915905.66
Nov 18, 2015Vehicle Routing Problem with Time Windows, C1_10_99040570.69040546.6
Nov 18, 2015Vehicle Routing Problem with Time Windows, R1_4_3367821.95367819.09
Sep 17, 2015Vehicle Routing Problem with Time Windows, C1_10_39040239.239040101.36
Sep 04, 2015Vehicle Routing Problem with Time Windows, C1_8_107224090.17224070.17
Jul 06, 2015Vehicle Routing Problem with Time Windows, RC1_4_7367957.64367953.49
Jun 30, 2015Vehicle Routing Problem with Time Windows, RC1_4_6368177.8368177.46
Jun 29, 2015Vehicle Routing Problem with Time Windows, R1_4_8367275.13367263.07
May 27, 2015Vehicle Routing Problem with Time Windows, C1_8_37224278.187224257.32
May 25, 2015Vehicle Routing Problem with Time Windows, RC1_6_95515922.65515891.18
May 07, 2015Vehicle Routing Problem with Time Windows, C1_4_9367043.74367043.37
May 06, 2015Vehicle Routing Problem with Time Windows, R1_4_7367641.22367619.04
Apr 13, 2015Vehicle Routing Problem with Time Windows, RC1_6_75516145.645516105.68
Apr 13, 2015Vehicle Routing Problem with Time Windows, C1_10_39040239.239040187.99
Mar 18, 2015Vehicle Routing Problem with Time Windows, C2_6_4176911.35176909.58
Mar 18, 2015Vehicle Routing Problem with Time Windows, C2_8_82311292.12311288.01
Mar 09, 2015Vehicle Routing Problem with Time Windows, C2_8_62313150.632312551.09
Feb 17, 2015Vehicle Routing Problem with Time Windows, C2_8_62313150.632312728.62
Jan 16, 2015Vehicle Routing Problem with Time Windows, C1_10_39040239.239040207.71
Dec 12, 2014Vehicle Routing Problem with Time Windows, C1_10_39040239.239040221.66
Nov 28, 2014Vehicle Routing Problem with Time Windows, RC1_6_15517118.75517031.33
Nov 28, 2014Vehicle Routing Problem with Time Windows, RC1_6_35515273.985515236.75
Nov 18, 2014Vehicle Routing Problem with Time Windows, RC1_6_45514839.615514811.21
Nov 10, 2014Vehicle Routing Problem with Time Windows, R1_6_75416615.135416611.86
Nov 10, 2014Vehicle Routing Problem with Time Windows, R1_6_85415696.585415650.58
Oct 28, 2014Vehicle Routing Problem with Time Windows, R1_6_45415819.625415801.04
Oct 28, 2014Vehicle Routing Problem with Time Windows, C1_8_47223841.117223824.17
Oct 28, 2014Vehicle Routing Problem with Time Windows, C1_8_97224389.57224342.07
Oct 09, 2014Vehicle Routing Problem with Time Windows, C1_8_87425293.097326684.02
Sep 15, 2014Vehicle Routing Problem with Time Windows, C1_8_97224389.57224349.32
Sep 15, 2014Vehicle Routing Problem with Time Windows, C1_8_67928665.577927202.7
Sep 05, 2014Vehicle Routing Problem with Time Windows, C1_10_69944108.349943830.21
Aug 22, 2014Vehicle Routing Problem with Time Windows, C1_8_87425293.097425250.78
Aug 21, 2014Vehicle Routing Problem with Time Windows, C1_10_79744806.739743453.92
Jul 28, 2014Vehicle Routing Problem with Time Windows, C1_8_37224278.187224267.08
Jun 24, 2014Vehicle Routing Problem with Time Windows, C1_6_85614429.485614422.48
May 16, 2014Vehicle Routing Problem with Time Windows, C1_6_65916345.445916039.29
Apr 14, 2014Vehicle Routing Problem with Time Windows, C1_6_75814816.555715927.17
Apr 11, 2014Vehicle Routing Problem with Time Windows, C1_10_79744806.739743772.66
Sep 13, 2013Vehicle Routing Problem with Time Windows, C1_6_45613563.175613558.93
Jul 08, 2013Vehicle Routing Problem with Time Windows, C1_8_47223840.327223827.02
Apr 01, 2013Vehicle Routing Problem with Time Windows, C1_10_49039641.469039468.6
Bekijk alles

Ontdek op welke wijze het optimalisatieteam het VRPTW heeft opgelost
SINTEF is een onafhankelijk onderzoeksbureau dat de beste bekende oplossingen voor de Solomon en Gehring & Homberger-versies bijhoudt. Wereldrecords worden door SINTEF geverifieerd en vastgelegd in hun Transportation Optimization Portal.

Quintiq blijft tijd, mensen en middelen investeren in het verbreken van wereldrecords op het gebied van optimalisatie. We verwachten in de nabije toekomst meer goed nieuws te kunnen melden. Houd deze pagina in de gaten!