Routing Container Ships Using Lagrangean Relaxation and Decomposition

Rana, Krishan; Vickson, R. G.
August 1991
Transportation Science;Aug91, Vol. 25 Issue 3, p201
Academic Journal
International shipping is a multibillon dollar business and shipping companies may expect large benefits from improving the routing and scheduling processes of their ships. In this paper, we describe a container-ship routing scenario in which a shipping company provides services to a network of ports. We formulate a mathematical programming model that maximizes total profit (i.e., revenue minus operating costs) for multiple ships and determines: (a) the optimal sequence of ports of call for each ship, (b) the number of trips each ship makes in a planning horizon, and (c) the amount of cargo transported between any two ports by each ship. The model contains discrete, 0-1 and continuous variables, and nonlinear complicating constraints. The multiple container ship model is quite different from those of vehicle routing and traveling salesman problems. We use a decomposition method for the model as well as for the network in order to solve the problem. Several problems on 10- to 20-port networks are solved and the results presented.


Related Articles

  • RELAXATION METHOD FOR LARGE SCALE LINEAR PROGRAMMING USING DECOMPOSITION. Tseng, Paul // Mathematics of Operations Research;Nov91, Vol. 16 Issue 4, p859 

    We propose a new decomposition method for large-scale linear programming. This method dualizes an (arbitrary) subset of the constraints and then maximizes the resulting dual functional by dual ascent. The ascent directions are chosen from a finite set and are generated by a truncated version of...

  • The Development of Hybrid Cross Entropy-Genetic Algorithm for Multi-Product Inventory Ship Routing Problem with Heterogeneous Fleet. Santosa, Budi; Damayanti, Rita // Proceedings of the International Conference on Industrial Engine;2014, p1356 

    This research develops multi-product inventory ship routing problem with heterogeneous fleet. ISRP is a problem that combines inventory level management in every unloading port and the routing process of the ship. The problem that developed in this research considers some different things those...

  • LAGRANGIAN RELAXATION.  // Encyclopedia of Operations Research & Management Science;2001, p437 

    A definition for the term "Lagrangian relaxation" is presented. It refers to an integer programming decomposition method.

  • Decomposition in single-machine scheduling. Szwarc, Wlodzimierz // Annals of Operations Research;1998, Vol. 83 Issue 1-4, p271 

    This paper discusses the recent research on decomposition techniques in single-machine scheduling. A variety of orderings between adjacent and nonadjacent jobs in an optimal scheduling are presented. A list of decomposition rules is given that enable one to solve large size instances of six...

  • THE TRANSHIPMENT PROBLEM. Orden, Alex // Management Science;Apr1956, Vol. 2 Issue 3, p276 

    The article discusses the "transportation problem," which is a class of linear programming problems involving the selection of the most economical shipping routes for a commodity from given sources to given destinations. The transportation problem has been typically approached either as a...

  • Multiple-Machine Lower Bounds for Shop-Scheduling Problems. Sourd, Francis; Nuijten, Wim // INFORMS Journal on Computing;Fall2000, Vol. 12 Issue 4, p341 

    In order to compute lower bounds for shop scheduling problems, a lot of attention has been paid to adjustment techniques based on one-machine relaxations. We present such a new technique but, following the observation that machines are connected to each other through precedence constraints, we...

  • A Discrete Lagrangian Algorithm for Optimal Routing Problems. Kosmas, O. T.; Vlachos, D. S.; Simos, T. E. // AIP Conference Proceedings;11/6/2008, Vol. 1060 Issue 1, p75 

    The ideas of discrete Lagrangian methods for conservative systems are exploited for the construction of algorithms applicable in optimal ship routing problems. The algorithm presented here is based on the discretisation of Hamilton’s principle of stationary action Lagrangian and...

  • THE LAGRANGIAN RELAXATION METHOD FOR SOLVING INTEGER PROGRAMMING PROBLEMS. Fisher, Marshall L. // Management Science;Jan1981, Vol. 27 Issue 1, p1 

    One of the most computationally useful ideas of the 1970s is the observation that many hard integer programming problems can be viewed as easy problems complicated by a relatively small set of side constraints. Dualizing the side constraints produces a Lagrangian problem that is easy to solve...

  • A computational analysis of lower bounds for big bucket production planning problems. Akartunalı, Kerem; Miller, Andrew // Computational Optimization & Applications;Dec2012, Vol. 53 Issue 3, p729 

    In this paper, we analyze a variety of approaches to obtain lower bounds for multi-level production planning problems with big bucket capacities, i.e., problems in which multiple items compete for the same resources. We give an extensive survey of both known and new methods, and also establish...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics