本研究では，混合整数線形計画問題（Mixed Integer Linear Programming : MILP） として定式化し，厳密解を求める．MILPを採用した理由は，記述性が高く，細かい拘 束条件についての数式を用いてのモデル化に対応できることにある．
151 Minimize
∑ℎ∈𝐻𝐻∑𝑛𝑛∈𝑁𝑁𝑧𝑧ℎ𝑛𝑛 (6.1)
Subject to
∑𝑛𝑛∈𝑆𝑆𝑚𝑚ℎ𝑛𝑛𝑛𝑛 = 1，ℎ ∈ 𝐻𝐻，𝑚𝑚 ∈ 𝑁𝑁 (6.2)
∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚ℎ𝑛𝑛𝑑𝑑 ≥ 𝑠𝑠1ℎ𝑔𝑔𝑑𝑑，ℎ ∈ 𝐻𝐻，𝑔𝑔 ∈ 𝐺𝐺，𝑠𝑠 ∈ 𝐵𝐵 (6.3)
∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚ℎ𝑛𝑛𝑑𝑑 ≤ 𝑠𝑠2ℎ𝑔𝑔𝑑𝑑，ℎ ∈ 𝐻𝐻，𝑔𝑔 ∈ 𝐺𝐺，𝑠𝑠 ∈ 𝐵𝐵 (6.4)
∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚ℎ𝑛𝑛𝑑𝑑 + ∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚ℎ+1，𝑛𝑛，𝑑𝑑 ≤ 1，
ℎ= 1,2, …𝑇𝑇 −1, 𝑔𝑔 ∈ 𝐺𝐺𝑝𝑝, 𝑠𝑠 ∈ 𝐵𝐵 (6.5)
∑𝑔𝑔∈𝐺𝐺𝑖𝑖𝑦𝑦ℎ𝑔𝑔𝑑𝑑 ≤ 1，ℎ ∈ 𝐻𝐻，𝑠𝑠 ∈ 𝐵𝐵 (6.6)
𝑦𝑦ℎ𝑔𝑔𝑑𝑑 − ∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚ℎ𝑛𝑛𝑑𝑑 ≤ 0，ℎ ∈ 𝐻𝐻，𝑔𝑔 ∈ 𝐺𝐺𝑘𝑘，𝑠𝑠 ∈ 𝐵𝐵 (6.7)
𝐾𝐾𝑔𝑔𝑦𝑦ℎ𝑔𝑔𝑑𝑑 − ∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚ℎ𝑛𝑛𝑑𝑑 ≥ 0，ℎ ∈ 𝐻𝐻，𝑔𝑔 ∈ 𝐺𝐺𝑘𝑘，𝑠𝑠 ∈ 𝐵𝐵 (6.8)
𝑚𝑚ℎ𝑛𝑛𝑙𝑙𝑑𝑑 − ∑𝑛𝑛∈𝑁𝑁𝑚𝑚ℎ+1,𝑛𝑛,𝑑𝑑 ≤ 1，
h = 1,2, …𝑇𝑇 −1, 𝑚𝑚𝐻𝐻∈ 𝑁𝑁𝐻𝐻，𝑠𝑠 ∈ 𝐵𝐵 (6.9)
𝑚𝑚𝑑𝑑𝑛𝑛𝑙𝑙𝑑𝑑 ≤ 0，𝑚𝑚𝐻𝐻 ∈ 𝑁𝑁𝐻𝐻，𝑠𝑠 ∈ 𝐵𝐵 (6.10)
∑ℎ∈𝐻𝐻∑𝑑𝑑∈𝐵𝐵𝑚𝑚ℎ𝑛𝑛𝑑𝑑 = 1，𝑚𝑚 ∈ 𝑁𝑁 (6.11)
𝐿𝐿+ℎ𝑛𝑛 − ∑𝑑𝑑∈𝐵𝐵𝑚𝑚ℎ𝑛𝑛𝑑𝑑 ≤ 𝑧𝑧ℎ𝑛𝑛，ℎ ∈ 𝐻𝐻，𝑚𝑚 ∈ 𝑁𝑁 (6.12)
𝑀𝑀+ℎ𝑛𝑛 + ∑𝑑𝑑∈𝐵𝐵𝑚𝑚ℎ𝑛𝑛𝑑𝑑 ≤ 0，ℎ ∈ 𝐻𝐻，𝑚𝑚 ∈ 𝑁𝑁 (6.13)
𝑚𝑚ℎ𝑛𝑛𝑛𝑛 ∈ �0， 1�，ℎ ∈ 𝐻𝐻，𝑚𝑚 ∈ 𝑁𝑁，𝑠𝑠 ∈ 𝑆𝑆 (6.14)
𝑦𝑦ℎ𝑔𝑔𝑑𝑑 ∈ �0， 1�，ℎ ∈ 𝐻𝐻，𝑔𝑔 ∈ 𝐺𝐺𝑘𝑘，𝑠𝑠 ∈ 𝐵𝐵 (6.15)
𝑧𝑧ℎ𝑛𝑛 ∈ �0， 1�，ℎ ∈ 𝐻𝐻，𝑚𝑚 ∈ 𝑁𝑁 (6.16)
目 的 関 数(6.1)式 は ，希 望 時 間 と の 差 異 の 最 小 化 で あ る ．変 数𝑧𝑧ℎ𝑛𝑛 は ，拘 束 条 件(d)に 違 反 す る ペ ナ ル テ ィ で あ り ，各 ト ラ ッ ク𝑚𝑚の 希 望 時 間ℎと マ ッ チ し て い な い 場 合 は 1， そ う で な い 場 合 は 0 と な る 2 値 整 数 変 数 で あ る ．𝑧𝑧ℎ𝑛𝑛
は ，(6.16)式 で 定 義 さ れ て い る ．(6.1)式 は こ の 𝑧𝑧ℎ𝑛𝑛 の 和 を 最 小 化 す る ． (6.2)式 は 各 ト ラ ッ ク𝑚𝑚に つ い て ，各 指 定 時 間ℎで「 無 し 」を 含 む バ ー ス𝑠𝑠に 必 ず 割 り 当 て ら れ る こ と を 表 す ．こ こ で ， 𝑆𝑆は バ ー ス の 集 合𝐵𝐵に「 無 し 」を
152
加 え た 集 合 で あ る ． 変 数𝑚𝑚ℎ𝑛𝑛𝑛𝑛 は ， 各 指 定 時 間ℎに ， 各 ト ラ ッ ク𝑚𝑚に つ い て 割 り 当 て ら れ た バ ー ス が𝑠𝑠の 場 合 は 1，そ う で な い 場 合 は 0 と な る 2 値 整 数 変 数 で ，(6.14)式 で 定 義 さ れ て い る ．
(6.3)，(6.4)式 は ，拘 束 条 件(a)に つ い て ，指 定 時 間ℎに お け る グ ル ー プ𝑔𝑔の バ ー ス𝑠𝑠に 対 す る 最 小 台 数𝑠𝑠1ℎ𝑔𝑔𝑑𝑑に 関 す る 制 約 お よ び 最 大 台 数𝑠𝑠2ℎ𝑔𝑔𝑑𝑑に 関 す る 制 約 を 表 し て い る ． ト ラ ッ ク は 車 格 な ど に よ っ て 各 グ ル ー プ に 所 属 す る ． 1 台 の ト ラ ッ ク は 複 数 の グ ル ー プ に 所 属 可 能 で あ る ．
(6.5)式 は ， 拘 束 条 件(b)に つ い て 表 し て い る ． こ こ で は ， 各 バ ー ス𝑠𝑠に お い て ， 集 合𝐺𝐺𝑝𝑝で 指 定 さ れ た グ ル ー プ の ト ラ ッ ク が ２ つ の 指 定 時 間 で 連 続 し て 割 り 当 て ら れ る こ と を 禁 止 し て い る ．
(6.6)式 も ，拘 束 条 件(b)を 表 す 制 約 で あ る ．指 定 時 間ℎの バ ー ス𝑠𝑠に お い て ， 割 り 当 て ら れ る 車 格 （ 小 型 ， 中 型 ， 大 型 等 ） は 1 つ 以 下 と し ， 異 な る 車 格 の ト ラ ッ ク を 同 時 に 指 定 す る こ と を 禁 止 し て い る ．変 数𝑦𝑦ℎ𝑔𝑔𝑑𝑑は ，1 ま た は 0 の 2 値 整 数 変 数 で あ り ，𝑦𝑦ℎ𝑔𝑔𝑑𝑑は(6.15)式 で 定 義 さ れ て い る ．集 合𝐺𝐺𝑘𝑘は ，グ ル ー プ の 集 合𝐺𝐺の う ち ，車 格 を 表 し て い る グ ル ー プ を 抜 き 出 し た も の で あ る ．
(6.7)，(6.8)式 は ，そ の 車 格 が 指 定 時 間ℎの バ ー ス𝑠𝑠に 割 り 当 て ら れ て い る か ど う か を 表 し て い る ．(6.7)式 で ，指 定 時 間ℎ，グ ル ー プ𝑔𝑔，バ ー ス𝑠𝑠に お い
て ，𝑦𝑦ℎ𝑔𝑔𝑑𝑑が 1 な ら ば ， グ ル ー プ𝑔𝑔に 含 ま れ る ト ラ ッ ク が 1 台 以 上 割 り 当 て
ら れ て い る こ と を 制 約 し ，逆 に(6.8)式 で ，グ ル ー プ𝑔𝑔に 含 ま れ る ト ラ ッ ク が 1 台 以 上 割 り 当 て ら れ て い る な ら ば ， 𝑦𝑦ℎ𝑔𝑔𝑑𝑑を 1 と し て い る ． 定 数𝐾𝐾𝑔𝑔は ， 各 グ ル ー プ の ト ラ ッ ク の 数 で あ る ．
(6.9)式 は ，処 理 時 間 が 1時 間 以 上 か か る 場 合（ 次 の 時 間 枠 に か か る 場 合 ） の 制 約 で あ る ． 集 合𝑁𝑁𝐻𝐻は 処 理 が 1 時 間 以 上 か か る ト ラ ッ ク の 集 合 で あ る ． こ の 集 合 で 指 定 さ れ た ト ラ ッ ク𝑚𝑚𝐻𝐻を 割 り 当 て ら れ た バ ー ス は ，次 の 時 間 帯 ， 空 き （ 割 り 当 て 不 可 ） と な る ．
(6.10)式 で ， 処 理 が 1 時 間 以 上 か か る ト ラ ッ ク の 場 合 ， 最 終 の 時 間 帯 に は 割 り 当 て る こ と を 禁 じ て い る ．
(6.11)式 は 拘 束 条 件(c)を 表 す 制 約 で あ り ， 各 ト ラ ッ ク𝑚𝑚が バ ー ス𝑠𝑠に 割 り 当 て ら れ る 総 数 が 1 回 で あ る こ と を 表 す ．
(6.12)式 は ，拘 束 条 件(d)に 関 す る 制 約 で あ る ．各 ト ラ ッ ク の 希 望 時 間𝐿𝐿+ℎ𝑛𝑛
を 使 っ て ， 各 ト ラ ッ ク𝑚𝑚の 指 定 時 間ℎを 制 約 す る ． 希 望 時 間 に マ ッ チ し な い 場 合 （ 違 反 ） を ペナルティ𝑧𝑧ℎ𝑛𝑛 で 認 め る こ と に よ っ て 緩 和 し て い る ．
(6.13)式 は ， 拘 束 条 件(d)の う ち ， 緊 急 性 ， あ る い は セ ン タ ー の 処 理 上 ， ペ ナ ル テ ィ が 許 さ れ な い も の を 表 す ．𝑀𝑀+ℎ𝑛𝑛は ， 各 ト ラ ッ ク の ペ ナ ル テ ィ が 許 さ れ な い 希 望 時 間 で あ る ．
153