業界ナンバー・ワンのQuintiq最適化テクノロジー

我々が更新した最適化世界記録でご確認ください。最新の事例をご紹介します。

時間枠付き配車計画問題(VRPTW)

この課題について
時間制約のある配車計画問題(VRPTW)は、組み合わせ最適化の分野で最もよく研究されている問題のひとつであり、1959年にダンツィグ/ラムゼー両氏によって初めて定義された配車計画問題(VRP)の変形です。VRPTWの解は、全顧客への訪問で構成される配送経路です。1車両につき1経路が割り当てられ、全顧客地点への訪問を時間枠内で行います。各経路に割り当てられる積載量の合計は、車両の容量以下とします。ここでは、車両台数と走行距離を最小限に抑える解を見つけることが課題となります。

VRPTWは、1970年代以降、科学界で注目を集めており、これまでに、その解法に関する数百件の論文が公開されています。これらの様々な解法を公正に比較する取り組みとして、ゲーリング/オムバーガーやソロモンをはじめとした科学者たちは、採用する手法にとらわれずに結果を比較できるようにするための一連のベンチマークを定義しています。

これら3氏のベンチマークにはいくつかのバリエーションがあり、ゲーリング/オムバーガー両氏のベンチマークには、顧客数がそれぞれ200から1,000の範囲で異なる複数の事例があります。また、注文仕様や距離などのその他の値も、問題の事例に応じて異なります。

VRPTWの各事例の特徴は以下のとおりです。
  • 中央の配送センター1拠点と特定の顧客数
  • 指定された時間枠内に配送する必要のある貨物の量が顧客単位で定められており、この値は顧客によって異なる
  • 顧客と配送センター間の距離とその移動時間が指定されている
  • 決まった数の車両が与えられ、車両ごとに最大容量が指定されている
  • 1つの注文を複数の車両に分散させることはできない

Quintiqの世界記録

Quintiqは当初、ゲーリング/オムバーガーの顧客数1,000のベンチマーク(インスタンスC1_10_4)を採用し、それ以来、様々な事例を解決しています。最大規模ゆえに最も難解な顧客数1,000のベンチマークを選んだのは、当社のお客様が実際に直面している計画問題に規模が最も近いためです。 

以下にQuintiqの最近の更新記録の一例をご紹介します。

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

Quintiqの最適化チームによるVRPTWへの取り組みをご覧ください - すべて表示
SINTEFは、ソロモンおよびゲーリング/オムバーガーの各インスタンスに対する既知の最良解を追跡調査している独立系調査組織です。世界記録は、SINTEFによって検証され、同社の輸送最適化ポータルに掲載されています

Quintiqでは、最適化分野で世界記録更新に取り組んでおり、近い将来最新ニュースをお届けできると考えています。