[1H4-GS-1c] 基礎・理論：アルゴリズム

[1H4-GS-1c-03] 解集合プログラミングを用いた多目的車両装備仕様問題の解法

〇竹内 頼人¹、田村 直之²、番原 睦則¹ (1. 名古屋大学、2. 神戸大学)

キーワード：解集合プログラミング、多目的最適化、車両装備仕様問題、CAFE方式、可変性モデル

車両装備仕様とは，簡単に言うと，自動車のカタログに記載されているモデル/グレードと装備の組合せのことである．多目的車両装備仕様問題は，与えられたモデル/グレードの個数，装備タイプの集合，装備オプションの集合などから，装備および燃費に関する制約を満たしつつ，予想販売台数の最大化や装備オプション数の最小化など，トレードオフの関係にある複数の目的関数のもとで最適な車両装備仕様を求める問題である．本発表では，CAFE 方式と呼ばれる燃費制約に基づく多目的車両装備仕様問題(多目的 CAFE 問題)に対して，解集合プログラミングを用いてパレート最適解を列挙する方法について述べる．提案手法は，可変性モデルで表現された問題インスタンスを ASP のファクト形式に変換した後，それらファクトと多目的CAFE 問題を解くための ASP 符号化と結合し，高速 ASP システムを用いて解を求める．企業から提供されたベンチマーク問題を用いた実行実験の結果，小規模な問題についてパレート最適解を全列挙することができた．