システム導入

対話型電子見積の核となる組み合わせ最適化技術には、調達におけるベストプラクティスを継続的に織り込まれています。特許取得済みまたは申請中のコンバインネット社の知的財産は、数学やコンピュータサイエンス、アルゴリズム工学における世界で最も優秀な頭脳集団によって、しっかりと支えられています。

サプライヤ選定は、本質的に数学における組み合わせ論の問題であり、サプライヤ選定に関わる意思決定のすべての属性をモデリングすることが極めて重要です。現実の世界で需要と供給の関係を考えるとき、部分々々での取引についての意思決定が全体の取引に影響すること、それぞれの取引が常に変化していることを、私たちは本能的に理解しています。ですので、分かりやすいからという理由だけで、固定の、或いは限定的なモデルに調達の問題を無理やり押し込めようとすると、単に満足する結果が得られないばかりか、多大なコスト低減の機会を失ってしまうという、まったく誤った結果に陥ることになりかねません。対話型電子見積の技術の特徴を一言で述べると、他の技術に比べて、対象となる最適化問題に関してより多くの属性をモデリングできることにあります。「対話型電子見積」のコンセプトを現実のものとしているのは、この分析能力です。対話型電子見積の分析能力に基づき、調達・購買・物流を担当とされる方々は、仕様見積のみならず、サプライヤからの様々な提案を、自社の事業目標、制約やしがらみ、要望に沿う様、際限なく分析し、最適なサプライヤの組み合わせを探し出すことができます。この多様な見積・提案の分析評価は、システムの処理時間が驚くほど短いことから、調達・購買・物流ご担当ご自身によって、迅速かつ容易に行うことができます。最適なサプライヤを見つけるための処理時間は常に向上しており、わずか3年前は実行不可能だと考えられていたような問題であっても、現在では最適なサプライヤの組み合わせを見つけられるようになっています。

対話型電子見積を実現するにあたっての大きな課題は、バイヤとサプライヤとの間で非常に多岐に亘るやり取りがなされるために、見積・提案の評価分析が複雑な組み合わせ最適化の問題になってしまうことでした。この種の市場取引の問題は、組み合わせ最適化では取引問題と呼ばれ、事業上のあらゆる制約を満足させつつ、どの売り手とどの買い手の組み合わせを成立させ、その内どの程度まで部分的にしか受け入れられない組み合わせを容認するか、どの取引を不成立とした方が市場全体の効率が高まるのかといった決定をしなければなりません。線形計画やその他の類似のアプローチでは、こうした調達の問題を解決することはできません。コンバインネット社のテクノロジーが対象としているマーケットメカニズムに基づく取引の問題には、自由な提案を出せる余地が必要です。つまり、対話型電子見積で扱っている取引問題には、莫大な量の売り手と買い手の組み合わせからなる探索空間を形成し、最適化エンジンは、この探索空間を生かせるだけの高い技術を伴っていることが重要です。それには、混合整数計画(MIP: Mixed integer programming)法を用いた木探索が適しており、弊社もこの技術を用いています。ただ、主要な混合整数計画エンジンに含まれている汎用的な混合整数計画法では、対話型電子見積で扱っている様な取引問題に対処するには十分ではありません。また、オークションや線形計画など他のアプローチと比べて、対話型電子見積には「調達という現実の世界の問題を、最も経験豊かな専門家によって妥協なくモデル化し、数秒で解決する」という違いがあります。対話型電子見積が世に出るまでは、対話型電子見積で扱っている規模や自由度で取引問題を処理できる技術はなく、500品目を対象に5,000件の入札を処理できるプログラミング技術がある程度でした。そのような中で、対話型電子見積は、その最適化およびアルゴリズムの技術開発により、処理速度を4から5桁早めることに成功しました。

対話型電子見積の核となる最適化エンジンは、高度に進化した木探索アルゴリズムを用いて、最適と判断される売り手の買い手の組み合わせを探し出します。ここで最適と判断されるという表現を用いているのは、弊社が近似解法というアプローチを用いているからです。組み合わせ最適化では、線形計画と異なり、実際の最適解が簡単に求まることはまずありません。そこで、最適解からの誤差を許容できる範囲に抑えつつ、処理速度を速めるという方法が研究されており、これが近似解法です。アルゴリズムが近似解ではなく実際の最適解を見つけるには、計算複雑性理論で最も難しいクラスに分類されるNP完全の問題であり、最悪の場合、入力情報のサイズによっては、処理時間が多項式時間を超えてしまいます。しかしながら、現実世界の最適化問題の実際を考えると、アルゴリズムは極めて高速で走ります(中央のランタイムは1秒未満であり、平均で20秒。稀に数日を要する異例も存在します)。このアルゴリズムはまた更新型で、最適解を探索している間にも、これまでに見つけた解よりも良いものがあれば、それをその時点での最適解として採用しますので、すべての探索を終えなくとも、いつでのその時点での最適解を回答することができます。

対話型電子見積のアルゴリズムの開発は1997年に始まりました。現在16名がアルゴリズムの開発を担当し、そのうち半数のスタッフがそれにすべての時間を費やしています。この担当チームは、オペレーションズリサーチ、コンピュータサイエンスで議論されてきたものや、コンバインネット社で独自に発明した何百もの技術を、何れが市場取引問題におけるスピード向上に適しているのかを見極めるために、テストしてまいりました。コンバインネット社は、その成果の一部を、探索アルゴリズムの第一世代として詳細に発表しています。これらのアルゴリズムにおける新しい概念には、アイテム分岐、入札分岐、多変数分岐といった組み合わせオークションでの基本的な取引問題のさまざまな処理方法や、動的に分解される要素間の上方/下方結合、各探索ノードにおける分岐選択戦略の動的選択、情報理論的分岐アプローチ、洗練された先読み処理、ソリューション播種、主要な経験則、ノード処理のパターン化と他への適用、領域特化型の処理技術、高速化のためのデータ構造、留保価格の扱い、相対的落札者の決定と見積価格計算処理などが含まれていました。

コンバインネット社はまた、木探索アルゴリズムにおける技術も多数開発し、現在のところそれらは独自仕様としています。それらのアルゴリズムには、市場取引問題に対する異なる処理や、数々の新しい分岐戦略、ユーザ定義による切断平面群、切断平面の生成と選択技術、インスタンス毎にどの処理が効果的かを予測し、動的に処理を選択する機械学習などが含まれています。

組み合わせオークションに関する学術論文は、入札間の相互の除外制約で補完される場合も含めて、パッケージ入札に焦点を置いてきましたが、コンバインネット社や弊社が実際に調達に接してきた経験では、調達における複雑性は、主に、数学的には側面拘束と呼ばれる、取引慣行や購入企業の意向といった様々な制約から生じています。よって、コンバインネット社はこれらの側面拘束に効率的に対処する技術の開発に大きく注力してきました。私たちは、現実の世界で数百種におよぶ側面拘束に直面してきました。それらは、弊社のソフトウェアでは、8つに分類されるアルゴリズムによって、すべて対処されています。このようにして、各アルゴリズムでの処理速度の向上は、そのアルゴリズムが対応するあらゆる側面拘束の処理に自動的に適用されます。

結果として生まれた最適化木探索アルゴリズムは、現実世界の高度な市場取引問題では、最先端の汎用MIPソルバの1万倍の処理速度を有しています。処理速度にこれほどまでに差が生じている主たる理由は、弊社がMIP問題の中でも調達に関わるサブクラスに特化し、そのサブクラスの2万の現実世界に対応したインスタンスのアルゴリズムの改善に注力しているからです。処理速度の向上により、対話型電子見積のお客様企業は、それぞれが複数のユニットから成る168,000品目を対象に250万以上の入札のある調達案件や、30万以上の側面拘束のあるものなど、はるかに大規模で自由度の大きい最適化問題に対処できるようになりました。

対話型電子見積は、このような技術に支えられています。ビジネスの成功にはスピードが不可欠です。対話型電子見積の組み合わせ演算技術を用いれば、貴社の非技術系の調達実務のご担当が、幾つもの見積・提案評価シナリオを何ヶ月と掛けることなく瞬時に分析できるようなります。調達業務のように、検討すべき項目が複雑で複数の利害関係者が関与する場合、組み合わせ最適化によって初めて実現される、複数の見積・評価シナリオの検討が成功の鍵となります。

このページの先頭へ