コンテナ輸送における 定期船の航路決定法

2009 年度
卒業論文
コンテナ輸送における
定期船の航路決定法
指導教員
宮本
上智大学
裕一郎
機械工学科
A0671211
助教
管理工学研究グループ
石井智彬
目次
第 1 章 序論 .................................................................................................... 3
1.1 研究背景 .................................................................................................... 3
1.2 研究目的 .................................................................................................... 4
第 2 章 基礎事項 ............................................................................................. 5
2.1 コンテナ船の増加...................................................................................... 5
2.2 混載輸送 .................................................................................................... 8
2.3 オペレーションモード .............................................................................. 9
2.4 Planning Levels ..................................................................................... 10
2.4.1Strategic Planning ............................................................................ 10
2.4.2Tactical Planning .............................................................................. 10
2.4.3Operational Planning ....................................................................... 10
第 3 章 従来研究 ........................................................................................... 11
3.1 非線形整数計画を用いた利益最大化問題 ................................................ 11
3.1.1 研究の概要 ........................................................................................ 11
3.1.2 線形整数計画問題 ............................................................................. 11
3.1.2.1 連続最適化問題と離散最適化問題 ................................................. 14
3.2 船一隻のみによる定期船問題.................................................................. 15
3.2.1 研究の概要 ........................................................................................ 15
3.3 配船計画問題 ........................................................................................... 15
3.3.1 研究の概要 ........................................................................................ 15
第 4 章 Ship Scheduling and Containerized Cargo Routing Problem ....... 17
4.1 本研究と従来研究との違い ..................................................................... 17
4.2Problem Description ............................................................................... 17
4.3Mathmatical Model ................................................................................. 18
4.4Greedy Algorithm.................................................................................... 19
4.5Column Generation Based Algorithm .................................................... 20
1
第 5 章 Finding Cycles Model ...................................................................... 22
5.1 問題設定 .................................................................................................. 22
5.2 本研究で提案する Heuristic ................................................................... 24
第 6 章 計算機実験 ........................................................................................ 26
6.1 パラメータ設定 ....................................................................................... 26
6.2 実験結果 .................................................................................................. 29
6.3 考察 ......................................................................................................... 32
第7章
まとめ ............................................................................................... 37
謝辞 .................................................................................................................. 38
参考文献 ........................................................................................................... 39
付録 .................................................................................................................. 40
2
第1章 序論
1.1 研究背景
戦後の日本は高度経済成長により，多くの発展を成し遂げてきた．この発展に大きく貢
献してきたものの一つには輸出入業が挙げられる．資源を多く得るため，または海外にマ
ーケットを広げて行くためには欠かせない手段である．
そして現在でも，わが国はエネルギー資源のほぼ全量を海外に依存し，衣食住の面で欠
くことのできない多くの資源を輸入に頼っている．我が国の貿易の中で，海上貿易の割合
は，金額ベースで 68.5％，トン数ベースで 99.7％を占めており，海運はわが国の貿易にと
って不可欠な輸送手段となっている．高価で小型のものを運ぶ手段として欠かせない空運
と金額ベースで比べてみても，海運は未だに貿易の主翼を担っていることがわかる．金額
ベースにおける海上貿易の割合を図 1.1 に示す．
本研究では，今後も世界の経済を支える海上貿易をより効率化，発展させるための航路
を決定させる手法を提案する．
図 1.1 金額ベースにおける海上貿易の割合[8]
3
1.2 研究目的
船の航路を決定し，それによってコストを下げ効率性を向上させることを目的とした．
船はコンテナ船に注目した．コンテナ船では，目的地や出発地が異なる貨物でも同時に
運ぶことができ，本研究では全ての貨物に対しての要求を満たすような航路を決定する．
これを以降配船計画とよぶ．
現在でも，船社にとって配船計画の作成は，荷役条件や船舶仕様など複雑な制約を同時
に考慮しなければならないため，非常に煩雑な作業となる．船の数にも左右されるが，一
般的に船社では 1 カ月の計画を作成するために，3 日から 4 日程度の作業が必要である．
本来は，より多く利益が確保できるような効率的な計画を作成することが望ましい．この
配船計画作成作業は，コンピューターによる計算で支援することができる．効率的な配船
計画をコンピューターでの計算により作成するための計算手法を，配船アルゴリズムとよ
ぶ[2]．
本研究では，1，2 週単位で船のサイクルを決め，ある様々な要求を持つ貨物が与えられ
た場合の定期船の航路を決定させることを目的とした．全ての貨物の需要を満たし，且つ
効率的な配船アルゴリズムを用いて配船計画を構築する．
本論文は以下のように構成されている．第 2 章では本研究で用いる手法の基礎事項と，
配船計画に必要な知識について説明する．第 3 章では配線アルゴリズムを用いた従来研究
の概要と特徴について述べる．また，そこに書かれている本研究に至るまでに必要であっ
た手法等について説明する．第 4 章では本研究の基盤となった従来研究のアルゴリズムと
モデルについて説明する．また，本研究で重要となる Sub Problem について述べる．第 5
章では本研究の問題設定や実験に用いる Heuristic に関して説明する．第 6 章では本研究で
実験を行った際のパラメータや結果と考察を示す．第 7 章で本研究のまとめについて述べ
る．
4
第2章 基礎事項
2.1 コンテナ船の増加
海運業界は多くの変化に直面している．最も目立った変化はコンテナ使用の増加が挙げ
られる．積み荷がコンテナに収容されるので，単一の機械での持ち運びが可能になる．ま
た，港労働を最小限にして積み荷取り扱いを容易にすることができる．そしてこの容器の
大きさが標準化され，TEU(Twenty-foot equivalent units)という単位で与えられる．TEU
とはコンテナ船の積載能力を示す単位．1TEU は 20 フィートコンテナ 1 個分を示す。20
フィートコンテナは長さ約 6m×幅約 2.438ｍ×高さ約 3m もの大きさである．コンテナの
輸送は 1985 年では 20％ほどでしかなかったが，現在では 60％もの輸送はコンテナによっ
てまかなわれている．この傾向からしても，現在コンテナ船の輸送は海運業において欠か
せないものであることがわかる．図 2.1 に世界のコンテナ船の隻数の推移を図 2.2 にコンテ
ナ船のイメージを示す．表 2.1 に主要船社のコンテナ船運航状況を表す．
図 2.1 世界におけるコンテナ船の隻数の推移[8]
5
表 2.1 主要船社のコンテナ船運航状況(*1)
コンテナ積載数
船
社
名
国 籍
隻数
(千ＴＥ
Ｕ)
対世界
比
(％)
川 崎 汽 船
日本
86
295
2.5
商 船 三 井
日本
110
368
3.1
日 本 郵 船
日本
114
409
3.5
Maersk Line
デンマーク
519
1,893
16.1
Hamburg Sud
ドイツ
104
273
2.3
Hapag Lloyd
ドイツ
133
492
4.2
Mediterranean Shipping Co.
スイス
383
1,309
11.1
CMA CGM
フランス
328
910
7.7
CSAV
チリ
87
271
2.3
120
442
3.8
110
189
1.6
American President Line (NOL)
Pacific International Lines
シンガポー
ル
シンガポー
ル
Evergreen Group
台湾
177
626
5.3
Yang Ming Line
台湾
84
294
2.5
Hanjin Shipping
韓国
85
369
3.1
Hyundai Merchant Marine
韓国
54
248
2.1
Orient Overseas Container Line
香港
82
354
3.0
China Ocean Shipping (Group) Co. 中国
135
462
3.9
China Shipping Container Line
中国
102
401
3.4
United Arab Shipping Co.
ＵＡＥ
41
135
1.1
Zim Integrated Shipping
イスラエル
108
282
2.4
計
2,962
10,021
85.1
そ の 他
1,656
1,754
14.9
合
4,618
11,775
100.0
小
計
(*1 国土交通省統計データより抜粋)
http://www.mlit.go.jp/statistics/details/kaiun_list.html
6
図 2.2 大型コンテナ船のイメージ図(*2)
(*2 東京都港湾局ホームページより抜粋)
http://www.kouwan.metro.tokyo.jp/kids/gaido/8.html
7
2.2 混載輸送
簡易化のためにトラックにおける従来の輸送について説明する[9]．一般的に部品メーカ
ーは当社工場の近隣に点在し部品を納入しているが，一部部品は他工場へも納入している．
この場合は荷量が少ないことが多く，デポと呼ぶ保管庫に一旦納入し他の荷と積み合わせ
工場に納入する．デポは納入工場の近くに立地しているため工場納入時刻を厳守できると
いうメリットがある反面，デポ費用（主に保管費）がかかる．これは物流費全体の 1/4 を占
めている．デポ費の削減が自動車部品輸送改善の課題となっている．
図 2.3 デポ輸送のイメージ図
混載輸送システムではデポを廃止して荷を工場に直接納入するシステムとした．この場
合，部品メーカーの荷を個々に直納したのではトラック積載率が低下してしまうため，出
荷側に集配センターを設置し荷を集荷・混載することとした．
図 2.4 混載輸送のイメージ図
8
混載輸送とデポ輸送の比較を表 2.2 に示す．混載輸送のメリットはデポを廃止し保管費
を削減できるということの他に，集配センターで荷を集約し，車両を大型化することによ
る輸送効率の向上がある．一方，集配センターから工場までの輸送距離が長いため，交通
渋滞などによる納入時間遅れが発生しやすいといった課題がある．
表 2.2 デポ輸送と混載輸送の比較
デポ輸送 混載輸送
保管費
×
○
輸送効率
○
◎
納入時間厳守
◎
×
この混載輸送を本研究では用いる．コンテナ輸送の場合，一隻で運べる限りの貨物を同
時に輸送することを混載輸送とする．これにより，海運輸送においては隻数の削減を可能
とした．
2.3 オペレーションモード
海運業のオペレーションモードには 3 つの区別があり，Industrial shipping, Tramp
shipping, Liner shipping の 3 つに分けられると 2004 年に Christiansen が発表している[7]．
この 3 つについて述べる．以下では貨物を配送する側のことをキャリアとよぶ．
(a)Industrial shipping
荷送人は船を所有し、総輸送コストの最小化を目指すこと。
(b)Tramp shipping
キャリアの荷主との契約で，特定の時間枠内で指定された港間で大量の貨物を運ぶため
に従事すること．船の容量を考慮して，貨物の収益を最大化させる．
(c)Liner shipping
キャリアが決定する航路やスケジュールを荷主にとって利用可能にし、その上で利益最
大化を目的とすること．
この 3 つは，
Industrial shipping は
“owning a car”
，Tramp shipping は“a taxi service”
，
Liner shipping は“a bus service”と表せる．本研究では，Liner shipping すなわち定期
船について議論する．定期船での配船計画とは主に定期的にスケジュールされたサービス
の経路上での貨物コンテナを運ぶことである．
次に定期船の特徴を述べる．
9
・定期船の特徴
不定期船は港から出発するまで容量を満たすまで待ち，定期船ではそれに関係なくスケ
ジュールを約束し，それに従う．したがって，定期船のほうが諸経費やコストがかかって
しまう．定期船では，航路の運搬回数によって船の数が左右される．
・定期船の成長
定期船輸送はコンテナ輸送において大きく成長している．2003 年のアメリカでは，貿易
全体の 60％が定期船貿易の負担でまかなっている．2000 年 1 月から 2006 年 1 月の間で，
国際的な定期船による取引は 5,150,000TEU から 9,135,000TEU まで約 77.4％増加してい
る．
2.4 Planning Levels
定期船輸送には Strategic，Tactical，Operational の 3 つのレベルによる方向性がある．
それらを以下に示す[5]．
2.4.1Strategic Planning
この段階では，最適な船舶の数を決定する．船を所有することは莫大な出資を伴い，ま
た一日あたり 200TEU の船のアイドリングのコストは$20,000 から$25,000 もかかる[1]．
よって戦略的なレベルの決定は非常に重要である．
2.4.2Tactical Planning
この計画段階では船のルートを作成して，これらの航路への発送割り当てをする．それ
ぞれのサイクルは，同じ港を廻って移動する．キャリアは定期的なスケジュールを計画し，
少なくとも 1 つのサイクルは毎週，各港からの顧客に提供するルートで輸送する．
キャリアがネットワークを設計する問題は船のスケジューリング問題と呼ばれる．
2.4.3Operational Planning
この段階では，キャリアが貨物を受け入れるか拒否する意思決定を行う．もしくは選択
した貨物を載せる船のパスを評価することである．これは cargo routing problem と呼ばれ
る．利益が少ない，もしくは他の貨物があるという理由でより利益を得られる貨物を選択
して運送する．
貨物はその定期船の出発港から到着港までいくつかの中間ポートを訪れることがある．
すなわち到着港から出発港への航路の間に訪れた港で貨物を 1 つの船から別の船に移す行
動を行う．
10
第3章 従来研究
3.1 非線形整数計画を用いた利益最大化問題
3.1.1 研究の概要
この研究は，非線形整数計画問題を用いて利益を最大化させる[5]．それぞれのコンテナ
船が訪れる港の最適な列を求める．またそれぞれの船が訪れる港の間で輸送する最適な貨
物の数を求める．船に複数貨物を積むことや輸送することを割り当てる．さらに貨物のい
ずれかの出発港または到着港を訪問しないように航路を決定することによって，積替えを
考慮しない問題とする．この研究では，アルゴリズムは船 3 隻と，最大 20 港を解くのに 1
時間以内で行う．
次に，線形整数計画問題について説明する．
3.1.2 線形整数計画問題
線形整数計画問題とは線形計画問題の解を整数に限定したものを指す[4]．
次に線形計画問題とは「線形不等式条件
n
∑a
j =1
ij
xij ≤ bi (1 ≤ ∀ i ≤ m )
(3.1)
を満たす x = ( x1 , x 2 ,..., x n ) ∈ R n で，線形の目的関数
n
∑c x
j =1
j
j
を最小（または，最大）にする
x = x * を求めよ」
という問題である．ここで， R
n
は n-次元ベクト空間を表す．また， aij , bi , c j はすべて実
数で，線形計画問題のデータとして与えられる．
条件(3.1)を満たす x を実行可能解，その集まりを P であらわす．P は n 次元ベクトル空
間R
n
内で，有限個の超平面
n
∑a
j =1
ij
xij ≤ bi (1 ≤ ∀ i ≤ m )
で囲まれた領域（有界とは限らない）になる．P を実行可能多面体と呼ぶ．線形計画問題
を
11
n

目的 : c j x j → 最小化 
∑
j =1

条件 : x = (x1 , x 2 ,..., x n ) ∈ P 
(3.2)
と記述する．

線形計画問題(3.2) の目的関数は線形であるから，その等高面  x :

元ベクトル空間 R
n
∑c
j =1
j
n
n
∑c x
j =1
j
j

= 定数  は n 次

内の超平面（n = 2 の場合には等高線）となる．等高面を目的関数
x j の値が小さくなる方向に，実行可能多面体 P の境界と接するまでずらすと最小解
が得られる．一般には，最小解の集合が得られるが，その中に必ず頂点が含まれる．この
ことより，最小解の候補を P の有限個の頂点に絞ることができる．
図 3.1 に数理計画問題においての整数計画問題の分類を表す．
図 3.1 連続最適化に属する代表的な数理計画問題
12
また線形整数計画問題は離散最適化問題に属する．図 3.2 にその図を示す．
図 3.2 離散最適化に属する代表的な数理計画問題
13
3.1.2.1 連続最適化問題と離散最適化問題
一般の数理計画問題は
目的 : f (x ) → 最小化


条件 : x ∈ F ≡ {x ∈ s : g (x ) ≤ 0}
(3.3)
と書ける[4]．ここで，S は n 次元ベクトル R 空間の部分集合，f は R で定義された実
n
数値関数，g は R
n
から m 次元ベクトル空間 R
m
n
への関数である．S は対象とする数理計
画問題を記述するのに用いられる基礎となる空間と考えればよい．
基礎となる空間 S, 実行可能領域 F を表現するのに使われる関数 g : R n → R m ，および，
目的関数 f に種々の条件を課した多くのクラスの数理計画問題が研究されている．数理計
画問題は大きく連続最適化問題と離散最適化問題に分けることができる．
連続最適化問題では，
・S = R （より一般的には，S は R
n
n
の開集合）
・ 関数 g : R → R は連続（多くの場合，微分可能）
n
m
が仮定される．連続最適化に属する代表的な数理計画問題のクラスとそれらの関係を示
すと図 3.1 のようになる．
離散最適化問題では，
・S は有限集合，または，離散的な集合．たとえば，
{
}
(有限集合 ),
S = x ∈ R n : x j = 0または1 (有限集合 ),
S = あるグラフの部分の集まり　{
}
(離散無限集合 ),
S = x ∈ R n : x j = 自然数 が仮定される．関数 f , g に連続性のみを仮定する非線形離散最適化問題のクラスも考え
ることができるが，そのような問題は非常に難しく，関数 f , g が線形関数である場合に限
定することが多い．このように限定したとしても，離散最適化問題には広範な応用がある．
14
3.2 船一隻のみによる定期船問題
3.2.1 研究の概要
この研究では，配送はすべての貨物の出発港のセットから単一のデポへ輸送されると見
なす[2]．つまり最初にデポを単一にすることにより，実行可能な 1 つのルートのみで解決
される．この問題も積替えを許可していない．
最大 19 隻で，ネットワーク上で最大 40 港に付きこのアルゴリズムは数秒以内に解決す
る．
3.3 配船計画問題
3.3.1 研究の概要
配船計画問題は，オペレーターが，荷主の輸送需要の発生場所，時期，量をみながら
船舶の効率的なルートを求める問題の総称である[10]．ここで，貨物輸送を依頼する企業を
荷主といい，荷主から依頼を受け，輸送を実施する企業をオペレーターとよぶ．配船計画
問題では，船隊を構成する船舶の基本性能の他に，港での荷役能力や荷役可能時間帯を考
慮しつつ船隊の運用コストを最小化することを目的とする．荷主とオペレーターにとって，
配船計画の効率化は，収益，省エネルギーの２点からみても重要である．ある一定数のオ
ーダーを運搬する場合，運賃はあらかじめ決まっているため船隊の運用コストを下げるほ
ど収益が増すが，その運用コストは配船計画の効率の善し悪しに直接影響される．したが
って，配船計画の善し悪しが直接収益に影響する．
配船計画問題は，配送計画問題とよばれる数理計画問題と同様の数理的構造をもつ．配
送計画問題とは，主にサプライチェインの最下流で発生する．複数の需要地点に輸送手段
を用いて，巡回しながら物を運ぶ問題である．配送計画問題の基本形は以下の仮定がある．
1. デポとよばれる特定の地点を出発した運搬車が，顧客を経由し再びデポに戻る．このと
き運搬車による顧客の通過順をルートとよぶ．
2. デポに待機している運搬車の種類および最大積載重量は既知である．
3. 需要地点の位置は既知であり，各顧客の需要量も事前に与えられている．
4. 地点間の移動時間，移動距離，移動費用も既知である．
5. 1 つのートに含まれる顧客の需要量の合計は運搬車の最大積載重量を超えない．
6. 運搬車の台数は決められた上限を超えない．
7. 運搬車の稼動時間が与えられた上限を超えない．
通常は，さらに需要地点への到着時間枠など様々な条件が付加される．これらの付加条
件をすべて取り去った問題は，巡回セールスマン問題とよばれる古典的な組合せ最適化問
題になる．
15
数理計画ベースの解法としては，輸送手段に対して可能な巡回路を部分的に列挙し，必
要に応じて巡回路を追加する列生成法とよばれ解法がしばしば有効である．
船舶による貨物輸送の目的は，必要なものを必要な場所に必要な時に届けることである．
鉄鋼メーカーやセメント製造会社など，国内各地の工場で製品を生産し出荷している企業
は，倉庫や工場間で様々な品目を船舶により輸送している．実際の輸送は，輸送を事業と
して行っている企業に運賃を支払って依頼することが多い．荷主は「10 月 1 日に A 港にあ
る鉄鉱石 200，10 月 3 までに B 港に届けてください」という注文をオペレーターに対して
行う．オペレーターは，自社で管理運用している複数の船舶を用いて，荷主から引き受け
た輸送オーダーを処理していく．オペレーターが管理運用する船舶を，まとめて船隊と呼
ぶ．船隊は通常複数の船舶からなっている．各船舶がいつ何をどこからどこに運ぶかは，
オペレーターの担当部門が決定し，それを各船長に指示する．各船舶は指示されたスケジ
ュールに従い，輸送オーダーを処理していく．引き受けた輸送オーダーを処理するための
各船舶のスケジュールは多数存在する．そして，それらのうちどのスケジュールにより運
航したときの，航行距離は互いに異なる．つまり，全く同じ輸送オーダーを処理するにも，
どの船でどの輸送オーダーをどの順序で輸送するかにより，環境に与える負荷も異なるの
である．そこで，オペレーターは，指定通りに貨物を届けるという条件の中で，できるだ
け航行距離(環境負荷評価値)が小さくするようなスケジュールを選択することにより，環境
に与える負荷を低減することができる．
16
第4章 Ship Scheduling and Containerized Cargo Routing Problem
4.1 本研究と従来研究との違い
従来研究では，混載輸送を考慮して定期船の輸送を問題とする[1]．本研究の基盤となっ
たこの従来研究は 2007 年に発表された．これは線形整数計画問題であり，定式化された式
を解くことによって解を得ることができる．しかし重要な点は定式化を解くことではなく，
Sub Problem として存在するサイクルを求めることにある．サイクルとは，本研究では定
期船の一周する航路のことを指す．定式化の中にある変数を決定することによって，定式
化を解くことが可能になる．詳細は後に述べる．本研究では従来研究の定式化の基，違っ
たアプローチによるサイクル決定を行い，納期を緩和できる問題とする．本章では，従来
研究と共通の定式化を示し，従来研究での解法を簡単に説明する．
4.2Problem Description
定式化を行うためには様々な記号や制約が必要になる．最初に定数の説明をする．
港のセットを P と定義する．そして貨物には出発港，到着港，納品される日のデータを
与える．またそれぞれの貨物を区別するために，出発点を o ，目的地を d ，納品される日
を i と定義する．ここで，そのデマンドの値を
D (o ,d ,i ) (TEU)
と与え，さらにそのデマンドの 1TEU あたりの利益を
R ( o , d ,i )
と定義する．また，デマンドのセットを Θ と置く．
キャリアの持つ船隊には様々な種類の船がある．実際には容量，速度，形などばらばら
であるが，ここでは容量の区別のみを行うことにする．そこで， A を全ての船の種類を表
すものとし， a は船を区別する指数としておく．これにより T (TEU)を a タイプの船のキ
a
ャパシティを示し， N a を a タイプの船の数を表す．また貨物，船にかかるコストをまとめ
たものを c とする．
次に，ネットワークの構造として
G = (V , E )
と置く． V は各頂点 v のセットを示し， E は各エッジ e のセットを表す．港 4 つ，曜日
ごとのノードを置いたネットワークの概念図を図 4.1 に示す．
17
図 4.1 ネットワークの概念図[1]
C はサイクルを示し，エッジ上の数字は運航にかかる日数を表す．また，T は積み替え
港を示す．
4.3Mathmatical Model
ここでは， 2 つの変数を示し実際に定式化を行う．
まず 1 つめの変数はエッジ上の流量として
f e(o ,d ,i )
∀(o, d , i ) ∈ Θ
と定義する．また，2 つめの変数はサイクル C が航路として利用されるかを示す 0-1 変数
xc ∈ {0,1}
を与える．これらと 4.2 章で定義した定数を用いることにより定式化を行う．
18
定式化
7
∑ ∑ R(
max
o , d ,i )
=
( o , d ,i )∈Θ j 1
f (vo ,d ,i,v)
((
d , j)
( o ,i )
)
−
∑ ∑ cf (
( o , d ,i )∈Θ e∈E
o , d ,i )
e
(4.1)
such　that
∑
e∈Inedge( v )
∑
f e(
( o , d ,i )∈Θ
7
f e(
j =1
−∑
{
∑
a∈ A C∈C a :e∈C
, ,
(d , j)
∑
−
e∈OutEdge ( v )
o , d ,i )
∑ f (vo d i,v)
(
o , d ,i )
( o ,i
))
o , d ,i )
0 ∀v ∈ V , ∀ ( o, d , i ) ∈ Θ　(4.2)　f e( =
}
T a xC ≤ 0 ∀e ∈ Ev (4.3)
≤ D ( o d i ) ∀ ( o, d , i ) ∈ Θ　(4.4)
, ,
f e( o d i ) ≥ 0 ∀e ∈ E , ∀ ( o, d , i ) ∈ Θ　(4.5)
, ,
となる．
(4.1)式は目的関数を示す．流量と 1TEU あたりの利益をかけ，そこから流量あたりのコ
ストを引いたものを最大化する．以降は制約式を表す．
(4.2)式は全てのエッジにおいて，入流量と出流量は等しいことを示す．(4.3)式は流用が
船のキャパシティを超えないことを表し，(4.4)式は流量の合計はデマンドの合計を超えな
いことを指す．(4.5)式は非負を示す．
サイクルを決定することにより，この計算を解くことが可能である．
次項から，従来研究でのアルゴリズムを図とともに簡単に説明する．
4.4Greedy Algorithm
このアルゴリズムでは，双対を用いる．先ほどの定式化を双対化することにより各エッ
ジに評価値を与えることができる．それを基に補助ネットワークを採用してネガティブコ
ストサイクルを見つける．最も評価値の高いネガティブコストサイクルに船を流し，それ
を繰り返すことでサイクルを決定し問題を解くアルゴリズムである．このアルゴリズムは
シンプルであり，簡単に解を求めることができる．しかしすぐ得られる解の制度は良いと
は限らない．図 3.2 にこのアルゴリズムのアウトラインを示す．
19
全ての船もしくはデマンド
が満たされているか
Yes
No
STOP
補助ネットワークを用いて
ネガティブコストサイクル
を見つける
No
ネガティブコストサイクル
があるか
yes
最も大きいネガティブコス
トサイクルに船を
割り当てる
エッジの容量を更新し、問
題を解く
図 4.2greedy algorithm のアウトライン
4.5Column Generation Based Algorithm
Column Generation とは，列生成法とも呼ぶ．集合分割問題の線形緩和問題を利用し，
列の部分集合からなる部分問題(Subset)を解く．その結果から有望な列の集合を追加してい
く手法である．この手法は幅広く用いられており，大規模な問題にも対応できることが知
られている．図 4.3 にこのアルゴリズムのアウトラインを示す．
20
Column generation problem
を解く
補助ネットワークを構築して
ネガティブコストサイクルを
見つける
ネガティブコストサイクルがあ
るか
No
yes
ネガティブコストサイクルのサ
ブセットを加える
線形計画問題を解く
図 4.3column generation algorithm のアウトライン
21
第5章 Finding Cycles Model
5.1 問題設定
Sub Problem である，サイクルを決定する問題設定を説明する．第 4 章で説明した通り，
デマンドはそれぞれにサイズ，出発港，到着港，供給された日にち(曜日)が与えられる．そ
のデータは制約の基，ランダムに与えられる．サイズは利用する船の容量の 0.1～1.0 倍の
数値で与えられる．それを全て満たすか，もしくは船が全て割り当てられるまでサイクル
を検討する．
また，船には 3 種類のサイズがある．また，混載輸送を用いるという前提で航路を決定
する．船自身は定期船であるため，サイクルが決まるとその航路，曜日をその後守って運
行するものとする．以下にこのような問題設定の決まりを列挙する．
1.
デマンドのパラメータは既知であり，任意の数の港，貨物を運ぶよう船の航海する航
路を決定する．
2.
出発した日にちから 1 週間もしくは 2 週間のサイクルを守って必ず元の港に帰って来
ることができるサイクルを構築する．
3.
それぞれの港は必ず 1 つはデマンドの出発港または到着港である必要がある．
4.
港にはそれぞれ曜日ごとのノードがあり，それらをどの順番で廻るかによってサイク
ルが定義される．
5.
船のスピードは一定としているので，港間の航行距離，すなわち航行日数は往復でも
等しい．
以上の条件の基，本研究のノードとエッジの概念図と共に説明を図 5.1 で行う．便宜上の
ため港 3 つ，デマンド 3 つを流す規模の小さいサイクルで表す．
表 5.1 はデマンドの仮のパラメータである．
表 5.1 デマンドのパラメータ
デマンド
出発港
到着港
曜日
サイズ
(TEU)
D[0]
A(0)
B(1)
月(0)
2560
D[1]
B(1)
A(0)
日(6)
2118
D[2]
C(2)
A(0)
金(4)
5894
22
A(0)
月
火
水
木
金
土
日
月
火
水
木
金
土
日
0 D[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
1日
B(1)
14
15
16
17
18
19
20
21
22
23
24
25
26
27
D[1]
2日
C(2)
28
29
30
31
32 D[2]
33
34
35
36
37
38
39
40
41
図 5.1 ノードの概念図
この図からわかるように，港のノードに番号が割り振る，図 5.1 では 1 週間のサイクル，
つまり最大でも曜日は 2 週間分与えることによって表すことが可能になる．矢印上の数値
は片道の航行日数がどれくらいかかるかを表している．また，表 5.1 よりデマンドが各ノー
ドに割り振られている．
つまり，本研究ではこれらのデマンドを効率よく運ぶためのサイクルを求める手法を提
案する．
23
5.2 本研究で提案する Heuristic
本研究では，冒頭でも述べたように納期緩和に対応した Heuristic を用いる．本研究では
従来研究とは違った，greedy search algorithm をベースにした局所探索法を採用した．そ
もそも greedy search algorithm と局所探索法とはどのようなものか，まず説明をする．
・greedy search algorithm(貪欲探索法)[6]
問題の目的は， u から非負の整数への写像 c; u → Z + が与えられた時


max  f ( x ) + ∑ c(u )　x ∈ F
u∈x


を与える解 x ∈ F を求めることである．
この問題は，最大安定集合，多制約ナップサック問題など多くの組み合わせ最適化問題
を含む一般的なフレームワークである．
貪欲解法では要素 u ∈ U を加えた時に実行可能性を崩さないものの中で c(u ) が最大にな
る u を順次加えることによって解を得る．
・局所探索法[6]
局所探索法の基本構造は，暗い夜道で懐中電灯を頼りに山登りをする人に例えられる．
それゆえ局所探索法は，しばしば丘登り法と呼ばれる．
いま，登山者は真夜中に山の中にいるものとする．ここでのゲームの目的は，限られた
時間内になるべく標高の高い地点に到着することである．夜道は暗いので，現在自分のい
る場所の周り以外は見ることができない．現在地点よりも高い方向がまわりにあればその
方向へ移動する．照らした範囲内に，現在地点よりも高い地点が見つからなかったら，あ
きらめて寝袋を出して寝る．そのときの標高が登山者のスコアになる．
この方法では，いつも最も高い地点で眠れるとは限らない．考えうる山は，いくつもの
丘があるからである．この方法での解は最適解とは限らない．しかし，ある程度の解の精
度が期待でき，かつ実行時間をかなり短縮して解を得ることができる手法である．
これをベースにした探索方法を説明する．まず，最も供給される日にちが早いデマンド
に着目してサイクルを構築していく．納期に従って，そのデマンドを流し，実行可能な他
のデマンドを探索していく．次の港に移動した場合も，その港，もしくは実行可能な港を
全て探索し，輸送可能なデマンドを全て輸送することにより解を得る．5.1章でも述べたよ
うに本問題は定期船であるため，出発港に帰港することを終了条件とした．この探索法で
得られる解はデマンドのデータに依存する．また本提案手法はheuristicを用いているので
必ずしも最適解を得られるわけではない．しかし，デマンドを可能な限り探索し，精度の
高い解を得つつ納期緩和に対応可能なものにした．図5.2にこのアルゴリズムのアウトライ
ンを示す．
24
全ての船もしくはデマンドが
満たされているか
Yes
No
STOP
最も供給されるのが早い
デマンドに船を割り当てる
実行可能な限りデマンドを
探索する
デマンドがあるか
yes
No
デマンドを輸送する．
目的港がこの船の出発港と
同じか
帰港して1つの
サイクルを構築する
yes
図 5.2 本研究の提案する手法のアウトライン
25
No
第6章 計算機実験
6.1 パラメータ設定
問題設定の通り，デマンドパラメータはランダムに割り振る．そこで，デマンドサイズ
以外を 3 種類のデータで実験した．また船のサイズは従来研究と同様に，2000，4000，
8000TEU のサイズを用いる[1]．
船のコストはサイズ毎に，2000,4000,8000 の値を与える．船の数はデマンドの数と等し
く，デマンドを満たせるものとする．1TEU あたりの収益は 5 と置いた．移動によるコス
トはかかる日数の 1000 倍，留まるコストは 200 とする．
港の数を 3，6，デマンドの数を 3，6，9 に設定する．またサイクルを 1，2 週間で実験
を行った(ポート 3 つ，デマンド 3 つ，納期緩和を 3 日，サイクル 1 週間の場合，以下
P6D3H3W1 と表す)．これらのパラメータの設定は，輸送コストが配船コストよりかから
ないようにして，使用する船の数をなるべく少なくしたい．
表 6.1 に Test Class を示し，表 6.2 にデマンドのデータ毎のパラメータを表す．{}内の第 1
項は出発港，第 2 項は目的港，第 3 項は納品日(曜日)を示す．第 1 項と第 2 項では，A～F
の港を順に 0～5 で表す．第 3 項は月～日を 0～6 で表し，2 週のサイクルの場合はその倍
数となる．
表 6.1Test Class
P3D3H0W1 P6D6S0W1 P6D9S0W1
P3D3H3W1 P6D6S3W1 P6D9S3W1
P3D6H0W2 P6D6S0W2 P6D9S0W2
P3D6H3W2 P6D6S3W2 P6D9S3W2
P3D6H6W2 P6D6S6W2 P6D9S6W2
26
表 6.2 デマンドのパラメータ
P3D3W1
P6D6W1
P6D6W2
P3D6W2
P6D9W1
Data1
Data2
Data3
{2,0,0},{0,1,3},{0,2,4},
{0,2,5},{1,2,2},{2,0,1},
{1,0,0},{2,0,3},{0,1,4}
{0,1,1},
{0,1,2},
{2,1,0},
{0,2,3},
{1,2,6},
{1,2,4},
{2,3,6},
{3,2,2},
{2,0,2},
{5,4,1},
{2,1,5},
{3,4,5},
{3,5,2},
{5,4,2},
{5,4,1},
{4,3,4}
{4,3,4},
{4,3,3},
{0,1,2},
{0,1,0},
{1,2,1},
{0,2,6},
{1,2,4},
{3,1,5},
{2,3,12},
{2,3,12},
{3,2,7},
{5,4,2},
{5,3,1},
{4,5,9},
{3,5,4},
{3,5,10},
{5,3,12},
{4,3,8},
{3,4,7},
{2,3,2},
{2,0,0},
{0,1,7},
{2,1,4},
{0,1,6},
{0,2,4},
{2,0,6},
{0,2,8},
{1,0,12},
{0,2,9},
{1,0,6},
{1,2,3},
{0,1,13},
{1,2,10},
{2,0,9},
{1,2,1},
{2,1,5},
{2,1,1},
{1,0,7},
{2,1,0},
{0,1,5},
{4,3,4},
{1,2,4},
{2,3,4},
{3,5,3},
{2,0,2},
{3,4,6},
{5,3,0},
{3,4,5},
{5,3,3},
{1,2,4},
{5,4,1},
{3,2,0},
{0,2,5},
{4,3,3},
{1,2,1},
{4,5,3},
{3,2,4},
{1,0,3},
{2,0,1},
{5,3,6},
{2,0,0},
{3,2,3},
{0,1,3},
{4,3,2},
{5,4,2},
27
P6D9W2
{0,1,2},
{1,0,0},
{2,1,2},
{0,2,6},
{5,3,1},
{4,5,6},
{2,3,12},
{3,2,8},
{0,2,9},
{5,4,2},
{2,0,13},
{2,0,1},
{3,5,4},
{4,3,12},
{5,4,3},
{4,3,8},
{0,2,2},
{3,5,10},
{1,2,7},
{1,2,6},
{1,2,8},
{4,5,9},
{2,3,8},
{3,2,13},
{3,2,13},
{4,5,10},
{4,3,5},
次に，港間で移動するのにかかる日数を表 6.3 に示す．
表 6.3 移動にかかる日数
A-B
B-C
C-D
D-E
E-F
P3W1
1
2
P3W2
1
2
P6W1
1
2
3
2
1
P6W2
2
3
5
3
2
本研究の問題設定では港の数毎，週の数毎にかかる日数を設定した．今回の実験では提
案する手法の有効性を示すため，現実性のあるデータではなく混載輸送や納期緩和を頻繁
に行えるような日数に設定した．
28
6.2 実験結果
まず，3 つのデータ毎のデマンドによる実験の解と実行時間の平均の表を表 6.4 に示す．
同様に，最大値を表 6.5 に表し，最小値を表 6.6 に示す．
表 6.4 実験結果平均
Demand Parameter (average)
Test Class
Data1
Solution
Cost
Data2
Time(s) Solution
Cost
Data3
Time(s) Solution
Cost
Time(s)
P3D3H0W1
41241.5
38000
0.0176
46207.5
36200
0.016
45468.5
34200
0.016
P3D3H3W1
44674.5
39800
0.0223
41843
35600
0.016
51889.5
35800
0.0192
P3D6H0W2
71535.5
57000
0.0406
67257
53000
0.0375
68237.5
53800
0.0374
P3D6H3W2
65871
49960
0.0392
57689.5
57040
0.047
86335.5
52580
0.047
P3D6H6W2
57470.1
62000
0.0549
55530.5
49360
0.0566
60162
56062
0.05
P6D6S0W1
29492.5
75400
0.0486
52560
80600
0.0454
75375
50200
0.0361
P6D6S3W1
35039.5
76080
0.0577
43274
70600
0.0548
75282
54340
0.0454
P6D6S0W2
24680.5
92600
0.07
47269.5
82000
0.0578
48551
76096
0.0609
P6D6S3W2
27516.5
93600
0.0764
36773.5
84000
0.0684
49395.5
75896
0.0669
P6D6S6W2
29020
91120
0.0828
40041.5
82800
0.0732
47524
80696
0.0764
P6D9S0W1
95188
100600
0.0516
100909.5
93600
0.0518
92238
97400
0.0549
P6D9S3W1
106892
93800
0.0591
107592.5
77650
0.0609
103630
89400
0.0687
P6D9S0W2
59110
137876
0.0955
69439.5
139400
0.0923
90128
95400
0.0748
P6D9S3W2
71929.5
135340
0.1051
65434
133440
0.0955
107538
99860
0.086
P6D9S6W2
57301
140420
0.1234
56341
144760
0.1251
104822
103360
0.0956
表 6.4 を見ると，港の数やデマンドの数等を増やすと結果が全て大きい値になっているこ
とがわかる．また，港の数を増やすよりもサイクルの週を増やしたほうが，解，実行時間
は大きな値になっている．しかし，コストは港を増やすほうが大きな値になっている．原
因は港の数は増やしても探索できる範囲はあまり変わらず，サイクルを増やすほうが探索
範囲は広いためである．したがって，港の数が多いほうが船を多用してしまい，コストが
高くなっている．実行時間が大きい理由は，探索範囲に比例するためだと考えられる．
29
表 6.5 実験結果最大値
Demand Parameter (max)
Test Class
Data1
Solution
Cost
Data2
Time(s) Solution
Cost
Data3
Time(s) Solution
Cost
Time(s)
P3D3H0W1
54830
42400
0.032
74060
39800
0.016
70075
40200
0.016
P3D3H3W1
62890
42600
0.032
71020
40000
0.016
68340
40200
0.032
P3D6H0W2
92860
64200
0.047
111875
63000
0.047
99460
63000
0.047
P3D6H3W2
135270
65000
0.047
86525
64400
0.047
112390
60400
0.047
P3D6H6W2
87385
67400
0.063
99190
64000
0.063
103170
68580
0.063
P6D6S0W1
42285
96200
0.063
92320
94600
0.047
104555
59000
0.047
P6D6S3W1
58660
94800
0.063
67450
94600
0.063
86385
64600
0.047
P6D6S0W2
38005
102200
0.078
71705
94200
0.063
77714
83696
0.078
P6D6S3W2
54970
106400
0.078
74030
94400
0.078
99119
85096
0.078
P6D6S6W2
41150
118000
0.094
80730
94400
0.078
79119
84296
0.094
P6D9S0W1
127380
113000
0.063
133440
108800
0.063
117975
107800
0.063
P6D9S3W1
137160
101600
0.063
161145
97000
0.063
130335
108000
0.078
P6D9S0W2
83110
165000
0.109
93730
148600
0.11
131695
109000
0.078
P6D9S3W2
100305
152200
0.125
91480
161800
0.11
149965
124600
0.094
P6D9S6W2
103130
153600
0.141
68425
152200
0.157
156075
155600
0.11
表 6.5 では最大値を表すため，最大の規模では特に実行時間が長い結果が見られる．これ
はデマンドのデータによって実行時間の差が開いてしまうためである．本研究の提案手法
は納期の早いデマンドから出発し，納期や制約に従って可能な限り探索を行う．そのため，
探索範囲がデマンドに与えるデータによって変わってくる．そして，探索範囲が広いデマ
ンドの場合実行時間が大きくなってしまうことがわかる．
30
表 6.6 実験結果最小値
Demand Parameter (min)
Test Class
Data1
Solution
Cost
Data2
Time(s) Solution
Cost
Data3
Time(s) Solution
Cost
Time(s)
P3D3H0W1
26840
30400
0.016
23860
27800
0.016
29985
28200
0.016
P3D3H3W1
29965
30600
0.016
29470
28000
0.016
33675
28200
0.016
P3D6H0W2
40645
52200
0.031
39070
43000
0.031
23310
43000
0.031
P3D6H3W2
26865
36600
0.031
33100
44400
0.047
47655
36400
0.047
P3D6H6W2
25210
43200
0.047
21430
40000
0.047
23365
44440
0.031
P6D6S0W1
13710
60200
0.047
30275
62600
0.031
53230
39000
0.031
P6D6S3W1
16645
53600
0.047
26825
54600
0.047
57875
42400
0.031
P6D6S0W2
6275
82200
0.062
24205
62200
0.047
11124
63696
0.047
P6D6S3W2
11635
78400
0.062
16670
74400
0.062
17694
65096
0.062
P6D6S6W2
14395
77200
0.078
17610
74400
0.062
14099
72296
0.062
P6D9S0W1
64890
85000
0.047
68340
80800
0.047
72615
79800
0.047
P6D9S3W1
70595
80400
0.047
78560
10500
0.047
72695
68000
0.047
P6D9S0W2
24570
102800
0.094
34945
128600
0.078
45310
81000
0.062
P6D9S3W2
45040
120200
0.094
26175
109200
0.078
59800
76400
0.078
P6D9S6W2
34970
116200
0.109
24090
139400
0.109
48960
84000
0.094
表 6.6 では，
他の表に比べて納期緩和 3 日より 6 日の解が悪い結果であることがわかる．
納期緩和 6 日は結果の変動が大きいため，最小値の表で悪い結果が見られた．納期緩和 6
日で実験を行うと，デマンドのデータによっては最も少ない船舶数で航路を決定すること
ができる．しかし，無駄な船の利用や滞在が増えてしまうこともある．そのため，変動が
大きくなると考えられる．
31
6.3 考察
表 6.2 で得られた結果をコストで Test class 毎に表した図を以下に示す．また，データ毎
のパラメータは表 6.2 に示す通りである．
同様に，表 6.2 で得られた解と実行時間を Test class 毎に表した詳細の図は，附録を参照
されたい．
図 6.1P3D3W1 のコスト
図 6.1 では本研究で行った最も小さい規模の結果である．データ 2 のみで納期緩和を行った
ほうが良い結果である理由は，このデマンドのデータが納期緩和を採用するメリットがあ
るためである．規模が小さいため，納期緩和のを行うメリットがはっきり分かれてしまう．
32
図 6.2P3D6W2 のコスト
図 6.2 は港の数は最も少ないが，デマンドの数とサイクルの週のみ規模を大きくしたもの
である．図 6.1 に比べて，探索範囲が広がっているため，納期緩和のメリットがより現われ
ていることがわかる．しかし，納期緩和なしは一番結果が安定している．これは，港が少
ない中で規模を大きくしたものなので納期緩和なしでも一定以上の探索ができ解が安定し
ていると考えられる．
図 6.3P6D6W1 のコスト
図 6.3 は図 6.2 と違い，港の数とデマンドの数を増やし，サイクルの週は 1 週間のまま行
った結果である．データ 2 のみが納期緩和ありで良い結果が見られた．しかし，全体で見
ても結果があまり変わらないのは納期緩和 3 日を行っても探索範囲が納期緩和なしとあま
り変わらないためである．
33
図 6.4 P6D6W2 のコスト
図 6.4 は港とサイクルの週の数が本研究で行った最大規模の結果である．コストは規模に
比例するので図 6.3 と比べて高くなっている．また，付録の図 C，D を見てもわかるように，
デマンドの数は変わっていないため，解の値も低くなってしまっている．しかし，港の数
を 6 つにするにはサイクルは 2 週にしないと現実的ではないため，この実験は必要である．
図 6.5P6D9W1 のコスト
図 6.5 を見ると唯一納期緩和をすると全て良い結果が得られている．これはランダムに与
えたデマンドのデータが偶然全て納期緩和のメリットがあるデータであったためである．
図 6.3 に比べてコストはあまり変わっていないのは，デマンドの数を増やしても混載輸送が
増えて船舶数はあまり変わらないためだと考えられる．
34
図 6.6P6D9W2 のコスト
図 6.6 は本研究で行った実験の最大規模である．この規模まで実験を行ったのは従来研究
との比較をするためである．従来研究との比較は表 6.7 で示す．データ 3 でかなりコストが
少ない結果が見られた．しかし納期緩和あり，なし共に同等の結果となっているので，デ
マンドのデータがその結果をもたらした理由であると考えられる．図 6.6 では納期緩和 6
日の結果は全て悪い結果となっている．これは規模を大きくすれば必ず納期緩和の値を大
きくすれば良いとは限らないことを示している．
多くのケースでは納期緩和を行うとコスとを少なく，解を良くした結果が得られた．し
かしこの提案手法はデマンドの出発港，到着港，輸送量等のデータに依存しているため，
値によって解やコストが変動している．デマンドのパラメータによっては，納期緩和をし
ないほうがコストは少ない，または良い解を得る結果も見られる．つまり納期緩和をする
ことによって無駄な滞在をしてしまっていることがある．また混載輸送を頻繁に行うこと
になるため，パラメータによっては空輸送が増えてしまうことがある．加えて必要以上の
サイズの船を利用してしまうこともある．しかし納期緩和を行ったほうが良い解を得てい
ることが多いのも事実である．納期緩和を 6 日にするよりも 3 日に留めたほうが良い結果
を得られることもあった．したがって必ずしも納期緩和を増やせば良いとは言い切れない．
すなわちデマンドのパラメータによっては納期緩和の値を変えて航路を決定することが必
要と言える．表 6.6 にポート 6 つ，デマンド 6，9 つの従来手法との実行時間の比較を示す．
35
表 6.7 従来手法との実行時間の比較
従来手法
従来手法
１
提案手法
従来手法
２
納期緩和
なし
納期緩和
3日
納期緩和
6日
P6D6
0.09
1.3
0.06
0.07
0.08
P6D9
0.13
1.73
0.09
0.1
0.11
従来手法 1 は Greedy Algorithm を示し，従来手法 2 は Column Generation Based
Algorithm を表す．
従来手法 2 よりも従来手法 1 の実行時間が短い理由は 4.4 章で説明した
通りである．
表 6.7 を見てもわかるように，従来手法よりも実行時間を短縮することに成功した．納期
緩和を行っても，従来手法より早く解を得ることができた．
結果として本研究の提案手法により実行時間の短縮，納期緩和への対応が可能となった．
36
第7章 まとめ
本研究ではコンテナ輸送における定期船の航路を決定することでより効率的に，またコ
ストを減少させて利益をあげることを想定した．その上で，従来手法とは異なった heuristic
を採用することにより納期緩和を加味した手法を提案した．
本研究の提案手法はデマンドのパラメータによって左右されてしまうため，必ずしも最
適解を得られるとは限らない．しかし実行時間を短縮し，納期緩和や混載輸送を含めるこ
とによって，より汎用性の高いアルゴリズムを構築することに成功した．
さらに本研究を実用的にするために，規模の拡大や探索範囲を広げることが今後の課題
である．また，納期緩和をすれば必ず良い解が得られるわけではなかったため，データ毎
に最適な納期緩和の値を与えるシステムも構築する必要がある
37
謝辞
本研究を進めるにあたって，終始丁寧にご指導，ご鞭撻を頂きました宮本裕一郎助教に
深く感謝の意を表します．
また，研究全般にわたり多くのご助言を頂きました伊呂原隆准教授に深く感謝の意を表
します．
その他，本論文を作成するにあたり，お世話になりました管理工学講座の皆様に深く御
礼申し上げます．
38
参考文献
[1]Richa Agarwal and Ozlem Ergun: Ship Scheduling and Network Design for Cargo
Routing in Liner Shipping. Transportation Science, 42(2), 2008, pp.1-29
[2]Fagerholt K.: Optimal fleet design in a ship routing problem. International
Transactions in Operational Research, 6, 1999, pp.453-464
[3]小林和博：配船アルゴリズム．海上技術安全研究所報告，7(4)
(38)，2007，pp.463-466
[4]小島政和：数理計画法の最近の発展— 内点法を中心にして—．第４８回理論応用力学講演
会講演論文集，1999，pp 306-309
[5]Rana,K and R,G,Vickson: Routing container ships using lagrangean relaxation and
decomposition. Transportation Science, 25, 1991, pp.201-214
[6]久保幹雄・JP ペドロソ：
『メタヒューリスティクスの数理』．共立出版，東京，2009
[7]Christiansen Marielle: Ship routing and scheduling. Transportation Science, 38(1),
2004, pp.1-18
[8]日本船主協会ホームページ：海運統計要覧．http://www.jsanet.or.jp/data/
[9]岡田和義，佐藤康治，久保幹雄：自動車部品の混載輸送における輸送計画モデル．オペ
レーションズ・リサーチ ．経営の科学 ，42(5)，1999，pp.321-324
[10]柴崎隆一：東アジアを中心とした国際海上コンテナ貨物流動シミュレーションモデルの
構築．計画・交通研究会ワーキングペーパーシリーズ，No.09-1，2009，pp.1-56
39
付録
表 6.2 で得られた結果を解，実行時間で Test class 毎に表した図を以下に示す．また，デ
ータ毎のパラメータは表 6.2 に示す通りである．
図 A P3D3W1 の解
図 B P3D6W2 の解
40
図 C P6D6W1 の解
図 D P6D6W2 の解
41
図 E P6D9W1 の解
図 F P6D9W2 の解
42
図 G P3D3W1 の実行時間
図 H P3D6W2 の実行時間
43
図 I P6D6W1 の実行時間
図 J P6D6W2 の実行時間
44
図 K P6D9W1 の実行時間
図 L P6D9W2 の実行時間
45