マルチエージェントの協調・交渉による動的最適化と合意形成～物流輸配送計画最適化への挑戦～
沖電気工業株式会社 経営基盤本部
研究開発センター AI 技術研究開発部
樋田 愛
OKI は昨年 12 月、NEC・豊田通商らと共に、内閣府総合科学技術・イノベーション会議による「戦略的イノベーション創造プログラム（SIP）第 2 期」の NEDO 公募事業に採択された。
現在、「AI 間連携によるバリューチェーンの効率化・柔軟化」をテーマとし、異なる個別システム内で動作する複数の AI 同士が、自動で協調・連携・交渉して働くための基盤技術の開発に取り組んでいる。OKI は特に物流業界の課題に着目し、複数事業者の協調によって高効率な輸配送を実現する輸配送計画調整技術、マルチエージェント自動交渉技術などの AI技術開発を行っている。

物流業界における課題
物流業界では近年、貨物の小口多頻度化が進んでいる。国土交通省によると、1 回の運送で運ばれる貨物の平均重量が 1990 年の 2.43 トンから減少を続ける一方、特に 0.1 トン未満の貨物の輸送件数は、割合・件数ともに大きく増加している [国土交通省, 2017]。道路貨物運送事業においては、労働力不足も顕著である。全日本トラック協会によると、労働力が不足している・やや不足していると回答した企業が全体の 70.4%を占めた [全日本トラック協会, 2019] 。特にトラックドライバーは全産業平均以上のベースで高齢化が進んでおり、将来的に更なる労働力不足が懸念されている。
このような背景を受け、物流業界では、限られたリソースでより多くの貨物を運ぶ高効率輸送の実現が喫緊の課題となっている。例えば、大手ビール会社数社は、各社の物流拠点を相互利用して、同じトラックや鉄道コンテナで商品を輸送する共同配送を一部地域で既に開始している。また、後続車両に無人運転システムを搭載したトラック隊列走行についても、公道での実証実験が始まった。これらの対策は、予め運行計画が決まっている定時・定ルート便の輸配送効率向上に寄与する。一方、BtoB の輸配送に多くみられる非定時・非定ルート便は、運行直前に都度輸配送計画を立案する必要があるため、上記のような手法を直接当てはめることは難しい。

輸配送計画の従来方式とその課題(非定時・非定ルートの)輸配送効率向上のためには、高積載率を達成する輸配送計画の立案が効果的である。国土交通省の自動車輸送統計調査によると、平成 30 年度の営業車平均積載率（＝輸送トンキロ／能力トンキロ）は 40%を下回っており [国土交通省, 2019]、改善の余地は大きい。従来の輸配送計画立案方式で積載率を担保できない理由は、主に 3点あると考えている。
1 点目は、計画立案のリソース不足である。非定期・非定ルート便の場合、物流事業者は運行前日などに輸送依頼の申し込みを締め切るため、限られた時間で計画を立案せざるを得ない。一方で、多くの企業では配車マンと呼ばれる専門家が経験と勘に従って計画を立てるため、時間の不足が計画精度に及ぼす影響は大きいと考えられる。
2 点目は、輸送条件の制約である。貨物輸送には、集配日時・場所の他にも、積み方、温度帯、輸送付帯業務の有無など、混載可能性に制約がある場合がある。このような制約下
では、自社の受けた依頼の割り振りのみで、十分な積載率を確保することは難しい。
3 点目は、輸送条件調整の柔軟性の低さである。計画立案段階で、物流需要家に対して輸送条件の変更を依頼することで、混載可能な貨物量を調整し、積載効率を向上させる方法も考えられる。しかし、電話等を介した人対人の交渉は非効率であるため、事業者側からの輸送条件変更や輸送辞退は通常行われない。従って、一部の繁忙期を除いては、このような調整が行われることは少ない。
上記より、個社・人力で立案する輸配送計画の積載率向上には限界がある。従って、課題解決のためには、AI 技術などを用いた業界横断的な計画最適化が必要であると考えた。

提案概要
これまでの輸配送計画は各物流事業者内で個別に立案されてきたが、我々は、複数事業者横断で輸配送計画を最適化するための方式を提案する。ここで紹介するのは、物流需要家、物流事業者、運送事業者などの AI エージェントが参加する電子的なマーケットを構築し、AI エージェント同士の協調・交渉を手助けすることにより、輸配送計画を最適化する方式である。本方式では、主に下記の 3 処理を行う。
1． 輸配送計画マージによる新計画提案：提携構造形成問題を適用して複数事業者横断で既存計画の調整を行い、数理計画法などを用いて新しい輸配送計画を生成する。この際、輸送依頼者の求める輸送条件が一部満たされないことも許す。
2． 自動交渉による合意形成：1 で提案した新計画から抽出された交渉論点について、計画に関係する各プレーヤと自動交渉を行い、合意または不合意の結論を出す。
3． 制約条件の変更と再調整：2 の交渉で合意に至らない場合、交渉内容などを元に制約条件の変更を行い、1 の方法で再調整・提案を行う。
上記の処理を通じて計画の提案、交渉、フィードバックを繰り返すことにより、全ての関係者と合意を結べる範囲で、最も望ましい計画を採用することができると考えている。
このようなマーケットにおいては、参加者がマーケットから離脱する誘因を作らないことも重要になる。計画の調整によって発生した余剰分の輸送コストは、計画変更のインセンティブとして各関係者に配分される。この配分額は交渉により決定される。また、メカニズムデザインの観点から、協調に協力的な参加者の優遇、悪意のある参加者の排除、計画変更による負担の長期的平準化などの仕組みを取り入れることで、各参加者が win-winとなる健全なマーケットの実現を目指している。

輸配送計画マージによる新計画提案
我々の提案するマーケットには、輸配送計画調整の主催者として、メディエータというAI が配置される。メディエータは、既存の輸配送計画を複数事業者横断に調整し、新計画を立案する役割を持つ。メディエータが参照できる輸配送計画情報は、各物流事業者の AIエージェントがマーケットへ送信したものに限られる。
我々は積載率向上のアイディアとして、輸配送計画のマージに着目した。輸配送計画のマージとは、同じトラックで運ぶことのできる条件を満たした複数の計画を、1 つの輸配送計画にまとめることである。メディエータの解く“効率的な輸配送のために、どの計画同士をマージするべきか”という問題は、協力ゲーム理論における提携構造形成問題（CSG）として定式化した。
メディエータは、CSG を解いてマージの構造を求めた後、再受注者の選定と各貨物の集配日時の決定を行う。複数拠点を巡回しての輸配送が必要な場合、貨物の集配日時は混載される他貨物の集配日時・場所と依存関係にある。従って、巡回する拠点の位置関係を考慮して巡回順序を決定する必要がある。ここでは、元々の計画における集配日時・場所情報と経路情報サービスから得られる拠点間所要時間情報を利用して、時間制約付き巡回セールスマン問題を解くことにより、巡回順序と集配日時を決定する。
CSG・巡回セールスマン問題は共に組み合わせ最適化問題であるため、問題の規模が大きくなると、その組み合わせ数と探索時間は爆発的に増加する。従って、現実的な時間で厳密解を求解することは難しく、効率的な近似アルゴリズムを求められる。我々はこれらの求解に、数理計画法パッケージ“Numerical Optimizer”を利用することにした。

マルチエージェント自動交渉による合意形成
調整済みの新しい輸配送計画を採用・履行するためには、その計画の全関係者から、計画変更の同意を得る必要がある。この関係者には、調整前の各計画を生成した輸送受注者（物流事業者）、輸送受注者から依頼を受けトラックを運行させる輸送請負者（運送事業者）、計画に含まれる各貨物の輸送依頼者（物流需要家）、配送先である荷受け者などが含まれる。
特に輸送受注者には、マージした計画を再受注する者と、マージされることにより受注が取り消される者が存在するため、特に後者との合意には何らかのインセンティブが必要となる。また、一部計画の輸送条件変更を許してより利得の大きい最適提携構造・巡回ルートを得た場合、変更に該当する計画の関係者はインセンティブを強く欲すると考えられる。
上記の関係者と合意形成を行うため、我々の手法では、マルチエージェントによる自動交渉技術を利用する。人手による交渉と比べ、時間あたりに可能な提案回数が桁違いに多い上、効用関数に従って合理的な提案を行えるというメリットがある。

マーケットに参加する各関係者は、マーケットプレイスの交渉プラットフォーム上に、自らの効用関数と交渉戦略を反映した交渉エージェントと呼ばれる AI を置く。また、マーケットの効用関数と交渉戦略を反映した交渉エージェントであるネゴシエータも、同プラットフォーム上に配置される。ネゴシエータは各交渉エージェントに対し、前述の新計画から生成した論点とインセンティブ額について並列自動交渉・合意形成を行う。
このようなマルチエージェント自動交渉のプラットフォームの実装には、“S 4 シミュレーションシステム”を利用することにした。

まとめ
本稿では、高効率輸送を実現する 1 手法として、複数事業者横断の輸配送計画調整、自動交渉による合意形成を備えた最適化方式を紹介した。本方式をベースに開発する物流マーケットは、同プログラム内で 2022 年までの社会実装を目指している。

謝辞
本研究は、内閣府総合科学技術・イノベーション会議の「SIP/ビッグデータ・AI を活用したサイバー空間基盤技術」（管理法人：NEDO）によって実施されました。

引用文献
Lewis, M., Yarats, D., Dauphin, Y. N., Parikh, D., & Batra, D. (2017). Deal or No Deal?

End-to-End Learning for Negotiation Dialogues.
伊藤孝行. (2014). マルチエージェントの自動交渉モデルとその応用. 情報処理 Vol.55
横尾真, 岩崎敦, 櫻井祐子, 岡本吉央. (2013). 『計算機科学者のためのゲーム理論入門』シ
リーズ第５回

協力ゲーム.

岡田章. (2011). ゲーム理論〔新版〕.

原祐輔. (2015). オークション理論とメカニズムデザイン.
国土交通省. (2017). 物流を取り巻く現状について. 参照先:
http://www.mlit.go.jp/common/001173035.pdf
国土交通省. (2019). 平成 30 年度自動車輸送の概要. 参照先:
https://www.e-stat.go.jp/stat-search/files?page=1&layout=datalist&toukei=0060
0330&kikan=00600&tstat=000001078083&cycle=8&year=20181&month=0&sta
t_infid=000031852401&result_back=1&result_page=1&tclass1val=0
坂井豊貴, 藤中裕二, 若山琢磨. (2008). メカニズムデザイン

資源配分制度の設計とインセンティブ.
全日本トラック協会. (2019). トラック運送業界の景況感. 参照先:
http://www.jta.or.jp/chosa/keikyo/keikyo.html