数理解析研究所講究録1114 巻 1999 年 194-205

194

時間枠制約付き配送計画問題に対する
局所探索法の適用について
京都大学情報学研究科
心都大学情報学研究科
京都大学情報学研究科

1

増田友泰
柳浦睦憲
茨木俊秀

MASUDA Tomoyasu
YAGIURA Mutsunori
IBARAKI Toshihide

序論

配送計画問題 (Vehicle Routing Problem, VRP) は, 様々な制約条件の下で複数の車両を用い,全ての客をちょうど– 回ずつ訪問するような経路集合の中で, 距離の総和が最短のものを求める問題である. これは, 代表的な組合せ最適化問題の– つであると同時に, 実用性のある問題で, 郵便・新聞配達, 廃棄物収集石油運搬やスクールバスのスケジューリングなどの応用を持つ. この問題は NP 困難であることが知られており, 大規模な問題例に対して厳密な最適解を求めることは現実的に極めて困難であると考えられている. そのような問題に対する妥鰯策として近似解法があり, 配送計画問題に対しても種々の近似解法が提示されている.
本研究では, 配送計画問題の制約条件として, 各車両の容量制約と時間枠制約を取り扱う. 容量
制約とは, -台の車両が訪問する客の要求量の総和が, -台の車両で処理出来る量を越えないというものである. 時間枠制約とは, 客が指定した時間枠内にサービスを開始しなければならないというものである. いずれの制約も, 容量制約のみを課した問題は分割問題を, 時間枠制約のみを課した問題はスケジューリング問題を特殊な場合として含むことから [1], -方の制約のみを課した問完全である. そのため探索を実行可能解に限定
題に対する実行可能解の存在の判定がすでにしてしまう手法 (例えば [2]) では, 制約が厳しい場合には探索が効率よく行えないと考えられる.
また現実問題では, 要求量や時間枠自体があいまいで, 厳密でないことが多い. そこで, これらの制約を考慮制約として扱い, 制約の違反量に応じたペナルティを付加した目的関数を最小化するという方針をとる. 制約を必ず満たす必要がある場合でも, ペナルティを十分大きくとることである程度対応できるので, このような定式化の方がより汎用性が高いと言える.
ところで, このようなペナルティの処理は, 容量制約については容易であるが, 時間枠制約についてこれを実現するためには, -つの車両が処理する客の訪問順序が決まったとき, ペナルティが$\mathrm{N}\mathrm{P}$最小となるような各客のサービス時刻を決定する問題を解く必要がある. 本研究では, この問題が動的計画法を用いて効率的に解けることを示す. なお, 提案する動的計画法は, 時間枠制約に対す
るペナルティ関数が区分線型関数であれば, 不連続や非凸であっても扱える. さらに, この動的計画法を組み込んだ局所探索法を提案し, その効果を計算実験により確認する.

2

問題

本節では, 本研究で扱う時間枠制約付き配送計画問題を定義する. 節点集合 $V=\{0,1, \ldots, n\}$ に対する完全有向グラフ $G=(V, E)$ と車両集合 $M=\{1, \ldots, m\}$ を考える. ここで節点 は “デポ
$0$

195

と呼ばれる特殊な節点であり, また, 他の節点はサービスを受ける客を表す. 各客 $i(i=0,1, \ldots, n)$には, サービスの要求量 (ただし $q0=0$ ), サービス開始時刻に対するペナルティ関数
, サー
ビス時間
$u_{0}=0$(ただし) が与えられ, 各車両 $k(k=1,2, \ldots, m)$ には, 処理できる要求量の上
限とデポを出発する時刻 が与えられる. さらに, 非対称距離行列と非対称移動時間行
列 (t のが与えられる. ペナルティ関数は, 区分線型関数とする. ただし, 非凸, 不連続であっても$p_{i}(t)$$q_{i}$$u_{i}$$Q_{k}$$(d_{ij})$$e_{0}$

良い.
各車両 の客の訪問順序を\mbox{\boldmath $\sigma$}k とし,$k$$\sigma=(\sigma^{1}, \ldots, \sigma^{m})$とする. ただし, 客の訪問順序を決定する

際には以下の制約条件が付く.
$\bullet$$\bullet$

各車両 $k(k=1, \ldots, m)$ はデポを出発し, デポに帰還する.

各客はちょうど 1 回だけある車両によリサービスされる.

このとき, 全ルートの距離の総和を, 各客のサービス時刻に対するペナルティの総和を,
容量超過量の総和をとすると, 上述の 2 つの制約条件を満たした上で最小化すべき目的関数
は以下のようになる.
$D(\sigma)$$T(\sigma)$$Q(\sigma)$cost $(\sigma)=D(\sigma)+\tau(\sigma)+\alpha Q(\sigma)$ .

(1)

ただし, \alpha は, 容量制約違反のペナルティに対する重み係数である.

3

局所探索法.
まず, 局所探索法が探索の対象とする探索空間について考察する. 客の訪問順序\mbox{\boldmath $\sigma$}$=(\sigma^{1}, \ldots, \sigma^{m})$を決定すると, 目的関数におけるとの値は決定される. また,については, 32 節の動的計画法により, を固定するという条件の下で $T(s)$ が最小となるように各客 のザービス
開始時刻 s’ を–意的に決定することができる. 以上より, 探索空間を実行可能解\mbox{\boldmath $\sigma$}の集合とする.
実行可能解\mbox{\boldmath $\sigma$}の近傍 $NB(\sigma)$ とは, \mbox{\boldmath $\sigma$}に対して適当な操作を加えて得られる実行可能解の集合のことである. 局所探索法とは, 現在の解\mbox{\boldmath $\sigma$}の近傍 $NB(\sigma)$ 内に\mbox{\boldmath $\sigma$} より良い解があればそれに置き換
える, という操作を反復するものである.
$D(\sigma)$$Q(\sigma)$$T(\sigma)$$\sigma$$i$

LOCAL SEARCH$(\mathrm{L}\mathrm{S}(\sigma))$$0$. 適当な近似解法で初期解を求め,$k$. \mbox{\boldmath $\sigma$}の近傍$NB(\sigma)$

つかれば, 解を\mbox{\boldmath $\sigma$}$\sigma$とする. $k=1$ とする.

内で\mbox{\boldmath $\sigma$} より良い目的関数値をもつ実行可能解\mbox{\boldmath $\sigma$}’ を探す. そのような\mbox{\boldmath $\sigma$}’ が見$:=\sigma’$と更新したのち $k:=k+1$ として

$k$

へ.

そうでなければ現在の暫定解\mbox{\boldmath $\sigma$} を返す.

局所探索法においては, 近傍をどのように定義するかによって最終的に得られる解の精度が大きく異なる. したがって個々の問題に応じた効率の良い近傍を定義する必要がある. 以下では, 本研究で用いる 3 つの近傍について述べた後, それらの近傍の探索順序について述べる. 次に, ルートが与えられた時の起動の最適なサービス時刻を決定する動的計画法について述べる. なお, 局所探索法において, 近傍内の解をどのような順序で調べるかには色々考えられるが, これを順序良く行うことで, 動的計画法の 1 回あたりの計算量を大幅に削減できる. よって, 本研究で提案する局所探索法の詳細と, 動的計画法のそのような高速化については, 最後にまとめて説明を行う. また,暫定解の評価法についても簡単に触れる.

196$\langle \mathrm{b})$$\{l)$$\iota 7$$\iota$.

I$i_{l}*lj,\iota$$j\iota\star l\mathfrak{x}$$(\beta)j^{\mathrm{j}}\prime_{r}8t_{\mathrm{J}*}*\mathrm{J},*\prime 1r\mathrm{I}^{l_{\mathrm{J}}}r:+r$

電 1: クロス交換近傍 (a), 2-opt*近傍 (b), およびルート内挿入近傍 (c) の操作の例.
と反転する場合 (b) の 2 通りを示す.
(c) については, パスの順序を変えない場合$(\alpha)$

3.1

近傍
クロス交換近傍と 2-opt*近傍311

異なる 2 つのルート間にまたがる近傍操作としてクロス交換操作と 2-opt*操作がある.
まずクロス交換操作であるが, これは, 異なる 2 つのルートのそれぞれから長さ Lcross 以下のパスを選び, それらを互いに交換する操作である (図 1 ). そして, 現在の解\mbox{\boldmath $\sigma$} に対してこの操作をと呼ぶことにする. 現在
加えることによって得られる解集合の全体をクロス交換近傍とに対してクロス交換操作を行って得らの解\mbox{\boldmath $\sigma$}について, 2 つの異なるルート$A,$) とすると,れる解集合を$(\mathrm{a})$$N^{cros\theta}(\sigma)$$\sigma^{A}$$=(\sigma^{1}, \ldots, \sigma^{m})$$\sigma^{B}$$B$$N^{CroS}s_{(\sigma},$(2)$N^{cross}(\sigma)=\cup N^{CroSs}(A<B\sigma, A, B)$

となる.

.

.

2-opt*近傍操作とは, 異なる 2 本のルートそれぞれから 1 本ずつ枝を取り除くことで, 各ルート).
を前半と後半の 2 つのパスに分け, 後半のパスをルート間で互いに交換する操作である (図$1(\mathrm{b})$2 つの異なるルート近傍の全体を$\sigma^{A},$に対して 2-opt*操作を行って得られる解集合を $N^{2opt}(*\sigma, A, B),$ 2-oPt*と表すと,$\sigma^{B}$$N^{2opt^{*}}(\sigma)$$N^{2opt^{*}},(\sigma)=A<B\cup N2oP^{t^{*}}(\sigma, A, B)$

(3)

となる.

3.1.2

ルート内挿入近傍

同–ルート内での近傍操作としてルート内挿入操作がある. これは, 長さ Llntra 以下のパスを同ルートの他の位置へ挿入する操作 (図 1 ) で, この操作によって得られる解集合をルート内挿に対してルート内挿入操作を行って得られる解集合を $N^{intra}(\sigma, A)$ , ルー
入近傍と呼ぶ. ルート
ト内挿入近傍の全体を $N^{inta}r(\sigma)$ と表すと,$(\mathrm{c})$$\sigma^{A}$$N^{intra}(\sigma)=\cup N^{int_{T}}A\epsilon Ma(\sigma, A)$(4)となる. なお, ルート内挿入近傍においては, 取り除いたパスの順序を反転させて挿入するという操作も加える. この操作を加えても, 332 節で述べる計算方法によって, これを行わない場合とオーダー的にほぼ同等の計算時間でコストの変化量の計算が可能である.

197
313

探索順序

本研究の局所探索法における上記で定めた近傍の探索順序は,
1. ルート内挿入近傍探索
2. 2-opt*近傍探索
3. クロス交換近傍探索である. さらに, 各探索は, その近傍内での解の改善が起こらなくなるまで行う. すなわち, ある探索によって解の改善が起こると, 繰り返し同じ近傍を探索するのである. また, クロス近傍探索を終えるとルート内挿入近傍探索に戻る. このループは, 上記の 3 つの近傍全てにおいて解の改善が起こらなくなるまで続ける.

3.2.

与えられたルートの最適サービス時刻の決定法

あるルートの客の訪問順序が与えられた時に, そのルートの時間枠に関するペナルティの総和が最小となるように, 各論のサービス時刻を決定する問題を考える.
車両 k が 番目に処理する客が であるとき, $\sigma^{k}(h)=i$ と記す. ルート
内の客数を
, 時間
枠制約のペナルティを表す区分線型関数の区分の数を, 車両 が処理する全ての客について和をとったものを\mbox{\boldmath $\delta$}k とする. また, 便宜上, $\sigma^{k}(0)=0,$ $\sigma^{k}(n_{k}+1)=0$ とおく,
本節では, このサービス時刻決定問題が動的計画法を用いて時間で計算出来ることを示す. この問題は, 各客のペナルティ関数が凸関数ならば, 凸計画問題として定式化でき, 汎用的な解法で解ける. –方, 本研究で提案する動的計画法では, ペナルティ関数が非凸や不連続であっても効率良く解ける.
$h$

$i$

$\sigma^{k}$$n_{k}$$k$$o(n_{k}\delta_{k})$’321アルゴリズムルート$\sigma^{k}$の最適サービス時刻の決定を考える. 関数を, ルートにおける 番目の客のサービス開始時刻が 以前であるときのペナルティの最小値と定義し, これを以後, 前向きペナル
ティ最小関数と呼ぶ. また, 便宜上,
を車両 k が 番目に処理する客の時間枠に対するペナル$f_{h}^{k}(t)$$\sigma^{k}$

$h$

$t$

$h$

$p_{h}^{k}(t)$

ティ関数,
とする.

$\tau_{h}^{k}$

このとき

を

$h$

$f_{h}^{k}(t)$番目の客から $h+1$ 番目の客までの移動時間と$h$

番目の客のサービス時間の和は次の漸旧式により計算される.
$+\infty$$f_{0}^{k}(t)=$

$\{$

$0$

$f_{h}^{k}(t)=$,,$t\in(-\infty, e\mathrm{o})$$t\in[e_{0}, +\infty)$$\min_{t’\leq t}(f_{h-1(t-}^{k.\prime}\mathcal{T}_{h-}1)k(+_{\mathrm{P}^{k/}}ht))$,$1\leq h\leq n_{k}+1$.

(5)を用いるが, このときシフトしていることに注意する. ルート全体のペナルティの最小値は $\min_{t}f_{n_{k}+}^{k}1(t)$ で求まる. 各客の最適サービス時刻と車両 がデポに帰還する時刻$h=1,$
は上記の漸化式 (5) で求めた$h=$$f_{h}^{k}(t)$$s_{\sigma^{k}(h)},$の計算には$\ldots,$$n_{k}$$f_{h-1}^{k}(t)$$f_{h-}^{k}1(t)\text{を右へ}\tau_{h-}^{k}l$$k$$s^{k}$$f_{h}^{k}(t),$198

1, ..., $n_{k}+1$ を用いて次の漸化式より計算される. なお, 漸化式中では, $s_{0}=g^{k}$ と解釈する.
$s^{k}= \min\arg\min_{t}f_{n+1}^{k}k(t)$$\min$$s_{\sigma^{k}(h)}= \min\arg$$f_{h}^{k}(t)$,$1\leq h\leq n_{k}$.

(6)$t\leq s_{\sigma^{k}(+1}-\mathcal{T}^{k}h)h$3.2.2

アルゴリズムの実現と時間量の評価

が区分線型関数-C-“ あること\mbox{\boldmath $\phi$}1も区分線型関数となる. よって, これらの関数を, 関数の各区分を要素とする連結リス
ら,トで記憶する. すなわち, リストの要素には区分線型関数の各区間とその区間での関数が記憶さの計算では, まず,れる.
の各区間を\tau hk-l シフトし, $f_{h-1}^{k}(t-\tau^{k}h-1)$ を求める. 次に,$f_{h-1}^{k}(t-\tau h-1)k$ とを, 区間の区切りをマージしつつ, 各区間に対応する線型関数を足し合わ(t–\tau hk-l)+pkh(科を求め, 新たな連結リストに保持する. 最後に, 得られたリスせることで,
トを の小さい方から順に走査しつつ, 最小値の計算を行う.
からとであるので,
それぞれの区間の最大数はと関数関数を求める計算は O(\mbox{\boldmath $\delta$}の時間で可能である. ペナルティの総和の計とを走査するだけなので,
算 (3.2.1) と各客のサービス時刻の決定の計算 (6) は, ともに時間で計算できる. 以上より, ルートのペナルティの総和の最小値と各客の最適サービス時刻は,時間で計算できる.
全体で
-

壷化式

’ を計算するための T-“—- 夕横造 1\mbox{\boldmath $\zeta$}ついで考える.

$p_{\mathrm{L}}^{k}.b\backslash (t)$,$(5)\backslash$$f_{h}^{k}(t)$$f_{h-1}^{k}(t)$$f_{h}^{k}(t)$$p_{h}^{k}(t)$$f_{h-1}^{k}$$t$$f_{h-1}^{k}(t)$$f_{h-1}^{k}(t-\mathcal{T}_{h-1})+p_{h}^{k}(t)$$f_{h-1}^{k}(t)$$O(\delta_{k})$$p_{h}^{k}(t)$$p_{h}^{k}(t)$$f_{h}^{k}(t)$$O(\delta_{k})$$f_{h}^{k}(t)$$O(n_{kk}\delta)$

3.3

局所探索法の高速化

この節では, 探索を高速化するための方法を 2 つ提案する.
まず, 1 つ目は解の改善が見込まれない近傍を探索しないようにすることである. そのために,との各行, 各列と$m\cross m$ 行列, 要素数 $m$ の配列 を用意する. 行列$(c_{k,\dot{k}}’)$$I$$(\mathit{0}_{k,k}’)$$(c_{k,k’})$$(\mathit{0}_{k,k’})$はルートに対応し, $(k, k’)$ 要素には, それぞれ, クロス交換操作, 2-opt*操作によるルート
間での解の改善に関する情報を保持する. また, 配列 I の第 k 要素には, ルート内挿入操作によるについては, 前回
ルート
での解の改善に関する情報を保持する. すなわち,のいずれかに変更が
ルートに改善解が存在しないと判定された以降の探索において,加えられた場合には, $c_{k,k’}=1$ とし, それ以外では $c_{k,k’}=0$ と定義する. $(o_{k,k}l)$ と配列 I の各要の探索を $c_{k,k’}=1$ のときに限り行うものとする.
素も同様に定義する. そして,Nintra についても同様である. こうすることにより, 改善の可能性のない近傍解探索を省$\sigma^{k},$$\sigma^{k’}$$N^{\mathrm{c}rosS}(\sigma, k, k’)$$\sigma^{k}$$c_{k,k’}$$\sigma^{k}\text{または_{}\sigma}k’$$N^{\mathrm{c}roSs}(\sigma, k, k^{/})$$N^{2opt^{*}},$

くことができる.
もう –方の方法は, 解の評価法を工夫することにより, 時間ペナルティの評価を高速化できるというものである. 現在の解を\mbox{\boldmath $\sigma$}curr, 近傍 $NB(\sigma^{curr})$ 内のある解を\mbox{\boldmath $\sigma$}new とすると, 解の改善が起こるのは, 以下で定義する $\Delta cost$ が正となるときである.
$\triangle cost$

ここで\Delta D は解\mbox{\boldmath $\sigma$}curr の距離の総和と$=$cost $(\sigma)curr-cost(\sigma)new$$=$$\Delta D+\Delta\tau+\alpha\triangle Q$$\sigma^{n\mathrm{e}w}$の距離の総和の差, \Delta T は解\mbox{\boldmath $\sigma$}curr の時間ペナルティのの時間ペナルティの総和の差,
総和と量の総和の差である. 以下の節では, これら$\sigma^{n\mathrm{e}w}$

察する.

(7)

$\triangle Q$

は解\mbox{\boldmath $\sigma$}curr の容量超過量の総和と$\triangle D,$$\triangle T$$\sigma^{new}$の容量超過, および\Delta Q の計算に要する時間について考

199

331

$\Delta D$について\Delta D=(取り除かれる枝の距離の和) –(挿入される枝の距離の和)によっそ\Delta D は計算される.

クロス交換近傍と 2-opt*近傍においては, 取り除かれる枝の本数と挿入される枝の本数は定数であるので, \Delta D の評価は定数時間で可能である. ルート内挿入近傍においては, 反転の操作のときに, 反転されるパス上の全ての枝について距離を再計算する必要がある
ので,$\triangle D$

3.3.2の評価は $O(L^{intr}a)$ となる.

\Delta T について\Delta T は, 近傍操作の対象となる 2’\supset (ルート内挿入操作の場合は 1 つのみ) の解に対するペナル
ティの変化量のみを計算すれば求まる. しかし, この計算を, 32 節で述べた前向きペナルティ最小関数の漸化式 (5) を毎回計算し直していたのでは効率が悪い. そこで, 以下に述べる関数 bkh(科をあらかじめ用意しておくことで, この部分の計算の高速化を図る.
関数を, ルート における 番目の客のサービス開始時刻が 以後で, 客\mbox{\boldmath $\sigma$}\mbox{\boldmath $\sigma$}k $(h),$$1),$
をサービスするときのペナルティの最小値と定義し, これを以後, 後ろ向きペナル
ティ最小関数と呼ぶ. すると,
(科の計算と対称的に, 以下の漸化式より計算できる.
は,$\sigma^{k}$$b_{h}^{k}(t)$$h$$\sigma^{k}(h+$$t$$\sigma^{k}(n_{k})$$\ldots,$$b_{h}^{k}(t)$$f_{h}^{k}$$b_{n_{k}+1}^{k}(t)=$$p^{k/}0(t)$$\min_{t\leq t},$$b_{h}^{k}(t)=$$\min_{t\leq t<},(b_{h+1(}^{k/k}t+\mathcal{T}_{h})+p^{k\prime}h(t))$,(8)$.1\leq h\leq n_{k}$
.

ある

$h$

に対し, 前向きペナルテと後ろ向きペナルテイ最小関数のペナルティの最小値$\triangleleft’\text{最小関}\dot{\text{数}}f^{k}h(\grave{t}\backslash )$れば, これらを利用することにより, ルート$\sigma^{k}$$\min_{t}f_{n_{k}}^{k}+1(t)$

は,

が既知であ
’

(9)

$\min_{t}(f_{h}^{k}(t)+b_{h+1}^{k}(t+\tau_{h}^{k}))$と計算できる. この計算は$b_{h+1}^{k}$

で可能であるため, 漸化式 (5) を再計算するよりも効率的である.
局所探索法の近傍内の探索順序を工夫することで, 各\Delta T の計算にこのアイディアを利用できる.
なお, この場合, 各類に対する前向きと後ろ向きのペナルティ最小関数をあらかじめ計算して記憶しておき, さらに, 解の更新時には, 変更の加わったルートに含まれる全ての客に対してこれらの関数を計算し直す必要があるが, 通常, 解の評価回数に比べて解の更新回数は十分小さいため, 問$O(\delta_{k})$

題はないと考えられる. 以下では, 各近傍について\Delta T の計算法の詳細を述べる. なお, $\tau(h, h’)$ を
客 から客 h’ への移動時間と客 でのサービス時間との和, すなわち, $\tau(h, h’)=u_{h}+t_{h,h’}$ とする.
$h$

$i$

クロス交換近傍における高速化
ノレ一トとに対するクロス交換操作を考える. ここで,
$i\geq j$ は客\mbox{\boldmath $\sigma$}k (i) からまでのパスを記すものとする. なお, $i<$ j のときは空パスを示すものとする. さて,$N^{cross}(\sigma, k, k’)$ の解を, 以下の 4 重ループに示す順序で探索する.
$\bullet$$\sigma^{k}$$\sigma^{k’}$$\sigma^{k}(i)arrow\sigma^{k}(j),$$\sigma^{k}(j)$for $i_{1}=0,1,$
do
for $i_{2}=0,1,$do$j_{1}=i_{1},$$i_{1}+L^{cross}$ do$i_{1}+1,$
for$j_{2}=i_{2},$$i_{2}+L^{cross}$ do$i_{2}+1,$for$\cdots,$ $n_{k}$$\cdots,$ $n_{k’}$$\cdots,$$\cdots,$

200

{パス
新しい解の評価を行う}$\sigma^{k}(i_{1}+1)arrow\sigma^{k}(j_{1})$とパス $\sigma^{k’}(i_{2}+1)arrow\sigma^{k’}(j_{2})$ を交換して得られる

end forend forend forend for$\sigma^{k}$のパス $\sigma^{k}(i_{1}+1)arrow\sigma^{k}(j_{1})$ と$\sigma^{k’}$のパス $\sigma^{k’}(i_{2}+1)arrow\sigma^{k’}(j_{2})$ を交換するときのコストを考える.

まず, クロス交換操作によって得られる新しい 2 本のルートの内, \langle デポ$\sigma^{k}(i1+1)arrow$ デポというルートについて考える. このノレ一 }が既知であれば,と記すことにする.
前向きペナルティ最小関数をいるので, このルートに対する時間帯ペナルティの最小値は,$arrow\sigma^{k}(i_{1}),$ $\sigma(k^{\dagger}i_{2}+1)arrow$$\backslash \#^{arrow}\llcorner \text{おける客}\sigma(j_{2}k’)$$\sigma^{k’}(i_{2}),$$\rangle$$f_{j_{2}}(t)$$f_{j_{2}}(t)$$b_{j_{1}+1}^{k}$までのは記憶されて(10)$\min_{t}[f_{j_{2}}(t-\tau(\sigma^{k}(j2)’, \sigma^{k}(j1+1)))+b_{j_{1}}^{k}+1(t)]$の計算であるが, 上記のループでは はまず に設定される. このとと計算できる. さて,となる. これ以降は,
からは, 空のパスが抜かれると解釈できるので,き, ルートは式 (5) と同様の漸化式の増加とともにデポから までの客数が 1 ずつ増えていくので,$i_{2}$$j_{2}$$f_{j_{2}}(t)$$f_{j_{2}}(t)=f_{i_{1}}^{k}(t)$$\sigma^{k’}$$f_{j_{2}}(t)$$j_{2}$$\dot{J}2$

時間で計算できる. もう –方の新しいルートについても同様である.
式 (10) の計算は, 2 つの関数の和をとり, 和をとった関数をスキャンするだけなので,時間となる.
時間で可能である. 以上より, クロス交換操作における\Delta T の計算量は,により,$O(\delta_{k}+\delta_{k’})$$O(\delta_{k}+\delta_{k’})$$O(\delta_{k}+\delta_{k’})$

交換近傍における高速化.
ルート . とに対する 2-oPt 交換操作を考える. このとき, 交換の対象となる枝が ( (i1),$\sigma^{k}(i_{1}+l))$ とであるとする. まず, 得られる新しい 2 本のルートの内, ノレ一はすでに記とト \langle デポ(i1), $\sigma^{k’}(i_{2}+1)arrow$ デポ について考える. この場合,憶されているので, 時間枠ペナルティの最小値は, (9) 式と同様に$\bullet$$2-\mathrm{o}\mathrm{p}\mathrm{t}^{*}$$\sigma^{k}$$\sigma^{k}$$\sigma^{k’}$$(\sigma^{k’}(i2), \sigma^{k’}(\dot{i}2+1))$$arrow\sigma^{k}$$f_{i_{1}}^{k}(t)$$\rangle$$b_{i_{2}+1}^{k’}(t)$$\min_{t}[f_{i_{1}}^{k}(t-\tau(\sigma^{kk}(i1), \sigma(j2+1)))\prime\prime]+b_{i_{2}}^{k}(+1t)$と計算できる. この計算は前述の式 (10) と同様に$\bullet$$O(\delta_{k,k’}\delta)$(11)

時間で可能である.

ルート内挿入近傍における高速化
ルート$\sigma^{k}$に対するルート内挿入操作を考える. このとき, 近傍 $N^{intra}(\sigma, k)$ 部分集合は, 以下の2 組の 3 重ループに示す順序により生成される.

, Lintra(取り除くパスの長さ) doline 1for $r=1,$
doline 2for $i=0,1,$doline 3for $j=i,i+r+1,i+r+2,$$\sigma^{k}(i+r+1)arrow\sigma^{k}(j),$ $\sigma^{k}(i+1)arrow\sigma^{k}(i+r),$ $\sigma^{k}(j+1)arrow$ デポ
line 4{ノレ一 } (デポの評価を行う (通常挿入の場合)
line 5$\sigma^{k}(i+r+1)arrow\sigma^{k}(j),$ $\sigma^{k}(i+r)arrow\sigma^{k}(i+1),$ $\sigma^{k}(j+1)arrow$ デポ
line 6{ノレ一 }, (デポの評価を行う (反転挿入の場合)
line 7line 8end forline 9dofor $j=i-1,i-2,$
linelO$\sigma^{k}(i+1)arrow\sigma^{k}(i+r),\sigma^{k}(j+1)arrow\sigma^{k}(i),\sigma^{k}(i+r+1)arrow$ デポ
ト(デポ
linell{$\cdots$$\cdots,n_{k}$$\cdots,$ $n_{k}$$\sim$$arrow\sigma^{k}(i),$$\rangle$$\}$$arrow\sigma^{k}(i),$$\rangle$$\}$$\cdots,0$$y\triangleright-$$arrow\sigma^{k}(j),$$\rangle$

201の評価を行う (通常挿入の場合)
line12$\sigma^{k}(i+r)arrow\sigma^{k}(i+1),$
line13{ノレ一 } \langle デポの評価を行う (反転挿入の場合)
line14line15end forline16end forline17 end for$\}$$arrow\sigma^{k}(i),$$\backslash$$\sigma^{k}(j+1)arrow\sigma^{k}(i),$ $\sigma^{k}(i+r+1)arrow$

デポ)}

$\}$

新しく生成されるルートにおける客\mbox{\boldmath $\sigma$}k(i) の前向きペナルティ最小関数をと表すことにする. まず, line 3 で始まる for ,について考える. 通常挿入の場合,が既知であれば, 挿入されたパス $\sigma^{k}(i+1)arrow\sigma^{k}(i+r)$ 上の全ての客に対して, $i+1$ , i+2, . . の順に漸化式 (5) の計$f_{i}(t)$$r\triangleright-\text{プ}$$f_{j}(t)$$\cdot$算を行えば $f_{i+r}(t)$ が求まり, これと記憶されている$b_{j+1}^{k}(t)$を用いて, 新たなルートに対する時間

枠ペナルティの最小値は,(12)$\min_{t}[f_{i+r}(t-\tau(\sigma^{k}(i+r),.\sigma^{k}(j+1)))+b_{j}k(+1)t]$と計算できる. また, 反転挿入のときも同様である. これらの計算は, 漸化式 (5) の計算を $o(r)$ 回行うことでできるので,時間で可能である.
上記の/L/–フ o では fl はまずに設定されるので, $f_{j}(t)=f_{i(t)}^{k}$ とな
さて,の計算であるが,る. これ以降は, fl はまず $i+r+1$ に設定され, さらに 1 つずつ増加していくが, それとともにパ$O(r\delta_{k})$$f_{j}(t)$ス\langle デポ$arrow\sigma^{k}(i),$ $\sigma^{k}(i+r+1)arrow\sigma^{k}(j)\rangle$

様の漸化式により各 に対して
なお, line 3 で始まる for$j$内の回数が 1 ずつ増えていくので,$f_{j}(t)$は式 (5) と同時間で計算できる.
.

$O(\delta_{k})$では, 取り除いたパスを挿入する位置が, ルートの進行方向において取り除いた位置よりも後方に限定されている (すなわち $l_{1}<i_{1}$ の場合は考えていない). そこで, 前方への挿入も考慮するために, linelO で始まる for ループが必要となる. このノ–. でのペナルティ計算は, line 3 で始まる for ループに対する上述のアルゴりごムを, 前向きペナルティ$J\mathrm{s}-\text{フ^{}\mathrm{p}}$$\text{フ^{}\mathrm{p}}$最小関数と後ろ向きペナルティ最小関数の役判を入れ替えて, 対称的に行うことで, 同様の計算時..

間で可能である.
.

以上の考察と,$r\leq L^{intra}$であることから, 一回あたりの$T(\sigma^{k})$の計算は,能であることがいえた.

3.3.3$\triangle Q$$o(\delta^{k}L^{i}ntra)$

時間で可

.

について

各ルートに対し, ルート内の客の総要求量をあらかじめ計算し, 記憶しておく. 近傍操作の前後でのこの値の変化を考える.
} 内挿入近傍では, この値は変化しない. クロス交換近傍と2-opt*近傍では, 交換操作の対象となる 2 つのルートの値が変化する. 以下では, この変化量の効率的計算法を示す.
$J\mathrm{s}-$ルート$\sigma^{k}$

内の

$i$

$\sim$

番目の客のサービス要求量を$q_{i}^{k}$と表す. このとき, ルート$\sigma^{k}$

内の各客垣こ対して, 累積要求量を,$c_{0}^{k}=0$$c_{i}^{k}= \sum_{p=1}^{i}q_{p}^{k}=c_{i-1}^{k}+q_{i}^{k}$と定義し, 記憶しておく. この計算は, ルート$\sigma^{k}$,$i=1,$(13)$\ldots,$$n_{k}$

に対して全体で $O(n^{k})$ で計算できる. すると, ルー

ト内の 番目から j 番目の客による部分パスの総要求量は,となり, 定数時間で計算できる. 局所探索を行うときの初期解の設定時と, 解の更新が行われたときに, 新しく生成されたルートに対して, ルート内の客の総要求量とを再計算する必要があるが, これは生成されたノ\leftarrow } の
長さの時間で可能であり, それ以外の\Delta Q の計算は定数時間で可能となる.
$i$$c_{j}^{k}-c_{i1}^{k}-$$c_{i}^{k}$$\backslash$

202

34

暫定解についてこの節では, 最良解の定義とその更新について述べる. 本研究の定式化では, 容量制約と時間枠制約を考慮制約として扱っているため, 局所最適解が, 容量制約と時間枠制約を絶対制約として扱
うときの実行不可能解となる場合がある. しかし, 探索の過程で評価する解の中には, 絶対制約を全て満たす解が存在する場合がある. 応用によっては, ペナルティ付き目的関数に対する局所最適解よりも, そのような解の方が重要である場合もあると考えられるので, 探索中に保持する暫定解を更新する基準として, 目的関数 (1) とは別の評価基準を設けることを許す (もちろん目的関数(1) をそのまま用いることも可能である). この基準となる評価関数を $best-eva\iota(\sigma)$ と記す.

4

反復局所探索法

この節では, メタヒューリスティクス (メタ解法, メタ戦略) の–種である反復局所探索法 (Iterated
Local Sear $ch$ , ILS) の説明をする.
反復局所探索法とは, 局所探索法を複数回適用し, 全ての探索の中で最も良い解を出力すると$\mathrm{A}\mathrm{a}$う方法であるが, 各反復の初期解の生成においてそれまでの探索で得た情報を用いるところにそ.
の特徴がある. その概略は下記のようなものである.
.: .

ITERATED LOCAL SEARCH (ILS)
1. 初期解\mbox{\boldmath $\sigma$} を生成し,

2. 局所探索法により$\sigma^{seed}:=\sigma,$$\sigma$$\sigma^{best}:=\sigma$とする.

を改善する. すなわち,

3. best-eval $(\sigma)<best$ -eval$(\sigma^{b\mathrm{e}St})$

4. cost $(\sigma)<cost(\sigma^{Seed})$ ならば,

ならば,$\sigma$$:=.LS(\sigma)$$\sigma^{b\mathrm{e}st}:=\sigma$$\sigma^{seed}:=\sigma$

.

とする.

とする.

5. 停止条件が満たされれば\mbox{\boldmath $\sigma$}best を出力して終了. そうでなければ\mbox{\boldmath $\sigma$}seed に少しだけ変形を加えて, 新たな初期解\mbox{\boldmath $\sigma$} を生成し, 2 に戻る.
ステップ 5 における\mbox{\boldmath $\sigma$}seed の変形は, 解の構造があまり変化しないような操作を利用してしまうと, 次の局所探索において同じ局所最適解が出力される可能性が高いので, そのようなことが出来るだけ起こらないように変形を加えなければならない. 本研究では, ランダムなクロス交換操作を用いた. ランダムなクロス交換操作とは, 異なる 2 本のルートをランダムに選択し, さらにそれらの中から交換されるパスの位置と長さをそれぞれランダムに選択し, 交換を行うというものである. そして, $\text{この操作を_{}\sigma^{s}}eed$ に対して r 回 (H はパラメータ) 繰り返して, 新しい初期解\mbox{\boldmath $\sigma$} を得る. 本研究の局所探索法では, 初期解に対して, まず, ルート内挿入近傍により, 同–ルート内の改善を行うので, 解の構造が前回の局所最適解と異なるようになり, 新しい探索によって得られる局所最適解が, 以前のものと –致することが少なくなると考えられる.

5

計算実験

実験は, ワークステーション Sun Ultra 2Model 2300 (300を用いて行った.

$\mathrm{M}\mathrm{H}\mathrm{z},$$1$

GB memory) 上で$\mathrm{C}$

言語

203

5.1

問題例

用いた問題例は, Solomon のベンチマーク問題 (http://dmawww.ep 乱 ch/rochat/rochat-data/solomon html) [3] である. この問題は, $[0,100]2$ の正方形内に 100 人の客が分布しており, 各客間の距離は, ユークリッド距離で与えられる. 移動時間は距離に等しい. 各客 には, 時間枠],
要求量 , サービス時間 が与えられている. 各車両の容量制約は全て等しく, その値としてある
一定値が与えられている. このベンチマーク問題では, 容量制約と時間枠制約を絶対制約として扱う. これらの問題は, 客の分布と時間枠の与え方により, いくつかのタイプに分類されている. 客の3の分布については, タイプ, および, 時間枠については.\acute タイプ 1 と 2 の 2 つがある. これら全ての組合せを考え, Rl, Cl,の 6 タイプが与えられている.
, R2, C2,タ
イプでは, 客が–様に分布しており,タイプでは, 10 人を 1 グループとする 10 グループが, そ
れぞれ固まって分布している.
タイプは, 両方のタイプの性質をおり混ぜたものとなっている.
また, タイプ 1 では, デポの時間枠が短く, そのため各客の時間枠を満たしてサービスを行う場合,比較的多くの車両が必要となる. それに対してタイプ 2 では, デポの時間枠が長く, 少数の車両で全ての客の時間枠を満たしながら, サービスを行うことが可能である.
容量制約と時間枠制約を絶対制約として扱うことから, 34 節で述べた $best-eva\iota(\sigma)$ としては,の辞書式順に最小化を行うという評価基準を用いた. 本研究のアルゴリズムの評価は, この評価基準で得られる暫定解の精度で測るものとする. また, 各客 のサービス開始時
刻に対するペナルティ関数としては,$i$$1^{e_{i},l_{i}}$$u_{i}$$q_{i}$$\mathrm{R},$$\mathrm{C}$$\mathrm{R}\mathrm{C}$$\cdot \mathcal{D}$$\mathrm{R}\mathrm{C}1$$\mathrm{R}\mathrm{C}2$$\mathrm{R}$$\mathrm{C}$$\mathrm{R}\mathrm{C}$$Q(\sigma),$ $T(\sigma),$ $D(\sigma)$$i$$w(e_{i}-t)$$p_{i}(t)\backslash =\{$

$0$,$w(t-l_{i})$,$t<e_{i}$.

(14)$e_{i}\leq t\leq l_{i}$,$l_{i}<t$を用いることにする. ここで, $w$ はパラメータである. さらに, 本実験においては, $L^{cross}$ と $L^{intra}$の値は等しいものとし, これ以降 $L$ と表記するものとする.
.
‘

52

本研究のアルゴリズムの性能評価

各問題例に対してパラメータを設定して反復局所探索法を適用し, 文献 [4] に掲載されているこのベンチマーク問題に対して出されている最良解との比較を行う. なお, 車両台数は, 文献 [4] で.

報告されている解に用いられた台数とした. 反復局所探索の停止条件は以下のように定める.

$\bullet$タイプ 1 の問題例に対しては, 1800 秒で探索を打ち切る.
タイプ 2 の問題例に対しては, 3600 秒で探索を打ち切る.
$\mathrm{A}$

ただし, 停止時刻において実行されている局所探索法は終了せず, 局所最適解が求まるまで探索を続ける. 結果を表 1 と表 2 に示す. これらの表において, $D$ は各ルートの総距離の和を表し, T は時間枠からのサービス開始時刻のずれの総和を表している. 全ての解において容量制約は満たされの値は省略した. よって, $T=0$ の場合は, 容量制約と時間枠制約を絶対制約とみているので,
なしたときの実行可能解となっている. なお, 最も右の列のおける は, 本研究の結果が, 現在までに知られている最良解と同等の解を出したことを示しており, また, $**$ はそれを更新したことを示している. これより, タイプ C の問題例に対しては, ほとんどの問題例について, 等しい精度の解を得ていることが分かる. また, 他のほとんどの問題例についても, ほぼ同程度の精度の解を得ていることが観測できる.
$Q$

$*$

204

表 1: これまでの最良解と本研究の最良解の比較 (1)6$\cdot$まとめ

時間枠制約付き配送計画問題の解法の–つとして, 動的計画法を用いて各客の最適サービス時
刻を決定することを局所探索法に組み込んだ解法を提案した. 代表的なベンチマーク問題に対す
る計算実験の結果より, 時間枠制約を考慮制約にした本研究のアルゴリズムは, 汎用的な解法であるにもかかわらず, 従来の方法に匹敵する性能を持つことが確認できた.
今後の課題として, 近傍の縮小やより効果的な近傍を考えることにより, 局所探索法 1 回あたりに要する時間の短縮が挙げられる. また, タブー探索法などの他のメタヒ 一リスティクスと組合$\mathrm{n}$せることなども考えている.

205

表 2: これまでの最良解と本研究の最良解の比較 (2)

参考文献[1] M. R. Garey and D. S. Johnson, Computers and Intractability, Freeman (1979).
[2] J. Y. Potvin, T. Kervahut, B. L. Garcia and J. M. Rousseau, “The Vehicle Routing Problem
with Time Windows. Part 1: Tabu Search,” INFORMS Journal on Computing, Vol.8, No.2,
158-164 (1996).

[3] M. M. Solomon, “The Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operations Research, Vol.35, No.2, 254-265 (1987).
[4] E. Taillard, P. Badeau, M. Gendreau, F. Guertin and J. Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Sciencef
Vol.31, No.2, 170-186 (1997).