1.Introduction

Ship fleet management bears in variety of problems such as routing, scheduling, and deployment of ships in a fleet. A good overview situation of ship fleet management planning provided by Ronen [1,2]. By definition, routing is the assignment of sequences of ports to a ship. Scheduling refers to the routing of ship with time attached in various events on a ship's route while deployment is defined when ships are designated to perform multiple consecutive trips on the same route, and therefore this problem is associated with a longer planning horizon.

The fleet of ships may involve ships of different size, speed and cost structure. A ship involves capital/fixed cost and operating cost. A capital cost usually counted to in million US dollars while the daily operating cost can be thousands of dollars. From these facts, it is crucial to improve significantly economic aspect of shipping by increasing ship utilization. In this sense shipping companies have many similar problems such as deciding routes and schedules for available ships in the fleet and deciding the optimal size of fleet as well. More efficient use of ships leads to the more efficient use of natural energy (fuel oil).

Mathematical modeling has been widely employed to solve several versions of ship fleet management problem. This study aims to apply mathematical modeling to several problems in ship fleet management planning. Following are three different topics which bears in the area of ship fleet management planning carried in this study: ship routing problem transporting two-type of commodities, marine inventory routing for petroleum products distribution problem, and ship routing design for Japanese domestic container transportation. Following sections are discussing individual research topics taken in this research.

2. Ship Routing Problem Transporting Two Types of Commodities

2.1.Background and Problem definition

In port operation, ships often require to deliver/pickup or both simultaneously pickup and deliver some amount of cargos. The type of cargos can be the same single cargo, or multiple commodities. As the operation of semi-container ship, she has to serve several amounts of cargos in different types say, cargos in container unit and pallet cargos in tonnage unit. This study aims to determine the size of fleet of known ships types and to determine corresponding route for each ship while transporting two-commodity cargos. In order to find the optimum size of fleet with their corresponding routes, the objective is set as to minimize total costs of transport which consist of fixed and operational costs.

The network of study is based on hub-and-spokes environment. In hub-and spokes environment, one port is set as a hub port and the remaining ports are set into feeder ports. One route is defined as voyage of a ship from hub port to at least one feeder port and return to the hub port. For preliminary study, the operation at hub port only to pickup the cargos while the operation at feeder port for delivering cargos. It is assumed that there is no simultaneously pickup and delivery operation at feeder port. Time operation/planning period are taken as weekly, service (168 hours). It means that as long as this planning period is not violating, the ship can make several routes within this planning period.

2.2. Solution Method and Numerical example

To solve the problem, solution approach is followed work of Fagerholt [3] and Suprayogi et al. [4]. In their approach, the procedure consists of three phases of the optimization algorithm; generating feasible single route, generating multiple routes, and solving the set partitioning problem formulation. In a development of from previous works [3,4], this study discusses two type of commodities to be transported by ship while their studies only focusing on one type of commodity.

In Phase 1, solution approach aims to generate all feasible single routes while all constraints are not violated such as ship capacity and planning route time. If there is more than one available ship, single routes are generated for all ship types. To ensure that ports in a route have an optimal visiting sequence, a traveling salesman problem (TSP) for ports in route is employed. In Phase 2, multiple routes based on all feasible single routes have been at phase 1 were generated. A multiple route can be described as a route which consists of two or more single routes. The feasibility of the multiple routes is controlled by maximum planning horizon. All generated multiple routes must not violate the maximum time horizon. Moreover, based on all feasible generated single and multiple routes, the optimal set of routes that give the cost minimum were selected by formulating the problem into set partitioning formulation. The algorithms on Phase 1 and Phase 2 can be seen in Table 1.

Solution method is applied to a set of ports in a hub-and-spokes environment. Seven ports in Indonesia are studied; Tanjung Perak, Tanjung Emas, Sampit, Samarinda, Balikpapan, Ujung Pandang, and Pantoloan. As a second largest port in Indonesia, Tanjung Perak which is located in Surabaya, East Java is selected as a hub port and other ports as feeder ports. Given demand data, ship type, and other economics data, Fig.1 shows the illustration of routes and fleet composition to cover all demand of shipping services.

3. Marine Inventory Routing for Petroleum Products Distribution Problem

3.1. Background and Problem definition

In order to distribute their products, a company often ships the products not initiated by orders from customers, but rather the company must schedule the shipments to assure the customer never run out of stock. This challenging problem in logistical problem by integration between vehicle routing problem and inventory control is known as inventory routing problem.

Another type of inventory routing problem also arises in the area of sea transportation where ships are used instead of trucks. Ronen [5] stated the term of marine inventory for the cases in the sea transportation. Although marine inventory routing problem are similar with the inventory routing problem, there are several differences: a fleet of ships may consist of ships with different size, compartment, cost structure and other characteristics. When shipment consists of multiple products to be loaded in the same ship, the quantity of product have to be adjusted to fit the available compartment size. In marine inventory routing, the number of ports in one voyage which are served by one ship usually consists of one or few unloading ports while the transit time is usually much longer (days instead of hours).

This study focuses on determining a set of delivery routes for heterogeneous ships from a single distribution center to several demand locations. Moreover, this study addresses the question on how much to ship the products to demand points within planning horizon. Due to its nature, the products must be shipped in separate compartments. There is a known limited storage capacity for each product at each demand point while distribution center is assumed never run out of stock availability.

3.2. Solution Method and Numerical example

Two phases of approach is employed to solve the problem. The main idea of the approach is to construct a set of delivery routes within shipment planning period and execute the routes in recurrent basis for longer planning horizon. In phase 1, by giving available ships with different compartment size and cost components, a set of delivery routes are generated. In phase 2, based on delivery routes obtained in phase 1, we decide how much of each product to ship at every shipment period.

In phase 1, the approach aims to generate a set of delivery routes for available ships to transporting products from a single distribution center to demand points in one shipment period. To determine a set of delivery routes, first we define a cluster of ports to be a group of demand points that can be served cost effectively by a single ship. Shipping distance that corresponds to a cost serving a cluster depends on geographic locations, storage capacities, and usage rates for each product. We estimate shipping distance to visit demand points in the cluster to be the length of an optimal traveling salesman problem (TSP) tour using Held and Karp dynamic programming. We employ a set partitioning in order to determine an optimal delivery routes from feasible routes using different ship sizes. Phase 2 addresses the question on how much each product to ship from distribution center to demand points using delivery routes obtained from phase 1. The shipment period is extended to longer planning horizon. The problem is modeled into mixed integer programming based on work by Campbell et al [6]. Moreover the formulation was modified to cover multi-products and heterogeneous types of ships. In the first step of this phase, we try to estimate how many routes should be made by the company within the planning horizon.

Three different product types (gasoline, kerosene, and diesel oil) need to deliver to demand points using small tanker ships. It is assumed that two types of small tanker ships are available. Small tanker type 1 has dedicated compartment for gasoline, kerosene, and Diesel oil respectively 500:750:750 m3 while small tanker type 2 has 700:1000:1000 m3. All ships have the same 12.5 knots of service speed. The company must ship their products in order to assure the demand point does not out of stock. The inventory of each product is specified by the maximum tanks' capacity and consumption rates of each product at demand locations. In order to increase ship utilization by means increasing operation time over planning, the ship is allowed to make multiple trips. Multiple trips were generated by combining every single trip obtained in phase 1 and the numbers of trips and quantity to deliver were calculated. Fig.2 shows solution by considering only single trips was done by the ships in the fleet while Fig.3 shows the solution when multiple trips are allowed.

From figures above, it can be seen that by allowing a ship to make several trips over planning horizon, the number of ships can be reduced as well as the total cost for distributing the cargos.

4. A Ship Routing Design for Japanese Domestic Container Transportation

4.1. Background and Problem definition

Due to the Kyoto protocol [7] released by the United Nations Framework Convention on Climate Change (UNFCCC) which is mainly concerned about greenhouse gas emission, Japan has to reduce greenhouse gas including carbon dioxide (CO2) at least 6% within the period of 2008 - 2012. In the transportation sector, one way to reduce CO2 emission can be achieved by effective and efficient transportation routes/planning. The optimal vehicle routes lead not only to the minimum CO2 emission but also to minimizing transportation cost.

In the Japanese domestic container transportation problem, Kobe port is considered as a hub port. There is a huge amount of containers imported from foreign countries what are being loaded down at Kobe port. Kobe port behaves as hub port in the vehicle routing problem with pickups and deliveries (VRPPD). A certain amount of containers have to be delivered to each feeder port and at the same time, some containers need to be picked up from the feeder port and sent back to the hub port (Kobe). The aim is to find the optimal set of ship routes and ship fleets with the least carbon dioxide emission which will satisfy all customer demands and respect the maximum capacity of vehicles and maximum ship traveling time constraint.

4.2. Solution Method and Numerical example

The method was done by formulating mathematical model two phases: route construction (Phase 1) and route combination phase (Phase 2). Phase 1 address on generating individual ship routes with the least carbon dioxide emission in total, while the route combination phase will combine the individual ship routes from Phase 1 and assign the combined routes to ships by not violating the maximum traveling time of ship. The objective of Phase 1 is to minimize the CO2 emission from ship transportation while Phase 2 is to minimize the number of required ships. In Phase 2, the problem is formulated and solved a bin packing problem. In this study, the maximum traveled time of each route is defined in advanced, and maximum time can be considered as a bin capacity. The total traveled time of each individual route is similar to the volume of objects to be packed in the bins.

Demand data for pickup and delivery cargos for 21 ports are considered in this study. To serve these ports, 4 types of ships with different capacity and speed are used. Following table shows the CO2 emissions resulted by each ship type. It can be seen that Shinnitsukaimaru gave the lowest CO2 emissions.

Several scenarios were simulated in order to find correlation between the ship sizes, speed and waiting time at port to the increase of CO2 emissions as shown in Fig.4 and Fig.5. From these Figures by employing larger ships (250 TEU) will give less CO2 emissions compared with smaller ships (140 TEU) since smaller number of ships in the fleet are necessary in order to cover all the demand.

5. Conclusion

In this thesis, mathematical modeling approach has been used in order to solve three different topics that bear in the area of ship fleet management planning. The contribution of this study is ranging from the modeling aspects to the development of solution approaches for the problems under study. Two types of commodity ship routing problem is considered in this study. Based on method proposed by other researchers, the origin models have been modified in order to solve routing of ships carrying different types of products. Formulation for solving marine inventory routing issue also developed. The development is done by some modification to existing methods. The proposed formulation worked well for given numerical example in order to solve problem of transporting various kinds of petroleum products to demand locations. The formulation also made possible that the different products can be carried by the same ship in her voyage. In the third topic, a modification from the existing Simultaneous Vehicle Routing Problem with Pickup and Delivery (SVRPPD) problem was done in order to solve the real shipping problem for the Japanese domestic container transportation.

Table 1: Algorithm on Phase 1 and Phase 2

Fig.1: Routes and fleet composition

Fig.2: Solution for single trip only

Fig.3: Solution by considering multiple trips

Table 2: Result summary from four types of ships

Fig.4: Waiting time and CO2 emission for 250TEU

Fig.5: Waiting time and CO2 emission for 250TEU

本論文は8章から構成される。

第1章は、研究の目的と背景について述べている。本研究の目的は、船舶管理分野の幾つかの航路設計問題に対し、数理モデルを用いた解法を提案することによって解決可能な問題領域を拡張すると共にその解析事例を示すことである。

第2章は海運業について概観している。本章では、まず海上輸送と船種について分類・整理し、輸送コストを構成する各要素の定義と相互の関連について説明している。次に、海上輸送における船舶投資やオペレーションに関する経済的な問題、更に海運業に特有な幾つかの課題についても簡潔に整理している。

第3章では船隊管理計画における幾つかの主要な問題、すなわち、船隊配置(ship deployment)、運航経路計画及びスケジューリング作成問題(ship routing and scheduling)、在庫を考慮した運航経路計画問題(inventory ship routing)について議論している。これらの課題は定期船運航業、不定期船運航業、及びインダストリアルシッピング(荷主兼船主)業に関係するものである。ここではそれら業態の分類を行い、課題の整理を行っている。また、これらの船舶分野の運航経路問題等は一般的な運搬経路問題等とも密接に関係するものであることから、それらの解法についても本章で概観している。

第4章は2種類の貨物を輸送する場合の運航経路計画問題について述べている。船は同一種類もしくは複数種の貨物を積載可能であるものとする。セミコンテナ船であれば、コンテナ貨物とパレット貨物が輸送対象となる。この研究では、あらかじめ定められた複数の候補船のサイズから船の大きさ、及びその運航経路を定めることを目的とする。解法は2つの主たるステップから構成される。一つは、可能な経路を生成する段階であり、もう一つは、生成された候補経路から実際に運航するルートを選択する段階である。従来は同種問題において1種類の貨物しか扱えていなかったが、本研究により複数種類の貨物を扱えるようになった。

第5章では、石油輸送を想定して、在庫を考慮した運航経路計画問題の解法について述べている。本研究では、複数品種の石油製品を単一の供給施設から複数の需要地点まで輸送することを考える。その際、製品輸送において供給施設では在庫がなくなることはないと仮定する。製品輸送の運航経路計画及びスケジューリングを行うに際し、問題を2つのステップに分解して考える。基本的な輸送ルートの決定ステップと、輸送量の決定ステップである。基本的な輸送ルートを決定するには動的プログラミングが用いられ、需要地点への輸送量の決定には混合整数計画問題として課題を定式化後、汎用ソルバーを求めて解を求めている。従来は同種問題において1種類の貨物しか扱えていなかったが、本研究により複数種類の貨物を扱えるようになった。

第6章では、日本の内航コンテナフィーダー輸送を例題として取り上げ、ハブー&スポーク輸送におけるピックアップ&デリバリー方式の輸送について輸送経路を求めている。時間内に運行が可能な場合には隻数を増やさず、同じ船舶で別のルートも運行するマルチトリップも考慮することができるようになっている。混合整数計画問題モデルがCO2排出量を最小化させるために用いられている。本研究により、荷役所要時間、輸送時間制約、輸送量制約等に関して従来よりも現実に即した扱いが可能となった。

第7章では将来の研究方針について議論を行っている。サービス網に入れるべき港の数が増えた場合や輸送量の増大等の事業の発展、政策の影響、提案手法による計算結果の実施法等について検討されている。

第8章では全体を通した議論を行い、本研究のまとめが示されている。

現実の問題は規模が大きく、純粋に数理計画法で解こうとするときわめて困難であるが、著者は二段階に解法を分割することで問題を解きやすくしている。このことは、厳密な解を得る保証はなくなることを意味しているが、例題を通して具体的かつ理解しやすい解が得られて、現実の問題に応用しうることを示している。このことは今後の船社の経営を見る上でも、また温室効果ガス低減のための各種政策を考える国家的な見地からも重要な環境学的分析を行う手法を提言しているといえる。

以上要するに、海上物流システムに数理計画法を巧妙に利用することで、あたらしい現実的な環境学的設計手法を提示できたといえる。

なお、本論文第4章は、Hiroyuki Yamato、Hiroshi Matsukuraとの共同研究であるが、論文提出者が主体となって分析及び検証を行ったもので、論文提出者の寄与が十分であると判断する。

本論文第5章は、Hiroyuki Yamato、Hiroshi Matsukuraとの共同研究であるが、論文提出者が主体となって分析及び検証を行ったもので、論文提出者の寄与が十分であると判断する。

本論文第6章は、Maytouch Udommahuntisuk、Hiroshi Matsukura、Hiroyuki Yamatoとの共同研究であるが、他の章と同様に論文提出者が主体となって分析及び検証を行ったもので、論文提出者の寄与が十分であると判断する。

したがって、博士(環境学)の学位を授与できると認める。