社会技術研究論文集

Vol.7, 131-138, Mar. 2010

積載量制約のある複数車両による辺巡回配送計
画問題の模擬焼きなまし法を用いた近似解法
A Heuristic Approach to Capacitated Arc Routing Problem Using Simulated Annealing
松本

1

修一 ・平島2

浩一郎 ・國府方1Ph.D.（工学）慶應義塾大学講師

3

久史 ・川嶋4

弘尚

先導研究センター (E-mail: shuichi@ae.keio.ac.jp）

2M.S.（工学）元慶應義塾大学大学院理工学研究科
3M.S.（工学）慶應義塾女子高等学校教諭 (E-mail:4Ph.D.（工学）慶應義塾大学教授

kokubu@mita.cc.keio.ac.jp)
理工学部 (E-mail:kawashima@ae.keio.ac.jp)

積載量制約のある複数車両による辺巡回配送計画問題は，容量制約つき枝巡回問題とも呼ばれ，節と辺によるネットワーク上で，辺にデマンドがある場合において，配送拠点から容量制約つきの車両がデマンドのあるすべての辺を巡回し配送拠点へ戻るときの巡回総コストが最小となるルートを求める問題である．
配車配送計画の効率化には，ネットワークの節にデマンド指定がある車両巡回問題が用いられる例が多い．
しかし，郵便配達のようなデマンドが密集した場合や，道路清掃など道路区間そのものにサービスを行う
場合には，辺にデマンド指定があるCARPのアプローチの方が適している．本研究では模擬焼きなまし法を用いたCARPの近似解法を提案した．

キーワード：ロジスティクス，配送計画問題，CARP，模擬焼きなまし法，ストリングモデル

1. まえがきRouting Problem:以下「VRP」と記す )である．この問題は，指定された節上にあるデポから容量制約のある複数の車両が出発し，分担して節にあるデマンドをすべて巡回しデポへ戻ってくるときのコストが最小となるルートを探す問題であり，現実で使われている多くの配送計画シス
テムに応用されている．また現実的な配送問題に対応するべく配送時間指定に対応したVRP with Time Window (以都市におけるロジスティクスの合理化は，配送コストの削減による経済活性化に寄与するだけでなく，走行距離の減少による二酸化炭素削減効果等環境の改善にも効果をもつものと考えられる．本研究は，道路に沿って密集した配達箇所がある郵便配達やごみ収集および道路清掃など，道路区間に配送･収集などのデマンドがあると考えられる配送計画問題における解法を提案するものである．このような問題は，積載量制約のある複数車両による辺巡回配送計画問題(Capacitated Arc Routing Problem:以下「VRPTW」と記す)，配送と集荷を同じ車両の経路で行うVRP-Backhaul など様々なバリエーションが考案されている3)．
一方，ARPの中でVRPに対応する問題が，CARPであ下「CARP」と記す)として形式化されており，容量制約
り，CARPは容量制約のある複数の車両で分担して辺につき枝巡回問題とも呼ばれ，複数ある巡回先を最適に巡あるデマンドを巡回する問題である．
回する時の経路を決定する巡回問題の一種である．一般
つまり，CARPとVRPは，巡回するデマンドが辺にあに，巡回問題は，節の集合V と辺の集合E によるグラフ
るか節にあるかの違いだけでそれ以外は同じ条件の問題
1) 2)
G = (V,E) において，大まかに以下のように分類される ． である．VRPはデマンドが節に指定され，現実の道路ネットワークをグラフネットワークで表現したとき交差点
z 節巡回問題 （Node Routing Problem:以下「NRP」とや配達先なども節で表現される．そのためVRPは適用範
記す）
囲が広く，小売店への商品輸送をはじめ宅配便配達，自z 辺巡回問題（Arc Routing Problem:以下「ARP」と動販売機の補充など数多くの適用例がある．
記す)
NRP がネットワークの節上に配送や集荷のデマンド
これに対し辺にデマンドの指定があるCARPは， 郵便
配達のように 交差点から交差点までの間に多数の巡回の指定を想定するタイプの問題であるのに対して，ARP
先が存在するようなデマンド密度の高い場合や， 道路
はネットワークの辺にデマンドの指定を想定するタイプ
清掃のように道路区間そのものに対してサービスを行うの問題である．
NRPの中で代表的な問題が，配送計画問題（Vehicle
場合ではVRPより有用である．

131

社会技術研究論文集

Vol.7, 131-138, Mar. 2010

本研究は，CARPを用いて配車配送計画を支援するソフトウェアの核となる解法の部分を開発する．特に，CARPを解くアプローチとして，既にVRPにおいて著者
らの研究によって高い性能を示している模擬焼きなまし法（Simulated Annealing:以下「SA」と記す）を用いた解法をCARP に適用し，既存の研究で提案されてきた解法と得られる解の精度や探索実行時間といった解法の性能を比較することを目的とする．
Fig. 1CARP のイメージ図
本論文では，２章でCARPについてその定義とこれまでの研究事例についてレビューを行う．また３章では解の表現方法であるストリングモデルとそのCARPへの応Golden and Wong の定義では，CARP はすべての辺に向用を述べ，CARPを解くための具体的なアルゴリズムを提案する．次に４章では計算機実験として，既存研究ときが無い無向ネットワークを仮定しており，彼ら以降の解法の性能を比較する計算機実験について詳細を述べる． CARPに関する研究もほとんどが無向グラフでの研究で最後に５章では本研究のまとめを行う．
ある．
また，CARPに良く似た問題のクラスにCapacitated
Chinese Postman Problem （以下「CCPP」と記す）がある．
CCPPは1973
年にChristofides4) によって提案されたもので，
2. CARPの定義と既存の研究容量制約のある複数車両でグラフ上の全ての辺を巡回す
1)
CARPは1981 年にGolden andWong によって提案されたる問題である．CARP はグラフ上に指定された辺のみをすべて巡回する問題であるため，CCPPはCARPの特別な問題である．彼らはこの問題を以下のように定義していケースであるといえる．
る．
CARP も VRP と同様に NP 困難な問題であり，小規模節の集合V = {v0, v1, . . . , vn} と無向辺の集合E = {(vi, vj) : vi, vjの問題でないと厳密解法を適用することが困難である．
∈ V, i < j} によるグラフG = (V,A) を考える．このうちの頂
CARP は，VRP に変換されることが知られている．たと
点v0をデポとし，均一な許容量制約Q を持った車両m 台
はすべてデポから出発し最終的にデポへ戻るものとする． えば，Pearn ら 5)の方法によると，デマンドのある辺の数
Eの部分集合R を本稿ではデマンド辺と呼ぶ．これらデの約 3 倍の節をもつ VRP に変換可能である．しかし，マンド辺はいずれかの車両によってサービスを受けなけ
CARP の多くの近似解法は，直接的に CARP の問題の構ればならない．
造を利用して解いている 6) ,7)．近似解法の研究は，すべての辺E には通過時にかかるコストcij（例えば，
Christofides による Construct-Strike 法 4)から始まり，Path距離，通過時間）が与えられており，すべてのデマンド
Scanning 法，Augment-Merge 法，二段階解法など様々な研辺R にはデマンドを表す非負の値qij が与えられている．
究がされている 7)．
近年では，メタヒューリスティックと呼ばれる汎用的
また，各々のデマンドは１台の車両によってのみデマンに近似解を求める手法が様々な組合せ最適化問題で利用ドを満たされるものとする．
CARPは以上の条件をすべて満たしながら，すべてのされている8)．Hertz ら9) はタブーサーチ（以下「TS」とデマンド辺R をサービスする車両m 台分の走行ルートの記す）を，Lacomme ら10) は遺伝的アルゴリズム（以下中で総走行コストが最小となるルートを探す問題である． 「GA」と記す）を用いてCARPを解く手法をそれぞれ提ARPはネットワークの辺に方向があるかどうかで次案している．Hertzらの方法は，車両ごとのルートの間の３つに分類される．
でデマンド辺の削除と挿入をタブーサーチによって行う（ 1 ） Undirected ARP : すべての辺が無向辺フェーズと車両の区切りをなくした全体のネットワーク（ 2 ） Directed ARP : すべての辺が有向辺におけるルートの最適化のフェーズをある条件の下に相
3
Mixed
ARP
:
（ ）
無向辺と有向辺が混在
互に繰り返す方法である．また，Lacommeらの方法も，車両ごとのルートの間で局所最適化を行うフェーズと車両の区切りをなくした全体のネットワークにおけるGAによる最適化のフェーズを相互に繰り返す方法である．
しかし，SA法を用いて，しかも単一のフェーズでCARPを解く研究は筆者らの知る限り見当たらない．
CARPを解くアルゴリズムを研究する研究者のために，

132

社会技術研究論文集

タ (大文字斜体標記) は以下の意味をもつ．
N ：問題の大きさ
SIZEFACTOR , CUTOFF ：1 つの T の値での繰返しの回数を定めるパラメタで， 試行回数が trials≧SIZEFACTOR･N
または解の受理回数が changes ≧CUTOFF･N となるまで繰り返す
INITPROB：初期の受理確率であり，初期温度 INITTEMP
は，changes / trials = INITPROB となるように定める
TEMPFACTOR：温度を下げる係数
FIN_DIVISOR ： 最 終 温 度 を 決 め る パ ラ メ タ で ，T≦INITTEMP / FIN_DIVISOR, となるとき，すべての繰返
しを終了する

スペインのValencia 大学においてCARPのベンチマーク問
題がインターネットで公開されている．CARPLIB11) と呼ばれるこのサイトには，４シリーズのベンチマーク問題が掲載されている．本研究でも，提案解法の性能比較のためにこれらの問題を用いた．

3. CARPのモデリングと評価関数(1) CARPへのSA法の適用
a) SA法SA法は，熱した固体を徐々に冷却すると完全格子をもつ構造に再結晶できるという金属工学における原理を取り入れた確率的探索手法である．SA法では，繰返し
計算における現在の解の近傍解のうちの１つをランダムに選んで次の時点の解の候補とするが，評価関数の値を改善する場合だけでなく，評価関数が改悪する場合にも温度に対応する変数 T の値に従う確率 exp(-ΔE/T)で，その解を次の時点の解として許容する．解探索の初期では，温度変数Tの値を大きく設定し解の改悪を実行する
確率を高くして局所最適解に陥らないようにし，徐々にTの値を低くしていった探索の後期には改悪の確率を減b) データ構造
ストリングモデルは，SA法を用いてVRPを解くために糸山ら13) によって考案されたモデリング手法である．
VRP の解は各車両のルートがデポを中心に結びついた形をしている．これを紐状に展開し，Fig. 2 のように横１列の１次元配列で表現したのがストリングモデルである．
ストリングモデルは，デマンドのある節を表現する記号とルートの区切りを表す記号の２種類から構成される．
デマンド節を表現する記号は，それぞれのデマンド節とそのデマンドに１対１で対応するものであり，ルートの区切りを表す記号とはデポを示す記号等でモデル中に複数存在する．Fig. 2の例では，アルファベットがデマン
ド節を意味する記号として用いられ，０は各車両のルー
トの区切れ目を示すとともにデポを示している．従って，０と０に挟まれた部分が１台の車両の配送ルートとなる．
この区切れ目となる０の数は，使用可能な車両をmとす
るとストリングモデルの両端の０も含めてm +1個必要とらし大域的な最適解への収束を促す．
本提案手法に適用したSA法のアルゴリズムは，以下のように表示できる．他の手法のように，いくつかの部
分アルゴリズムを統合して大域的最適化を図ることがな
いため本手法はきわめて単純な構成になっている点が特
徴である．
１
２
３
４
５
６
７

８
９
10
11

Vol.7, 131-138, Mar. 2010

初期解 x を生成
評価関数の値 E(x) を最良値 E* として記録
同一温度での平均探索近傍数 N を指定
温度変数 Tを INITTEMP に設定
試行回数 trials := 0 ,解変形実施回数 changes:= 0 に設定
xの近傍解x’をランダムに生成し，
trials := trials + 1 : ΔE := E(x’)－E(x)ΔE<0 のときは必ず，そうでないときもTの値に従う確率exp(-ΔE / T)で解変形を実施し，changes := changes + 1, x := x’,
E(x)<E*ならば，E* := E(x)，x* := x
trials < SIZEFACTOR・N かつchanges < CUTOFF・N なら step６へ
T := T・TEMPFACTOR
T > INITTEMP / FINDIVISOR なら step５へ
最良解 x* の出力なる．

Fig. 2

VRPにおけるストリングモデル

このモデルは，各車両へのデマンド節の割り当てと割り当てられたデマンドへの巡回順序，すなわち配送ルー
トを同時に表現する．これはCARPにおける解の変形のここで，アルゴリズム中のJohnson et al 12)によるパラメ

133社会技術研究論文集

Vol.7, 131-138, Mar. 2010s = (s1,s2,…,sn) : ストリングモデル
ck : 辺 k でデマンドをサービスするのに必要なコスト(ただし，k=0 のとき， ck=0 )pk,l : 辺 k の終点と辺 l の始点を結ぶ最小コスト（すべての pk,l は，あらかじめフロイド法で計算しておく）

説明の際に後述するように，配車とルーティングの両方を同時に考慮することを可能にする．
糸山ら13) はVRPに対し，ストリングモデルとSA 法を組み合わせた解法を用いて大規模な現実問題に対しても解法としての高い性能を示した．またストリングモデル
は基本的なVRPだけでなく，車両の回転利用が可能なケースや時間帯制約つきの問題VRPTW などに対しても応用可能であることが示されており14)，拡張性・発展性の高い解の表現方法と考えられる．
本研究ではストリングモデルとSA法を組み合わせた解法を辺にデマンド指定があるCARP への適用させることを提案する．この前提として，あらかじめすべての辺間の最短経路をフロイド法にて計算を行い，辺間の使用
経路を一意に決定しておく．なお，標準的なCARPでは同一車両の回転利用を考慮しないので、本研究でも同様の前提を置いている．

（１）式の第１項はデマンド辺内を通過するときにかかるコストである．第２項はストリングモデル内の次のデマンド辺へ移動するときにかかるコストである．

車両 1
A

B
D
C
A, B, C, E : 有向デマンド辺D : 無向デマンド辺

切りを表す記号による１次元配列を通じて解の状態を表現するストリングモデルによって，解の状態を表現することができる(Fig. 3参照)．グラフ上のすべての辺に向きがある有向グラフの場合，デマンド辺の進入方向がすべて指定されるため，ストリングモデルで表現された解から巡回ルートを一意に指定できる．一方，デマンド辺の中に無向辺が含まれる場合は， Fig. 4 に示すように，無向デマンド辺に関しては＋，－の符号を用い，無向デマ
ンド辺の進入方向をストリングモデルの中で指定することで巡回ルートを表現する．
これまでのCARPの研究では，Golden and Wongによる
CARPの定義が無向グラフを仮定していたことから，こ

0

0

D

E 0

め，解がいつも同じ値になる保証はなく，実行するたびに異なる結果となる可能性がある．そこで探索を k 回繰り返し実行し，その解の平均および最良解で評価することとした．その計算過程を以下のフローで行う．

れた解s から巡回総コストE を求めるには，次の式で計
算できる．

i =1

C

(3) 計算手法
本節では，本研究で提案する計算手法を概説する．
SA法は乱数を用いて探索を行う確率的探索法であるた

巡回路（実行可能解）の中で，巡回総コストが最も小さくなる解を求めることである．ストリングモデル表現さ∑

B

Fig. 4 無向デマンド辺を含むルートの表現(2) 評価関数
CARPの目的は，積載量制約などの制約条件を満たす

csi +

A

Fig. 3 CARP のストリングモデル

れまでに提案されてきた解法の中には無向グラフにのみ対応した手法が多い．しかし提案手法は上記の通り，無向グラフに限らず，有向グラフ，混合グラフであっても解を表現できる．よって，一方通行などの進入方向の制限が存在するような現実の配送問題への適用を考える場
合，この辺の向きに関する対応は非常に重要である．

n

車両 2
0

c) ストリングモデルのCARP への適用
CARPにおいても，デマンド辺を表す記号と車両の区

E=

E

n−1

∑p
i =1

si , si+1

１．ネットワークデータを読み込み，デマンド辺間の最短距離計算をフロイド法を用いて行いて，デマン
ド辺間のコストとする

（１）

134

Vol.7, 131-138, Mar. 2010

社会技術研究論文集

２． 乱数系列を指定する
３．初期解を生成する
４．SA 法による探索を行う
５．最良解を出力する

現在の解Ba). 一対一交換
BCA

以上の２～５をk 回繰り返し，解の平均および最良解を出力する．

C

A
0

0
0

(4) 試行変形
SA法で最適解の探索を行うのに，現在の解からデマ
ンド辺についての操作を行うことにより近傍解を発生させる変形方法として，「1 対1 交換」「削除・挿入」および±で表現する無向辺の進入方向を変更させるための「辺の進行方向反転」を加えた３種類の試行変形を適用した（Fig. 5参照）．これらの試行変形は，デマンド辺

A

B

C

0

0

A

C

B

0

c) 辺の方向反転
Bb) 削除・挿入
B
C

A

C

A
0

を表す文字と車両区切りを表す0と区別せずに実行することで，大幅な変形を行うことができる．以下に各々の試行変形を説明する．

0
0

C

A

a) 一対一交換

B

0

0

-B

A

C 0

Fig. 5 試行変形の概要

この試行変形はストリングモデルの中の２つの要素（デマンド辺２つあるいはデマンド辺とデポ）をランダ
ムに選択し，両者の位置を入れ替える操作である．ただし，０同士の交換は結果的に解の変形にはならないため行わない．０以外の２つの記号の一対一交換により同一車両での配送順序の入れ替え(Fig. 6参照)あるいは異なる
車両間での担当デマンド辺の入れ替え(Fig. 7参照)がなさ

Vehicle 1

E
Vehicle 2

A0
Bれる．片方の要素が０である場合は，ルートの統合と分割を伴う大幅な変形を行うことになる(Fig. 8参照)．

DCb) 削除・挿入
この試行変形はストリングモデルの中から抜き取る要素とそれを挿入する場所をランダムに選び，抜き取られた場所から挿入する場所までの間の要素をシフトさせてから，抜き取った要素を挿入する変形である．この変形により，車両間のデマンド辺割当の移動，あるいは同一
車両内での１デマンド辺の巡回順の変更が成される．また０が移動の対象となる場合には，一対一交換の場合と同様に，部分的なルートの統合と分割を同時に行う大幅な変形操作となる．

0

A

B

C

0

D

E

0

0

C

B

A

0

D

E

0

Vehicle 1

E

A

Vehicle 20Bc) 辺の方向反転
この試行変形はストリングモデルの中の１要素をランダムに選択し，その±符号を逆にする操作である．すなわ
ち，無向デマンド辺の進入方向を逆向きにする操作となる．ただし，ランダムに選んだ要素が有向辺であった場
合やデポを表す０であった場合には，試行変形を行わない．

DCFig. 6 ’0’と’0’の間にある2つの記号の一対一交換

135

社会技術研究論文集

Vol.7, 131-138, Mar. 2010

4. 計算機実験

Vehicle 1

E
Vehicle 2A(1) ベンチマーク問題
解法の比較を行うCARPのベンチマーク問題として，
インターネットのCARPLIB11)で公開されているベンチマ
ーク問題集を用いた．具体的には，比較的小規模な問題が多いGDB シリーズ全21 問，中規模の問題の多い
BCCM シリーズ全34 問，そして，大規模な問題を含む
EGLESE シリーズ全24 問，合計79問である．

0
B
D
C
0

A

B

C

0

D

E

0
一対一交換

0

A

D

C

0

B

Vehicle 1
A

E

Table 1 CARPのベンチマーク問題 (CARPLIB)

0

シリーズ

E
Vehicle 2
0

問題数

GDB

21

BCCM

34

EGLESE

24

B
D
C

ネットワークの構成
デマンドのある 19～55 個の無向辺のみデマンドのある 39～97 個の無向辺のみデマンドのある 51～190個の無向辺と，0 から 115
個のデマンドのない無向辺Fig. 7 ‘0’をまたいだ2つの記号の一対一交換

Vehicle 1

このベンチマーク問題の下限値に関しては，2003 年にBelenguer and Benavent15) による，切除平面法を用いた研究の結果がこれまでに最も良い結果を報告している．
また，メタヒューリスティックスを用いた解法としては，
2000 年のHertz, Laporte and Mittaz によるTSによる研究9) と，2001 年のLacomme, Prins and Ramdane によるGAを用いた研究10) の両方が，これまでに良い結果を報告している．

E
Vehicle 2

A
0
B
D
C
0

A

B

C

0

D

E

(2) 実験結果および考察
提案手法を用いてベンチマーク問題の解を求め前出の既存研究結果と比較を行った．解の試行変形としては，
３章４節で述べた一対一交換，削除・挿入，辺の方向変換の３つを等確率で適用した．３章１節に示したSAのパラメタの値は，Johnsonら12)の推奨している値および筆者らの予備実験の結果から，次のように定めた．
N = 2L2 (L :はストリングの長さ)
SIZEFACTOR = 4，CUTOFF = 0.1
INITPROB = 0.4

0

一対一交換
0

A

0

Vehicle 1
A

C

B

D

E

E

0

Vehicle 20

TEMPFACTOR = 0.99 (つまり Tn+1 = 0.99Tn)
FIN_DIVISOR = 10BD

また，計算における初期解は，デマンドが各車両の容量制約を超えないように，ランダムに配分した実行可能解を用いた．

C
Fig. 8‘0’と他の記号との一対一交換

136

社会技術研究論文集

Table 2 GDBシリーズとBCCMシリーズの問題例の計算結果のTable 4Vol.7, 131-138, Mar. 2010

EGLESEシリーズの問題例の計算結果 (抜粋)

比較(抜粋)
問題番
号

GDB1
GDB3
GDB9
GDB23
BCCM1A
BCCM3B
BCCM6CBCCM9B

デマン
ドのあ
る無向
辺の数
22
22
51
55
39
35
50
92

車 両
台数

Hertz
ら
(TS)

5
5
10
10
2
3
10
4

316
275
317
235
173
87
329
329

Lacomme
ら
(GA)
316
275
303
235
173
87
317
326

問題番
号

提案手法に
よる 10 回の
計算結果
平均
316
275
312
235
176
88
320
330

e1-A
e2-B
e3-C
e4-A
s1-B
s2-C
s3-A
s4-B

最良
316
275
309
233
173
87
317
326

算結果のまとめ

GDB
シ リ
ーズ
BCCM
シ リ
ーズ

提案法によ
る 10 回の計算結果
平均
最良

Lacomme ら
(GA)

平均誤差
率

0.3%

0.1%

0.8%

0.1%

平均誤差
率

1.4%

0.2%

2.4%

0.9%

車 両
台数
5
7
17
9
10
27
15
27

提案手法 10 回計算結果
平均
最良
計算時
間(s)
3769
3602
9.7
6429
6393
20.8
10559 10421
42.7
6738
6566
43.3
6668
6553
23.4
17036 16847
376.6
10749 10591
144.3
16993 16776
478.2

また，EGLESEシリーズについては，既存研究も少な
く，Hertzら9)やLaccomeら10)による結果も与えられていな
いが，提案手法により具体的な計算時間で解を求めることができた．
このように提案手法は1つのフェーズで最適化を行う方式であり，全体最適化と局所最適化の2つのフェーズをもつ既存手法に比べてアルゴリズムが単純であるにもかかわらず，ほぼ同程度の性能をもつことが示された．

Table 3 GDBシリーズとBCCMシリーズのすべての問題例の計

Hertz ら
(TS)

デマンド
のある無
向辺の数
51
72
87
98
75
147
159
190

5. まとめTable 2 およびTable 3 はGDBシリーズとBCCMシリーズの問 題例 におけ る， Hertz ら によ る TSの 解， およびLacommeらによるGAの解と提案手法によるSAの解との本論文では，配車配送計画を効率化するアプローチとして，積載量制約のある複数車両による辺巡回配送計画問題であるCARPに着目し，様々な組合せ最適化問題へ比較を示す．2つの先行研究では，計算実験の回数が記応用できるメタヒューリスティックのうち，これまで研載されていないが，提案手法は確率的な探索に基づくも究例の少ないSA法を用いてCARPを解く解法を考案した．
のであり，計算実験ごとに結果が異なるので，10回の計
また，解のモデリングとしては，ストリングモデルを用
算実験を行い，最良解だけでなく平均の解の性能を記載
いた表現方法を提案し，CARPの解の状態および変形をした．Table 2 はそれぞれのシリーズの問題4つずつにつ
シンプルにかつ効果的に表現することに成功した．
いて結果の比較を示している．GDB23のように，提案手
また，提案手法をこれまでに研究されたCARPの解法
法で得られた解がTSやGAによる解よりも良い問題例もと同じベンチマーク問題へ適用して解法の性能を比較しあり，全問題例の結果としては，DBシリーズ全21問のたところ，単純なアルゴリズムをもつ提案手法が2つのうち19問で既存解法の解と一致する解を得て，BCCMシ
フェーズをもつ既存手法とほぼ同等な性能をもつことがリーズ全34問中19問で既存解法の解と一致する解を得た． 確認された．
Table 3は，それぞれのシリーズのすべての問題例におけアルゴリズムが単純であることは，ソフトウェアの開る平均誤差率の結果を示している．Table 3 にある平均誤発および実装の際に有利である．また，調整すべきパラ差率とは，それぞれの解の値をTS法またはGA法で得ら
メタの種類も少ないことから，現実の配送・集荷の最適れた解のうちのよい方の値で割った数値から1を引いた化システムの構築の際に，より適合すると考えられる．
数値である．同一のSAパラメタを用いて提案手法を10
3節のモデリングの説明の際に述べたように，本論文回計算したうちの最良値の質は，GDBシリーズではTSで提案した解法は，先行研究との性能比較を行うため，法よりよくGA法と同等であり，より問題の規模が大き
標準的なCARPの問題に合わせて条件を設定しているの
いBCCMシリーズでは，TS法とGA法の間であることがで，同一車両の回転利用を考慮していない．しかし，現分かる．計算時間は，Pentium IV 1.8GHzのPCを用いて，実の配送問題において，車両群の積載容量の合計よりも
GDBシリーズで平均11秒，BCCMシリーズで平均34秒で配送需要の方が多い場合には，一つの車両が配達を終え
ある．

137

社会技術研究論文集

Vol.7, 131-138, Mar. 2010てデポに返ってから再び配送に赴く回転利用を考慮しなければ配送計画を作成することができない．本論文で提案したストリングモデルそのままでは，回転利用を要す
る配送問題に対応していない．著者らは，これまでVRP
で車両の回転利用を行う場合に対応するストリングモデ
ルのアイデアを提案しており16)，それをCARPに適用することが可能であると考えている．しかし，回転利用を要するCARPのベンチマーク問題は筆者らの知る限り公表されているものがなく，また，現実の配送データも入手できていないので，回転利用に対応するストリングモ
デルを用いた解法の検証ができていない．また，このことは，配送・集荷の時間帯制約があるCARPについても同様である．今後は，このような問題についての現実の配送・集荷のデータを入手して，本研究の解法の有効性についての検証を行いたいと考えている．

Academic Publishers, 2000
7)

H.A. Eiselt, M. Gendreau, G. Laporte. (1995) Arc routing problems,part II: the rural postman problem, Oper. Res, 43(3), 399–414.

8)

久保幹雄, 「メタヒューリスティックス」室田一雄編『離散構造とアルゴリズム IV』 ( pp.171-230) 近代科学社,.

9)

A. Hertz, G. Laporte, M. Mittaz. (2000) A tabu search heuristic for thecapacitated arc routing problem, Oper. Res., 48(1), 129–135

10)P. Lacomme, C. Prins, W. Ramdane-Cherif. (2001) A genetic
algorithm for the capacitated arc routing problem and its extensions,Lecture Notes in Computer Science 2037, 473–483.

11)

CARPLIB HP： http://www.uv.es/belengue/carp/ [2009,August 15 ].

12)

D.S. Johnson, C.R. Aragon , L.A. MacGeoch, C. Schevon. (1989),
Optimization by Simulated Annealing : An Experimental Evaluation,
Part I, Graph Partitioning, Operations Research, 37, 865-892.

13)

糸山日出男, 國府方久史, 川嶋弘尚(1995) 「配送計画問題(Vehicle Routing Problem) のモデリングとシミュレーテッド

参考文献

アニーリング法による解法」 『統計数理研究所共同研究
レポート 77

1)

B.L. Golden, R.T. Wong. (1981) Capacitated arc routing problems,

277–283.

Networks, 11, .305–315.
2)
3)

14)

5)

6)

H. Kokubugata, H. Kawashima (2008) Application of simulated

J.K. Lenstra, A.H.G. Rinnooy Kan. (1981) Complexity of vehicle

annealing to routing problems in city logistics, in ‘Simulated Annealing',routing and scheduling problems, Networks, 11, .221–227.

Cher Ming Tan (Ed.), I-Tech Education and Publishing, Vienna,

B.L. Golden, A.A. Assad, ed.. (1988) Vehicle Routing: Methods andpp.131-154.
15)

Studies.
4)

最適化：モデリングとアルゴリズム７』

J.M. Belenguer, E. Benavent. (2003) A cutting plane algorithm for

N. Christofides. (1973) The optimum traversal of a graph, OMEGA,

capacitated arc rouing problem, Computers & Operarions Research, 30,

1(6), 719–732.

705-728.

W. L. Pearn, A. A. Assad and B. L. Golden. Transforming Arc

16)

T. Hasama, H. Kokubugata and H. Kawashima (1999) A heuristic

Routing into Node Routing Problems. Comput. & Opns. Res. 14, pp.

approach based on the string model to solve vehicle routing problem

1987.285-288.

with various conditions, Preprint for World Congress on Intelligent

M. Dror (ed.): Arc routing: theory, solutions and applications., Kluwer

Transport Systems, No.3027, Toronto, Canada, Nov. 1999

A Heuristic Approach to Capacitated Arc Routing Problem Using Simulated Annealing
1

2

3

KOKUBUGATA ,Shuichichi MATSUMOTO , Koichiro HIRASHIMA , Hisafumi
4and Hironao KAWASHIMA
1

Ph.D. (Engineering) Senior Assistant Professor, Keio University, Advanced Research Center(E-mail:shuichi@ae.keio.ac.jp)
2
M.S. (Engineering) Graduate School of Keio University, Faculty of Science and Technology.
3
M.S. (Engineering) Teacher, Keio Girls Senior High School. (E-mail: kokubu@mita.cc.keio.ac.jp)
4
Ph.D. (Engineering), Professor, Keio University, Faculty of Science and Technology.
(E-mail: kawashima@ae.keio.ac.jp)
Capacitated Arc Routing Problem (CARP) is the problem in which routes are made in order to minimize the total
cost of vehicles’ trip back to depot through each demand arc in network. For the cases like mail delivery where
demand is concentrated, and road sweeping where road section itself is the target of service, it is suitable to adopt theapproach based on CARP in which demands are set on arcs. In this paper, a solution of CARP, utilizing simulated
annealing is proposed. Adoption of “string model”, a one-dimensional alignment model makes efficient search forbetter solution possible. The proposed method is simple and implemented in one phase procedure, while preceding
methods are constructed in two phases. Computational experiments are conducted on benchmark instances.

Key Words: Logistics, Routing Problem, CARP, Simulated Annealing138