依存関係を考慮した訪問順の制約付き最適化

依存関係を考慮した訪問順の制約付き最適化

Optimization Under Precedent and Dependency Constraints

Using Multi-valued Decision Diagrams

大滝 啓介

1∗

沓名 拓郎

1

大社 綾乃

1

西 智樹

1

Keisuke Otaki

1

_{Takuro Kutsuna}

1

_{Ayano Okoso}

1

_{Tomoki Nishi}

1

1

_{株式会社 豊田中央研究所}

1

_{Toyota Central R&D Labs., Inc.}

Abstract: We study the optimization problem under permutations of (at most) N locations under user-defined constraints, particularly focusing on precedent and dependency constraints among locations. Our approach is based on representing the feasible set of solutions; that is the solution space using multi-valued decision diagrams, and solve the optimization problem on the diagrams. We present preliminary results via numerical experiments and discuss our methods.

1

はじめに

地点の訪問順序を最適化する問題は，交通システム における組合せ最適化問題として広く研究されてい る[13]．本稿では特に，選択可能な訪問順序に制約が課 されている場合を考える． まずは形式的な表記から導入する．本稿ではN 地点 がpi= (xi, yi)∈ R2に位置し，地点iとjの間の距離 をCi,j=∥pi− pj∥2とする．このときN地点全てに訪 問しながら，総移動コストを最小化する訪問順序を求め る．訪問順序はサイズN の順列であり，本稿ではベク トルπ = (π1, . . . , πN)∈ S[N ] で表す．ただしS[N ] は 集合[N ] :={1, 2, . . . , N}の要素を並び替えて構成され る全ての順列の集合である．総移動コストCは式(1) C(π) := ∑ 1≤i≤|π|−1 Cπi,πi+1 (1) として定義される．最適化問題はminπ∈S[N ]C(π)と して表現される．問題によっては，選択可能な順列π に制約が課される．典型的な制約の例として，先行制 約 (precedent constraints) がある．これは地点pi, pj について，pi をpjより先に訪問することを要求する制 約である．図1aに，N = 4の場合の例を2つ示す．こ こで地点⃝4は，例えば先行制約によって最後に到達すべ き地点である．2つの順列π1 = 1234とπ2= 2314を ∗_{連絡先:(株) 豊田中央研究所 〒112-0004 東京都文京区後楽} 1-4-14 後楽森ビル 10F E-mail:[email protected] (a) 2つのサイズN = 4の 順列: 1234と2314 (b) 顧客2を訪問しない順 列: 134 図1: 例題(地点4は最終目的地を表す) 比較すると，C(π1) < C(π2)である．このような形式 の最適化問題は配送計画問題 [13]やスケジューリング 問題[8, 9]において研究されてきた．これらの問題の多 くはNP困難な問題として知られているが，問題の性質 や制約を用いて効率的に解を求める技術が研究されてい る [3, 10]．本稿では特に，決定グラフを用いる最適化 技法に注目する [2]．例えば[10]で提案されたπMDD と呼ばれる決定グラフを用いると，先行制約を満たすよ うなサイズN の順列を多値決定グラフ (Multi-valued decision diagrams; MDDs)としてコンパクトに表現し， 最適化問題に適用できる． スケジューリングにおいて利用される決定グラフは， N 地点を全て訪問する順列のうち，制約を満たす順列 のみをコンパクトに表現する．一方で経路計画において は，距離制約や時間制約などにより，全ての地点を訪問 することができない場合がある．図1bは，車両の走行 可能な距離の制約により地点⃝2が訪問されず，π = 134 という3地点のみを訪問する順列の例を示す．本稿では 式(1)とその最小化問題を拡張し，地点i∈ [N]を訪問 人工知能学会研究会資料 SIG-FPAI-B902-03

しないことを考慮した最適化問題として min π∈S[N ] C(π) + λΩ({n ∈ [N] | n ̸∈ π}) のような問題を考える．ここでS[N ]はS[N ]を一般化し た集合である(後に定義する)．例えば図1bでは目的関 数値がC(134) + λΩ({2})として評価される．パラメー タλは訪問する地点としない地点の間でバランスを取 る．似た形の最適化問題として，例えば訪問できた顧客 数|π|を最大化しつつ，移動コスト制約C(π) < ˜λを満 たすような最大化問題を考えることもできる．いずれの 場合でも，順列の集合に対して様々な制約を課すことが できるデータ構造が求められる． 以上の例に基づき，本稿では既存のデータ構造では πMDDを拡張する．πMDDはサイズNの順列のうち， 有向グラフGpで表現される先行制約を全て満たす順列 のみをコンパクトに表現する．そこで本稿では 要件1 πMDDの構造を利用して，サイズN 未満の順列 を同時に表現する 要件2 顧客の同乗制約を新しく考慮する という2つの性質を満たすデータ構造を提案する．ここ で2つ目の性質は，図1bのように，地点⃝1と⃝3で乗客 する予定の2人の乗客が，今考えている車両に同時に乗 るか，逆に同時に乗らずに他の車両に乗る，といった問 題設定において利用することを想定している．

2

準備

本稿では集合V と要素v ∈ V に対して，V ⊕ v := V∪{v}，またはV⊖v := V \{v}と表す．また[N ]は集 合{1, . . . , N}を表し，集合{i1, . . . , in}を単に要素の列 としてi1. . . in と表す．要素の列LをL =⟨i1, . . . , in⟩ のように表し，逆順の列をL−1=⟨in, . . . , i1⟩で表す．

2.1

順列とグラフ構造

集合[N ]上の順列πは，[N ]から[N ]への全単射であ り，特にベクトルとしてπ = (π1, . . . , πN)で表す．ま た集合S[N ] は[N ]上の全ての順列の集合であり，例え ばS[2]={(1, 2), (2, 1)}である． 本稿ではDAGをG = (V, A)で表す．頂点v ∈ VG の入次数と出次数をそれぞれd−_G(v) := |{(v, u) ∈ E | u ∈ V }| と d+_G(v) := |{(u, v) ∈ E | u ∈ V }| で定 義する．頂点の集合S ⊆ V による誘導部分グラフを G[S] で 表 記 す る ．DAG G上 の 長 さ k の パ ス P を k + 1頂点の列としてP :=⟨v1, . . . , vk+1⟩と表す(∀1 ≤ i ≤ k, (vi, vi+1) ∈ A である)．同様に無向グラフを U = (V, E)で表す．無向グラフU における頂点vの近 (a)先行制約グラフGp (b)依存制約グラフUd 図2: 最適化問題に与えられる制約のグラフ表現 (詳細 は3.1節を参照) 傍をNU(v) = {u ∈ V | {u, v} ∈ E}で表し，次数を dU(v) :=|NU(v)|で表す． ■グラフで表現される制約 有向グラフGp = (Vp, Ap) を考える．今(v1, v2)∈ Apであるとき，v1はv2に先 行しなければならないと解釈する．この意味で，有向グ ラフGpを先行制約グラフと呼ぶ．以降ではVp = [N ] と仮定する．また無向グラフUd = (Vd, Ed)を考える． ここで頂点uの近傍NUd(u)は，uと同時に訪問順に含 まれなければならないと解釈する．つまり，u∈ V, v ∈ NUd(u)である頂点u, v は，πに共に含まれるか，共 に含まれない．この意味で，グラフUdを依存制約グラ フと呼ぶ．以降ではVd ⊆ [N]と仮定する．2つのグラ フGpとUdは所与とする． 図2に例を示す．図2aにおいて，地点⃝4は最終目的 地と設定されており，他の3地点よりも後に訪れる必要 があることがグラフで表現される．また図2bでは，地 点⃝1と⃝3に依存関係があること，⃝2は他の地点に依存し ないことが表現されている．

2.2

多値決定グラフ

以下に[4, 10]の定義を踏襲し，本稿で利用する多値決 定グラフ (Multi-valued Decision Diagram; MDD)と，

MDDを用いてサイズN の順列を表現するπMDDに ついて説明する． 定義 1 (MDD). 多値決定グラフD = (VD, AD, λD)は (辺ラベル付き)有向グラフであり，唯一の根ノードr∈ VD (d−D(r) = 0)と唯一の終端ノードt∈ VD (d+D(t) = 0)を備える．一般にDの頂点はレイヤー毎に解釈され る．レイヤー数をlr (D)で表し，第1レイヤーはrのみ， 第lr (D)レイヤーはtのみが属す．ノードn∈ VDの属 するレイヤーの番号をlr (n) (例えばlr (r) = 1).で表す． ノードn∈ VD⊖ tの子ノードの集合をCh(n) :={n′∈ VD | (n, n′) ∈ AD} で定義する．MDDにおいて，辺 a∈ ADに関連付けられた値をラベルと見なしてλD(a)

で表す*1_{．またその値域をdom(a)で表記する．同様} にノードn ∈ VD に対してdom(n) = {λD((n, n′)) | (n, n′)∈ AD}とする． 最適化問題に用いられる MDDはしばしば以下の 性質を満たすように定義される．長さk のパスP := ⟨n1, . . . , nk+1⟩ ∈ VDk+1について

lr (ni) + 1 = lr (ni+1), (ni, ni+1)∈ AD. (2)

パスP の各辺に関連づいた値の集合を取得する操作を λD(P ) := {λD((ni, ni+1)) | 1 ≤ i ≤ k}で同じ記号 で表す．本稿では単純化のため，ノードn1∈ VD から n2∈ VD⊖ n1への全てのパスの集合をΠ(D, n1, n2)で 表す．同様にΠ(D) := Π(D, r, t)とする． ■順列を表現するためのMDDs (πMDD) 定義2 (πMDD [10]). MDD Dと，整数N が所与とす る．Dが順列の集合を表現する場合，D の各ノードを 関数I : VD→ 2[N ]を用いて次のように解釈する． 1. I(r) = [N] およびI(t) = ∅. 2. ノードn∈ VD\ {r, t}に対して，I(n) = λD(P ) かつP ∈ Π(D, n, t). 3. 2つのノードn, n′ ∈ VDが辺a = (n, n′)∈ AD

を構成するとき，I(n) \ I(n′) ={e} = {λD(a)}

が成り立つ．

パスP は順列πP ∈ S[N ]を以下の定義により表現す

る: パスP =⟨v1, . . . vN +1⟩ (v1= rかつvN +1= t)に

対して，πP = (πP ,1, . . . , πP ,N)は任意のi∈ [N]につ

いてπP ,i:=I(vN−i+1)\ I(vN−i+2)．パスPから順列

を取り出す操作をπP := VAL(P−1)で表す． 図 3 に 例 を 示 す ．こ こ で r か ら t へ の パ ス P = ⟨r, a, b, e, t⟩に対して，1234 → 123 → 23 → 2 → ∅ という集合の列が対応し，ここから順列πP = 2314 = VAL(P−1)を得る．根ノードから終端ノードへの全て のパスを用いて，与えられた制約を満たす順列の集合と してΠ(D) := {1234, 1324, 2134, 2314, 3124, 3214} を 得る．このように解空間を決定グラフDによって表現 する技術は，これまでの例では例えば[4, 5, 10]におい てジョブスケジューリング問題に利用されている．ここ では最適化問題を直接解く代わりに，決定グラフ上の最 短/長パスを求めることで，元の最適化問題を解く． 最後にこのようなπMDDの構築方法をAlgorithm 1 に引用する．グラフGp= (Vp, Ap)が所与とし，πMDD *1_{例えば BDD B = (VB, AB) であれば，どの辺 e}∈ A_{Bも 0} または 1 の値が紐付いている． 図3: πMDDの例と解釈による順列の表現 Algorithm 1 maker-πMDD Input: DAG G = (V, A) of V ⊆ [N] Output: πMDD D 1: if V =∅ then return終端ノードt 2: else if グラフGに対するπMDD DGが未計算then 3: πMDD D← (VD, ED)ただしVD={V }, ED=∅ 4: for d+_G(v) = 0であるv∈ V についてdo 5: V′← V ⊖ v 6: πMDD D′←maker-πMDD(G[V′]) 7: VD← VD∪ {V′}, ED← ED∪ {(V, V′)} 8: 作成したDをDGとして記録する 9: returnグラフGに対するπMDD DG を深さ優先探索によって順列πの後ろから順番に決定 する形で構築する．つまりあるノードの子ノードを作成 するとき，Alg. 1は先行制約グラフGpを新しいグラフ Gp[V′]で置き換える．ここでV′は，順列πに含まれる ことを選択したノードが乗り除かれている．他の決定グ ラフ技法と同様に，既に生成されたノードはキャッシュ される(8行目)．本稿では先行制約グラフGpを満たす 順列の集合を表現したπMDDをD(Gp)で表す．

3

提案手法

本章ではπMDDを拡張し，第1章で述べた要件を満 たす技法を構築する．そのため式(2)を緩和し，ノード 間の辺やパスの解釈を拡張する．

3.1

πMDD

の拡張

まずはじめに要件1について議論する．これまでスケ ジューリング分野で利用されていたπMDDでは地点を 棄却することを想定していない．しかし決定グラフにお いて，レイヤー間を跳躍する辺を利用することで地点の 棄却を実現することができる．以下に例を挙げる． 例1 (顧客の棄却(図1より)). 地点⃝4は最終目的地であ

図4: 拡張されたデータ構造と解釈の例 る．これはGp = ({1, 2, 3, 4}, {(1, 4), (2, 4), (3, 4)})に より表現され，GpとN = 4から構成されるπMDDが 図3である． 例えばI(a) = {1, 2, 3} であるノードa を考える． Alg. 1がGpを処理する際，ノードaを作成した後の状 況ではd+_G p(1) = d + Gp(2) = d + Gp(3) = 0が成り立ち，そ れぞれのノードv ∈ {1, 2, 3} を選ぶことで，子ノード を深さ優先で生成していく．ここでv = 1を選ぶ場合 (1∈ π)に，仮にv = 1を選ばない(1̸∈ π)という情報 を追記することを考える．地点の棄却を本稿では¬vと 表す．つまり今n = aから1と¬1の値がついた辺の両 方を作成し，制約を満たすかどうかを確認する． 形式的には，次のような拡張を考える． 定義3 (πMDDの拡張). πMDD D = (VD, AD, λD)と 地点数N が与えられるとする．以下のようにπMDD を拡張する． • 長さkのパスP =⟨v1, . . . , vk+1⟩ ∈ VDk+1は lr (vi) + 1<lr (vi+1), (vi, vi+1)∈ AD のように，レイヤー間を跳躍してもよい．

• 経路の解釈を VAL(P ) :=⟨λD((vi, vi+1))| 1 ≤ i≤ k, λD((vi, vi+1)) > 0⟩として一般化する． 拡張されたデータ構造の例を図4に示す．例えばパス P が列⟨−2, 1, 3, 4⟩を備えるとき (図では⟨r, a, c, e, t⟩, λD(e, t) =−2である),このパスをπP = 134として解 釈する． 次に要件2について，例を用いて説明する． 例 2. 本稿では「顧客の棄却」を導入するために，新し い制約として依存制約グラフを採用した．グラフGpと N = 4から求めたπMDD D(Gp)は図3に示される通 りである．ここで依存制約グラフUd = (Vd, Ed) (ただ しVU ⊆ Vp)として，Ud= (Vd, Ed) := ({1, 2, 3}, {13}) を用意し，次のような制約を表現していると解釈する． • 無向辺{1, 3} ∈ Edは，⃝1と⃝3が依存することを 意味する． • 孤立点2∈ Vdは，⃝2をπから除外できることを 意味する．また他の頂点と依存関係はない． • 頂点4 ∈ Vp, 4̸∈ Ud は⃝4を除外できないことを 意味する． このような制約を満たすサイズN = 4未満の順列とし て，例えば134や314，または24がある．これらの順 列は，D(Gp)のみでは表現できない．

3.2

構築アルゴリズム

本稿では2つの制約を表現するグラフGp, Udが与え られた時，制約を満たす全ての順列を表現した図4の データ構造を構築する．このデータ構造をD(Gp, Ud) で表す．Alg. 1を拡張し，D(Gp, Ud)を構築するアルゴ リズムをAlg. 2に示す．Alg. 2では，出次数d+_G p(v) = 0 である頂点vを処理して部分MDDを作成する際に，新 しく例1中の¬vに相当する処理を10行目から16行目 において実行する．ここで¬vに相当する部分MDDを 計算するために，Alg. 2では既に訪問済みの地点を納め た情報Pを同時に引数に渡す．仮に¬vを計算する際に 除外すべき頂点の集合E := v ∪ NU(v)に対して，ある 頂点u∈ Eがu∈ Pであれば，この除外処理を禁止す る．もしそのような頂点が存在せずにE ∩ P = ∅である 場合，新しい部分MDDとしてI(n′′) = V′′= V \ Eを 作成し， λD((V, V′′)) =¬vを付けて結合する． MDD D(Gp, Ud)は，拡張された辺を含んだ場合で あっても根ノードと終端ノードが含まれるDAGである ため，各頂点に計算結果や過程を記録し，子から親へと 計算を伝播していくことができる． 最後に，1 章で用いた集合S[N ] について定義する． 集合T について，Comb(T, k) = {C ∈ 2T _{| |C| = k}} とPerm(T, k) =∪_{C∈Comb(T,k)}SCを定義する(ただし 1≤ k ≤ |C|). このときS[N ]は S[N ]:= ∪ 1_≤k≤N Perm([N ], k) (3) で あ る ．ま た 2 つ の 制 約 グ ラ フ Gp, Ud が 所 与 で あ る 場 合 に S[N ](Gp, Ud) := {π ∈ S[N ] |

π satisfies both Gp and Ud} とし，これが Π(Gp, Ud)

Algorithm 2 mk Input: DAG G = (V, A) of V ⊆ [N], UG U = (VU, EU), 訪問済みの位置集合P ⊆ [N] 1: if V =∅ then return終端ノードt 2: else if (G,P)に対するπMDD DG,Pが未計算then 3: πMDD D← (VD, ED) of VD={V }, ED=∅ 4: for d+ G(v) = 0であるv∈ V についてdo 5: V′← V ⊖ v 6: P′← P ∪ {v} 7: D′←mk(N, G[V′], U,P′) 8: VD← VD∪ {V′} 9: ED← ED∪ {(V, V′)} ▷ (以下で¬の処理) 10: v′← ¬v, NU,v ← NU(v) 11: if v∈ VUthen 12: if NU(v)∩ P = ∅ then ▷ (制約を満たす場合) 13: V′′← V′\ NU,v 14: D′′←mk(N, G[V′′], U,P′) 15: VD← VD∪ {V′′} 16: ED← ED∪ {(V, V′′)} 17: memorize D as DG 18: return DG

4

Pickup-and-Delivery

本章では提案したデータ構造を利用し，以下に定義す る簡易的な最適化問題を解く．

問題1 (Pickup-and-Delivery with exclusion). N地点 と地点間の移動コストCij，2つの制約グラフGp, Udが 所与とする．このとき，π∈ S[N ](Gp, Ud)に対して，以 下のコストを最小化するようなπを求める． C(π) := ∑ 1≤i≤|π|−1 Cπi,πi+1+ ∑ j∈{n∈[N]|n̸∈π} λj, (4) ただしλjはj∈ [N]を訪問しないペナルティである．

なお本稿の実験はOSがUbuntu 18.04，CPUがXeon W-2145 (3.70GHz)，メモリが64GBのPC環境にイン ストールしたJulia 1.3.0の上で実行した． ■インスタンスの作成 本稿ではN を偶数とする．特 に1 ∈ [N]を車両の出発地点，N ∈ [N]を最終目的と し，2 からN − 1 までの地点を訪問候補地点とする． ただし，偶数番号の地点iを顧客の乗車位置 (pickup)， i + 1を降車位置 (delivery)と設定し，この制約をGp で表す．各地点i ∈ [N]にランダムな2次元上の位置 {(xi, yi)}Ni=1を設定し，Cijをユークリッド距離で求め る．ペナルティλiについても乱数で設定する． 表1: N ≤ 12の結果([s]もしくは[ms]) N 6 8 10 12 tbuild 0.2 [ms] 0.5 [ms] 3.4 [ms] 0.11 [s] tddopt ≤ 0.1 [ms] ≤ 0.1 [ms] 0.2 [ms] 0.8 [ms] tenum ≤ 0.1 [ms] 0.6 [ms] 19.3 [ms] 1.15 [s] 表2: N ≥ 14の結果 N tbuild [s] tddopt[s] 14 0.11 0.03 16 0.60 0.16 18 3.49 0.76 20 17.04 4.29 22 83.65 28.59 ■実験内容 実験を通して，まずDDを構築するために 必要な時間tbuildを計測する．次に構築したDDを用い て，以下の2つの手法を比較する 1. DD上で最適化計算を行う 2. DDから解空間S[N ](Gp, Ud)を列挙し最小コス トとなる解を逐次探索する 手法1.による計算時間をtddopt，手法2.による計算時 間をtenumと書く．ただしS[N ]自体が大きくなり列挙 する時間が指数的に大きくなるため，列挙法については N ≤ 12のみを計測した． 実験ではN を6から22まで2ずつ (顧客1人ずつ) 増加させ，それぞれの問題設定において100回ずつラン ダムなインスタンスを作成し，計算した結果要した平均 計算時間を求める． ■結果 3つの計測結果を表1に示す．また表2は，列 挙法は計測せずに，DD上での最適化に必要な時間のみ をN ≥ 14の例に対して計測した結果を示す． N = 5の場合に作成したランダムなインスタンスと， 計算した最適な巡回順に沿って移動した経路を可視化し たものを図5に示す． ■まとめ 本節の実験より，以下の点が明らかになっ た．まず表1から分かる通り，制約Gp, Udが所与の場 合，一度制約をDAG構造D(Gp, Ud)に表現し直すこと で，複数のインスタンスの最適化問題を高速に解くこと ができる．仮にD(Gp, Ud)から解空間S[N ](Gp, Ud)を 一度列挙すれば，同様のことが可能である．しかし表1 から示唆される通り，この列挙に必要な時間は指数的に 増加し，DD上で最適化計算を行う方がよりスケールす る．現在の実験結果から判断すると，DD上で行う最適 化計算は列挙法と比較して場合によっては100倍程度の

(a)例題1 (b)例題2 (c)例題3 図5: 3つのN = 12におけるインスタンスと解の例． いずれも制約Gp, Udは共通のものである．赤丸は出発 地，青丸は目的地を示す． オーダで高速である． 一方でD(Gp, Ud)を構築する時間も，N につれて大 きくなっていき，この増加分は指数的な挙動を示す．こ れは問題設定におけるGpが比較的スパースであり，作 成するD(Gp, Ud)が爆発しやすい傾向があるためと考 えられる．例えば既存研究[10]においても同様の傾向が 見られ，Gpが密であればあるほど，D(Gp, Ud)はコン パクトになる．今回例題に用いたPickup-and-Delivery with exclusionでは，顧客の依存関係をほとんど利用し ていないため，疎なDDを得ることは難しい．

5

まとめ

本稿ではスケジューリング問題において広く研究され ているMDDを用いて，顧客を棄却したり，顧客間に制 約がある場合であっても表現できるようなπMDDの拡 張を提案した．作成したデータ構造を簡易的な Pickup-and-delivery型の最適化問題に適用し，結果を報告し た．離散構造処理系としての決定グラフは現在広く注目 されている[11, 7, 4, 6]．本稿や他のMDDを用いる最 適化技法では陽に考慮していないことがあるが，縮約規 則を適用するなど，決定グラフとして研究の余地があ る．また決定グラフに付随する演算や，変数順序の問題 などについても，議論する余地があると考えている．ま た巡回セールスマン問題を含む研究との関連として，時 間窓に対応する技法や，その他の手法との関係性につい て議論する余地がある[1, 12]． 今後の課題として，上記の離散構造処理系としての特 性について検証することや，根ノードから終端ノードへ のパスに関する正規化，また複数車両に対応するための 拡張などについて研究を行う予定である．

参考文献

[1] S. R. Ait Haddadene, N. Labadie, and C. Prod-hon. The VRP with Time Windows, Synchronization and Precedence COnstraints: Applications in Home Health Care Sector. In Proc. of the MOSIM 2014, 2014.

[2] D. Bergman, A. A. Cire, W.-J. van Hoeve, and J. N. Hooker. Discrete optimization with decision dia-grams. INFORMS Journal on Computing, 28(1):47– 66, 2016.

[3] F. A. Chudak and D. S. Hochbaum. A half-integral linear programming relaxation for schedul-ing precedence-constrained jobs on a sschedul-ingle machine.

Operations Research Letters, 25(5):199–204, 1999.

[4] A. A. Cire, et al. MDD propagation for disjunctive scheduling. In Twenty-Second International

Confer-ence on Automated Planning and Scheduling, 2012.

[5] A. A. Cire and W.-J. van Hoeve. Multivalued deci-sion diagrams for sequencing problems. Operations

Research, 61(6):1411–1428, 2013.

[6] J. N. Hooker. Decision diagrams and dynamic pro-gramming. In Proc. of the CPAIOR2013, pp. 94–110. Springer, 2013.

[7] D. E. Knuth. The Art of Computer Programming:

Vol. 4, No. 1: Bitwise Tricks and Techniques-Binary Decision Diagrams. Addison Wesley Professional, 2009.

[8] E. L. Lawler. Sequencing jobs to minimize total weighted completion time subject to precedence con-straints. In Annals of Discrete Mathematics, Vol. 2, pp. 75–90. Elsevier, 1978.

[9] J. K. Lenstra and A. Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations

Research, 26(1):22–35, 1978.

[10] K. Matsumoto, K. Hatano, and E. Takimoto. De-cision diagrams for solving a job scheduling prob-lem under precedence constraints. In Proc. of the

SEA2018, 2018.

[11] S.-i. Minato. Zero-suppressed bdds for set manipula-tion in combinatorial problems. In 30th ACM/IEEE

Design Automation Conference, pp. 272–277. IEEE,

1993.

[12] X. Tan and J. X. Huang. On computational com-plexity of pickup-and-delivery problems with prece-dence constraints or time windows. In Proc. of the

IJCAI2019, pp. 5635–5643, 2019.

[13] P. Toth and D. Vigo. Vehicle Routing. Society for Industrial and Applied Mathematics, 2014.