(57)【要約】【課題】One to One最適化キャンペーン実施の鍵となる、One to One最適化問題向けの高速・効率的な、新規な求解方法及び装置、並びにその基礎となるモデル構築方法及び装置を提供する。【解決手段】（１）営業コストを削減することを目的とする営業コスト最小化目的関数、（２）企業収益を拡大することを目的とする企業収益最大化目的関数、（３）既存顧客を維持しながら、新規顧客を開拓することを目的とする顧客開拓最大化目的関数、（４）上記三つの目的関数を組合せすることによる多目的関数のいずれかを目的関数として考慮し、One to Oneマーケティングの最適化を図る。【選択図】図１
2006331390.tif 000002
【特許請求の範囲】
【請求項１】
大規模One to Oneマーケティング最適化モデルの構築方法であって、下記（１）〜（４）のいずれかを目的関数として考慮し、One to Oneマーケティングの最適化を図ることを特徴とする、大規模One to Oneマーケティング最適化モデルの構築方法
（１）営業コストを削減することを目的とする営業コスト最小化目的関数
（２）企業収益を拡大することを目的とする企業収益最大化目的関数
（３）既存顧客を維持しながら、新規顧客を開拓することを目的とする顧客開拓最大化目的関数
（４）上記三つの目的関数を組合せすることによる多目的関数。
【請求項２】
請求項１に記載の大規模One to Oneマーケティング最適化モデルの構築方法であって、下記（１）〜（６）の少なくとも１つの制約条件の下に、One to Oneマーケティングの最適化を図ることを特徴とする、大規模One to Oneマーケティング最適化モデルの構築方法
（１）キャンペーン活動のコスト支出に関わるコスト制約
（２）供給できる商品の在庫数による製品在庫制約
（３）ある顧客に対して使用できるコンタクトチャンネルによるチャンネル制約
（４）ある顧客が受入希望のOfferによるOffer制約
（５）顧客から製品注文に関する注文制約
（６）ある顧客に対して、製品のOfferを一種類しか利用しない単一Offer制約。
【請求項３】
2006331390.tif 000039
【請求項４】
2006331390.tif 000040
【請求項５】
2006331390.tif 000041
【請求項６】
2006331390.tif 000042
【請求項７】
2006331390.tif 000043
【請求項８】
2006331390.tif 000044
【請求項９】
上記（３）ある顧客に対して使用できるコンタクトチャンネルによるチャンネル制約条件が、
2006331390.tif 000045
なる関係式で表されることを特徴とする、請求項２〜８のいずれか一に記載の大規模One to Oneマーケティング最適化モデルの構築方法。
【請求項１０】
2006331390.tif 000046
【請求項１１】
2006331390.tif 000047
【請求項１２】
2006331390.tif 000048
【請求項１３】
2006331390.tif 000049
【請求項１４】
請求項１〜１３のいずれか一に記載の大規模One to Oneマーケティング最適化モデルの構築方法を実施するための装置であって、
大規模One to Oneマーケティング最適化のモデル作成及び処理に必要な入力データ及び計算結果を蓄積するためのデータベースと、
モデルデータを標準MPS線形計画記述フォーマットに変換するためのMPSデータ出力インターフェースと、
ユーザからキャンペン目的及びキャンペン制約を選択できるインターフェースと、
ユーザのキャンペンデータベースにある企業セールス情報に基づいてデータマイニングのための最適化モデル構築モジュールと、
を具えることを特徴とする、大規模One to Oneマーケティング最適化モデルの構築装置。
【請求項１５】
請求項１〜１３のいずれか一に記載の大規模One to Oneマーケティング最適化モデルの構築方法に基づいた、大規模One to Oneマーケティング最適化の求解方法であって、線形計画アルゴリズムに基づいて、大規模One to Oneマーケティング最適化を求解することを特徴とする、大規模One to Oneマーケティング最適化の求解方法。
【請求項１６】
2006331390.tif 000050
【請求項１７】
請求項１〜１３のいずれか一に記載の大規模One to Oneマーケティング最適化モデルの構築方法に基づいた、大規模One to Oneマーケティング最適化の求解方法であって、Mehrotra予測−修正方法により予処理し、予処理後の大規模One to Oneマーケティング最適化問題の双対問題に対してKKT条件の下に求解することを特徴とする、大規模One to Oneマーケティング最適化の求解方法。
【請求項１８】
請求項１〜１３のいずれか一に記載の大規模One to Oneマーケティング最適化モデルの構築方法に基づいた、大規模One to Oneマーケティング最適化の求解方法であって、
LDL分解技術を用い、LDL分解技術を構造予測と数値計算との二つの部分に分けて、大規模One to Oneマーケティング最適化問題を求解することを特徴とする、大規模One to Oneマーケティング最適化の求解方法。
【請求項１９】
請求項１〜１３のいずれか一に記載の大規模One to Oneマーケティング最適化モデルの構築方法に基づいた、大規模One to Oneマーケティング最適化の求解方法であって、
後ろ向き追跡法を用いて大規模One to Oneマーケティング最適化問題を求解することを特徴とする、大規模One to Oneマーケティング最適化の求解方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分析型CRMマーケティング向け最適キャンペーンを実施するための目的関数と制約条件の構築とを含んだ最適モデルの構築、および構築した最適化モデルに対して線形計画法を用いた求解方法の発明に関する。
【背景技術】
【０００２】
One To Oneマーケティング最適化技術は分析型CRMの鍵となる技術の一つである。前記One To Oneマーケティング最適化技術は、企業がOne to Oneマーケティングの実施の一環として最適キャンペーンを展開する場合に、どのような顧客にどのようなofferを提供すれば、顧客のロイヤリティを高められ、企業の持続可能な成長と高い利益率を維持できるかの補助ツールとして機能する。
【０００３】
現状としては、国内外のCRMベンダーが分析型用のOne to Oneマーケティング最適化を研究開発しているが、実際にはまだ初期段階であって十分実用に供することができるようなレベルではない。従来のOne To Oneマーケティング最適化技術においては、双方向情報交換による顧客レスポンスの集計技術、データマイニング技術、企業の履歴データの分析による顧客選好度把握技術などを用いており、それらの技術の総合適用により商業ルールベース推理方法に基づく企業と顧客とのコミュニケーションの内容、コミュニケーションチャンネル、コミュニケーション頻度の効率化を実現している。
【０００４】
このような商業ルール推理方法はOne to Oneマーケティングの効率化をある程度実現できるが、商業ルール推理の人間の主観的な介入と、情報の膨大さが原因で、大規模なOne to Oneマーケティングの最適化に対しては適用の限界があり、真の意味でのOne to Oneマーケティング最適化の実現が困難である。
【０００５】
One to Oneマーケティング最適化問題に関して、数理計画の目的関数と制約条件によりその特徴を記述すれば、数理計画の枠組みで解くことが可能であり、企業のOne to One最適キャンペーンの客観的な策定と最適キャンペーンの実施による企業利益の最大化に資することができる。
【０００６】
実際問題の非線形性と大規模性、目的関数の多様性と制約条件の複雑性等の要因により、非線形モデルの代わりにモデルの構築と大規模系統への求解が可能である線形計画法での記述が適切である。
【０００７】
数十種類の製品、数種のチャンネル、数十万の既存および潜在顧客を有する企業に対して、One to Oneマーケティング最適化キャンペンモデルの変数と制約条件の数はそれぞれ108及び106程度になる。Simplex法、DSF法など一般的な線形計画方法では大量の計算時間とメモリが必要になり、現在のPC環境では実用時間内に解を得ることが不可能になる。したがって、One to One最適化問題向けの高速・効率的な求解方法の開発がOne to One最適化キャンペーン実施の鍵となる技術になる。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、One to One最適化キャンペーン実施の鍵となる、One to One最適化問題向けの高速・効率的な、新規な求解方法及び装置、並びにその基礎となるモデル構築方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
大規模One To Oneマーケティング最適化問題に対して、線形計画モデルにより記述し、利益最大化、コスト最小化、獲得顧客数最大化のキャンペーン目的に応じて目的関数を作成し、所定の制約条件を作成することにより、目的の最適化モデルを構築する。
【００１０】
本発明においては、上述したようなキャンペーン目的を考慮すると、以下に示すような目的関数を設定することができる。
（１）営業コストを削減することを目的とする営業コスト最小化目的関数
（２）企業収益を拡大することを目的とする企業収益最大化目的関数
（３）既存顧客を維持しながら、新規顧客を開拓することを目的とする顧客開拓最大化目的関数
（４）上記三つの目的関数を組合せすることによる多目的関数
【００１１】
また、上述したキャンペーン目的及び目的関数を考慮すると、以下に示すようなキャンペーン制約条件を設定することができる。
（１）キャンペン活動のコスト支出に関わるコスト制約
（２）供給できる商品の在庫数による製品在庫制約
（３）ある顧客に対して使用できるコンタクトチャンネルによるチャンネル制約
（４）ある顧客が受入希望のOfferによるOffer制約
（５）顧客から製品注文に関する注文制約
（６）ある顧客に対して、製品のOfferを一種類しか利用しない単一Offer制約
【００１２】
そして、ユーザは、そのキャンペーン目的に応じて、例えば上述した目的関数及びキャンペーン制約条件を考慮し、その制約の下で大規模One To Oneマーケティング最適化のモデルを作成する。
【００１３】
この場合において、モデル構築装置のデータ取得部分が、二種類の方法で対応することができる。一つはユーザがSQL Serverに蓄積してある企業情報データを基に、商業規則に基づいて自動的に最適化モデルを構築する。もう一つはMPSフォーマットから直接取得して自動的に最適化モデルを構築する。なお、本装置がMPSフォーマット対応のデータ入力・出力インターフェースを用意し、SQL ServerのデータをMPSフォーマットに変換する機能を有する。
【００１４】
また、本発明は、大規模One to Oneマーケティングにおけるキャンペーン最適化数理計画モデルの目的関数、制約条件を作成し、そのモデルを構築する装置を提供する。
【００１５】
大規模One to Oneマーケティング最適化の目的関数と制約条件の記述により、本発明がOne to Oneマーケティング最適化用のモデル自動作成装置を以下のように設計する。
（１）最適化モデルモジュール
（２）One to Oneマーケティング最適化用データベース
（３）MPSデータ出力インターフェース
（４）ユーザ選択入力インターフェース
【００１６】
本装置がモジュール化し、ユーザが選択した目的関数と制約条件によりSQL Serverの中に蓄積した企業情報を取得しOne to Oneマーケティング最適化モデルを自動作成し、最適化計算結果を保存する。
【００１７】
さらに、本発明は、上述のようにして構築したモデルに基づいた、One to Oneマーケティング最適キャンペーンの解を求める効率的な方法とその実装装置を提供する。
【００１８】
前記求解方法は、以下の項目を含む。
（１）One to Oneマーケティング最適キャンペン問題を線形計画問題に変換する前処理技術
（２）Mehrotra予測−修正子技術により前予処理後の大規模One to Oneマーケティング最適キャンペン問題に対して求解する。
（３）後退追跡法により求解のための最適ステップパラメータを求める。
（４）LDL分解方法によりマトリックス線形方程式問題を処理する。
（５）列近似最小オーダ順序付け技術によりLDL分解中のfill-inを削減する。
【００１９】
前記求解装置は、以下の項目を含む。
（１）大規模One to Oneマーケティング最適化キャンペンモデルの計算モジュールの設計。
（２）メモリプール管理リストによりメモリの配分のリリースを管理する。
（３）最適計算モジュール部分がDLL技術を採用する。
（４）マルチスレッド技術により計算パフォーマンスの最適化する。
（５）MPS、LPフォーマットのインターフェース設計により、標準線形計画モデルのデータフォーマットをサポートする。
【発明の効果】
【００２０】
以上説明したように、本発明によれば、One to One最適化キャンペーン実施の鍵となる、One to One最適化問題向けの高速・効率的な、新規な求解方法及び装置、並びにその基礎となるモデル構築方法及び装置を提供することができる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の詳細、並びにその他の特徴及び利点について、最良の形態に基づいて詳細に説明する。
【００２２】
2006331390.tif 000003
【００２３】
2006331390.tif 000004
【００２４】
2006331390.tif 000005
【００２５】
2006331390.tif 000006
【００２６】
2006331390.tif 000007
【００２７】
2006331390.tif 000008
【００２８】
2006331390.tif 000009
【００２９】
2006331390.tif 000010
【００３０】
以下、One to Oneマーケティング最適化モデルにおいて、上述した目的関数は、企業のOne to Oneマーケティング活動を通じて到達したい目的を反映する。問題記述の的確性と最適解を求めることの可能性を配慮し、目的関数の記述が次のような点を考慮する。
【００３１】
（１）最初に、上述した目的関数（１）における営業コスト最小化目的関数においては、Offerのコスト（商品コストとOfferに関わるコストなど）を目的関数の中に反映する。
（２）また、上述した目的関数（２）における企業収益最大化目的関数においては、各顧客が企業にもたらす利益を目的関数の中に反映する。
（３）さらに、上述した目的関数（３）における顧客開拓最大化目的関数においては、既存顧客を維持しながら新規顧客をできるだけ開拓することを目的関数の中に反映する。
【００３２】
2006331390.tif 000011
【００３３】
2006331390.tif 000012
【００３４】
2006331390.tif 000013
【００３５】
以上の分析により、One to Oneマーケティング最適化の目的関数は、以下のようにまとめることができる。
【００３６】
2006331390.tif 000014
【００３７】
One to Oneマーケティング最適化に関しては、主としては以下に示す２種類の制約条件を考慮する必要がある。第１には、顧客からOfferへの受入制約である。この場合、各顧客からの受入Offerの制約と特殊顧客から受入Offerの制約との両方を含む。第２には、Offerに関する制約、具体的には、主に提供できるOffer数量の制約、費用の制約、利益制約および適応性制約を含む。
【００３８】
2006331390.tif 000015
【００３９】
2006331390.tif 000016
【００４０】
2006331390.tif 000017
【００４１】
2006331390.tif 000018
【００４２】
2006331390.tif 000019
【００４３】
次に、Offerの適応性制約、例えば在庫数による製品在庫制約などによって、主に各顧客にどのようなOfferが提供でき、どのようなOfferが提供できないかの制約である。すなわち、
2006331390.tif 000020
それにより、次の制約条件が得られる。
2006331390.tif 000021
【００４４】
2006331390.tif 000022
【００４５】
また、Offer適応性制約について、もう一つ考慮すべきことは同じ顧客に対して同じ製品に関する複数のOfferを提供することを避けることである。以下のように表させる。
2006331390.tif 000023
【００４６】
One to Oneマーケティング最適化問題の目的関数と制約条件の詳細記述を以下の式（２３）でまとめる。
2006331390.tif 000024
【００４７】
以下では一つの簡単な例により上記One to Oneマーケティング最適化モデルの構築について説明する。
【００４８】
2006331390.tif 000025
【００４９】
2006331390.tif 000026
【００５０】
2006331390.tif 000027
【００５１】
次に、図１〜３を参照して、One to Oneマーケティング最適化の自動モデル作成の具体的な実施方法について述べる。
【００５２】
最初に、One to Oneマーケティング最適化の自動モデル作成のために構造化モジュール設計を行う。この際、データの完全性と安全性とを保つために各モジュールの内部データに対してカプセル化を行う。各モジュール間のデータの転送及びアクセスをデータ入力インターフェース及びデータ出力インターフェースにより実現し、操作の便利性と各モジュールのデータの変化が他のモジュール影響を与えないことを図る。
【００５３】
図１が本発明装置のワークフロー図である。異なる最適化目的と制約された条件により、ユーザが異なる顧客制約、製品制約、チャンネル制約を選択し、最適化モデルを構築する。製品制約とチャンネル制約に対して、選択により簡単に対応できるが、顧客制約に対しては、連続顧客と非連続顧客の選択により分類する。非連続IDの顧客に対しては、また顧客の属性（信誉度、グレード）により再選択する。モデルを作成後、装置によりモデル関連の情報をデータベース内のModelテーブルに保存し、直接に作成するモデルと関連するデータ情報が可視フォーマットによりデータベース内に保存する。
【００５４】
本発明装置のデータベースは、以下の7個の情報テーブルを含む。
顧客テーブル
製品テーブル
チャンネルテーブル
注文テーブル
モデルテーブル
キャンペン方策テーブル
最適解テーブル
【００５５】
装置の情報モデルを図２に示す。各データテーブルの間に矢印付き直線でそれらのリレーションを現す。直線上の数値が二つのデータテーブルの間の関連の度合いを表す。各テーブルの中にpk（Primer Key）と注釈してあるのは優先キー、fk（Foreign Key）と注釈してあるのは従属キーである。
【００５６】
装置のデータ流れ図を図３に示す。企業のセールス営業情報８（顧客情報、チャンネル情報、製品情報など）が予めセールスデータベース９の中に保存され、３つのキャンペーン目的（関数）と６つの制約条件をユーザのOne to Oneマーケティング最適化策定の選択へ提供する。モデルデータはMPSデータ出力インターフェースで標準MPS線形計画記述フォーマットに変換され、ファイルされる。また、ユーザからキャンペン目的及びキャンペーン制約はインターフェイスにおいて選択できるように構成されている。さらに、ユーザのキャンペーンデータベースにある企業セールス情報に基づいてデータマイニングし、最適化モデルを構築するための最適化モデル構築モジュールが設けられている。
【００５７】
One to Oneマーケティング最適化モデル装置はSQL Server 2000をデータベースバックオフィスとする。データベースへのI/O操作がADOデータアクセス訪問応用プログラムのインターフェースによって実現する。データへのアクセスとデータの表示の速度が、大規模One to Oneマーケティング最適化問題のデータベース規模の膨大さにより遅くなる。この問題を解決する為に、本装置は設計の時にデータのページ分離技術を採用する。
【００５８】
本装置の上記ページ分離技術の設計原理に基づいて、データテーブル内の全記録を違うページに分け、プログラムが毎回一つのデータページ内のすべての記録を訪問する。本装置がインターフェース上に、ユーザが柔軟的に違うページのデータ記録を訪問・サーチするためには、以下の処置を行なう。
【００５９】
記録集を開く→総記録数を計算する→サブページを確定する→記録集ポイント位置を確定する→指定したページの記録を検索する。本装置が各サブページの記録が100レコードとし、データアクセス速度と１サブページの示す情報量の間のバランスを取る。
【００６０】
本大規模One to Oneマーケティング最適化のモデルの作成方法とモデルの変換が自動的にOne to Oneマーケティング最適化モデルを作成することができる。本最適化モデルがOne to Oneマーケティングの商業目的と規則に従い、できるだけ正確に問題を記述する。なお、作成した最適化モデルが線形計画により記述することにより、線形計画方法での求解が可能となり、企業の営業活動の最適化に資する。
【００６１】
次に、図４と関連させて、本発明の具体的な実施方法の詳細について説明する。本例では、One to Oneマーケティング最適化問題を線形計画問題に変換する予処理技術の実施詳細について示す。
【００６２】
2006331390.tif 000028
【００６３】
本発明でOne to Oneマーケティング最適化問題求解のために採用したMehritra予測−修正法の実装詳細を以下に示す。
【００６４】
2006331390.tif 000029
【００６５】
2006331390.tif 000030
【００６６】
2006331390.tif 000031
【００６７】
2006331390.tif 000032
【００６８】
2006331390.tif 000033
【００６９】
2006331390.tif 000034
【００７０】
2006331390.tif 000035
【００７１】
2006331390.tif 000036
【００７２】
2006331390.tif 000037
【００７３】
実施の詳細を以下に示す。
LDL分解手順を構造予測と数値計算の二つの部分に分ける。消去枝理論を用いて、予めLの非ゼロ要素構造を確定し、この構造にある非ゼロ要素の値を計算する。それにより余分なメモリと数値計算時間を削減し、少ないメモリで高速に大規模疎行列の因子分解を処理する。
【００７４】
2006331390.tif 000038
【００７５】
以上、具体例を挙げながら発明の実施の形態に基づいて本発明を詳細に説明してきたが、本発明は上記内容に限定されるものではなく、本発明の範疇を逸脱しない限りにおいてあらゆる変形や変更が可能である。
【図面の簡単な説明】
【００７６】
【図１】本発明のOne to Oneマーケティング最適化の自動モデル作成におけるフローチャートを示す図である。
【図２】本発明のOne to Oneマーケティング最適化の自動モデル構築装置のデータベース情報図である。
【図３】本発明のOne to Oneマーケティング最適化の自動モデル構築装置のデータ流れ図である。
【図４】本発明のOne to Oneマーケティング最適化問題を線形計画問題に変換する予処理技術に関するデータ流れ図である。
【図１】
2006331390.tif 000051
【図２】
2006331390.tif 000052
【図３】
2006331390.tif 000053
【図４】
2006331390.tif 000054