東海大学紀要情報通信学部
vol.3,No2,2010,pp.62-66
東海大学紀要情報通信学部
Vol.3 , No.2 , 2010, pp. -解説
解説

運搬経路問題の近似解法
森山 弘海 *1

Approximate Algorithms for the Vehicle Routing Problem
byHiroumi MORIYAMA(received on November 30, 2010 & accepted on January 11, 2011)

Abstract
The vehicle routing problem (VRP) can be defined as the problem of designing routes for vehicles to make deliveries tocustomers subject to vehicle capacity constraints. Routes for the vehicles are designed to minimize total travel cost. This
problem is one of the representative problems in mathematical programming, and it has various applications in many fields.
Therefore, many studies have been made on the VRP. In this paper, we expound four approximate algorithms for the VRP. The
first algorithm is based on the constructive method. The second algorithm belongs to the class of the route-first/cluster-second
method, and the third algorithm belongs to the class of the cluster-first/route-second method. The fourth algorithm is thenear-optimal solution on the basis of the Lagrangian heuristic.
Keywords: Vehicle routing problem, Approximate algorithm, Heuristic method
キーワード：運搬経路問題，近似解法，ヒューリスティック解法

1．はじめにデポ（運搬センター）から多数の顧客にある商品を運搬するとき，各運搬車が巡回する最適なルート（デポを出発したあと，いくつかの顧客を巡回し，再びデポに戻る閉路）を求める問題を運搬経路問題（vehicle routing problem）という．
運搬経路問題の基本形は一般に，以下の仮定をもつ．
(1) 各顧客の需要量（運搬量）は既知である．
(2) 顧客（デポを含む）間の移動費用（移動距離，移動時間）は既知である．
(3) 使用できる運搬車の最大積載量と移動費用（移動距離，移動時間）の上限は既知である．
(4) 各顧客の需要は1台の運搬車が1度にまとめて運搬する．
(5) 各運搬車が巡回する顧客の需要量の総和は，その運搬車の最大積載量を超えない．
(6) 各運搬車が巡回するルートの移動費用（移動距離，移動時間）の総和は，その運搬車の移動費用（移動距離，移動時間）の上限を超えない．
これらの仮定の下で，総移動費用（総移動距離，総移動時間）が最小となるような各運搬車のルートを求めることが運搬経路問題の目的である．
運搬経路問題は数理計画法における代表的な問題の1つであると共に，実用上も極めて重要な問題であり，小売店への商品の配送，生産工場への原材料の搬入，工場内における仕掛品の運搬，各種廃棄物の回収などに幅広い応用をもつ．このため，運搬経路問題に関しては膨大な研究（文献1）にはこの問題に関する699の研究が，文献2）にはこの問題に関する330の研究が列挙されている）があり，これまで*1 情報通信学部経営システム工学科准教授―
1 −―− 62に種々の最適解法や近似解法が提案されている3）4）5）6）7）．
本稿では，これらの膨大な研究の中から，運搬経路問題の基本形に対する代表的な近似解法のいくつかを取り上げて解説する．
以下では，次の2.において本稿で用いる用語と記号を定義する．次いで，3.では，構築法に基づく近似解法を解説する．また，4.では，ルート先・クラスター後法に基づく近似解法を，5.では，クラスター先・ルート後法に基づく近似解法を解説する．そして6.では，ラグランジアンヒューリスティック法に基づく近似解法を解説する．

2．用語と記号
ここでは，本稿を通して用いる用語と記号を定義する．
運 搬 車 の 集 合 を � � ����� � � �� ， 顧 客 の 集 合 を � ������ � � �� とする．また，デポを0で表し，�にそれを加えた集合を�� � � � �0� する．さらに，顧客� � �の需要量を�� ，運搬車� � �の最大積載量（重量または容量）を�� ，運搬車
� � �の顧客（デポを含む）� � �� から顧客（デポを含む）
�，運搬車� � �� � �� への移動費用（移動距離，移動時間）を���の移動費用（移動距離，移動時間）の上限を�� とする．
先の仮定(1)～(5)だけを考慮した（仮定(6)を考慮しない）
場合の問題を特に積載量制約付き運搬経路問題（capacitated vehicle routing problem）といい，先の仮定(1)～(6)のすべてを考慮した場合の問題を特に距離制約付き運搬経路問題（distance constrained vehicle routingproblem）という．また，移動費用（移動距離，移動時間）�� ���� � � � �� �� � � �� で あ る 場 合 の 問 題 を 対 称が ���（symmetric）といい，そうでない場合の問題を非対称（asymmetric）という．さらに，運搬車の区別をしない場

森山弘海

合 の 問 題 を ， す な わ ち ， �� � �, �� � �, � � � で ， か つ�� ��� , � � �, �, � � �� で あ る 場 合 の 問 題 を 等 質
���（homogeneous）といい，そうでない場合の問題を非等質（heterogeneous）という．
以下では，対称でかつ等質である場合の積載量制約付き運搬経路問題を対象とする．

ji00

Fig.1

��� � ����� � ��� � � ���� � ��� �� � ���� � ��� � ��� �� ��� � ��� � ������

だけ削減することができる（Fig.1の右図参照）．この削減
される移動費用 ��� のことを，顧客ペア ��, �� のセービン
グ値という．セービング法は，このセービング値 ��� が大きい顧客ペア ��, �� を順次連結してルートを生成する方法である．セービング法の手順は以下のように記述できる．
手順1

セービング法S1. すべての顧客ペアのセービング値を計算する．
S2.セービング値の大きい順に並べた（セービング値が正の）顧客ペアのリストを作成する．
S3. デポと各顧客間の往復ルートを生成する．
S4. リストの最上の顧客ペア ��, �� が次の3つの条件を満たすかどうか（実行可能性）を調べ，いずれの条件も満たす場合には顧客ペア ��, �� を連結してルートを併合する．
① 顧客 � と顧客 � は異なるルート上の顧客である．
② 顧客 � と顧客 � はルート上でデポの直前または直後の顧客である．
③ 顧客 � と顧客 � を含む（2つの）ルート上の顧客の需要量の総和は運搬車の最大積載量以下である．
S5. リストの最上の顧客ペアをリストから削除してS4へ．リストが空ならば終了．

4．ルート先・クラスター後法
ルート先・クラスター後法（route-first/cluster-secondmethod）とは，最初にデポとすべての顧客を巡回するルー―
2 ―
− 63
−

j＋ ＋

3．構築法
構築法（construction method）とは，何もないところから徐々にルートを拡大していき各運搬車のルートを求める解法の総称である．ここでは，古典的な構築法の１つであるセービング法（節約法：saving method）を解説する．
セービング法は，1964年にClark-Wright8）によって提案された近似解法であり，当時のIBM製の大型計算機に実装され，VSP（Vehicle Scheduling Program）の名で販売されたことで有名となった解法である．セービング法は，近似解法の基本戦略である貪欲法に基づく解法であり，自明な初期ルート（デポと各顧客間の往復ルート）から出発し，移動費用の削減量が最大のものからルートを（実行可能性を保ったまま）併合していく方法である．
いま，1台の運搬車が顧客 � だけを，そして他の1台の運搬車が顧客 � だけを巡回しているものとすると，この場合の移動費用は ���� � ��� � � ���� � ��� � となる（Fig.1の左図参照）．しかし，1台の運搬車が顧客 � と顧客 � をどちらも巡回すると，移動費用を－i

Calculation of ��� .

0
Fig.2

0

Conceptual diagram of the route-first/cluster-secondmethod.

ト（巨大ルート）を生成し，その後でそれをいくつかのクラスターに分けることで各運搬車のルートを求める解法の総称である（Fig.2参照）．ルート先・クラスター後法の一般形の手順は以下のように記述できる．
手順2

ルート先・クラスター後法

S1. デポとすべての顧客を巡回する巨大ルートを求める.
S2. S1で求めた巨大ルートをいくつかのルートに分割する（すべての顧客をいくつかのクラスターに分割する）．
ただし，各ルート上の顧客の需要量の総和が運搬車の最大積載量以下となるようにする．
この手順のS1においては，デポとすべての顧客を巡回する巨大ルートを求める必要があるが，そのような巨大ルートを求める問題は，よく知られた巡回セールスマン問題（traveling salesman problem）となる．巡回セールスマン問題は，運搬経路問題と同様にNP-困難な問題であるが，運搬経路問題よりも比較的解き易い問題であり，種々の最適解法や近似解法が提案されている9）10）．そこでここでは，この手順のS2を実行する方法を中心に解説する．
デポとすべての顧客を巡回する巨大ルートを，その顧客の巡回順序を保ったまま“最適な”いくつかのルートに分割する方法がBeasley11）により提案されている（この方法は最適分割法（optimal partitioning method）と呼ばれている2））．いま，デポを出発したあと，すべての顧客を巡回し，再びデポに戻る巨大ルートが与えられているものとし，その巡回順序を�とする．すなわち，��0� をデポ 0 とし，����を � 番目に巡回する顧客の番号とする．そして，��� �� � ��を 0 � ��� � �� � ��� � 2� � � � ���� � 0 と巡回するルートの総移動費用とする。ただし，このルート上の顧客の需要量の総和が運搬車の最大積載量を超える場合には ∞とする．すなわち，
������ ��� �������� � � ����������� � ������ ,���������
�∞,�� ����� � � の場合�����,その他
�, � � �� �� � �� �2�と定義する．そして， �� を頂点の集合とし，運搬経路問題の近似解法

� � ���, �� � �� � �� � � � �����である�を有向枝の集合とし，有向枝 ��, �� の重みを��� とす
� とする．このとき，最適分割法の手順
るネットワークを �は以下のように記述できる．
手順3

最適分割法

� 上の頂点 0 から頂点 � への最短路
S1. ネットワーク �を求める（最短路問題を解く）.
S2. S1で求めた最短路上のすべての有向枝 ��, �� に対して，ルート0 � ��� � 1� � � � ���� � 0 を定める．

5．クラスター先・ルート後法

クラスター先・ルート後法（cluster-first/route-secondmethod）とは，最初に顧客をいくつかのクラスターに分割したあと，各クラスターごとにルートを求める解法の総称である（Fig.3 参照）．クラスター先・ルート後法の一般形の手順は以下のように記述できる．
手順4∆�� � ���� � ���� � ��� � � � ����� � ��� � � � ��� � ���� � �����4�とする（Fig.4参照）．このとき，この ∆�� を運搬車 � が顧客 � を巡回する場合の（近似的な）移動費用とし，変数
��� を1, 運搬車 � が顧客 � を巡回する場合
��� � �0, その他と定義すると，すべての顧客をいつくかのクラスターに分割する問題は，次のような一般化割当問題に定式化できる．
�GAP� ��� � � � ∆�� ����� ��

クラスター先・ルート後法S1. すべての顧客をいくつかのクラスターに分割する．ただし，各クラスターに含まれる顧客の需要量の総和が運搬車の最大積載量以下となるようにする．
S2. S1で求めた各クラスターごとに，デポとクラスターに含まれる顧客を巡回するルートを求める．
クラスター先・ルート後法は，クラスター分割の方法により種々の解法が提案されているが，ここでは，数理計画法に基づく解法である一般化割当法（generalized assignment method）を解説する．なお，手順4のS2は，前述のルート先・クラスター後法（手順2）のS1と同様に，巡回セールスマン問題となることに注意する．
一般化割当法は，Fisher-Jaikumar12）により提案された近似解法であり，すべての顧客をいくつかのクラスターに分割する際に，一般化割当問題（generalized assignment prob-lem）と呼ばれる問題を解く．一般化割当問題は，運搬経路問題と同様にNP-困難な問題であるが，実際的には比較的解き易い問題であり、効率的な解法が提案されている13）14）．
いま，� から � 個の核となる顧客 �� , � �� , � , �� を選択する．そして，運搬車 � がデポ 0 と顧客 �� 間の往復ルー

0Fig.3

トを巡回しているものとし，その往復ルートに顧客 � を挿入した場合の移動費用の増加量を ∆�� とする．すなわち，0Conceptual diagram of the cluster-first/route-secondmethod.
��0＋i－＋��0
Calculation of ∆�� .

� ��� � 1,������ � �0,1�,������

���� � �, � � ����� �� ��� � � ,���������

ここで，式(5)は目的関数で（近似的な）移動費用の総和を最小化することを表す．式(6)は各顧客にちょうど 1 台の運搬車が割り当てられることを保証する．式(7)は運搬車に割り当てられた顧客の需要量の総和が運搬車の最大積載量以下であることを保証する．
一般化割当法の手順は以下のように記述できる．
手順5

一般化割当法

S1. 核となる � 個の顧客 �� , � �� , � , �� を定める．
S2. 運搬車 � が顧客 � を巡回する場合の（近似的な）移動費用 ∆�� を求める.
S3. 一般化割当問題�GAP�を解いてすべての顧客をいくつかのクラスターに分割する．
S4. S3で求めた各クラスターごとに，デポとクラスターに含まれる顧客を巡回するルートを求める（巡回セールスマン問題を解く）．

6．ラグランジアンヒューリスティック法
ラ グ ラ ン ジ ア ン ヒ ュ ー リ ス テ ィ ッ ク 法 （ Lagrangianheuristic）とは，対象とする問題が整数計画問題として定式化できる場合に，そのラグランジュ緩和問題を解いて得られる様々な情報を利用して実行可能解を構成する解法の総称である．ここでは，Fisher15）により提案されたラグランジアンヒューリスティック法に基づく運搬経路問題の近似解法を解説する．
以下では，6.1 において，運搬経路問題の 0-1 整数計画問題への定式化を説明する．そして，6.2 において，ラグランジュ緩和問題を解いてこの問題の下界値を求める方法を示したあと，6.3 において，その方法を組み込んだラグランジ
アンヒューリスティック法を解説する．
6．1Fig.4��� ���

0-1 整数計画問題への定式化

ここでは，運搬経路問題の 0-1 整数計画問題への定式化―3 ―− 64−

森山弘海を説明するが，この定式化においては，先の仮定(1)～(5)に加え（積載量制約付き運搬経路問題においては仮定(6)を考慮しないことに注意），次を仮定する．

0(7) 各運搬車は，少なくとも2つ以上の顧客を巡回するものとする．
いま，�� を頂点の集合とし，�� � ���, �� � �� ＆�� | � � ��である�� （非順序対の集合であることに注意）を枝の集合とする無向グラフを� � ��� , �� �とする．このとき，次を定義する 16）．
定義 1 �の部分グラフ�� � ��� , ��� �は，|��� | � � � �でかつ，��� が�� を張るならば�-木であるという（Fig.5 参照）．
定義 2 �-木は，頂点0（デポ）の次数が��ならば，特に次数制約付き�-木であるという（Fig.6 参照）．

定義から明らかのように，頂点� � �の次数がすべて 2 である場合の次数制約付き�-木は、�個のルートとなる．他方，上述の仮定(7)より，�個のルートは頂点� � �の次数がすべて 2 である場合の次数制約付き�-木となる．よって，�個のルートと，頂点� � �の次数がすべて 2 である場合の次数制
約付き�-木とは，1 対 1 に対応する．そこで，� � ��� , �� �の枝��, �� � �� に変数��� を付与して��� � �1, 運搬車が顧客（デポを含む）�, �間を移動する,場合0, その他と定義すると，ある� � ���� �に対応した� の部分グラフ
���� � ��� , �� ����が定まる．ただし，
�10�� � �� � �0,1�|�� | | ����は�の次数制約付き�� 木�

�11��P� ��� ��1��である．そして，変数� � ���� �に関してとおく．また，�の部分集合�に関して���� � ����� �� ���とおき（�·� は · 以上の最小の整数を表す），�� � �� ��とおく．
このとき，運搬経路問題は，次のような 0-1 整数計画問題に定式化される．ただし，��� と��� は同じ変数を表すものとする．

�� ��� ��� �����,������ ��� � �,����������� � ��� � �����,��� �������

Fig.6

Example of degree-constrained �-tree(� � 8, � � �).

ラグランジュ乗数� � ��� �，� � ��� � � �を用いて，式(13),(14)を�P�の目的関数に組み込むと，次のような�P�のラグランジュ緩和問題を得る．
�L�� � ��� �ただし，

�� ��� ��� ��� � � � �� � � � �� ������,�����

������������,������ ����,����� ,�����, �� � ���1���1���18�であり，�� � 0であるものとする．ここで，問題�·�の最適値 を ��·� で 記 す と ， ラ グ ラ ン ジ ュ 緩 和 法 の 原 理 よ り ，��L�� � � ��P�である．つまり，�L�� �の最適値は�P�の下界値を与えるが，�L�� �は枝��, �� � �� に重み ��� を付与した場合の次数制約付き最小�-木問題であり，その最適解は多項式時間��|�� |� �で求めることができる 16）．
また，�P�の下界値��L�� �は，当然のことながら，ラグランジュ乗数 � � ��� �，� � ��� � � � に依存する．それゆえ，
�P�のより強い下界値を得るには，��L�� �が最大となるような �，� を求めることが望まれるが，そのようなラグランジュ乗数はよく知られた劣勾配法（subgradient algorithm）で漸近的に求めることができる 17）18）．
ラグランジアンヒューリスティック法の手順

これまでに �P�の下界値を求める方法について説明したが，それを組み込んだラグランジアンヒューリスティック法の手順は以下のように記述できる．ただし，次の手順における � は繰返し数，�L と �U はそれぞれ�P�の下界値と上界値，そして � は計算打切りのためのパラメータである．
なお，次の手順のS5を実行する方法については後述する．

�1��

�1��

手順6

ここで，式(12)は目的関数で総移動費用の最小化を表す．また，式(13)と(15)は，�個のルートが生成されることを保証する．そして，式(14)は，各ルートに含まれる顧客の需要量の総和が運搬車の最大積載量以下であることを保証する．
6．2

06．3

�1��
� � �, |�| � �

Example of �-tree(� � 8, � � �).

��� � ��� � �� � �� ���, �� � �� ����� ��� � ���, �� � �� | ��� � 1�Fig.5

ラグランジュ緩和法による下界値の算出

ここでは，ラグランジュ緩和問題を解いて�P�の下界値を求める方法を説明する．

―4 ―− 65−ラグランジアンヒューリスティック法

S1. � � 1，�L � 0，�U � �とおく．
S2. 初期ラグランジュ乗数を�� � 0, � � �，�� � 0, � � �, |�|� �とおく．
S3. �L�� � を解いて ��L�� � を求める．
S4. �L � ��L�� � ならば，�L � ��L�� � と更新する．
S5.�P�の実行可能解����� �と，その目的関数値 �� を決定する．
それが決定できない場合はS7へ．

運搬経路問題の近似解法

S6. もし �U � �� ならば，�U � �� と更新する．
S7. ラグランジュ乗数 �，� を劣勾配法で更新する．
S8. � � � � �としてS3へ．� � �ならば終了．

この手順は，繰返し数 � が予め設定した � になったら計算を終了する．これに対して，相対誤差 � を� � ��U � �L �� �L と定義し，それが予め設定した値以下になったら計算を終了させることもできる．
なお，式(14)における�の個数は��2� �であるから，式(14)に含まれる制約式をすべて陽に列挙することは実際的でない．しかし，�L�� �の最適値��L�� �は式(14)に含まれる制約式がすべて判明していなくても求まる．すなわち，判明していない制約式に対するラグランジュ乗数はすべて�� � 0であるとすれば，判明している制約式だけを利用して��L�� �が求まる．事実，Fisherは，一部のSを初期集合として生成し，適宜Sの追加と削除を繰返しながら，手順6のラグランジアンヒューリスティック法を実行している．
また，Fisherは，この手順のS5を実行するための，すなわち，�P�の実行可能解 ����� � を決定するための3つの方法を提案している．ここでは，それらの中から，ラグランジ
ュ緩和問題 �L�� � の目的関数の係数 ��� に注目した次の手順を紹介する．ただし，次の手順においては��� � ∞� �� �∞であるものとする．また，次の手順の開始時における����� �の値はすべて 0 である．
手順7

実行可能解の決定

S1. � � �，� � �，� � 0とおく．
S2. 次式の � � � � � �0� を求める．
� � � ��� ��� ����������

S3. もし �� � � � ならばS5へ．
S4. ���� � � �，� � ���� � �，� � � � �� � ，� � � � としてS2へ．
S5. ���� � �，� � �，� � 0としてS2へ．� � � ならば終了．
なお，この手順の終了時に定まる ����� � より運搬車のルートを構成できるが，それが１つの顧客だけを巡回するルートを含む場合（�P�においては上述の仮定(7)を考慮しなければならないことに注意）や使用する運搬車の台数が � 台を超える場合には，�P�の実行可能解を決定できないことに注意する．

7．おわりに運搬経路問題に関しては，これまでに膨大な研究があり，種々の最適解法や近似解法が提案されている．本稿では，これらの研究の中から，運搬経路問題の基本形に対する代表的な近似解法のいくつかを取り上げて解説した．なお，運搬経路問題に対する他の近似解法や最適解法に関する情報については，文献1）2）3）4）5）6）7）を参照されたい．

参考文献
1） L. Bodin, B. Golden, A. Assad and M. Ball : "Routingand Scheduling of Vehicles and Crews, the State ofthe Art", Computers and Operations Research, Vol.1,
pp.69-211, 1983
2） 久保幹雄, 田村明久, 松井知己 : 「応用数理計画ハン―5 ―− 66−ドブック」, 朝倉書店, pp.983-1063, 20003） G. Laporte : "The Vehicle Routing Problem : An
Overview of Exact and Approximate Algorithms",
European Journal of Operational Research, No.59,
pp.345-358, 1992
4) M. O. Ball, T. L. Magnanti, C. L. Monma and G. L.
Nemhauser : "Network Routing", North-Hooland,
pp.1-30, 1995
5） D. J. Bertsimas and D. S. Levi : "A New Generationof Vehicle Routing Research : Robust Algorithms,Addressing Uncertainty", Operations Research,
Vol.44, No.2, pp.286-304, 1996
6) J. Bramel and D. S. Levi : "The Logic of Logistics",
Springer, pp.67-138, 1997
7) P. Toth and D. Vigo : "Models, Relaxations and Exact
Approaches for the Capacitated Vehicle Routing
Problem ", Discrete Applied Mathematics, Vol.123,
pp.487-512, 2002
8) G. Clark and J. W. Wright : "Scheduling of Vehicles
from a Central Depot to a Number of Delivery Points",
Operations Research, Vol.1, pp.568-581, 1964
9) 山本義嗣, 久保幹雄 : 「巡回セールスマン問題への招待」, 朝倉書店, 1997
10) D. L. Applegate, R. E. Bixby, V. Chvátal and W. J.
Cook : "The Traveling Salesman Problem : A Computational Study", Prinston University Press, 2006
11) J. E. Beasley : "Route First-Cluster Second Methodfor Vehicle Routing", Omega, Vol.11, No.4, pp.403408, 198312) M. L. Fisher and R. Jaikumar : "A GeneralizedAssignment Heuristic for Vehicle Routing",
Networks, Vol.11, pp.109-124, 1981
13) D. Cattrysse and L. N. Van Wassenhove : "A Surveyof Algorithms for the Generalized Assignment
Problem", European Journal of Operational Research,
Vol.60, pp.260-272, 1992
14) M. Savelsbergh : "A Branch-and-Price Algorithm for
the Generalized Assignment Problem", Operations
Research, Vol.45, No.6 pp.831-841, 199715) M. L. Fisher : "Optimal Solution of Vehicle Routing
Problems Using Mimimum K-Trees", Operations
Research, Vol.42, No.4 pp.626-642, 199416) M. L. Fisher : "A Polynomial Algorithm for theDegree-Constrained Minimum K-Tree Problem",
Operations Research, Vol.42, No.4 pp.775-779, 199417) M. L. Fisher : "The Lagrangian Relaxation Method for
Solving Integer Programming Problem", ManagementScience, Vol.27, No.1, pp.1-18, 1981
18) J. E. Beasley : "Lagrangean Relaxation", In C. R.
Reeves, Editor, Modern Heuristic Techniques for
Combinatorial Problems, pp.243-303, McGraw-Hill,
1995