퀸틱의 최적화 기술이 단연 업계 최고라는 것을 어떻게 입증할 수 있을까요?

퀸틱은 세계에서 가장 까다로운 여러 최적화 과제를 해결했습니다. 최근 수립한 기록은 다음과 같습니다.

시간 제약이 있는 차량 경로 문제에 대한 신기록 수립

문제 개요
VRPTW는 연산 최적화 분야에서 가장 많은 연구가 이루어지고 있는 문제 중 하나입니다. 이는 1959년 Dantzig & Ramser가 처음 정의한 차량 경로 문제(VRP)의 변형입니다. VRPTW에 대한 해답은 고객들을 방문하는 순서로 구성된 일련의 경로로서 각 경로가 차량에 지정되면 정해진 시간대 내에 모든 고객을 방문해야 합니다. 각 경로에 지정된 총 운송량은 해당 차량의 운송량을 초과할 수 없습니다. 이 과제는 사용하는 차량의 수와 주행 거리를 최소화하는 해결책을 찾는 것입니다.

VRPTW는 1970년대 이후 과학계의 화두가 되었습니다. 그 해결 방법에 도달하는 방법론에 대한 수많은 논문들이 발표되었습니다. 다양한 방법론 간의 공정한 비교를 위해 Gehring & Homberger 및 Solomon 등과 같은 과학자들이 채용한 방법론에 관계 없이 그 결과를 비교할 수 있는 일련의 벤치마크를 규정했습니다.

Solomon과 Gehring & Homberger 벤치마크에는 여러 인지 변수들이 있습니다. Gehring & Homberger에는 여러 인스턴스가 있으며 이들 각각은 200개에서 1000개까지 다양한 고객의 수가 부여됩니다. 주문 시방서와 거리와 같은 다른 값들은 해당 문제의 인스턴스에 따라 차이가 있습니다.

이는 다음과 같은 특징을 가지고 있습니다.
  • 중앙 차량 기지와 일단의 고객을 보유하고 있습니다.
  • 각 고객은 지정된 시간 내에 지정된 물량을 배송해야 한다고 요구하고 있으며, 이는 각 고객마다 다릅니다.
  • 고객과 차량 기지 간에는 일정한 거리가 있습니다. 이들 각 여정에 소요되는 시간이 주어집니다.
  • 일단의 차량을 보유하고 있으며, 각각은 최대 운송량이 정해져 있습니다.
  • 하나의 주문을 2대 이상의 차량으로 분산시킬 수 없습니다.

퀸틱의 세계 최고 기록

퀸틱은 먼저 Gehring & Homberger's 1000-고객 벤치마크, 인스턴스 C1_10_4에 착수했으며 이후 많은 다른 인스턴스들을 해결했습니다. 퀸틱은 실제 자사 고객들이 당면하고 있는 계획 문제와 가장 근접한 규모라는 점에서 가장 크고, 따라서 해석하기 가장 어려운 1000개 고객사 벤치마크를 선택했습니다.

최근 수립한 기록은 다음과 같습니다.

이전 세계 기록 퀸틱의 세계 최고 기록
일자 기록 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
보기

퀸틱의 최적화 팀이 VRPTW을 해결한 방법을 확인해 보십시오.
퀸틱은 먼저 Gehring & Homberger's 1000-고객 벤치마크, 인스턴스 C1_10_4에 착수했으며 이후 많은 다른 인스턴스들을 해결했습니다.

SINTEF는 Solomon과 Gehring & Homberger 인스턴스에 대한 가장 널리 알려진 해법을 계속해서 기록하고 있는 독립 조사 연구 기관입니다. 세계 최고 기록은 SINTEF의 운송 최적화 포털 (Transportation Optimization Portal)에서 검증 및 기록되고 있습니다.