The Surprising Influence of Maritime Transportation on the Field of Mixed-Integer Programming

In the landmark paper “An Automatic Method for Solving Discrete Programming Problems”, which was re-published in 50 Years of Integer Programming 1958-2008 in association with the 12th Combinatorial Optimization Workshop AUSSOIS 2008 in Aussois, France, the authors Ailsa Land and Alison Doig describe how crude shipping was a large motivator for their research in what is today known by all students of integer programming as ``branch-and-bound":

In the late 1950s there was a group of teachers and research assistants at the London School of Economics interested in linear programming and its extensions, in particular Helen Makower, George Morton, Ailsa Land and Alison Doig. We had considered the ‘Laundry Van Problem’ until we discovered that it was known as the Traveling Salesman Problem, and had looked at aircraft timetabling, until quickly realizing that even the planning for the Scottish sector was beyond our capability! Alison Doig (now Harcourt) had studied the paper trim problem for her Masters project in Melbourne before coming to England.

At the same time, British Petroleum was developing linear programming models for their refinery operations. They had ambitions to extend the model to deal also with the planning of world movement of oil from source to refinery, but knew that the capacity restrictions on the ships and storage tanks introduced discrete variables into their models. BP contracted with LSE to pay the salaries of Alison Doig and Ailsa Land for one year to investigate the possibility of incorporating discrete variables into linear programming models.

We rapidly decided that the oil transport model was much too big to tackle until we had a working method to handle discrete variables. We easily found papers with smaller examples, ones with known optimal solutions, to use for testing purposes. We are pretty sure that we got the approval of BP for this switch of attention. At the time, BP did not want their sponsorship acknowledged for any publication we might make on discrete variables. We suppose they did not want to alert competitors to their interest in the area, but we assume this prohibition no longer applies!
 

Characterizing Maritime Inventory Routing Problems

Maritime inventory routing problems can be classified along several axes. Several are described below:

Inventory Routing vs. Cargo Routing

It is important to distinguish maritime inventory routing problems from a closely related class of problems known as cargo routing problems. As discussed in Al-Kayyal and Hwang, cargo routing problems are mainly constrained by the cargo, which is usually defined by the loading and discharging ports, and by time windows for loading and discharging. Inventory routing problems are constrained by inventory requirements such that the inventory level of products at ports should be maintained. In general, cargo routing is performed under more restrictive constraints since the time windows to load and discharge are usually narrow and the quantities to be loaded and discharged are known in advance. In contrast, in a MIRP, the number of calls (i.e., visits) at a given port over the planning horizon, the quantity to be loaded or discharged at each port call, as well as the port pickup and delivery pairings are not specified in the data. Thus, due to the larger solution space, it can be argued that maritime inventory routing is often more challenging computationally than traditional cargo routing.

Industrial vs. Tramp vs. Liner Shipping

Maritime routing problems are often classified by their shipping environment, of which there are three main types: industrial, tramp, or liner (Lawrence 1972, Ronen 1993). Industrial operators own or control both the vessels and cargo to be transported, and focus on minimizing their transport costs. Tramp shipping is analogous to a taxi service, as the vessels go after cargoes that become available in the market. Liner shipping, for which there are virtually no MIRP applications in the literature, resembles bus line operations since the vessels follow published itineraries and schedules.  In practice, MIRP applications may involve elements from both industrial and tramp shipping.

Deep-sea vs. Short-sea Shipping

Deep-sea shipping pertains to intercontinental trips through deep seas in which travel times are much longer than the time required to load and discharge at ports. Short-sea shipping typically refers to short regional trips having travel times that are likely to be shorter than the time requirements at a port, and therefore port operations and service constraints are necessary to adequately model reality.