## Ship Scheduling and Network Design for Cargo

TRANSPORTATION SCIENCE

Vol. 00, No. 0, Xxxxx 0000, pp. 000–000 issn 0041-1655 | eissn 1526-5447 | 00 | 0000 | 0001

INFORMS

doi 10.1287/xxxx.0000.0000 c 0000 INFORMS

Ship Scheduling and Network Design for Cargo Routing in Liner Shipping

¨ Richa Agarwal, Ozlem Ergun

School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA. ragarwal@isye.gatech.edu, oergun@isye.gatech.edu

A common problem faced by carriers in liner shipping is the design of their service network. Given a set of demand to be transported and a set of ports, a carrier wants to design service routes for his ships as eciently as possible, using the underlying facilities. Furthermore, the protability of the service routes designed depends on the paths chosen to ship the cargo. We present an integrated model, a mixed integer linear program, to solve the ship scheduling and the cargo routing problems simultaneously. The proposed model incorporates relevant constraints, such as the weekly frequency constraint on the operated routes, and emerging trends, such as the transshipment of cargo between two or more service routes. To solve the mixed integer program, we propose algorithms that exploit the separability of the problem. More specically, a greedy heuristic, a column generation based algorithm and a two phase Benders decomposition based algorithm is developed and their computational eciency in terms of the solution quality and the computational time taken is discussed. An ecient iterative search algorithm is proposed to generate good schedules for ships. Computational experiments are performed on randomly generated instances simulating real life with up to 20 ports and 100 ships. Our results indicate high percentage utilization of ships’ capacities and a signicant number of transshipments in the nal solution. Key words : maritime transportation; liner shipping; Benders decomposition

Introduction

Sea cargo is the freight carried by ships and it includes anything travelling by sea other than mail, persons and personal baggage. A global sea carrier is a person, business or organization that oers transportation services via sea on a worldwide basis. A shipper is a person or company who is either the supplier or the owner of the cargo that is to be shipped. With rates for sea cargo transportation at approximately one-tenth of air freight rates, fewer accidents and less pollution maritime transportation is regarded as a cheap, safe and clean transportation mode, compared to other modes of transportation. Increasing globalization and inter-dependence of various world economies is leading to a tremendous positive growth in the sea cargo industry. International and domestic trade of many nations depend on this mode of transportation. According to American Association of Port Authorities (2006), in the United States, which is the largest trading nation in the world for both imports and exports - accounting for nearly 20% of world trade, sea cargo is responsible for moving over 99% of the international cargo. U.S. ports and waterways handle more than 2.5 billion tons of trade annually, and this volume is projected to double within the next fteen years. Increase in sea-borne trade worldwide has led to similar trends in the growth of the world eet. In 2005, world sea-borne trade increased to 7.11 billion tons of loaded goods (a 3.8 % annual growth rate) and the world eet expanded to 960.0 million deadweight tons (a 7.2% increase) (United Nations Conference on Trade and Development (2006)). Although the eet mix and size have changed over time considerably, the ecient utilization of the ships remains to be one of the main determinants of a carrier’s protability. A ship involves a major capital investment, in millions of US dollars, and its daily operating costs can be in tens of thousands of dollars. Hence, development of optimization based decision support systems is necessary for ecient eet management.

1

2

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

Figure 1

Growth in container movements worldwide. Source: Drewry Container Market Quarterly

The sea cargo industry is going through many changes that are reshaping its face. First, we briey discuss some of these emerging trends. One of the most prominent changes is the increasing use of containers. Containerized cargo is the cargo that have been physically and economically stored in a container. Containerization of cargo has revolutionized the sea cargo industry by minimizing port labor and facilitating cargo handling. The dimensions of containers have been standardized. The term twenty foot equivalent unit (TEU) is used to refer to one twenty foot long container. According to Drewry (2001), at the start of 1980s only around 20% of all general cargo shipments were carried in containers. In 2001, this gure increased to 60%. An IBM white paper, Hingorani et al. (2005), shows that the container shipping market is still growing at 8-10% per year. This trend is depicted in Figure 1. A serious challenge associated with containerized shipping is the repositioning of empty containers. Because of the huge imbalance in trade volume on some routes, carriers need to reposition empty containers incurring signicant costs. According to ROI (2002) a 10% reduction in equipment and repositioning costs can potentially increase protability by 30-50%. The sea cargo industry has seen a tremendous growth in number as well as in size of transshipment ports. A transshipment port is a port where cargo is transferred from one ship to another. Through a sequence of moves by cranes, cargo is transferred either directly from one ship to another or temporarily stored at the port before being loaded onto outbound ships for further transportation. Use of containers makes this transfer very convenient and cost eective. Transshipment services provide carriers with additional routing options, reduced transit times and act as facilitator of international trade. For example the Hutchinson terminal in Freeport, Bahamas has become a major transshipment port between the Eastern Gulf Coasts of the United States, the Gulf of Mexico, the Caribbean, South America, and trade lanes to European, Mediterranean, far Eastern and Australian destinations. Other major international transshipment ports include Singapore, Port Klang in Malaysia and Hong Kong. In 2003, approximately 30% of worldwide container movements were transshipped and it is believed that this number is rising. According to United States Customs Service (2003) 80% of all containers handled at the port of Singapore, world’s second largest container port and world’s busiest port in terms of shipping tonnage, are transshipments. Collaboration among sea carriers is not new. Carriers used conferences, as a means for curbing competition and controlling tari rates in the market, as early as 1875. More recently, carriers are forming strategic alliances that allow them to realize economies of scale, extend their customer base and increase asset utilization while providing customers with more frequent sailings and faster transit times (Song and Panayides (2002)). Since 1990, when Sea-Land and Maersk introduced the

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

3

Strategic Planning (long term) Acquire resources, determine fleet size and mix

General policies and guidelines Revenue and cost information

Tactical Planning (medium term) Design the service network (frequency of routes, port selection, port rotation), assign ships to routes

Goals, rules and limits Revenue and cost information

Operational Planning (short term) Choose which cargo to accept/reject for routing, route the selected cargo Simultaneous ship scheduling and cargo routing problem

Figure 2 Dierent planning levels for liner shipping

alliance system and began sharing ships in the Atlantic and Pacic oceans, strategic alliances have become increasingly common. Today smaller alliances collaborate to form even bigger alliances, for example The Grand Alliance and The New World Alliance laid down the foundation for cooperating in 2006. The trend of consolidating eets and service routes demands better decision support systems to control a large eet of ships and to solve large scale scheduling and optimization problems. Christiansen et al. (2004) describe in detail the division of the global shipping industry into three dierent modes of operation, industrial, tramp and liner. In industrial shipping, the shipper owns the ships and aims to minimize the total shipping costs. In tramp shipping, a carrier engages in contracts with shippers to carry bulk cargo between specied ports within a specic time frame. Additional cargo (if any available in the market) are picked depending on the eet capacity to maximize revenue. In liner shipping, a carrier decides on a set of voyages, makes the schedule available to shippers and operates on it. Thus, one can identify industrial shipping with “owning a car,” tramp shipping with “a taxi service” and liner shipping with “a bus service” with denite schedules and a published itinerary. The focus of this paper is liner shipping. Liner shipping mainly involves carrying containerized cargo on regularly scheduled service routes. Liner services involve higher xed costs and administrative overhead than for example tramp shipping because tramps usually wait until they are full before departing from a port whereas liner services promise to depart on predetermined schedules regardless of whether the ship is full. The number of ships required for a given liner service route is determined principally by the frequency required on the service route, the distance travelled by a ship on the route and the speed of the ship. For example, a weekly liner service between New York and Hamburg may require four ships to maintain the necessary frequency. As observed by Christiansen et al. (2004), liner shipping is growing at a high pace with the increasing global container trac. In the United States, in 2003, liner shipping with its network of ships, containers, port terminals and information systems, handled over 60% of the total sea-borne trade. According to Barry Rogliano Salles- AlphaLiner (2006) between January 2000 and January 2006, the TEU capacity deployed on global liner trades has risen from 5,150,000 TEUs to 9,135,000 TEUs, a 77.4% increase. Liner shipping involves decision making at strategic, tactical and operational planning levels. Figure 2 outlines the key decisions that need to be made at dierent levels of the planning horizon. In the strategic planning stage, the optimal number and mix of ships in a eet is determined. Given that owning a ship involves a huge capital investment (usually in millions of US dollars)

4

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

and the cost of idling a 2,000TEU ship is $20,000-$25,000 per day, the strategic level decisions are extremely important. In the tactical planning stage, the service network is designed by creating the ship routes, i.e. the sequence of port visits by a given eet, and the assignment of ships to these routes. Ships move in cycles from one port to another following the same port rotation for the entire planning horizon. To maintain a customer base and to provide customers with a regular schedule most carriers have at-least one departure each week from each port visited on a service route (i.e. a cycle). This requires that the number of ships that operate on a cycle be at-least equal to the number of weeks that it takes to complete the cycle. Some cycles such as those connecting Asia to North America, may take up to eight weeks to complete, which means that a carrier requires at-least eight ships to introduce a new service on such a route. The problem of designing the service network of a carrier is referred to as the ship scheduling problem. In the operational planning stage, a carrier makes decisions regarding which cargo to accept or reject for servicing and which path(s) to use to ship the selected cargo. This is referred to as the cargo routing problem. A carrier may elect not to transport some cargo, either because it is not protable or because there is other cargo, perhaps at other ports, that is relatively more protable. A cargo starts its trip from an in-land location and arrives at its origin port. This network which utilizes trucks, railroads, or waterways to bring cargo from an inland location to its origin port is known as the feeder network. Cargo then moves from its origin port to its destination port, possibly after visiting some intermediate ports. From there it is taken to its nal in-land destination using another feeder network. Some of the intermediate ports that a cargo visits during its journey from the origin port to the destination port may act as transshipment ports where cargo is transferred from one ship to another. The decisions made at one planning level aect the decision making at other planning levels as well. The decisions at the strategic level set the general policies and guidelines for the decision making at the tactical and operational levels. Similarly, the decisions at the tactical level set the capacity limitations and network structure for the operational planning level. In the reverse direction, the information on cost and revenue that are generated by the system given the set parameters provides the much needed feedback for decision making at a higher level. Over the years, the sea cargo industry has been conservative in terms of adopting new decision support systems. It has a long tradition of manual planning by experienced planners. Moreover, in general ship scheduling involves a large variety of problems. Hence, mostly tailor made models for specic problems with specialized constraints and objectives are available in the literature. Furthermore, most of the available literature have been developed for industrial and tramp shipping (Christiansen et al. (2004)). Because of the many dierences in modelling and problem structure itself, it is dicult to draw comparisons between the existing literature. We next briey overview a set of representative papers related to container and liner shipping. For a comprehensive review of literature on ship scheduling and cargo routing we recommend Ronen (1983) for the work done before 1983, Ronen (1993) for the decade 1982-1992 and Christiansen et al. (2004) for the last decade. Rana and Vickson (1991) provides a nonlinear integer program to maximize total prot by nding an optimal sequence of ports to visit for each container-ship and an optimal number of cargo units to be transported between each pair of ports by each ship. They allow multiple pick ups and delivery on their ships. However, a special network structure with a restriction on loading and unloading of cargo at the end ports is considered. Furthermore, the model does not consider transshipments by not allowing cargo to be carried on ships that do not visit either the port of origin or the port of destination. They report that their algorithms solve instances with 3 ships and up to 20 ports within an hour.

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

5

Fagerholt (1999) considers the liner shipping problem in a special network where all cargo is transported from a set of production ports to a single depot. The problem is solved by rst generating all feasible single ship routes, and then solving a set partitioning problem. Again the model does not allow for transshipments. Although a weekly frequency constraint is imposed on the operated routes, the feasible routes for the particular problem considered have a maximum route time of one week only. Thus on any of the feasible routes a single ship can maintain weekly frequency. Instances with up to 19 ships on a network with up to 40 ports are reported to be solved within a couple of seconds. Finally, Perakis (2002) provides a review of linear and integer programming models, that only consider the deployment of a eet of liner ships, with dierent ship types, on a set of predetermined routes with targeted service frequencies to minimize operating and lay-up costs. As noted earlier, decisions made at one planning level aect decision making at other planning levels. Given a eet size and mix, the service network laid at the tactical planning level governs which routes can be formed at the operational planning level to route cargo. The cargo picked at the operational planning level and the routes selected determine the cost and revenue that can be generated and thus the protability of the given service network. These two problems are highly inter-dependent and thus it is important that they be studied in an integrated framework. The contribution of this paper is two folds. First, a new mixed integer programming (MIP) model is presented for the integrated ship scheduling and the cargo routing problem for containerized cargo. As shown in Figure 2, we refer to this problem as the simultaneous ship scheduling and the cargo routing problem. Second, since the proposed integer program is too large to be solved economically by general mixed integer programming codes, we develop algorithms to solve it eciently. Our model handles many relevant constraints and emerging trends that appear in practice, but have not been considered previously in the literature. For instance, customers expect carriers to provide them a regular schedule by maintaining at least a weekly frequency on the routes they operate on. To the best of our knowledge, this constraint has not been considered in the literature in its full generality. We successfully impose the weekly frequency constraint at the ports visited by a carrier. As is common in container shipping, we allow multiple pickup and delivery on our ships i.e. we allow containers loaded at one port to have more than one port of destination. Moreover, the eet of a carrier usually consists of various ship types with dierent characteristics that may change over time. We consider a heterogeneous eet with ships of dierent sizes, cost structures and speeds. In the literature, although there are references (see for example Fagerholt (1999)) to models with a heterogeneous eet, most of these models consider ships with identical service speeds. Repositioning of empty containers eciently is a big problem in liner shipping. Our model with some modications has the exibility to incorporate empty container repositioning. Empty container repositioning has been studied by Shen and Khoong (1995) and Cheung and Chen (1998) also, however these papers consider only the movement of empty containers on a given network. We also allow for cargo routes to encompass a combination of cycles rather than a single cycle (with some simplifying assumptions on the cost of transshipment), thus providing carriers with increased routing opportunities. We are not aware of any earlier results on transshipment of containers at an intermediate port from one ship to another. These features allow the use of our model in a wide variety of problem settings. In the most general approach for solving ship scheduling problems to date, Fagerholt (1999) generates a set of feasible schedules by including non-linear and intricate constraints, and then solves a set partitioning problem. Our goal in this paper is to model the simultaneous ship scheduling and cargo routing problem in its generality and solve it for large-scale instances. Hence, rather than being limited to an initial set of routes or exhaustively listing all the routes for ships, we design algorithms that exploit the separability of the problem to iteratively generate good cycles for ships and eciently route the demand. More specically, we utilize the fact that the ship

6

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

scheduling problem can be reduced to a cycle generation problem and the cargo routing problem can be reduced to a multicommodity ow problem. We develop a greedy heuristic, a column generation based algorithm and a two phase Benders decomposition based algorithm and compare the computational eectiveness and eciency of these approaches. Our computational results are encouraging and establish that some of the algorithms developed can be used to solve larger instances, as compared to the literature, in terms of eet size that arise as a result of collaborations and mergers in the sea cargo industry. We report computational results on problem instances with up to 100 ships and 20 ports. The rest of the paper is organized as follows. The next section introduces our notation, mathematical formulation and a note on the complexity of the problem. Three dierent algorithms, a greedy heuristic, a column generation based algorithm and a Benders decomposition based algorithm, are discussed in Section 2. Section 3 provides various algorithmic and implementation details. Computational experiments are presented in Section 4. Conclusions and directions for future work are discussed in the nal section.

1.

Problem Description

We now present a mathematical formulation for the simultaneous ship scheduling and containerized cargo routing problem after introducing our notation and a space-time network. Let P denote the set of ports. We will treat demand as a set of commodities with a positive supply at the origin ports and a positive demand at the destination ports. Each such commodity is characterized by an origin port, o, a destination port, d, the day of the week, i, when the supply is available at port o, the maximum demand (in TEUs) that may arise at port d, D(o,d,i) , and the revenue obtained by satisfying one TEU of the demand, R(o,d,i) . We use the triplet (o, d, i) to identify a particular demand and we let Θ be the set of all such triplets. We call such triplets demand triplets. A carrier typically has several dierent types of ships in his eet. Each ship type usually has dierent capacity and speed and species the characteristics of a group of ships that are considered identical. We denote by A the set of all the ship types and use the index a to represent a particular ship type. We associate the following information with each ship type a ∈ A: T a denotes the capacity a of a ship in TEUs for a ship of type a, for p, q ∈ P , l(p,q) denotes the number of days it takes for a ship of type a to make a sailing from port p to port q and N a denotes the number of ships of type a available in the given eet. Given that the temporal aspects of the problem are important, we formulate the simultaneous ship scheduling and cargo routing problem as a multicommodity ow problem with side constraints on a space-time network. Furthermore, we use days as our time units in the space-time network, since in general the transoceanic routes do not visit more than one port in a given day. Let G = (V, E) be a directed space-time network with vertex set V and edge set E. Each vertex v ∈ V represents a port, port(v), on a day of the week, time(v). That is, for each port p ∈ P we create seven vertices in V . For notational convenience, we associate a subscript with each vertex, i.e. v = v(p,i) where port(v) = p and time(v) = i. We refer to the vertices of G either by v or v(p,i) depending on the ease of exposition. The network G = (V, E) contains three types of edges. The rst is the set of ground edges. For every ship type a ∈ A, we construct ground edges by connecting nodes v(p,i) to v(p,i+1) p ∈ P and 1 ≤ i ≤ 6. We also connect v(p,7) to v(p,1) p ∈ P . For a ship, these edges represent an over-night stay at a port and for cargo they represent an overnight stay at a port either on ground, or on the same or on a dierent ship before continuing further. Next, for every ship type a ∈ A and pair of ports a p, q ∈ P , we construct voyage edges, (v(p,i) , u(q,j) )a for 1 ≤ i, j ≤ 7 such that i j = l(p,q) mod(7). The voyage edges represent the movement of ships and cargo from one port to another at a given speed. Finally, we create a set of ctitious edges, (v(d,j) , u(o,i) ) for all demand triplets (o, d, i) ∈ Θ

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

7

Port C T 6 3 C2 3 6 Port D

Port A Mon Tue Wed Thu Fri Sat Sun 1 1

Port B

C1

Ground Edges

Cycle C2 Cycle C1

T

Figure 3

Transshipment port

Numbers on edges represent the length of the edge

Network with four ports and two cycles

and 1 ≤ j ≤ 7. An edge (v(d,j) , u(o,i) ) only allows the ow of commodity (o, d, i) on it and enables us to view the ow of commodity (o, d, i) in the network as a circulation. Let us denote the set of all a ground edges by Eg , the set of all ground edges for ship type a by Eg , the set of all voyage edges a by Ev , the set of all voyage edges for ship type a by Ev and the set of all ctitious edges by Ef . a a That is, Eg = a∈A Eg , Ev = a∈A Ev and E = Eg ∪ Ev ∪ Ef . We also use the following additional notation: InEdges(v) denotes the set of incoming edges into vertex v and OutEdges(v) denotes the set of outgoing edges from vertex v; for an edge e = (u, v) ∈ E, tail(e) denotes vertex u and head(e) denotes vertex v. Figure 3 represents a space-time network with four ports and two cycles, C1 and C2 . Note that port C acts as a transshipment port to transport cargo from port A to port D. a a The length of voyage edge e = (v, u) ∈ Ev , le , is equal to the number of days it takes for a ship of type a to reach from port(v) to port(u). We also let le = 1 for e ∈ Eg and le = 0 for e ∈ Ef . The capacity of an edge represents the total amount of ow in TEUs that the edge can sustain. Ground edges at a port may have nite or innite capacity depending on whether we wish to impose a limit on the amount of cargo that can be handled/stored at a port. Capacity on a voyage edge depends on the number of ships (and their capacities) that cover the edge. There are various xed and variable costs associated with the simultaneous ship scheduling and cargo routing problem. While some of these costs are incurred by ships, others are incurred by cargo. For the costs related to ports, we let cs,a be the one-time cost incurred by a ship of type v a ∈ A when visiting port(v) and cc be the total cost that a TEU of cargo incurs at port(v) per day. v The port visit costs may be dierent at dierent ports. Similarly, cs,a reects the cost of operating e a a ship of type a on edge e in deep sea if e ∈ Ev and the cost of an overnight stay for a ship of type a a at port(head(e)) if e ∈ Eg . For cargo, cc for e ∈ Ev reects the cost of shipping a TEU of cargo e on edge e and for e ∈ Eg reects the cost of storing or holding a TEU of cargo at port((head(e)). Fictitious edges are assigned zero costs. We make sure that the port visit cost is incurred only once at each port even if a ship makes an over-night stay at the port. To account properly for the port visit cost in the time expanded network, we subtract the port visit cost for ship type a at the port from the ship cost cs,a on e the ground edge e. Thus if a ship makes an overnight stay at a port then though the port visit cost is counted twice via the node costs it is subtracted once via the ground edge cost. Idling of a ship at a port is penalized by imposing the overnight stay cost on the ship. Long stay of cargo

8

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

at a port, which is dierent from its port of destination, is penalized through the holding cost at the port. In this paper, we are using days of the week as the level of time discretization, thus we assume that if ships on two dierent cycles meet at a port on the same day then transshipment can occur in both the directions (i.e. cargo can be transferred from both the ships on each other). By considering ner discretization of time, one can account for smaller time windows on which ships at a port meet for transshipments and to determine if transshipment is possible in only one direction (without incurring the holding cost). Given that in the space-time network the level of discretization is in days, a commodity that becomes available at port o on the ith day of the week is represented as a supply on vertex v(o,i) in the network. We assume that supply appears at vertex o (for destination d) at the same day of week every week. We believe assuming that an average amount of demand arises at a port on a given day is reasonable in our context since we are considering a tactical model. Since the demand from week to week is taken to be the same for a carrier, the service characteristics may also remain the same every week. To this end, we assume that given any cycle, the weekly frequency on the cycle is maintained using ships from the same eet. We characterize a cycle C by the port rotation that it follows, the days of the week it visits each port in its rotation, the type of ship that is used to service C and the number of ships LC it takes to maintain a weekly frequency on C. Due to the indivisibility of ships, LC is integral by denition. A cycle is said to be feasible if it satises pre-specied rules in terms of the number of ships required to maintain a weekly frequency on the cycle and the number of ports visited. We denote the set of all feasible cycles for ship type a by a le e∈C C a . Mathematically, for a cycle C ∈ C a , LC = 7 . Whenever necessary we represent a cycle C by a sequence of vertices, for example a cycle from vertex v1 to vertex vr via v2 , , vr1 is represented as C = v1 v2 vr v1 . Cost of a cycle C ∈ C a is denoted by CostC and is calculated as CostC = cs,a + cs,a . v e

v∈C e∈C

1.1. Mathematical Model We now present a mixed integer programming formulation for the simultaneous ship scheduling and cargo routing problem. Our formulation has two sets of variables. First, for every feasible cycle C we dene a binary variable xC . xC = 1 if a weekly frequency is maintained on cycle C and is 0 otherwise. The xC variables are taken to be binary rather than integer as the possibility of departing two ships of same type from a port following the same port calls on the same days of the week is highly unlikely. Next, we dene non-negative continuous variables representing the ow on edges. For each edge (o,d,i) e ∈ Eg ∪ Ev and each triplet (o, d, i) ∈ Θ we dene fe to denote the ow of commodity represented by (o, d, i) on edge e. For a ctitious edge e = (v(d,j) , u(o,i) ) ∈ Ef , a single ow variable, (o,d,i) fe , for commodity (o, d, i), is dened since the ow of other commodities on this edge is not allowed. Note that, we let the ow variables to be continuous since adjusting for picking a fractional container does not inuence the solution quality very much for the purposes of our tactical model. Before presenting the model we summarize the following additional assumptions that we make. A1-A3 are for the clarity of exposition and in no way restrict the usability of our model, however assumption A4 is more signicant. (A1) Capacity on ground edges is assumed to be innite i.e. we do not put any restriction on the amount of cargo that can be handled/stored at a port. (A2) We assume that all costs on cargo can be modelled via edge costs i.e. we set cc = 0 v ∈ V . (A3) v We assume that all cargo is available in identical 1 TEU containers. Thus, D(o,d,i) represents the number of containers of a commodity required at port d that become available at port o on day i of the week. (A4) Finally, we do not consider the costs involved with transferring cargo from one ship to another. As discussed before, cargo incurs holding costs whenever it stays at a port

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

9

overnight. To account for transshipment costs correctly we need to distinguish between the capacity provided by dierent cycles on the same edge of the network. If the edges are duplicated for all the feasible cycles it will increase the size of the graph tremendously. Thus, it is hard to account correctly for transshipment costs if the network is not known (i.e. the cycles to be operated have not been selected). Since our aim is to consider the network design and cargo routing problems simultaneously and generate feasible cycles as a sub-problem, we ignore the transshipment costs for now. In Section 4.4 we present a computational study to discuss the eects of transshipment costs on cargo routing decisions once a set of cycles, to be operated by the given eet, has been selected. The simultaneous ship scheduling and cargo routing problem can be formulated as the following mixed integer program:

7

(SSSCR) : max

(o,d,i)∈Θ j=1

R(o,d,i) f(v(d,j) ,v(o,i) )

(o,d,i)∈Θ e∈E

(o,d,i)

(o,d,i) cc fe e a∈A C∈C a

CostC xC

(1)

such that

(o,d,i) fe e∈InEdges(v) (o,d,i) fe (o,d,i)∈Θ e∈OutEdges(v) (o,d,i) fe = 0 v ∈ V, (o, d, i) ∈ Θ

(2) (3) (4) (5) (6) (7)

T a xC ≤ 0 e ∈ Ev

a∈A {C∈C a :e∈C} 7 (o,d,i) f(v(d,j) ,v(o,i) ) j=1

≤ D(o,d,i) (o, d, i) ∈ Θ

LC xC ≤ N a a ∈ A

C∈C a

xC (o,d,i) fe

∈ {0, 1} C ∈ C a , a ∈ A ≥ 0 e ∈ E, (o, d, i) ∈ Θ.

We now explain the above formulation. The objective function (1) maximizes the net prot by subtracting the sum of operating costs from the revenue generated. The rst term in the objective function denotes the total revenue generated by transporting cargo between various origin and destination pairs. The second term captures the cost incurred by cargo during its routing from the origin port to the destination port. The third term denotes the total cost of operating ships on the selected cycles. Constraint (2) is a ow balance constraint at every vertex of the space-time network. It ensures that the total ow into vertex v, of each commodity (o, d, i) ∈ Θ, is equal to the total ow out of it for the same commodity. Constraints (3) and (4) are capacity constraints on the edges. Constraint (3) requires that the total ow on a voyage edge must be less than the sum of the capacities of ships servicing that edge. Constraint (4) models that the total ow of a given commodity from an origin port to a destination port must be less than the demand at the destination port. Note that we do not have a capacity constraint on ground edges because of assumption A1. Constraint (5) requires that for each eet type, we do not use more ships than we have available. Note that if cycle C ∈ C a is selected, i.e. xC = 1, then it will utilize LC ships of type a to maintain a weekly frequency. (o,d,i) Finally, (6) denotes xC as binary variables and (7) denotes fe as non-negative continuous ow variables. 1.2. Hardness of the Problem The decision version of the simultaneous ship scheduling and cargo routing problem is in NP, that is given a set of cycles to be operated and a ow of cargo on the edges it can be determined

10

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

in polynomial time whether the total revenue generated is greater than a given constant K. We show the NP completeness of the problem by reducing a well known NP-complete problem, 0-1 Knapsack, into a simultaneous ship scheduling and cargo routing problem. The decision version of the 0-1 Knapsack problem is dened as the following: Given set N = {1, 2, n}, integers K, ci and wi for every i ∈ N is there a subset S of N such that wi ≤ W

i∈S

and

i∈S

ci ≥ K?

Theorem 1. The decision version of the simultaneous ship scheduling and cargo routing problem is NP-complete. Proof: Suppose there are W identical ships with capacity T TEUs each. Construct a sea cargo network as follows. For each i ∈ {1, 2 n} construct two ports, a demand port(di ) with demand ci TEUs and an origin port (oi ). Let a ship in the eet take wi weeks to make a sailing from port 2 oi to port di . Assume symmetric distances between ports and that the distances between oi and dj , 1 ≤ i = j ≤ n is large. Thus wi ships are needed to maintain weekly frequencies on cycles Ci = oi di oi for 1 ≤ i ≤ n and all other cycles are infeasible. Let T = maxi∈N ci and let revenue generated by satisfying unit demand between any o d pair be 1. Assume there are no operating costs involved. Observe that : All feasible cycles are disjoint. A cycle Ci needs wi ships to maintain weekly frequency and can generate ci units of revenue. If a set S N of cycles is chosen to be serviced then wi ≤ W and a total of ci units of

i∈S i∈S

revenue is generated. It follows easily now that a set of chosen cycles, S, will give a revenue of K units or more if and only if the 0-1 Knapsack problem has a feasible solution. Thus the 0-1 Knapsack can be solved by solving a SSSCR problem.

2.

Solution Methodology

The linear program given by (1)-(7) contains a large number of variables even for moderate size problems. The large size of the model is a direct result of the exponential number of possible feasible cycles. Furthermore, each demand triplet adds a set of ow variables to the MIP model. An interesting observation however is that if we determine the set of cycles to be operated for each eet type, i.e. given non-negative values xC satisfying eet availability constraints (5), model (1)-(7) reduces to the following multicommodity ow problem where each demand triplet is considered as a dierent commodity.

7

(M CF ) : max

(o,d,i)∈Θ j=1

R(o,d,i) f(v(d,j) ,v(o,i) )

(o,d,i)∈Θ e∈E

(o,d,i)

(o,d,i) cc fe e

(8)

such that

(o,d,i) fe e∈InEdges(v) (o,d,i) fe (o,d,i)∈Θ a∈A {C∈C a :e∈C} 7 e∈OutEdges(v) (o,d,i) fe = 0 v ∈ V, (o, d, i) ∈ Θ

(9) (10) (11) (12)

T a xC ≤ 0 e ∈ Ev f(v(d,j) ,v(o,i) ) ≤ D(o,d,i) (o, d, i) ∈ Θ

j=1 (o,d,i) fe ≥ 0 e ∈ E, (o, d, i) ∈ Θ. (o,d,i)

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

11

Benders Decomposition

Initialize: S = {o-d-o cycles} Set LB =0, UB = ∞ Solve the relaxed Benders master problem. Update UB

Greedy Heuristic

Initialize: Capacitye = 0, S = All ships used/ demand met?

For each ship type a

Column Generation

Initialize: S = {o-d-o cycles} Solve the column generation master problem

For each ship type a

Yes Stop

No

Construct auxiliary network Ga Find negative cost cycles in Ga negative cost cycle? Yes No

Construct auxiliary network Ga Find negative cost cycles in Ga No

Solve the Benders sub-problem. Update LB

negative cost cycle? Yes Add a subset of negative cost cycles Solve the integer program

UB – LB < No

ε?

Yes

Pick the most negative cycle, C S=S U {C}. Assign ships to cycles Update capacity on the edges, Solve the cargo routing problem

Add the optimality cuts Solve the integer program

Figure 4

Outline of the three algorithms considered.

Note that (8)-(12) is a linear program with no integrality constraints as it only involves the (o,d,i) (o,d,i) (o,d,i) ow variables fe . Let π = {πv : πv unrestricted, v ∈ V, (o, d, i) ∈ Θ} , λ = {λe : λe ≥ (o,d,i) (o,d,i) 0 e ∈ Ev } and ω = {ω :ω ≥ 0 (o, d, i) ∈ Θ} be the set of dual variables associated with constraints (9), (10) and (11) respectively. Next, we present three heuristic algorithms that exploit the above observation to solve the SSSCR problem. First, we provide a simple greedy heuristic that selects good cycles one by one and then assigns cargo to routes. Then we present a column generation based algorithm that generates a pool of good cycles and then selects the best cycles among these while also routing cargo in the network. Finally we present the details of a more involved Benders decomposition based algorithm. Figure 4 presents an outline of the three algorithms. 2.1. Greedy Algorithm Let S represent the set of cycles that are in operation i.e. ships have been assigned to maintain weekly frequencies on cycles in set S. The desirability or the value of cycle C depends on the revenue generated by routing ow on ships employed in C, the number of ships required to maintain weekly frequency on C and the various costs involved in operating the cycle C. The marginal value of cycle C also depends on the cycles already present in set S. Thus, a greedy selection of cycles must take into account the set of existing operational cycles and demand triplets (o, d, i) ∈ Θ. Let Aa , a ∈ A, represent the number of ships of type a that are currently available. The greedy algorithm starts with an empty set of selected cycles. To nd protable cycles an auxiliary network Ga = (V a , E a ) is created utilizing dual information from the solution of the M CF problem to a a assign edge costs. Ga is constructed for each ship type a such that V a = V and E a = Ev ∪ Eg . Each a s,a a edge e ∈ E is assigned a cost ce = ce + λe and each vertex v ∈ V is assigned a cost cv = cs,a . v For every ship type, the algorithm then nds a minimum cost cycle in the auxiliary network by using a procedure F indCycle(Ga ). Details of this procedure will be provided in Section 3. Finally, if feasible the cycle with minimum cost is selected and a suitable number of ships, to maintain weekly frequency, is assigned to it. The process is repeated while there are ships to be assigned. 2.2. Column Generation based Algorithm Though the greedy algorithm is simple and provides a feasible solution quickly it is not very eective. It works with a very small set of feasible cycles and once a feasible cycle is generated it is picked in the nal solution without any further considerations. Next we propose a column generation based algorithm that iteratively generates a good pool of protable cycles for solving the linear programming (LP) relaxation of (1)-(7).

12

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

Column generation is an eective way of solving linear programs with a large number of columns (see Bertsimas and Tsitsiklis (1997) for an introduction). Rather than enumerating all the columns explicitly, it begins by solving a restricted problem (called the master problem) with a select set of columns. A subproblem is solved to generate “attractive” columns and they are subsequently added to the master problem. The process is repeated until no further protable columns can be generated. The column generation technique has been successfully used to solve many large scale optimization problems, please see (Barnhart et al. (1994)) for an example in solving airline crew assignment problems. To solve the LP relaxation of SSSCR, the master problem in the column generation is initialized by restricting the set of cycle selection variables, to one simple cycle for every demand triplet. At every step of the column generation process, the master problem is solved to nd the best value for all the decision variables. The pricing subproblem for the column generation is equivalent to identifying negative cost cycles in an auxiliary network, for every ship type. The auxiliary network, a a Ga = (V a , E a ) is constructed for each ship type a such that V a = V and E a = Ev ∪ Eg . Dual variable values from the master problem are used to assign costs to the edges and the vertices e of the auxiliary network. Each edge e ∈ E a is assigned a cost ce = cs,a + T a λe + l7 σ a and each e a s,a a vertex v ∈ V is assigned a cost cv = cv so that negative cost cycles in G correspond to columns with positive reduced costs in the master problem. Note that since SSSCR is a maximization problem, protable columns are the ones with positive reduced cost. Procedure F indCycle(Ga ) (described in Section 3) is used to identify negative cost cycles in the auxiliary network and corresponding columns are added to the master problem. The process is continued until no new cycles can be found. Finally, integrality constraints are imposed on the cycle selection variables and a branch-and-bound framework is used to obtain an integer solution for the SSSCR problem. No new columns are generated during the branch-and-bound phase. Dierent branching rules, with dierent advantages, can be devised to obtain the integer solution. For example branching on the largest feasible cycle forces many other binary variables also to satisfy the integrality constraints. However, we use the variable that aects the solution quality the most as the variable to branch on, giving preference to the up (xC = 1) branch, because this strategy performed the best in our computational experiments. 2.3. Benders Decomposition Based Algorithm As the number of ports, ships and demand triplets increase, solving model (1)-(7) by column generation becomes increasingly dicult. The number of constraints as well as the number of variables increase with the increase in the number of ports, ships and demand triplets, in the column generation master problem. We next decompose the LP relaxation of the model (1)-(7) using Benders decomposition to obtain a pair of problems that utilize the separability of SSSCR. The decomposition results in a master problem, where the number of variables increases as the number of cycles increase, and a subproblem, where the number of constraints increases as the number of demand triplets increase. Thus the eect of the increase in problem size is divided between a master problem and a subproblem. Further, this decomposition is used to eectively solve the LP relaxation and the solution is embedded in a branch-and-bound approach to obtain an integer solution. Benders decomposition (Benders (1962)) is a popular technique to solve mixed integer linear programming problems with linking constraints. This approach is useful when master problem has all the integer variables and it is dicult to treat them in sub-problems. The solution process iterates between an integer master problem, which passes on the value of integer variables to subproblem(s), and subproblems generate cuts (feasibility and optimality) which are passed back to the master problem. Though this approach has proved to be suitable for many problems it has the drawback that an integer master problem has to be solved at each iteration. McDaniel and

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

13

Devine (1977) proposed a modication to this approach in which the solution of a sequence of integer programs is replaced by the solution of a sequence of linear programs and a few integer programs. The basic techniques of McDaniel and Devine (1977) and its modications have been used successfully to solve many hard problems. Florian et al. (1976) used it for solving an engine scheduling problem and Wiel and Sahinidis (1996) used it for solving a time-dependent travelling salesman problem. More recently, these techniques have been used successfully to solve locomotive car assignment (Cordeau et al. (2000), Cordeau et al. (2001a)) and aircraft routing and crew scheduling (Cordeau et al. (2001b)) problems. For these problems enormous time reductions and signicant improvements in solution quality were achieved by rst relaxing the integrality constraints in the master problem. After the relaxation is solved, to acceptable time or optimality criteria, the integrality constraints are introduced back in the master problem. We now present the use of Benders decomposition method to solve the SSSCR problem. 2.3.1. Benders reformulation As noted earlier for given non-negative values xC satisfying eet constraints (5), the LP relaxation of model (1)-(7) reduces to the M CF . Since M CF is a multicommodity ow problem with no integrality constraints, the optimal value of M CF problem is equal to the optimal value of its dual. The dual problem (DP ) of the M CF problem can be written as (DP ) : min

e∈Ev a∈A {C∈C a :e∈C}

T a xC λe +

(o,d,i)∈Θ

D(o,d,i) ω (o,d,i)

(13)

such that πhead(e) πtail(e) + λe (o,d,i) (o,d,i) πhead(e) πtail(e) + ω (o,d,i) (o,d,i) πv λe ω (o,d,i)

(o,d,i) (o,d,i)

≥ cc e ∈ E Ef , (o, d, i) ∈ Θ e ≥ R(o,d,i) cc e ∈ Ef , (o, d, i) ∈ Θ e unrestricted, v ∈ V, (o, d, i) ∈ Θ ≥ 0 e ∈ Ev ≥ 0 (o, d, i) ∈ Θ.

(14) (15) (16) (17) (18)

Let D be the feasible region of the dual problem and PD and QD be the set of extreme points and extreme rays of D, respectively. Note that D does not depend on xC . Also, since R(o,d,i) ≥ (o,d,i) 0 (o, d, i) ∈ Θ and cc = 0 e ∈ Ef , a feasible solution for the dual subproblem is πv =0 v∈ e (o,d,i) (o,d,i) V, (o, d, i) ∈ Θ, λe = 0 e ∈ Ev and ω =R (o, d, i) ∈ Θ, and thus D = . Now, by strong duality, either the M CF problem is infeasible or it is feasible and bounded. Clearly the null vector 0 is a feasible solution for M CF . This means that the primal-dual pair of M CF and DP is feasible and bounded. Thus the optimal value of M CF and DP can be characterized in terms of only the extreme points of DP , i.e. the set PD , and can be written as: D(o,d,i) ω (o,d,i) . min { T a xC }λe +

(π,λ,ω)∈PD e∈Ev a∈A {C∈C a :e∈C} (o,d,i)∈Θ

Introducing an additional free variable z, model (1)-(7) can be reformulated as the following Benders master problem (BMP). This problem has integer variables xC and one free continuous variable z. (BM P ) : max z such that z≤

e∈Ev

(19)

{

a∈A {C∈C a :e∈C}

T a xC }λe +

(o,d,i)∈Θ

D(o,d,i) ω (o,d,i)

a∈A C∈C a

CostC xC (λ, ω) ∈ PD (20) LC xC ≤ N a a ∈ A (21)

C∈C a

xC ∈ {0, 1} (22) z f ree. (23)

14

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

Note that we do not have any feasibility constraints in the Benders master problem because (DP) is bounded. The optimality constraints (20) ensure that z is restricted to be smaller than or equal to the value of the right hand side of constraint (20) at various extreme points of DP . In general, the above model contains many more constraints than the LP relaxation of model (1)-(7) but most of them are inactive at optimality. Thus a natural approach to solve (19)-(23) is by dropping constraints (20) and generating them as needed. We now present the basic Benders algorithm to solve the linear relaxation of SSSCR problem to optimality. Later, integrality constraints are introduced to solve the original SSSCR problem. We denote the linear relaxation of BM P as LP BM P and the relaxation of LP BM P obtained by dropping constraints (20) as the RLP BM P . 2.3.2. Overview of the algorithm The basic Benders decomposition based algorithm for solving the LP relaxation of SSSCR iteratively selects good cycles, by solving the RLP BM P , for the ship scheduling problem and then eciently solves the cargo routing problem, by solving the M CF problem. The M CF problem utilizes the RLP BM P solution to assign capacity to voyage edges before solving the ow problem. In return, at each iteration, the dual solution of the M CF problem provides an optimality cut to the RLP BM P . t Let t be the iteration number and PD be the restricted set of extreme points of D available at t iteration t, i.e. the RLP BM P at iteration t is obtained from LP BM P by replacing PD by PD in t (20). Note that the solution of the RLP BM P at each iteration t, denoted by z , provides an upper bound for the original LP BM P (since the RLP BM P has fewer constraints than the LP BM P ). Algorithm 1 The basic Benders decomposition based algorithm Procedure Basic Benders() t Set t = 1, PD = , lower bound = 0, upper bound = ∞. while (upper bound > lower bound + ) do STEP 1. SOLV E the RLP BM P to obtain solution z t and {xC }t . Set upper bound = z t . STEP 2. Solve the M CF problem taking {xC }t as input to obtain v({xC }t ) and optimal dual solution (π, λ, ω). Set lower bound = max{lower bound, v({xC }t ) CostC xC }.

a∈A C∈C a

Set

t+1 PD

=

t {PD

∩ {(x, z) : z ≤

e∈Ev a∈A {C∈C a :e∈C}

{

T a xC }λe +

(o,d,i)∈Θ

D(o,d,i) ω (o,d,i)

t = t + 1. end while The original BM P (or SSSCR) problem with integrality constraints is solved heuristically in two phases. In Phase I, all integrality constraints are relaxed and the LP BM P is solved to optimality by using basic Benders decomposition algorithm (Algorithm 1). Since the set of feasible cycles can be exponential, the RLP BM P , in this phase, is solved in a column generation setting. For phase I, SOLV E in Algorithm 1 refers to this column generation and its details will be provided next. Retaining all optimality cuts and cycles generated in the rst phase, Phase II puts the integrality constraints back on the master problem. Algorithm 1 is started once more, however in this phase the RLP BM P in Step 1 is replaced with the mixed integer program BM P , together with the cuts and cycles generated in the rst phase. Since the DP polytope is not aected by the integrality constraints, all optimality cuts generated in Phase I can be used to generate corresponding cuts for the mixed integer program in Phase II. Additional optimality cuts are generated at each iteration. Note however that in phase II Algorithm 1 in Step 1 solves an integer problem at every iteration.

a∈A C∈C a

CostC xC }}.

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

15

Thus in Phase II no new cycles are generated and SOLV E simply refers to a branch-and-bound solution of the relaxed BM P . This two phase approach for solving integer programs using Benders decomposition was originally proposed by McDaniel and Devine (1977) and the intuition behind it is the hope that many of the necessary constraints for the master problem may be generated by solving a linear program in place of the more computationally expensive integer program. The branch-and-bound tree in Phase II is searched by a depth rst search, giving preference to the up (xC = 1) branch. As in Section 2.2, the variable that aects the solution quality the most is chosen as the branching variable. Note that solving the mixed integer program in BM P is a computationally expensive step. Since any feasible integer solution can be used to generate an optimality cut, the mixed integer program BM P does not need to be solved to optimality at every iteration. However, if the BM P is solved heuristically the upper bound it provides during the Benders iterations could be much smaller than the true upper bound which might lead to a premature termination of the algorithm. In the worst case, the upper bound could become smaller than the lower bound. To avoid such a premature termination of the algorithm, the branchand-bound search is terminated only when the solution quality obtained reaches an acceptable optimality gap (the gap between the best integer objective and the objective of the best node remaining). Searching the branch-and-bound tree for a solution with small optimality gap is likely to take large computation time but it is also likely to provide better solution quality by providing better bounds for the Benders iterations. Thus, a suitable optimality gap must be chosen to avoid the premature termination of the algorithm and to keep it computationally ecient. 2.3.3. Column generation for solving the RLPBMP The master problem in the Benders decomposition (the RLP BM P in Algorithm 1) is solved in a column generation setting. The pricing subproblem in the column generation reduces to identifying negative cost cycles in an auxiliary network, Ga = (V a , E a ), for every ship type a. As before, Ga is constructed such that V a = V and a a E a = Ev ∪ Eg . We next present how we compute the costs on the vertices and the edges of network a G . Let Π(λ,ω) and σ a denote the dual variables corresponding to constraint (20) and (21), respectively. The reduced cost cC of a cycle C ∈ C a can now be written as: cC = 0

(λ,ω)

CostC

{e:e∈C∩Ev }

T a λe Π(λ,ω) + LC σ a .

(24)

Note that in (24) the second summation is only over the voyage edges of cycle C. Since the ground edges have innite capacity, at optimality, by complementary slackness conditions λe = 0 e ∈ Eg . Thus, ground edges can also be included in the summation in (24). From LP theory, we know that if the reduced cost cC ≤ 0 for each cycle C ∈ C a and every eet type a ∈ A then we have the optimal solution to our problem. That is the column generation iterates as long as there exists a cycle C ∈ C a for some a ∈ A such that cs,a + v

(λ,ω) v∈C e∈C

cs,a e

v∈C

(λ,ω)

Π(λ,ω) cs,a v

T a λe Π(λ,ω) + e∈C

e∈C

e∈C

(λ,ω)

Π(λ,ω) λe T a

a le σa < 0 7

+

e∈C

(λ,ω)

Π(λ,ω) cs,a + e

e∈C

a le σ a < 0. 7

(25)

16

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

For the network Ga , we assign cost cv =

(λ,ω)

Π(λ,ω) cs,a to every v ∈ V a and cost ce = v

le a σ 7

Π(λ,ω) λe T a +

(λ,ω) (λ,ω)

Π(λ,ω) cs,a to every edge e ∈ E a . Let, CostC represents the cost of e

e∈C

a le 7

cycle C with the above cost structure. Let CostC be the cost when we replace the CostC by

e∈C

a le 7

term in

. Note that, since x ≥ x, if the optimal value of the pricing subproblem a ∈ A

is greater than zero then there are no more protable cycles because CostC ≥ 0 CostC ≥ 0. If however, the optimal value of the pricing subproblem for some a ∈ A is less than zero than we need to check if CostC < 0. If it is, then we have found a protable cycle, otherwise either there are no more protable cycles to be added or protable cycles have very low negative cost (> 1) and are therefore ignored. We use Procedure F indCycle(Ga ) (as will be described in Section 3) to identify negative cost cycles in Ga .

3.

Algorithmic Issues

In this section we discuss several algorithmic ideas we utilize to make our algorithms more eective, ecient, and stable. 3.1. Solving the Pricing Subproblem The pricing subproblems for both the column generation and Benders decomposition based algorithms reduce to nding protable cycles in the auxiliary network Ga . Similarly, the Greedy algorithm needs to nd protable cycles in the auxiliary network. It is tempting to solve directly a minimum cost circulation problem in the network Ga , to identify negative cost cycles. However, the cycles obtained by decomposing the solution of the circulation problem into simple cycles are not guaranteed to be practical. For example, our initial computational experiments with the circulation problem suggest that most of the cycles thus generated are too long and require a large number of ships to maintain weekly frequency. Hence, we rst discuss rules based on the real world practice of liner shipping companies for dening feasible cycles. Next, a recursive algorithm, F indCycle(G), is presented to eciently nd negative cost cycles, satisfying pre-dened feasibility conditions, in a given network G. 3.1.1. Dening feasible cycles To solve the pricing subproblem to optimality one must consider all sequences of ports as candidates for possible protable cycles. However, searching for negative cost cycles in such an unconstrained manner not only makes our algorithms inecient by generating cycles that create undesirable eects such as large integrality gaps but also it generates cycles that would never be operated in practice. Hence we impose a set of constraints that a cycle must satisfy to qualify as a feasible cycle. Global carriers operate in dierent regions, for example OOCL operates mainly in North America, Europe and Asia, and cater to the demand of various markets, such as trans-Atlantic, trans-Pacic, intra-Asia, and Asia-Europe trade routes. Figure 5 represents an Asia-Europe cycle for OOCL. For a carrier it is important to tap the benets of both inter-region and intra-region markets. Whereas, some of the inter-region markets, for example the trans-Pacic, are the most protable ones, some of the intra-region markets, for example the intra-Asia market, form the backbone of international shipping. We considered the published cycles by OOCL (2005) and APL (2005) in trans-Pacic and intraAsia trade routes to come up with the following guidelines for dening the set of feasible cycles distributed in two regions, ri and rj .

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

17

Figure 5

An Asia-Europe cycle for OOCL. Source: OOCL

1. The number of ports visited by a cycle must not be too high. Most of the current trans-Pacic cycles visit up to 10-15 ports and intra-Asia cycles visit up to 7-10 ports. Let R(ri ,rj ) denote the maximum number of ports that a cycle visiting region ri and rj is allowed to visit. 2. The length (in weeks) of a cycle must be bounded by a suitable number, i.e. the number of ships that can be committed to a particular cycle are limited. Most of the trans-Pacic cycles are up to 15 weeks long and most of the intra-Asia cycles are up to 6 weeks long. Let L(ri ,rj ) be the maximum allowed length in weeks for a cycle visiting region ri and rj . 3. Cycles that operate in multiple regions must enter and leave a region only once, i.e. no interregion loops are allowed. However, 1-2 intra-region loops are allowed. 4. Each cycle must directly (without using capacity on other cycles) serve the origin and destination ports of at least one demand triplet. It is highly unlikely for a carrier to introduce a cycle that does not satisfy any demand directly. 3.1.2. Finding negative cost feasible cycles Incorporating any of the rules that guide the feasibility of a cycle into the circulation problem yields a NP hard problem. (This is easily seen from the fact that shortest weight-constrained path problem is NP complete (Garey and Johnson (1979)).) Furthermore, an exhaustive enumeration of cycles following the above rules still yields a large number of cycles. For ports distributed in two regions, up to 10,000 cycles for a 10 port, 30 demand triplets problem, over a million cycles for a 15 port, 50 demand triplets problem and more than 10 million cycles for a 20 port, 80 demand triplets problem exist. We now describe an iterative search algorithm for constrained negative cycle detection which yields good computational results. In essence, the algorithm utilizes Lemma (1) due to Lin and Kernighan (1973) to prune the search tree by ignoring paths with non-negative costs. This pruning helps the algorithm to maintain time- and space-eciency. Ahuja et al. (2003) have used lemma (1) to develop a similar algorithm for detecting subset disjoint negative cycles. Lemma 1. For a negative cost (directed) cycle C = v1 v2 .... vr v1 there exists a node vh in C such that each partial (directed) path vh vh+1 , vh vh+1 vh+2 , vh vh+1 vh+2 ... (where indices are modulo r) is a negative cost (directed) path. We now present a cycle generation algorithm for ports distributed in two regions: r1 and r2 . Note that these ideas can easily be carried over to ports distributed in more than two regions. Before presenting the algorithm we dene some notation. With each directed path p, we associate the following information: head(p) and tail(p) denote the last node and rst node on p. Cost(p) denotes the cost of path p. N Rr1 (p) and N Rr2 (p) denote the number of ports from region r1 and r2 , ER(p) denotes the number of inter-region edges and nally l(p) denotes the length of path p. Note that each edge in the network is either between two nodes of the same region (intra-region edge) or between two nodes of dierent regions (inter-region edge) and that the set {N Rr1 (p), N Rr2 (p), ER(p)} completely describes the region(s) visited by a path p. For a path p we denote the set {head(p), tail(p), ER(p)} as DSet(p). We say that a path p dominates another path q if DSet(p) = DSet(q) and Cost(p) < Cost(q).

18

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

Note that a cycle can be obtained by connecting the endpoints of a path. Lemma (1) suggests that to nd negative cost cycles it is enough to consider paths with negative cost. Further, the above denition of dominance suggests that among the paths with the same DSet() only the path with the least cost needs to be explored further. A path p is said to be feasible if it has negative cost and if it can be extended to form a feasible cycle. Let Pk denote the set of all non-dominated, feasible paths with k nodes. For each ship type a, Algorithm (2) detects negative cost cycles in the auxiliary network Ga , described earlier with various cost structures. It works inductively by constructing set Pk+1 from the set Pk . For each path p ∈ Pk it examines if the path can be extended by adding a single edge to form path p , that is if path p is feasible. Procedure if f easible path(p) checks for the feasibility of path p depending on the region(s) visited by p, by ensuring that the guidelines set in Section 3.1.1 are met, and accounts for the fact that for a ship type a no cycle can be longer than N a , number of available ships for ship type a, weeks. The path is then checked for dominance in Pk+1 , using procedure if dominated(p , Pk+1 ) and non-dominated paths are added to Pk+1 . For a cycle C, procedure if f easible cycle(C) checks if the cycle C is feasible. For a path p all information can be maintained in O(1) time. For example, to maintain ER(p), we assign a value 0 to all intra-region edges and value 1 to inter-region edges. Thus whenever an edge is appended to a path p ∈ Pk to obtain path p ∈ Pk+1 , ER(p ) can be obtained by adding the value of the appended edge to ER(p). Since we maintain all information regarding the region(s) visited by a path, feasibility check for a path and a cycle can be done in constant time. To check the dominance of a path p ∈ Pk , we rst need to check if there exists a path q ∈ Pk such that DSet(p) = DSet(q). This is a computationally expensive step. We use standard hashing techniques to eciently detect paths with the same DSet. Once such a path is found, dominance can be checked in O(1) time. Note that at any given time, set Pk will contain only one path with a particular DSet, i.e. the non-dominated path. Rather than storing only the most negative cycle C Algorithm (2) can easily be modied to maintain a pre-dened number of best cycles. 3.2. Choosing an Initial Set of Cuts Even though the Benders decomposition based Algorithm (1) may be initialized with an empty set of extreme points, the choice of an initial set may aect its convergence. In our experiments, the addition of several cuts helped us improve the performance of Algorithm (1). (o,d,i) Note that, πv = 0 v ∈ V, (o, d, i) ∈ Θ, λe = 0 e ∈ E and ω (o,d,i) = R(o,d,i) (o, d, i) ∈ Θ is a feasible but not necessarily an extreme point solution of the DP polytope. It can thus be used to obtain the valid cut z≤

(o,d,i)

R(o,d,i) D(o,d,i)

a∈A C∈C a

CostC xC .

(26)

The above cut is equivalent to adding the constraint that the value of the optimal solution must be less than or equal to the revenue that can be generated by satisfying all the available demand minus the cost of operating the picked cycles. Similarly, λe = max R(o,d,i) e ∈ E and ω(o,d,i) = 0(o, d, i) ∈ Θ is a feasible solution for the

(o,d,i)∈Θ

DP polytope and provides the valid cut z ≤ max R(o,d,i)

(o,d,i)∈Θ e∈Ev a∈A C∈C a :e∈C

T a xC

a∈A C∈C a

CostC xC .

(27)

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

19

Algorithm 2 An iterative constrained negative cycle detection algorithm Procedure FindCycles(Ga ) for all e ∈ E a do p = {e} if if f easible path(p) then P1 = P1 ∪ {p} end for k = 1, C = , CostC = 0 while k < R do while Pk = do Remove a path p from Pk Connect the ends of path p to form cycle C. if if f easible cycle(C) and CostC < CostC then C = C for all {(head(p), j) ∈ OutEdges(head(p))} do p = p ∪ {(head(p), j)} if {if f easible path(p )} then Pk+1 = Pk+1 ∪ {p } if if dominated(p , Pk+1 ) then Remove the dominated path end if end for end while k+1 end while

3.3. Making Column Generation Eective While performing column generation, both in the pure column generation based algorithm for SSSCR and for solving the RLP BM P in Benders decomposition based algorithm, we identify and add more than one protable column per iteration. During the iterative cycle generation instead of maintaining just the most negative cycle we maintain a set of 5 10 most protable cycles at almost no extra cost. This helps to signicantly reduce the numbers of iterations during column generation without substantially increasing the time taken per iteration. During a typical column generation, the problem keeps growing as the column generation process keeps adding columns to the master problem. To keep the list of columns manageable, we frequently delete nonbasic columns with high negative reduced cost from the master problem. This reduces the time per iteration signicantly, though it increases the number of iterations slightly in many cases. As another speed up for the column generation process, if no new cycle is detected for a ship type in an iteration then cycle generation for that ship type is suspended for 2-5 iterations.

4.

Computational Experiments

In this section, we present the results of our computational study after describing the schema employed for generating test cases. We rst establish the dominance of the Benders decomposition based algorithm over the greedy heuristic and the column generation based algorithm. Next, we present a deeper analysis of the Benders decomposition based algorithm. Finally, we discuss some of the interesting characteristics of the solutions obtained by our algorithm and show that it supports the recent trends observed in the sea-cargo industry. All of our algorithms were implemented in C++ in an Unix environment and we made extensive use of the callable libraries in CPLEX 9.0. All computational experiments were performed on a Sun280R workstation with UltraSparc-III processor. All times are reported in minutes.

20

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

4.1. Data Generation We performed our computational experiments on networks with ports distributed in two regions. Each generated port is randomly assigned to one of the two regions, with equal probability, and the sailing distance between ports are chosen to represent the sailing distance between ports distributed in the Asia and the North-America regions. Typically, as observed from OOCL (2005) and APL (2005) service networks, intra-region sailing times for ports in Asia and North-America are 2-30 days whereas the inter-region sailing times are 14-42 days. Origin-destination pairs are chosen randomly from the pairs of ports. Day of the week on which supply arises at the origin port is assumed to be the same every week and is chosen uniformly at random from the seven days of a week. The demand sizes are randomly generated from the interval 0.1 to 1.0 times the capacity of the largest ship available. Similar proportions are used in Fagerholt (1999) and it is suggested that this represents the demand sizes observed by a liner shipping company. Revenue generated by satisfying demand for a given demand triplet (o, d, i) is chosen to be in direct proportion to the distance between port o and port d, i.e. more revenue is generated by satisfying a demand at a port in North-America from a port in Asia as compared to satisfying a demand between two ports in North-America. The proportionality constant is chosen randomly from [100, 200]. Since the eet of a carrier usually consists of ships of dierent types we considered three dierent ship types in our eet. The three ship types have capacity 2000 TEU, 4000 TEU and 8000 TEU. Bendall and Stent (1999) and Imai et al. (2006) suggest that ships with 2000 TEU and 4000 TEU capacity are currently in use. According to OOCL (2005), OOCL has ships of dierent types with capacity varying from 2,500TEU to 8,063TEU. A recent increase in literature regarding the viability of larger ships, Imai et al. (2006), points towards the increasing use of big ships and Bendall and Stent (1999) suggests that ships of up to 8000+ TEUs are in design. There are various xed and variable costs involved in shipping a cargo. As in Christiansen and Nygreen (1998) we do not consider the daily running costs including cost of capital, personnel, insurance etc. since they are xed during the planning period. However, we consider various operational costs that eect a carrier’s decision regarding which ports to visit and which cycles to operate on. For every ship type, a ∈ A, and for all the ports, v ∈ P , we consider a port visit cost incurred by a ship of type a if it visits port v. At a port p, port visit cost for a ship is proportional to the capacity of the ship i.e. a ship with 8000 TEU capacity incurs a higher port visit cost as compared to a 2000 TEU capacity ship. At every port, v ∈ P , we consider a per unit cargo per night holding cost. This cost is incurred by a unit of cargo if it is held at a port for one night and is assumed to be the same for all cargo types. At a port, holding cost per unit cargo is chosen to be considerably smaller than the port visit cost for a ship. For every ship type, a ∈ A, and for every pair of ports, {u, v }, we consider the operation cost for sailing a ship from port u to v. The operation cost depends on the type of ship that is used for the sailing and is proportional to the distance between the ports. We generate various classes of random instances, utilizing the above schema, to test the robustness of our algorithm. Classes are characterized by specifying the number of ports (P ), the number of ships (S) and the number of demand triplets (D). For example, an instance with 6 ports, 30 ships and 18 demand triplets is represented as P 6S30D18. We tested our algorithm on networks with 6, 10, 15 and 20 ports to be serviced. In each of the test classes 20-30 % of all pairs of ports are considered to be origin destination pairs. A eet size of up to 100 ships is scheduled. Grand Alliance which is one of world’s largest alliances has a eet of 100 ships and APL (2005) has a eet of more than 80 container ships. For each test class, results reported in this section were obtained by generating 5 random instances and then taking an average over them. To report the results of our computational study in tabular form we use the following abbreviations:

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

21

G: The greedy algorithm. C: The pure column generation based algorithm. B: The two phase Benders decomposition based algorithm where column generation is used for solving the master problem in Phase I. F : The cycle generation algorithm based on the ow decomposition of the circulation problem. I: The cycle generation algorithm based on the iterative search algorithm. Combination of these are used to represent the overall algorithm tested. For example, the two phase Benders decomposition based algorithm with the iterative search algorithm for cycle generation is represented by BI.

4.2. Eectiveness of the Algorithms We now compare the Benders decomposition based algorithm with the other proposed algorithms. While solving the problem with the pure column generation based algorithm the LP relaxation is rst solved to optimality and then the integer solution is obtained using branch-and-bound. However, while solving the problem with the two phase Benders decomposition based algorithm, in Phase I the cuts are generated until the relative dierence between the upper bound provided by the Benders relaxed master problem and the lower bound provided by the subproblem is less than 1% or the number of iterations in the rst phase of Benders are less than 200. Phase I terminates when one of these criteria is met. The LP solution obtained by the pure column generation based algorithm is used as an upper bound to estimate the quality of the nal integer solution. Table 1 presents a comparison between the greedy algorithm, the pure column generation based algorithm and the Benders decomposition based algorithm. It also compares the ow decomposition based cycle generation algorithm with the iterative search algorithm for cycle generation. The second and third column of Table 1 report the number of cycles generated and the CPU time taken to solve the problem using greedy algorithm with iterative cycle generation. The fourth and fth column report these statistics for the pure column generation based algorithm with iterative cycle generation. The next four columns, two each, report the corresponding statistics for the Benders decomposition based algorithms with algorithm F and algorithm I for cycle generation, respectively. The last three columns report the gap corresponding to the relative dierence between the solution value of the GI and the BI algorithm, the CI and the BI algorithm and the BF and the BI algorithm, respectively. Initial cuts described in Section 3.2 are used in both of the Benders decomposition based algorithms. Also, columns with reduced cost less than -1,000,000 are removed after every 10 iterations, during the column generation phase in algorithm C and while solving the master problem in Phase I of algorithm B. As discussed at the end of Section 2.3.2, care must be taken in setting the stopping conditions for the mixed integer program BM P in Phase II of the Benders decomposition based algorithm. In our computational experiments, stopping the MIP when a 1% optimality gap for small instances (6-10 ports) and a 3-5% gap for large instances (15-20 ports) is reached provided a good balance of computational time and solution quality. These parameters were set after initial computational experiments. Specically, for the 6 port instances when the optimality gap is reduced from 1% to 0.1%, the solution quality improves by only 0.04% whereas the time taken to solve the integer program increases by 55%. Hence we believe that heuristically solving the MIP’s did not have a signicant eect in prematurely terminating the Benders algorithm if the optimality gap was chosen properly. Also, in our computations when we use the above optimality gaps as stopping criterions we never ran into a situation where the upper bound obtained by the MIP was less than the Benders lower bound. For the CI, BF and BI algorithms, column # cycles reports the number of cycles in the integer program. Note that in these algorithms a larger number of cycles are generated during column generation, while solving the LP, but subsequently removed if they have high negative reduced cost. The results of our tests show that there is a very signicant dierence in the solution quality obtained by the greedy algorithm and the solution quality obtained by the other two algorithms.

22

Table 1 Comparison Test GI Class #cycles P6S18D6 2 P6S18D9 3 P6S30D6 3 P6S30D9 4 P10S30D18 5 P10S30D27 5 P10S50D18 7 P10S50D27 8

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

between dierent algorithms. CI BF BI time #cycles time #cycles time #cycles time 0.03 62 0.95 234 0.68 49 0.16 0.05 70 2.10 272 2.59 64 0.30 0.09 181 7.26 215 1.30 96 0.33 0.13 239 34.42 366 1.73 120 0.57 0.76 312 760.20 1926 67.97 213 15.41 1.65 358 1312.00 2355 160.83 292 30.56 1.78 607 2077.10 3102 583.82 371 61.34 2.64 790 2910.00 4587 1318.68 578 116.35

%GI %CI %BF -BI -BI -BI 49.27 0.01 3.92 57.84 0.60 2.90 37.28 1.10 2.81 33.01 -0.21 1.99 60.29 -0.28 3.50 67.00 2.21 3.21 47.39 2.10 5.25 45.01 0.02 5.65

Though the greedy heuristic is fast, it works with a very small set of cycles and picks each cycle that it generates without any further considerations. The pure column generation based algorithm yields solution qualities comparable to the Benders decomposition based algorithm with iterative cycle generation however it incurs a longer computational time and this dierence increases as the problem size increases. Though the number of cycles passed on to the integer program in the pure column generation is not very high as compared to the number of cycles at the end of Phase I in algorithm BI, the amount of time taken is much higher. This can be contributed to the fact that as the problem size (number of ports, ships and demand triplets) increases the number of variables as well as the number of constraints increases in the column generation based algorithm. However, in the Benders decomposition based algorithm the eect of increase in problem size is distributed between the master problem and the subproblem. Though the BI algorithm outperforms the BF algorithm uniformly, the dierence between the solution quality obtained by these algorithms is less than 6%. However, the time taken in the BF algorithm is 4-5 times higher than the time taken by the BI algorithm. This can be attributed to the fact that, in algorithm BF , many infeasible cycles are generated by solving the circulation problem and decomposing its ow in the rst phase of the Benders decomposition based algorithm. For a 6(10) port problem BF generated about 65%(60%) infeasible cycles in Phase I. Though more cycles are submitted at the end of Phase I by algorithm BF , the branch-and-bound takes far less time as compared to the corresponding branch-and-bound in algorithm CI since most of the cycles generated by algorithm BF are infeasible for the integer program and are removed at the start of the branch-and-bound. Moreover, in the CI algorithm most of the time is spent in solving the LP relaxation via column generation. Table 1 reports results for test cases with up to 10 ports because the pure column generation based algorithm and the ow decomposition based cycle generation algorithm become computationally very expensive thus making CI and BF ineective. Also, the solution quality of the greedy algorithm decreases further as compared to the Benders decomposition based algorithm. Table 1 establishes the superiority of the solution, in terms of both CPU time and revenue generated, obtained by the two phase Benders decomposition based algorithm with iterative cycle generation. Thus, we used this algorithm to perform all further experiments. 4.3. Analysis of the Benders Decomposition based Algorithm Our next set of experiments perform a deeper analysis of the Benders decomposition based algorithm and are presented in Table 2. In these experiments we used initial cuts and removed columns with large negative reduced costs after every 10 iterations in the rst phase of the Benders decomposition based algorithm. The second column in Table 2 represents the number of iterations in the rst phase of the algorithm. The third, fourth and fth columns present a breakdown of the total time taken in various processes while solving the LP BM P . The next column represents the additional time taken to obtain an integer solution. The last column reports the gap corresponding

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

23

Table 2 Analysis of the Benders decomposition based algorithm. Test Phase I Phase Class iters sub-problem master cycle-gen II %gap P6S18D6 13 0.02 0.11 0.09 0.01 10.24 P6S18D9 16 0.10 0.19 0.14 0.03 12.10 P6S30D6 20 0.06 0.23 0.17 0.03 2.30 P6S30D9 27 0.16 0.36 0.27 0.05 3.32 P10S30D18 47 7.24 6.13 5.17 1.99 8.55 P10S30D27 56 17.02 7.65 3.63 6.54 9.80 P10S50D18 75 23.87 20.64 16.09 19.65 1.91 P10S50D27 95 52.69 31.20 18.37 35.55 3.24 P15S45D42 130 105.86 69.46 52.27 35.25 8.63 P15S45D63 175 141.60 110.69 72.00 33.80 8.53 P15S75D42 181 172.25 152.49 118.80 167.72 5.30 P15S75D63 200 254.26 212.56 156.08 174.78 5.92 P20S60D76 200 1165.87 73.12 39.92 42.07 12.70 P20S60D114 200 1750.63 113.18 47.38 173.37 7.51 P20S100D76 200 2507.51 164.61 72.81 262.45 5.05 P20S100D114 200 3784.38 380.11 149.65 478.01 7.21

to the relative dierence between the upper bound, obtained by the CI algorithm, and the integer solution value obtained by the BI algorithm. To keep computational time under control, in Phase II, only 2-3 iterations of the Benders algorithm were performed. Table 2 suggests that as the number of demand triplets increase the time taken in solving the sub-problem increases. This is mainly because every demand triplet is considered a dierent commodity thus as the number of demand triplets increase the complexity of the multi-commodity ow problem or the subproblem increases (in the number of variables and constraints) signicantly. Note that an increase in the number of demand triplets results in an increase in the time taken to solve the master problem also. This is because of the increased possibilities with regard to the cycles that can be generated. The overall time increases as we increase the number of ports, the number of ships or the number of demand triplets. For the same number of ports, as the number of ships increases the integrality gap reduces signicantly. This suggests that the set of cycles generated in the rst phase are good for the second phase also and given sucient number of ships the gap can be reduced further. For small test cases with 6 ports, we observed that the integer solution obtained by our algorithm is indeed close to the optimal solution in many cases and that LP based upper bound is not very tight. It is easily seen that the integrality gap can be very bad. Consider a two port, one ship instance such that the sailing time between ports is one week. An LP solution will assign half a ship to each edge whereas an integer solution will yield zero revenue resulting in a 100% integrality gap. However, given a sucient number of ships such extremely pathological cases are highly unlikely to occur. Our next set of experiments studies the eect of using the renements described in Section 3.2 and Section 3.3. Using the two phase approach we solve each instance rst without the initial set of cuts, then without removing any column at intermediate steps and nally by incorporating the initial cuts and removing columns at intermediate steps to keep only a subset of columns. Parameters are chosen so that the solution quality is not aected by these renements however the computational time is reduced signicantly. Table 3 reports cycles generated, iterations performed and the time taken for each of these cases. The total CPU time taken to nd an integer solution is also reported. Table 3 reports results for networks with up to 10 ports because the time taken in both phases of the Benders decomposition based algorithm becomes prohibitively high, for networks with more than 10 ports, if we remove the initial cuts or do not remove cycles with large negative reduced cost. Note that removing columns with negative reduced cost less than -1,000,000 does not reduce the

24

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

Table 3 Eect of algorithmic renements. Test No Cuts + All Cols Cuts + All Cols Cuts + Remove Cols Class #cycles iters time #cycles iters time #cycles iters time P6S18D6 62 15 0.20 51 13 0.17 49 13 0.16 P6S18D9 93 15 0.34 87 15 0.33 64 16 0.30 P6S30D6 194 22 0.66 105 20 0.44 96 20 0.33 P6S30D9 240 30 1.03 131 27 0.88 120 27 0.57 P10S30D18 494 52 18.82 464 45 18.68 213 47 15.41 P10S30D27 673 60 64.50 603 55 50.45 292 56 30.56 P10S50D18 882 79 271.03 790 71 168.82 371 75 61.34 P10S50D27 1102 99 748.23 889 91 364.81 578 95 116.35

number of cycles signicantly for 6 port instances since not many cycles for such a small network have a large negative reduced cost. However the same renement reduces the number of cycles for 10 port instances to approximately half the size suggesting that this renement must be tuned according to the problem size to properly control the number of columns in the linear program. Table 3 suggests that the CPU time as well as the number of iterations, in the rst phase of the Benders decomposition based algorithm, reduce by introducing the initial cuts. However, a more signicant reduction in time is achieved by removing columns with large negative reduced cost. Removing very negative reduced cost cycles does not aect the time taken in Phase I very much, but the number of columns that the integer program works with in Phase II are reduced considerably and thus the time taken in the second phase of the Benders decomposition based algorithm reduces signicantly. Finally, we study the eect of having only one ship type, in the eet, on the solution quality. Table 4 reports results for a eet of identical ships with 4000 TEU capacity. For each test class, we report the CPU time taken in Phase I and Phase II of the Benders decomposition based algorithm with iterative search for cycle generation, the total number of cycles generated and the optimality gap. In this case also, 2-3 iterations of the Benders algorithm were performed in Phase II.

Table 4 Eect of identical ships in the eet. Test Phase I Phase Class sub-problem master cycle-gen II #cycles %gap P6S18D6 0.02 0.09 0.07 0.00 35 1.43 P6S18D9 0.04 0.17 0.14 0.01 42 2.14 P6S30D6 0.03 0.11 0.09 0.00 60 0.16 P6S30D9 0.06 0.20 0.18 0.04 72 2.01 P10S30D18 3.92 2.97 2.41 0.30 190 2.25 P10S30D27 5.06 2.16 1.82 0.62 202 2.23 P10S50D18 8.32 6.98 5.25 2.02 243 1.45 P10S50D27 13.38 8.36 6.82 2.54 275 1.74 P15S45D42 51.72 17.40 15.35 3.72 398 2.53 P15S45D63 97.05 25.59 21.97 4.97 520 2.01 P15S75D42 171.12 52.77 37.77 5.20 583 1.93 P15S75D63 209.07 87.28 52.78 6.83 647 1.56 P20S60D76 1023.53 106.96 91.60 12.83 450 1.32 P20S60D114 1869.77 193.79 117.76 13.50 791 1.16 P20S100D76 1825.67 181.85 144.67 14.82 957 1.91 P20S100D114 2923.28 189.13 141.51 16.50 980 2.01

Table 4 suggests that if all the ships are identical the optimality gap reduces even further in all the test classes. Since all ships are identical, in Phase II it becomes easier to operate a service route using ships of similar kind to maintain the weekly frequency. Comparing Table 2 to Table 4 suggests that the overall time taken also reduces. The time taken in the cycle generation process

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

25

Table 5 Analysis of the obtained solutions. Test # picked Trans cost =0 Trans cost =20 Trans cost =100 Trans cost =1000 Class -cycles % utili % trans % di % trans % di % trans % di % trans -zation shipped demand shipped demand shipped demand shipped P6S18D6 3 0.58 17.28 0.00 12.84 0 12.84 30.99 15.17 P6S18D9 3 0.82 21.26 0.00 17.12 0.65 16.86 28.96 6.41 P6S30D6 4 0.71 20.03 0.00 13.77 0.27 13.48 53.54 0.01 P6S30D9 5 0.79 17.33 0.00 14.47 1.59 13.48 33.79 6.58 P10S30D18 6 0.83 22.30 0.00 15.63 0.66 14.99 23.00 3.71 P10S30D27 6 0.86 28.07 0.00 23.08 0 23.08 13.94 11.96 P10S50D18 7 0.88 34.09 0.25 29.46 1.08 28.81 31.79 14.42 P10S50D27 8 0.91 32.53 0.26 27.84 0.74 27.44 30.44 11.41

reduces signicantly as now the cycle generation needs to be solved only for one ship type at every iteration. Thus the time taken in the master problem decreases. Also note that a fewer number of cycles are generated and thus the time taken in Phase II reduces signicantly. As a result the overall solution time is reduced. 4.4. Analysis of the Solution In this section, we take a closer look at the solution generated by the Benders decomposition based algorithm and its implications. Also, we perform preliminary experiments to study the eect of transshipment cost on cargo routing. The second column in Table 5 reports the number of cycles or service routes picked in the nal solution. The number of service routes increases as the number of ships and the number of ports increase. The next two columns in Table 5 report the average percentage utilization of capacity on the edges of the network and the percentage of the cargo that is transshipped. These results are for the case when we do not consider transshipment cost i.e. the cost of transshipment is 0. Utilization of capacity on an edge is calculated by dividing the total ow on that edge by the total capacity of the edge. Recall that the capacity of an edge is dened by the number of ships (and their capacities) that utilize the given edge. Across our problem instances, our algorithm consistently reports high average percentage utilization, 70-90%, of capacity. Note that higher the number of service routes, higher is the number of possibilities for cargo routes. As a result the percentage of the cargo transshipped to the total cargo shipped increases as the problem size increases. This trend is observed in our computational study also as the amount of transshipped cargo increases from 19% for a 6 port problem to 30% for a 10 port problem. Next, we perform preliminary experiments to study the eect of transshipment cost on cargo routing. Depending on the set of chosen service routes we construct a new network. In the new network, at every port where two or more cycles meet a new node is constructed for every cycle. The new nodes are connected to the original port node via edges. These edges act as loading/unloading edges and have corresponding costs associated with them. For example, for the network represented in Figure 3 the new network is given by Figure 6. At port p, cu and cl denote the unloading and p p loading cost respectively and the transshipment cost is given by cu + cl . Thus a transshipment p p occurs when at an intermediate port cargo travels on an unloading and then a loading edge. In Figure 6, a cargo that is routed from port B to port D is transshipped at port C and it uses the unloading edge from cycle C1 to port C and the loading edge from port C to cycle C2 . To perform the experiment, we construct the new network for the cycles selected at the end of the second phase of the Benders based algorithm. The cargo routing problem is solved for both the, new and the original, networks. The eect of the transshipment costs on the cargo routing decisions is studied by observing the percentage dierence between the demand satised in the original network (in the absence of transshipment costs) and the new network (in the presence of transshipment costs). Also we compute the percentage of cargo transshipped to the

26

Port A Mon Tue Wed Thu Fri Sat Sun

Ground Edges Loading/unloading edges

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

Port B 1

Port C

Port D

6

3 C2 3

C1 1 6

Cycle C2 Cycle C1

Figure 6

New network to study the eects of transshipments

total cargo shipped. These two statistics are reported in Table 5 for three dierent scenarios: transshipment cost = 20 units/per unit of cargo, transshipment cost = 100 units/per unit of cargo and transshipment cost = 1000 units/per unit of cargo. Recall that the holding cost at ports is chosen randomly from [1, 10] and the revenue generated by satisfying demand is chosen to be proportional to the distance (proportionality constant being chosen randomly from [100, 200]) between the origin and destination ports. Note that as the distance between ports is chosen from [2, 42] days, the revenue generated is chosen from [200, 8000]. Thus the rst scenario represents the case when the transshipment cost is low and is comparable to the holding cost at a port. The third scenario represents the case when the transshipment cost is very high and is comparable to the revenue generated by satisfying demand. Such high transshipment costs are highly unlikely however we discuss this scenario to present an extreme case. Our computations yield that when the cost of transshipment is of the order of the holding cost at a port or low as compared to the revenue generated by satisfying demand, the routing decision in both networks are similar. However, as the transshipment cost increases the routing decisions change. Specically, as the transshipment cost increases from 20 to 1000 units the percentage change in the amount of demand satised increases from 0% to 36%. We note that as the transshipments become more and more expensive the percentage of the cargo transshipped to the total cargo shipped decreases. An anomaly occurs in the rst row last column of Table 5 as the percentage of transshipped cargo increases from 12.84% to 15.17% when the transshipment cost increases from 100 units to 1000 units. This occurs because as the transshipment cost increases not only does the transshipments decrease but also the demand that is satised decreases in many cases since the routing options get limited. Thus for the last column the numerator as well as the denominator decreases. For instances in the class P 6S186 the denominator decreases faster than the numerator because for this class of instances we have very few demand pairs (few things to route) and on average very few selected cycles (very few alternative routing options).

5.

Concluding Remarks and Future Research

In this paper we presented a new mathematical model for the simultaneous ship scheduling and containerized cargo routing problem for liner shipping. The proposed model captures the important weekly frequency constraint faced by the carriers and allows them to take advantage of transshipping cargo. The structure of the model makes it well suited for decomposition, leading to ecient

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

27

algorithms. Eective service routes for ships are generated selectively in a column generation setting using an iterative search algorithm. Finally, the proposed solution approach is tested on various test classes. Considering the preliminary results obtained, we believe that the suggested solution approach has the potential to help the planners in developing better routes for a eet of up to 100 ships. The planners can also add their pre-determined service routes to the model as a set of initial cycles and thus be a part of the solution process to obtain a solution which is a “user’s solution” rather than a “computer’s solution”. Our results indicate high percentage utilization of ships’ capacities and a signicant number of transshipments in the nal solution. Our aim in this paper is to provide a basic framework for simultaneous ship scheduling and cargo routing. The model and the solution strategy presented here can be enhanced in dierent ways. Next, we present some directions for future research. The model presented in this paper allows for transshipping the cargo from one ship to another. At the end of Section 4.4 we presented an approach to account for transshipment costs during cargo routing. However, the model does not take in to account the transshipment costs while designing the service routes. Further research is required to extend or modify the model to include transshipment costs. This aspect is expected to increase the complexity of the model and the solution procedures signicantly. In this paper we allow only one ship type to maintain weekly frequency on a service route. This provides same capacity in the network every week and is useful when a carrier faces same demand each week. However, it is possible that the demand structure is not the same each week. Further research is required to allow for multiple ship types on a service route. Changes in demand from week to week can be incorporated easily by expanding the planning horizon, however incorporating cycles with multiple ship types will require changes in the model and the cycle generation scheme. In terms of the solution approach, in the pure column generation algorithm and the Benders decomposition based algorithm, no new columns are generated when solving the integer program. New columns can be generated by solving the integer program in a branch-and-price (rather than the branch and bound used in this paper) framework. Branch-and-price is expected to improve the solution quality. However, there are many important and challenging issues that are required to be resolved for developing a successful branch-and-price algorithm. Specically, a good branching rule needs to be devised. Standard branching on the cycle or the xC variables creates a problem along the branch where a variable has been set to zero. xC = 0 means that cycle C needs to be excluded. However, it is possible that the next time the pricing problem is solved to generate a protable cycle in this branch, the optimal solution is precisely the cycle C. Thus the second best cycle must be considered. More over, at depth l in the branch and price tree it might be necessary to construct the lth best cycle. Note that a successful branch-and-price algorithm requires a pricing problem that can be solved very eciently, as it will be invoked many times. Explicitly excluding the specied cycles from the pricing problem is computationally expensive. Even if a pool of cycles is generated at every column generation step, one needs to keep track of all the cycles that need to be excluded. Furthermore, since commercial softwares such as CPLEX cannot handle the branch and price framework, managing the search tree eciently poses many implementation challenges, such as deciding which nodes to branch on and which search technique e.g. breadth rst search, depth rst search, best bound, etc to use.

6.

Acknowledgements

¨ Ozlem Ergun was supported in part under NSF grant DMI-0238815. We would like to thank the anonymous referees for their valuable suggestions.

References

Ahuja, R. K., J. B. Orlin, D. Sharma. 2003. A composite very large scale neighborhood structure for the capacitated minimum spanning tree problem. Oper. Res. Letters 31 185–194.

28

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

American Association of Port Authorities. 2006. America’s ports today. URL http://www.aapa-ports. org/. AAPA Policy Paper. APL. 2005. www.apl.com. Barnhart, C., E. L. Johnson, R. Anbil, L. Hatay. 1994. A column-generation technique for the long-haul crewassignment problem. Optimization in industry 2: Mathematical programming and modeling techniques in practice. John Wiley & Sons, Inc., 7–24. Barry Rogliano Salles- AlphaLiner. 2006. Archived Report. Liner shipping report. URL http://www.alphaliner.com.

Bendall, H. B., A. F. Stent. 1999. Longhaul feeder service in an era of changing technology : an asia-pacic perspective. Maritime Policy and Management 26(2) 145–159. Benders, J. F. 1962. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4 238–252. Bertsimas, D., J. N. Tsitsiklis. 1997. Introduction to Linear Optimization. Athena Scientic. Cheung, R. K., C-Y. Chen. 1998. A two-stage stochastic network model and solution methods for the dynamic empty container allocation problem. Transportation Sci. 32(2) 142–162. Christiansen, M., K. Fagerholt, D. Ronen. 2004. Ship routing and scheduling: Status and perspectives. Transportation Sci. 38(1) 1–18. Christiansen, M., B. Nygreen. 1998. A method for solving ship routing problems with inventory constraints. Ann. Oper. Res. 81 357–378. Cordeau, J-F., F. Soumis, J. Desrosiers. 2000. A Benders decomposition approach for the locomotive and car assignment problem. Transportation Sci. 34 133–149. Cordeau, J-F., F. Soumis, J. Desrosiers. 2001a. Simultaneous assignment of locomotives and cars to passenger trains. Oper. Res. 49 531–548. Cordeau, J-F., G. Stojkovic, F. Soumis, J. Desrosiers. 2001b. Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Sci. 35 375–388. Drewry. 2001. The drewry container market quarterly. Drewry Shipping Consultants Limited September 2001. Fagerholt, K. 1999. Optimal eet design in a ship routing problem. Internat. Trans. Oper. Res. 6 453–464. Florian, M., G. Bushell, J. Ferland, G. Guerin, L. Nastansky. 1976. The engine scheduling problem in a railway network. INFOR 14 121–138. Garey, M. R., D. S. Johnson. 1979. A list of NP-complete problems. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freedman and Co., 214–215. Hingorani, N., D. Moore, K. Tornqvist. 2005. Setting a new course in the container shipping industry. IBM Business Consulting Services Travel and Transportation. Imai, A., E. Nishimura, S. Papadimitriou, M. Liu. 2006. The economic viability of container mega-ships. Transportation Res. E 42 21–41. Lin, S., B.W. Kernighan. 1973. An eective heuristic algorithm for the travelling salesman problem. Oper. Res. 21(2) 498–516. McDaniel, D., M. Devine. 1977. A modied Benders partitioning algorithm for mixed integer programming. Management Sci. 24 312–379. OOCL. 2005. www.oocl.com. Perakis, A. N. 2002. Fleet operations optimization and eet deployment. C. T. Grammenos, ed., The Handbook of Maritime Economics and Business. Lloyd’s of London, 580–597. Rana, K., R. G. Vickson. 1991. Routing container ships using lagrangean relaxation and decomposition. Transportation Sci. 25(3) 201–214. ROI. 2002. Prot optimization for container carriers. URL http://www.imsworldgroup.com/Downloads/ ROI%20Product@Services%%20v1.8.pdf. The ROI Container Cargo Alliance White Paper.

Agarwal and Ergun: Network Design for Liner Shipping Transportation Science 00(0), pp. 000–000, c 0000 INFORMS

29

Ronen, D. 1983. Cargo ships routing and scheduling: Survey of models and problems. Eur. J. Oper. Res. 12 119–126. Ronen, D. 1993. Ship scheduling: The last decade. Eur. J. Oper. Res. 71(3) 325–333. Shen, W. S., C. M. Khoong. 1995. A dss for empty container distribution planning. Decision Support Systems 15 75–82. Song, D. W., P. M. Panayides. 2002. A conceptual application of cooperative game theory to liner shipping strategic alliances. Maritime Policy and Management 29(3) 285–301. United Nations Conference on Trade and Development. 2006. Review of maritime transport. URL http: //www.unctad.org/en/docs/rmt2006_en.pdf. Report by the UNCTAD secretariat. United States Customs Service. 2003. Singapore, the World’s busiest seaport, implements the container security initiative and begins to target and pre-screen cargo destined for U.S. URL http://www.cbp.gov/xp/cgov/newsroom/press_releases/archives/c%bp_press_releases/ 032003/03172003.xml. Archived Press Release. Wiel, R. J. Vander, N. V. Sahinidis. 1996. An exact solution approach for the time dependent travelling salesman problem. Naval Res. Logist. 43 797–820.

### 相关推荐

- SHIP SCHEDULING AND SERVICE NETWORK INTEGRATION FOR
- Transit network design and scheduling A global review
- Ship routing and scheduling with flexible cargo sizes
- Centralized and Distributed Algorithms for Network Scheduling
- Communication Requirements and Network Design for IVHS
- Joint design of network coding and channel decoding for wireless networks
- Design and Implementation of Auto-Monitoring System for Wireless Network
- Evolutionary algorithms for neural network design and training
- Design and Implementation of a Fibre Channel Network Driver for SAN-Attached RAID Controller
- ABSTRACT Adaptive Network Coding and Scheduling for Maximizing Throughput in Wireless Netwo

### 最新更新

- 初中化学人教五四学制版九年级第十一单元第2课《化学肥料》优质课公开课教案教师资格证面试试讲教案
- 【工作计划总结】“自来水公司工会二00四年计划”工会工作计划_1
- 小学语文人教版 三年级上册11《秋天的雨》优质课公开课教案资格证面试试讲教案
- 修读校际共享课程学生学分认可和成绩转换申请表
- 小学二年级写人作文：家有“手机迷”
- 空调室外机低频噪音危害
- 2018高考地理一轮复* 7.1 城市空间结构与不同等级城市的服务功能课件 湘教版说课材料
- 春节祝贺词送亲人
- 2019-2025年中国苯酐聚酯多元醇市场发展战略及投资前景预测咨询报告
- 2011届高考数学复*好题精选-函数的奇偶性
- 2019年三年级上册英语课件-Unit 1《Hello Miss Liu》｜重大版 共18张PPT语文
- 培训师成长手册学*笔记
- 他变化真大作文
- MySQL数据备份，压缩并清理
- python+django：19、密码加密存储和解密
- 专利文献检索及专利挖掘基础知识培训PPT课件

### 猜你喜欢

- 2019-2020学年八年级英语下单元练*题精选 Unit3 人教新目标版.doc
- 程序员跳槽的10个建议
- 爆破材料库管理制度
- 331生产物流培训-81页精品文档
- 2014年1-6月广西壮族自治区及全国初级形态的塑料月度产量数据统计报告
- 专科院校独生子女学生心理健康状况的调查报告
- 百数图里的灵感
- 9-3 装配图视图选择
- 2017年电商*台运营实施计划书
- 影音先锋和西瓜影音还有吉吉影音哪个比较好
- 部编版一年级语文下册《13.荷叶圆圆》同步课时练*题及答案
- 上海欢瑜文体发展有限公司企业信用报告-天眼查
- 自制排毒养颜茶配方
- 跆拳道馆学员登记表Excel
- 优秀初一抒情散文：小花被
- 老年痴呆的护理查房.ppt
- 高考化学二轮复*2.3电解质溶液名师精编课件(全国)
- 中通建设股份有限公司员工职业生涯规划管理办法
- 2018年七年级生物上册第3单元第67章期末复**题课件新版北师大版20180917425
- 北京科润宝经贸有限责任公司摄影服务中心企业信用报告-天眼查
- 春季如何预防咽喉炎复发
- 巷道顶板离层记录表
- 文安县惠泰机械有限公司企业信用报告-天眼查
- 夏季防病常识
- 重庆优乐鲜生态农业有限公司企业信用报告-天眼查
- 初一话题作文：初一新生军训心得体会600字
- 城区建筑垃圾运输特许经营项目招标文件
- 料字开头的成语接龙长一点
- 道路工程质量管理内容有哪些？
- 盐酸赛庚啶片含量测定方法的研究
- 八年级语文下册第一单元作文教案苏教版
- 服务贸易发展的基本规律和我国的战略抉择
- “中低速磁浮C型成套钢铝复合导电轨”通过技术评审
- UCM系列以及CVC系列冷轧机特点初步分析
- 备战2011年研究生入学考试流程
- Wkvy11年考研教育学[外国教育史]复习背诵资料
- 干部教育培训工作状况调研报告
- Android本地数据存储：Shared Preferences安全风险浅析
- 2017届高考一轮总复*课标版物理课时跟踪训练39含答案
- 蝼蛄的功效与作用_蝼蛄的药用价值
- 北京航博优考教育科技有限公司(企业信用报告)- 天眼查
- 苯乙烯苯乙烯与下游产业利润解析