日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

車両装備仕様問題に対する解集合プログラミングの適用
竹内 頼人

田村 直之

番原 睦則

車両装備仕様とは，簡単に言うと，自動車のカタログに記載されているモデル／グレードと装備の組合せのことである．車両装備仕様問題は，与えられた装備仕様の個数，装備タイプの集合，装備オプションの集合などから，装備および燃費に関する制約を満たしつつ，予想販売台数を最大化する車両装備仕様を求める問題である．本論文では，企業平均燃費 (Corporate Average Fuel Eﬃciency; CAFE) 方式と呼ばれる燃費規制に基づく車両装備仕様問題に対して，解集合プログラミング (Answer Set Programing; ASP) を用いたソルバーの実装と評価について述べる．提案手法は，まず与えられた問題インスタンスを ASP のファクト形式に変換した後，それらファクトと車両装備仕様問題を解くための ASP 符号化と結合した上で，高速 ASP システムを用いて解を求める．ASP 符号化として，基本符号化と改良符号化の 2 種類を考案した．特に，改良符号化は，装備仕様の燃費や予想販売台数を算出するために必要な ASP のルール数を少なく抑えるよう工夫されており，大規模な問題への有効性が期待できる．また，製造ラインの削減や大量生産を促進することを狙いとして，予想販売台数の最大化に加えて，装備オプション数の最小化も行える拡張符号化についても触れる．最後に，提案手法の評価として，企業から提供を受けた実用規模の問題インスタンスを含む問題集を用いた実験結果について述べる．の装備の種類を表す．装備オプションは 4 気筒エンジ

1 はじめにン，CVT などの具体的な装備を表す．車両装備仕様

車両装備仕様とは，簡単に言うと，自動車のカタロ

問題の目的は，与えられた装備仕様の個数，装備タイグに記載されているモデル／グレードと装備の組合プの集合，装備オプションの集合から，装備および燃せのことである．車両装備仕様を決めるには，販売さ費に関する制約を満たしつつ，予想販売台数を最大化れる国や地域の法規や規制，地域や市場の特性，市場する車両装備仕様を求めることである．の嗜好や競合など十分に考慮する必要があり，現状で本研究では，燃費に関する制約として，欧米で採用は専門知識をもつ技術者の多大な労力が費やされてされ日本でも 2020 年度から導入されている企業平均燃いる．そのため，車両装備仕様探索の自動化・効率化

費 (Corporate Average Fuel Eﬃciency; CAFE [5])は自動車メーカーにとって重要な課題の一つである．

方式を用いる．この CAFE 方式は自動車の燃費規制

車両装備仕様問題は組合せ最適化問題の一種であで，車種別ではなくメーカー全体での出荷台数を加り，主に装備タイプと装備オプションから構成され味した平均燃費を算出し，規制をかける方式である．

る．装備タイプはエンジンやトランスミッションなど

CAFE 方式の特長は，ある特定の車種では燃費基準を達成できなくても，他の車種の燃費を向上させるこ

Applying Answer Set Programming to Vehicle Equipment Specification Problem
Raito Takeuchi, Mutsunori Banbara, 名古屋大学 大学院情報学研究科, Graduate School of Informatics,Nagoya University.
Naoyuki Tamura, 神 戸 大 学 情 報 基 盤 セ ン タ ー, Information Science and Technology Center, Kobe
University.とで基準を達成できることが可能な点である．本論文
では，CAFE 方式に基づく車両装備仕様問題 (以降，CAFE 問題と呼ぶ) を対象とする．
解集合プログラミング (Answer Set Programing;

ASP [1] [3] [4]) は，論理プログラミングから派生した宣言的プログラミングパラダイムである．ASP 言語

CAFE 問題
インスタンス-- ASP ファクト - ASP システム -変換器

CAFE 問題の解ASP 符号化(論理プログラム)
図1

提案する CAFE 問題ソルバーの構成は一階論理に基づく知識表現言語の一種である．論理

本論文の貢献は，CAFE 方式と呼ばれる新しい燃プログラムは ASP のルールの有限集合である．ASP

費規制に基づく車両装備仕様問題に対して，解集合プ

システムは論理プログラムから安定モデル意味論 [3]ログラミング技術をはじめて適用し，実用規模の問題に基づく解集合を計算するシステムである．近年，を用いた実験結果を通じて，その有用性を確認したこ

SAT ソルバー技術を応用した高速 ASP システムがとである．

実現され，ロボット工学，システム生物学，システム検証，制約充足問題，プランニングなど様々な分野へ

2 CAFE 問題の実用的応用が急速に拡大している [2]．

CAFE 問題の入力は以下の通りである．以降，装本論文では，ASP を用いた CAFE 問題ソルバー

備タイプをタイプ，装備オプションをオプションと簡の実装と評価について述べる．提案ソルバーは，まず単に書くことにする．

与えられた問題インスタンスを ASP のファクト形式

1. タイプの集合に変換した後，それらファクトと CAFE 問題を解く

2. オプションの集合ための ASP 符号化と結合した上で，高速 ASP シス

3. タイプとオプションの対応関係テムを用いて解を求める (図 1 参照)．

4. 各タイプで選択可能なオプション数の上下限値

ASP 符号化として，基本符号化と改良符号化の 2種類を考案した．基本符号化は，CAFE 問題の制約

5. タイプ同士，オプション同士，および，タイプとオプション間の依存関係を ASP のルール 17 個で簡潔に表現できる．改良符

6. 各オプションに付加された IWR 値

号化は，装備仕様の燃費や予想販売台数を算出するた

7. 求めたい装備仕様の個数めに必要な IWR (Inertial Working Rating) 値の総8. 各装備仕様とタイプ (あるいはオプション) 間の和の上下限を厳密に計算することにより，基礎化後のルール数を少なく抑えるよう工夫されている．これにより，改良符号化は大規模な CAFE 問題への有効性が期待できる．また，製造ラインの削減や大量生産を促進することを狙いとして，予想販売台数の最大化に加えて，装備オプション数の最小化も行える拡張符号化についても触れる．

依存関係

9. 各装備仕様に含まれるオプションの IWR 値の総和と燃費との対応表

10. 各装備仕様に含まれるオプションの IWR 値の総和と予想販売台数との対応表

11. CAFE 基準値
入力 6 の IWR は Inertial Working Rating の略で，提案手法の有効性を評価するために，企業から提供直観的には各オプションの重量を表す．入力 7 の個数を受けた小規模・実用規模・大規模の CAFE 問題には，求めたい派生車両の数と考えるとわかりやすい．

対して実行実験を行った結果，基本符号化と改良符号

CAFE 問題は，上記の入力から，装備および燃費に化はどちらも小規模な問題の最適解を求めることが関する制約を満たしつつ，予想販売台数を最大化するできた．また，実用規模およびより大規模な問題に対車両装備仕様を求める問題である．

しては，改良符号化が基本符号化より優れた結果を示CAFE 問題の制約は以下の通りである．

し，その優位性が確認できた．

範囲制約 : 各装備仕様について，各タイプで選択

VP

VP

Grade

Tire

[1..1]vv

STD= 580[1..1]v

DX= 580v

LX= 580v

15inch= 90v

16inch= 110v

17inch= 130

18inch= 150

requires v vrequires v v
requires v vvv

VP

VPTransmission

Drive Typev

HEV= 115[1..1]
5MT= 48v
v

6AT= 125

6MT= 55v

2WD= 125

4WD= 200

VP

VPEngineSun Roof

[1..1]vv

10AT= 95

[1..1]

CVT= 80v

excludes v vv

V4= 120

図2[1..1]v

V6= 200

Nomal
= 35v

Panorama= 70

CAFE 問題の例

されるオプション数は，入力 4 で与えられた上下限値の範囲内でなければならない．

D!:(Variation Point)ÌæïÄ(Variant)
VVP

依存制約 : 各装備仕様について，入力 5 で与えられた依存関係を満たさなければならない．依存制
約には，要求制約と排他制約の 2 つがある．
燃費制約 : 入力 11 の CAFE 基準値を t，入力 7の装備仕様個数を n として，以下の CAFE 規制を満たさなければならない．

∑nF Ei · SVii=1∑nSVii=1≥t[name][name]!Q(Variability Dependencies)¬R¶(Alternative Choice)optional[min..max]

mandatoryMÿQ(Constraint Dependencies)
requires_V_V

requires_v_v

requires_V_VP requires_v_vp

requires_VP_VP requires_vp_vp

excludes_V_V

excludes_v_v

excludes_V_VP excludes_v_vp

excludes_VP_VP excludes_vp_vp

図3

可変性モデルの表記法 [6]によって記述されている．図 3 に，可変性モデルの基不等式の左辺は n 個の装備仕様の平均燃費を表本的な表記法を示す．可変性モデルでは，仕様ごとにしている．F Ei と SVi は，装備仕様 i の燃費と変わりうる項目を可変点と呼び，三角形で表す．可変

予想販売台数を表しており，それぞれ，入力 9 と点の具体的なインスタンスをバリアントと呼び，長方10 の対応表を元に計算される．

形で表す．可変点とバリアントの対応関係には変異依

初期制約 : 入力 8 で与えられた依存関係を満たさなければならない．

存性と選択肢があり，選択肢の場合は，その多重度も付記される．可変点同士，バリアント同士，および，CAFE 問題の例を図 2 に示す．この例は，ソフト可変点とバリアント間の依存関係は，制約依存性にウェアプロダクトライン開発の分野で用いられる可変よって表される．制約依存性には，要求 (requires) と性モデル (Orthogonal Variability Model; OVM [6])排除 (excludes) の 2 種類がある．

表1

CAFE 問題 (図 2) の解

装備仕様

3 解集合プログラミング12

3

ASP の言語は，一般拡張選言プログラム (GeneralGradeSTDDXLX

Extended Disjunctive Program) をベースとしていDrive Type

2WD2WD2WDる [4]．本節では，説明の簡略化のため，そのサブクEngineV4V6V6

ラスである標準論理プログラムについて説明する．以

Tire

16inch17inch18inch降，標準論理プログラムを単に論理プログラムと呼ぶ．

Transmission

5MT

6MT

10AT

論理プログラムは，以下の形式のルールの有限集合-Normal-

IWR 値の総和

983

1,125

1,180

燃費 (km/L)

10.2

8.9

8.5

予想販売台数

745

1,988

1,171

装備

Sun Roof

平均燃費 (km/L)

9.0

予想販売台数 (合計)

3,904

である．

a0 ← a1 , . . . , am , ∼am+1 , . . . , ∼an(1)

このルールの直観的な意味は，「a1 , . . . , am がすべて成り立ち，am+1 , . . . , an のそれぞれが成り立たないならば，a0 が成り立つ」である．ここで，0 ≤ m ≤ nであり，各 a はアトム，∼ はデフォルトの否定 †1 ，i“,” は連言を表す．← の左側をヘッド，右側をボディ
可変性モデルで CAFE 問題を記述する場合，タイプは可変点，オプションとその IWR 値はバリアン
ト，タイプとオプションの対応関係および選択可能なオプション数の上下限値は選択肢，タイプ同士，オプと呼ぶ．ボディが空のルール (すなわち a0 ←) をファクトと呼び，← を省略してよい．
ヘッドが空のルールを一貫性制約と呼び，以下のように表す．

← a1 , . . . , am , ∼am+1 , . . . , ∼an

ション同士，および，タイプとオプション間の依存関(2)係は制約依存性によって表される．以上から，CAFE

例えば，一貫性制約 “← a1 , a2 ” は，「a1 と a2 が両方問題の入力のうち，1〜6 は可変性モデルによって記同時に成り立つことはない」を意味し，“← a1 , ∼a2 ”

述されることがわかる．

は，「a1 が成り立つならば，a2 が成り立つ」を意味

図 2 の問題例は，6 個のタイプ，19 個のオプショする．

ン，5 個の依存制約から構成され，各タイプの選択可

ASP 言語には，組合せ問題を簡潔に記述するために，能なオプション数はすべて 1 である．本論文では，可アグリゲート (aggregate) と呼ばれる拡張構文がいく

変点で表されるタイプは，各装備仕様に対して必須つか用意されている．例えば，選択子 “{a1 ; . . . ; an }.”とする．ただし，Sun Roof のような選択可能なタイは，アトム集合 {a1 , . . . , an } の任意の部分集合を解集

プ (必須ではないタイプ) については，破線の可変点合に含めることを意味する．個数制約は選択子の両端で表すものとする．に選択可能な個数の上下限を付けたものである．例え

図 2 の問題に対する解の例を表 1 に示す．この解ば，“lb {a1 ; . . . ; an } ub ← Body” と書くと，「Bodyは，CAFE 基準値に 9.0km/L，求めたい装備仕様のが成り立つならば，a1 , . . . , an のうち，lb 個以上 ub個数に 3 を与え，装備仕様とオプションの依存関係個以下が成り立つ」を意味する．重み付き個数制約として，(装備仕様 1, STD), (装備仕様 2, DX), (装備“t = #sum {w1 : a1 ; . . . ; wn : an }.” は，a1 , . . . , an

仕様 3, LX) を要求して得られたものである．各装備のうち真となるアトムの重み和が項 t に等しくなる

仕様の燃費 (km/L) は，左から順に 10.2, 8.9, 8.5 とことを意味する．項 wi は重みを表し，演算子とし個々には CAFE 基準値を満たしていないが，3 台のては “=” 以外にも “≤”,“≥” などを使用できる．さ

平均燃費は 9.028km/L となり，CAFE 規制を満たらに，重み付き個数制約の “#sum” を，“#max” やしている．

†1 失敗による否定とも呼ばれる．述語論理で定義される否定 (¬) とは意味が異なる．

表2

論理プログラムとソースコードの対応
vp_def("Drive_Type").

論理プログラム

←,;

∼#sum

ソースコード

:-,;

not

#sum

v_def("2WD", "Drive_Type", 125).
v_def("4WD", "Drive_Type", 200).

vp_def("Engine").

“#min” に書き換えると，重み和ではなく，真とな

v_def("V4", "Engine", 120).

るアトムの重みの最大値や最小値を求めることがで

v_def("V6", "Engine", 200).

きる．また，組合せ最適化問題を解くために，最小化vp_def("Grade").

関数 (#minimize)・最大化関数 (#maximize) 等も用

v_def("STD", "Grade", 580).

意されている．

v_def("DX","Grade", 580).

v_def("LX","Grade", 580).

近年，clingo †2 ，DLV †3 ，WASP †4 など，SATソルバー技術を応用した高速な ASP システムが開発されている．なかでも clingo は，高性能かつ高機能vp_def("Sun_Roof").
v_def("Nomal","Sun_Roof", 35).

v_def("Pnrorama", "Sun_Roof", 70).

な ASP システムとして世界中で広く使われている．
これらの高速 ASP システムは，変数を含む論理プロ

vp_def("Tire").
v_def("15_inch_Tire", "Tire",90).

グラムを変数を含まない論理プログラムに変換 (基礎v_def("16_inch_Tire", "Tire", 110).

化) したのち，ASP ソルバーを用いて解集合を計算

v_def("17_inch_Tire", "Tire", 130).

する．本論文で使用する ASP システム clingo は，基v_def("18_inch_Tire", "Tire", 150).

礎化のためのグラウンダー gringo と ASP ソルバー

vp_def("Transmission").

clasp をシームレスに結合したものである．

v_def("6AT","Transmission", 115).

v_def("10AT", "Transmission", 125).

以降の節で示す論理プログラムのソースコードはすべて gringo 言語で書かれており，表記上の対応については表 2 の通りである．

4 ASP に基づく CAFE 問題ソルバー

v_def("HEV","Transmission",95).

v_def("CVT","Transmission",80).

v_def("5MT","Transmission",48).

v_def("6MT","Transmission",55).

require_v_v("STD", "16_inch_Tire").
require_v_v("DX","17_inch_Tire").

提案する CAFE 問題ソルバーは，与えられた問題

require_v_v("LX","18_inch_Tire").

インスタンスを ASP のファクト形式に変換した後，require_v_v("LX","10AT").

それらファクトと CAFE 問題を解くための ASP 符

exclude_v_v("V4","10AT").

号化 (論理プログラム) を結合した上で，高速 ASP シ

require_vp("Drive_Type").

ステム clingo を用いて解を求める (図 1 参照)．本節

require_vp("Engine").

では，CAFE 問題の入力と制約を論理プログラムとして表現する方法について述べる．本論文では，説明

require_vp("Grade").
require_vp("Tire").
require_vp("Transmission").の簡単化のため，各タイプが選択可能なオプション数
group(1). group(2). group(3).の上下限値を 1 とする．
require_g_v(1, "STD").

4. 1 ASP ファクト形式

require_g_v(2, "DX").
require_g_v(3, "LX").

CAFE 問題の入力は，CAFE 基準値 (入力 11) を除いて，ASP のファクトで表される．CAFE 基準値†2 https://potassco.org/†3 http://www.dlvsystem.com/dlv/†4 https://www.mat.unical.it/ricca/wasp/

コード 1

CAFE 問題の例 (図 2) のファクト表現．装備仕様の個数:3，装備仕様とオプションの依存関係: (装備仕様 1, STD), (装備仕様 2, DX), (装備仕様 3, LX)

は ASP の定数 t で表すものとし，実行時に clingoのオプションから値を指定する．

1{ vp(VP,G) } :- vp_def(VP), group(G).

2:- not vp(VP,G), require_vp(VP), group(G).

CAFE 問題の例 (図 2) をファクトで表現したも3のをコード 1 に示す．この 2 つを見比べると，可変4% 範囲制約

51 { v(V,G) : v_def(V,VP,_) } 1 :- vp(VP,G).

性モデルの可変点，バリアント，制約依存性 (要求)， 6
制約依存性 (排除) が，それぞれファクト vp_def/1,v_def/3, require_v_v/2, exclude_v_v/2 に対応し7% 燃費制約8iwr(S,G) :-9ていることがわかる．例えば，バリアント V4 は，ファ 10
クト v_def("V4", "Engine", 120). に対応していS = #sum { IWR,V : v(V,G), v_def(V,_,IWR) },group(G).

11fe(FE,G) :- iwr(S,G), fe_map(S,FE).

12sv(SV,G) :- iwr(S,G), sv_map(S,SV).

る．可変性モデルは CAFE 問題の入力 1〜6 を含んで 13:- not 0 #sum { (FE-t)*SV,FE,SV,G : fe(FE,G), sv(SV,G) }.

いる．この他，require_vp/1 は必須タイプ，group/1 1415は装備仕様の識別子 (入力 7)，require_g_v/2 は各 16% 要求制約:- require_v_v(V1,V2), v(V1,G), not v(V2,G).

装備仕様とオプション間の依存関係を表している (入 17:- require_v_vp(V,VP), v(V,G), not vp(VP,G).

力 8)．例えば，require_g_v(1, "STD"). は，装備 18:- require_vp_v(VP,V), vp(VP,G), not v(V,G).

仕様 1 がオプション STD を要求することを表す．

19:- require_vp_vp(VP1,VP2), vp(VP1,G), not vp(VP2,G).

20

IWR 値の総和と燃費の対応表 (入力 9) は，ファク 21% 排除制約22:- exclude_v_v(V1,V2), v(V1,G), v(V2,G).

23:- exclude_v_vp(V,VP), v(V,G), vp(VP,G).

S は IWR 値の総和，F E は燃費を表す．同様にして，24:- exclude_vp_v(VP,V), vp(VP,G), v(V,G).

IWR 値の総和と予想販売台数の対応表 (入力 10) は，25:- exclude_vp_vp(VP1,VP2), vp(VP1,G), vp(VP2,G).

ト fe map(S,F E) の有限集合で表される．ここで，ファクト sv map(S,SV ) の有限集合で表される．

4. 2 CAFE 問題の ASP 符号化

2627% 初期制約28:- not v(V,G), require_g_v(G,V).

2930

CAFE 問題の各制約は，ASP の個数制約および一 31% 目的関数
#maximize { SV,G : sv(SV,G) }.

貫性制約を使って簡潔に表現される．CAFE 問題の制約と目的関数を表す論理プログラムをコード 2 に

コード 2

基本符号化示す．装備仕様 G がタイプ VP を装備することを意味するアトム vp(VP,G) を導入する．また，装備仕様数 SV を表す．13 行目のルールは，第 2 節で示した

G がオプション V を実装することを意味するアトム

CAFE 規制の式を以下のように変形し，ASP の重みv(V,G) も併せて導入する．

付き個数制約で表している．

1 行目のルールは，各装備仕様 G，各タイプ VP に

∑ni=1(F Ei − t) · SVi ≥ 0

対して，vp(VP,G) の候補を生成する．2 行目のルー

要求制約は 16〜19 行目のルールで表される．例えルは，各装備仕様 G に対して，VP が必須タイプならば，16 行目のルールは，装備仕様 G がオプション V1ば，G は VP を装備しなければならないことを表す．

を実装し，かつ，V1 が V2 を要求するならば，G は V2

範囲制約は 5 行目のルールで表される．このルールを実装しなければならないことを表す．他の要求制

は，タイプ VP を装備する装備仕様 G に対して，VP の約，排除制約，初期制約も同様に，一貫性制約を用いオプションからちょうど 1 個を実装することを表す．て簡潔に表現できる．

燃費制約は 8〜13 行目のルールで表される．8 行目

CAFE 問題の目的は，予想販売台数を最大化するの iwr(S,G) は，装備仕様 G の IWR 値の総和が S であことである．この目的関数は，31 行目の最大化関数ることを表す．11〜12 行目の fe(FE,G) と sv(SV,G)#maximize によって表される．本節で述べた論理プ

は，それぞれ，装備仕様 G の燃費 FE と予想販売台

ログラム (コード 2) を基本符号化と呼ぶ．

ub_vp(UB,VP) :-1% 予想販売台数の最大化

UB = #max { IWR,V : v_def(V,VP,IWR) },2#maximize { SV@2,G : sv(SV,G) }.

vp_def(VP).

3lb_vp(LB,VP) :-4% オプション数の最小化

LB = #min { IWR,V : v_def(V,VP,IWR) },5

used_v(V) :- v(V,G).

vp_def(VP).

6#minimize { 1@1,V : used_v(V) }.

ub_iwr(S) :-コード 4

オプション数の最小化

S = #sum { UB,VP : ub_vp(UB,VP) }.
lb_iwr(S) :S = #sum { LB,VP : lb_vp(LB,VP), require_vp(VP) }.

4. 4 符号化の拡張
製造ラインの削減や大量生産を促進することを狙iwr(S,G) :S = #sum { IWR,V : v(V,G), v_def(V,_,IWR) },LB <= S, S <= UB, lb_iwr(LB), ub_iwr(UB),
group(G).

いとして，予想販売台数の最大化に加えて，オプション数の最小化も可能なように拡張する．コード 4 に拡張のための論理プログラムを示す．

コード 3

基本符号化 (コード 2 の 8〜10 行目) の改良

予想販売台数の最大化 (2 行目) ついては，これまでと同じである．5 行目の used_v(V) は，オプショ

4. 3 符号化の改良

ン V がいずれかの装備仕様において実装されたことを前節で述べた基本符号化は CAFE 問題の制約を簡意味する．オプション数の最小化は，used_v(V) が潔に表現できるが，改良できる点も残っている．

成り立つ V の数を最小化することにより，容易に実タイプの集合を V P ，必須タイプの集合を V P ∗ ，現される (6 行目)．目的関数中の@の右側はその優先オプションの集合を V ，タイプ i ∈ V P が実装可能度を表しており，今回の拡張例では，予想販売台数のなオプションの集合を Vi ，オプション j ∈ V の IWR

最大化 (優先度 2)，オプション数の最小化 (優先度 1)

値を wj とする．このとき，基本符号化 (コード 2) のの順に最適化される．改良符号化の目的関数を，コー8〜10 行目のルールで生成されるアトム iwr(S,G) にド 4 で置き換えた符号化を拡張符号化と呼ぶ．

ついて，IWR 値の総和を表す S の上下限は，

0≤S≤∑j∈Vwj

図 2 の CAFE 問題に対して，最適解の全列挙をした結果を表 3 に示す．CAFE 基準値が 8.5km/L のとである．しかし，これは自明な上下限であり，各タイき，予想販売台数が 5,525 台である最適解が，改良プが選択可能なオプション数の上下限値，および，必符号化では (解 1, 解 2, 解 3) の 3 つ存在した．一方

須かどうかの別を考慮することで，で，オプション数の最小化を加えた拡張符号化では，

minj∈Vi wj ≤ S ≤i∈V P ∗最適解は (解 3) のただ 1 つだけとなる．このように，∑∑maxj∈Vi wji∈V Pのように S の上下限をより厳密に計算することがで

ASP に基づく CAFE 問題ソルバーでは，ユーザの選きる．下限値は，各必須タイプが選択可能なオプショ

好にあわせて目的関数を柔軟に追加することにより，ンの IWR 値の最小値の総和である．上限値は，各タ複数ある最適解に対して優劣をつけることができる．

イプが選択可能なオプションの IWR 値の最大値の総和である．このアイデアを元にした論理プログラ

5 実行実験

ムをコード 3 に示す．基本符号化 (コード 2) の 8〜

提案符号化の有効性を評価するために，開発した10 行目を，コード 3 で置き換えた符号化を，改良符

CAFE 問題ソルバーの実行実験を行った．ベンチマー

号化と呼ぶ．改良符号化は，基本符号化と比較して，ク問題 (表 4 参照) には，企業から提供を受けた小iwr(S,G) に関する基礎化後のルール数を少なく抑え規模 (small)・実用規模 (medium)・大規模 (big) のることができる．そのため，大規模な問題への有効性

CAFE 問題 (3 問) に対して，5 種類の CAFE 基準値が期待できる．

(8.5, 9.0, 9.5, 10.0, 10.5km/L) を適用した問題イン

表3CAFE 問題 (図 2) の最適解全列挙．CAFE 基準値: 8.5km/L

解1

解2

解3装備仕様1231

23

123装備 Grade

STD

DX

LX

STD

DX

LX

STD

DX

LX

Drive Type4WD

2WD 4WD2WD 2WD 4WD 2WD 2WD 4WD

EngineV4

V6V6V6V6V618

Tire

1617181617Transmission

5MT

HEV 10AT

CVT

HEV 10AT

Sun Roof

Panorama--Nomal--V6V6V6161718

6AT HEV 10AT---

IWR 値の総和

1,128

1,130 1,255

1,130 1,130 1,255 1,130 1,130 1,255

燃費 (km/L)

8.9

8.8

8.8

予想販売台数

2,007

2,007 1,511

8.0

8.8

8.0

8.8

8.8

2,007 2,007 1,511 2,007 2,007 1,511

平均燃費 (km/L)

8.6

8.5

8.5

予想販売台数 (合計)

5,525

5,5255,525

オプション数

141312

表48.0

問，改良符号化が 13 問であり，改良符号化がより多ベンチマーク問題

くの問題に対して優れた結果を示している．特に，大問題名 タイプ数 オプション数 要求制約数

規模インスタンス big については，5 問すべてに対し

small

8214て，改良符号化が基本符号化よりも優れた解を得るこ

medium86229147とに成功している．これにより，改良符号化の大規模big315

1,3370な問題への有効性が確認できた．小規模なインスタン
ス small については，基本符号化と改良符号化ともに 5 問すべてに対して最適解 (あるいは UNSAT) をスタンス (合計 15 問) を使用した．求めたい装備仕様の個数は 3 とした．

求めることができた．
インスタンス small について，それぞれの符号化でASP システムには，広く普及している高速 ASP シ

最適解，あるいは UNSAT を得るまでに要した CPU

ステム clingo-5.4.0 を使用し，一問当たりの時間制限時間を表 6 に示す．各問題インスタンスごとに，よりは 7,200 秒とした．実験環境は，Mac mini (3.2GHz

短い CPU 時間をボールド体で示している．改良符号Intel Core i7, 64GB メモリ) である．

化は，基本符号化と比較して 5 問中 4 問で優れた結果

表 5 に実験結果を示す．左から順に，問題名，CAFEを示している．また，CPU 時間の平均からも改良符基準値，基本符号化と改良符号化の予想販売台数 (目号化の方がより高速に解を求めていることがわかる．

的関数の値) となっている．記号 ‘∗’ 付きの値は最適

次に，基本符号化と改良符号化とで，基礎化後の値であることを表す．各問題インスタンスごとに，よルール数を比較した結果を表 7 に示す．括弧内の数字

り良い予想販売台数をボールド体で示している．まは，基本符号化のルール数を 1 としたときの比率でた，UNSAT は制約を満たす実行可能解が存在しないある．表 7 より，改良符号化は，基本符号化と比較しことを意味し，UNKNOWN は制限時間内に実行可能て，基礎化後のルール数を少なく抑えられていること解が一つも求められなかったことを意味する．

がわかる．特に，big では，70%以上のルール数の削最適値・最良値を求めた問題数は，基本符号化が 6減に成功している．このルール数の削減が，改良符号表5問題名small

mediumbig

実験結果

表7CAFE

予想販売台数基準値

基本符号化 改良符号化

比較結果: 基礎化後のルール数．CAFE 基準値:

9.0km/L

問題名

基本符号化

改良符号化

8.5

6,021*

6,021*

small

83,520 (1.00)

32,855 (0.39)

9.0

5,007*

5,007*

medium93,017 (1.00)

56,940 (0.61)

9.5

2,688*

2,688*

big

155,654 (1.00)

42,190 (0.27)

10.0

1,318*

1,318*

10.5

UNSAT

UNSAT

8.5

6,010

6,021

9.0

5,595

5,595

9.5

3,447

3,430

10.0

2,245

2,250

10.5

1,690

1,845

8.5 UNKNOWN

3,877

6 おわりにとした．n = 3 では 5 問すべて，n = 6 では 5 問中4 問について、最適解あるいは UNSAT を求めることができた．n = 12 では 5 問中 3 問は UNSAT であった．残り 2 問については実行可能解は得られたが，その最適性を証明するには至らなかった．

9.0

1,038

4,623

本論文では，CAFE 方式と呼ばれる新しい燃費規

9.56883,121制に基づく車両装備仕様問題に対して，解集合プログ

10.0

1,634

2,064

ラミング技術をはじめて適用し，その記述性の高さ，10.5538904

柔軟な最適解探索などの利点を確認した．また，効率最適値・最良値の数

613性についても，企業から提供された問題集を用いた実験結果から，実用規模の問題に対して適用可能である

表6解を得るまでに要した CPU 時間 (秒)ことが確認できた．
装備の組合せに関する制約は，まず企画部門で設定

問題名CAFE

CPU 時間され，そのあと開発部門，生産部門，販売部門に受け基準値

基本符号化

改良符号化

8.537.868

23.318ていく．これら様々な制約を調査・整理・実装するこ

9.048.965

43.362とにより，CAFE 問題ソルバーを拡張することが今

9.595.110

173.172

後の課題である．

10.099.954

0.343

10.5439.613

0.080

144.302

48.055small

平均化の大規模問題に対する優位性につながっていると考えられる．
さらに，インスタンス small を用いて，求める装備仕様の個数を増やした予備的な実験を行った．装備仕様の個数は n = 3, 6, 12 とし，CAFE 基準値は前述の実験と同じ 5 種類を用いた．各装備仕様とオプション間の依存関係については，同じ装備仕様が生じないように与えた．制限時間は 1 問あたり 1 時間渡され，各部門で制約が追加されながら徐々に成熟し

参 考 文 献[1] Baral, C.: Knowledge Representation, Reasoning
and Declarative Problem Solving, Cambridge University Press, 2003.
[2] Erdem, E., Gelfond, M., and Leone, N.: Applications of ASP, AI Magazine, Vol. 37, No. 3(2016),
pp. 53–68.
[3] Gelfond, M. and Lifschitz, V.: The Stable Model
Semantics for Logic Programming, Proceedings ofthe Fifth International Conference and Symposiumon Logic Programming, MIT Press, 1988, pp. 1070–1080.
[4] 井上克巳, 坂間千秋: 論理プログラミングから解集合プログラミングへ, コンピュータソフトウェア, Vol. 25,
No. 3(2008), pp. 20–32.

[5] 経済産業省, 国土交通省: 乗用車燃費規制の現状と論点について, 第 5 回自動車燃費基準小委員会, 2018.

[6] Pohl, K., Böckle, G., and van der Linden, F.:
Software Product Line Engineering, Springer, 2005.