1. INTRODUCTION
Ship routing involves the solution of optimal control problems resulting from the meteorological navigation of ships. For instance in ship routing, the route of a ship between two given points may be determined so that a certain criterion (e.g. transit time, fuel consumption, damage to cargo or comfort of passengers) is optimized. To compute an optimal path all the disturbing forces that could influence the ship on its way must be known. One of the most important forces that a ship encounters is formed by the disturbed ocean surface. As a consequence it is assumed here that the state of the ocean surface is fully known beforehand for the complete passage.
The history of ship routing goes back to the middle of the nineteenth century, when Maury (Reference Maury1855) recommended least-time tracks for sailing vessels based on statistical wind and current data compiled from ships' logs. In those days the wind direction was of course extremely important. The conversion from sail to other means of propulsion made Maury's work obsolete, although there may be a revival of his work should the shortage of energy become acute. Although developments in aviation led to several investigations in the field of navigation (for a bibliography the reader is referred to Arrow, Reference Arrow1949), it was not until more than a century later that Hanssen and James (Reference Hanssen and James1960) published their paper on a manual method for the calculation of least-time tracks for ships, by introducing time fronts analogous to wave fronts in geometrical optics.
The introduction of the computer led to the development of several methods for minimizing the sailing time. The most obvious approach was to adapt the manual method for computer application. Other methods result from applications of the calculus of variations or optimal control theory, and dynamic programming. In a series of papers (Bijlsma, Reference Bijlsma2001, Reference Bijlsma2002, Reference Bijlsma2004a) we showed how these methods could be generalized to include minimization of the fuel consumption.
Today the pollution of the air and oceans caused by the use of heavy fuel oil in shipping is drawing increased attention. Heavy fuel oil, sometimes called bunker fuel or residual fuel oil is most often used to fuel the main combustion engines of large ocean-going vessels. From the Prevention of Air Pollution from Ships published by the Marine Environment Protection Committee of the International Maritime Organization, 7 April 2005 and the documentation of the seminar Mind the Gap, Gothenburg, 3 May 2006 we learn that apart from the pollution of the oceans, the air pollution caused by the use of heavy fuel oil in the marine combustion engines is a growing problem. Emissions are significant and are expected to constitute a larger share of total emissions, especially if Europe and the United States continue to reduce emissions from land-based sources. There are, however, feasible and cost-effective methods of substantially reducing air emissions from ships. These include reduction of the sulphur content in marine fuel, sulphur oxides cause acidification, erosion and corrosion; seawater scrubbing for sulphur dioxide; reduction measures for nitrogen oxides, causing acidification, ozone/smog formation in the lower atmosphere and damage to vegetation; and the introduction of filters for fine particulate matter, which is detrimental to lungs. Most of these emission control measures are not only feasible and cost effective, but are more cost-effective than additional reductions of emissions from many land-based sources, and will produce benefits far in excess of their costs.
The emissions of particulates, sulphur and carbon dioxide, which contribute to the greenhouse effect, are not only related to the choice of fuel but also to the amount of fuel consumed in the combustion process. Therefore an additional option to reduce air pollution is to decrease the fuel consumption during the transit. Prescribing a minimal-fuel route for a ship on an ocean crossing could be the solution to achieve this. But it is very difficult to verify whether the instructions for such a route will be followed. We can circumvent this problem by specifying the amount of fuel that can be consumed on a specific ocean crossing, as is the practice in aviation where the aircraft fuel consumption on a specific flight is estimated beforehand, mainly for economic reasons (see for instance Schilling, Reference Schilling1997), and by computing a minimal-time route for that given amount of fuel. Note that the amount of fuel must be chosen to be greater than the amount of fuel consumed along a minimal-fuel track. The foregoing approach could also be used to check for illegal dumping of oil at sea because any disappearance of oil can be traced, particularly in combination with a stricter surveillance on the observance of environmental laws.
In this paper we give the mathematical tools that are needed to solve the time-optimal problem with beforehand-specified fuel consumption. Those familiar with shipping should be consulted for providing practical information on this subject. The paper is organized as follows. The next section pays attention to modifications that should be introduced to meet the condition of fixed fuel consumption. In section 3 necessary conditions for the computation of a minimal-time route with fixed fuel consumption are derived using relevant results from the calculus of variations. A method of solution for this optimal problem is suggested, which is relatively simple and most convenient for operational use; the practical aspects of this approach are discussed in section 4. Conclusions are presented in section 5.
2. MODIFICATIONS IN THE CASE OF FIXED FUEL CONSUMPTION
Let us consider the fuel consumption of a ship during its transit over the ocean between two given points. In order to simplify the computations, the navigation area is mapped conformally onto a plane, for instance by means of stereographic projection (see Bijlsma, Reference Bijlsma1975, p. 14). Introducing a Cartesian coordinate system with coordinates x 1 and x 2, it is assumed that the nonzero fuel consumption per unit of time can be described by the equation
where x 0 denotes the fuel consumption and where the dot stands for differentiation to the time t. The speed V and course p are control variables, which belong to open sets. The case in which the course belongs to a closed set meaning that certain courses are forbidden can be found in Bijlsma (Reference Bijlsma2004b). The dependence of f 0 on t,x 1 and x 2 reflects the effect of the wave field (wave height and direction) on the fuel consumption for given values of V and p. The equations of motion read
where S 1(t,x 1,x 2) and S 2(t,x 1,x 2) are the components of the ocean current, which for simplicity is neglected but could be included. Inclusion, however, does not result in a substantial contribution to the final result. Indeed, compared with the speed ships can attain, the ocean current is really negligible (see also Nagle, Reference Nagle1961). The fuel consumption along a given trajectory can be written as
with the initial and end conditions x i(0)=x i0; x i(t 1)=x i1 (i=1,2).
The problem is now to find optimal control functions V(t) and p(t) and a corresponding arc (x 1(t),x 2(t)) so that the transit time t 1 is minimized with the condition that the fuel consumption x 0(t 1) is fixed, which is denoted by 
. In a previous paper (Bijlsma, Reference Bijlsma2006) we discussed the reverse problem i.e. minimization of the fuel consumption with a fixed transit time. To solve the present problem it is convenient to perform a change of variables. Instead of the time t the fuel consumption x 0 is now considered as the independent variable. The equations of motion are then modified as
where the dash denotes differentiation to x 0. The relation between t and x 0 required to obtain the necessary wave information at a particular point follows from the simultaneous integration of the inverse of equation (1)
with the initial condition t(0)=0.
The new problem is to find control functions V(x 0) and p(x 0) and a corresponding arc (x 1(x 0),x 2(x 0)), which satisfy equations (4), (5) and (6) with the initial and end conditions 
(i=1,2), so that the integral
is minimized. This problem with fixed fuel consumption can be transformed into a similar problem with variable fuel consumption by introducing a variable x 3, which satisfies
with the initial condition x 3(0)=0 so that x 3≡x 0. We now have the following optimal problem (cf. Pontryagin et al., Reference Pontryagin, Boltyanskii, Gamkrelidze and Mishchenko1964, p. 64).
Given the points (x i0,0) and 
(i=1,2) in the three-dimensional space of variables x 1,x 2 and x 3. We now seek to find continuous optimal control functions V(x 0) and p(x 0) and a corresponding trajectory (x 1(x 0),x 2(x 0),x 3(x 0)) satisfying equations (4), (5), (6) and (8), which minimize the integral (7) among all paths between the beginning and end points (x i0, 0) and (i=1,2). Note that the fuel consumption over the voyage need not to be considered as fixed in this case because the arrival at the end point (i=1,2) can only occur for 
.
This problem is an example of the control problem of Bolza (Reference Bolza1909), which has been dealt with extensively in the literature. A comprehensive treatment can be found in Hestenes (Reference Hestenes1966). Below we formulate necessary conditions for a solution of this optimal problem.
3. NECESSARY CONDITIONS FOR A SOLUTION OF THE OPTIMAL CONTROL PROBLEM
The necessary conditions for the control functions V(x 0) and p(x 0), and the trajectory x(x 0)=(x 1(x 0),x 2(x 0),x 3(x 0)) to be optimal i.e. to give a solution of the optimal problem is that there exist continuously differentiable multipliers λ(x 0)=(λ0(x 0), λ1(x 0), λ2(x 0), λ3(x 0)), λ0(x 0)=constant⩽0 and a function
so that the following conditions hold.
(a) The first necessary condition. On x(x 0) the Euler-Lagrange equations
(10)hold. Variables as subscripts denote partial differentiation.
(b) The necessary condition of Weierstrass. Along x(x 0) the following inequality
(11)holds. In addition the relation(12)holds at the end point.
It is assumed here that the arc x(x 0) is normal, which implies the existence of a one-parameter family of arcs between the points (x i0,0) and (i=1,2) satisfying equations (4), (5), (6) and (8) and having x(x 0) as one of its members. As a consequence of normality the option λ0=0 is excluded. The abnormal case is highly singular. In fact, if the arc is abnormal it may be the only arc satisfying the above conditions of our problem. Solutions of the Euler-Lagrange equations with continuous control functions are called extremals. By its definition an optimal trajectory is obviously an extremal. Observing that every part of an optimal trajectory is an optimal trajectory itself, which is a direct consequence of the principle of optimality (Bellman, Reference Bellman1957), the relation H=0 holds on x(x 0) so that we may write the Euler-Lagrange equations as
It follows that λ3 is constant. An obvious choice is λ3<0 We observe that the solution of equations (13) and (14) does not change if the Lagrange multipliers λ1 and λ2 are multiplied by an arbitrary constant. This is the case because λ0 and λ3 can be chosen arbitrarily and the multipliers λ0,λ1,λ2 and λ3 are defined up to a common factor of proportionality. Introducing polar coordinates, the initial values of the multipliers λ1 and λ2 can be written as λ1(0)=cos a and λ2(0)=sin a for every choice of λ0 and λ3. We choose λ3=−1 and set λ0=−μ, where the parameter μ has to be determined so that the fuel consumption over the voyage between beginning and end point is equal to 
as we will see at the end of this section. All extremals emanating from the starting point are found by varying the parameter a. After substitution the equations become
Equations (20) and (21) show a system of two simultaneous equations, which define the speed V and the course p implicitly. These equations together with H=0 express the necessary conditions so that the function
of the variables V and p attains a maximum value (equal to unity) at the points V=V(x 0) and p=p(x 0) along an optimal trajectory. In practice it is convenient to follow the method described in Bijlsma (Reference Bijlsma2001, Reference Bijlsma2004b). In that method the speed V is chosen such that it maximizes the quotient
where f 0 for given values of t, x 1, x 2 and p is an increasing function of V, which can be approximated by an appropriate exponential function depending on the ship's characteristics (Klompstra et al., Reference Klompstra, Olsder and van Brunschot1992, p. 285). As a result, in every point of the (x 1,x 2) plane, an optimal speed V(t,x 1,x 2,p,μ) can be identified, leading to a more direct approach to the problem. For small values of μ this speed tends to the minimal-fuel speed whereas the speed increases with increasing parameter μ. The new problem is to determine a course p=p(x 0) over the journey that minimizes the integral (7) subject to the equations of motion (4), (5) and (6). In all these and further equations the speed V stands for V(t,x 1,x 2,p,μ). For the sake of simplicity the notations V and f 0 are maintained. From the foregoing it follows that the Euler-Lagrange equations for the new problem become
Note that equations (24) and (25) are equivalent to equations (18) and (19), after substitution of V(t,x 1,x 2,p,μ) in f 0(t,x 1,x 2,V,p), if in the latter equations V(t,x 1,x 2,p,μ) is kept fixed when differentiating with respect to x 1 and x 2. It is more convenient, however, to use equations (24) and (25) in practical applications. Since the H-function vanishes along an extremal we also have
Combination of equations (26) and (27) gives
where 
.
It is convenient to introduce a polar “velocity” diagram giving the ship's “velocity” (V 1,V 2) as a function of the angle between the ship's heading and the wave direction for fixed values of t, x 1 and x 2. The geometric meaning of equation (28) is then illustrated in Figure 1. The discussion that follows focuses on solutions of equations (4), (5), (6), (24), (25) and (28) for fixed parameter μ, which are continuous in their dependence on the parameter a. Therefore, the two following theorems are used.
Figure 1. The course p for which the projection of (V 1,V 2) on (λ1,λ2) attains a maximum value.
First, from a theorem on the initial value problem for a system of ordinary differential equations (see Walter, Reference Walter1972, p.93) we learn that the right-hand sides of equations (4), (5), (6), (24) and (25), where p is implicitly defined by equation (28), must be continuous and bounded, and must satisfy a Lipschitz condition with respect to t,x 1,x 2,λ1 and λ2 so that the solutions depend continuously on the parameter a.
Second, application of a theorem on implicit functions (Hestenes, Reference Hestenes1966, p. 22) to equation (28) shows that V ip and V ipp(i=1,2) must be continuous functions with respect to t,x 1,x 2 and p, and that the condition
(29)must hold so that p is a continuous function of t,x 1,x 2,λ1 and λ2. This condition implies that the polar ‘velocity’ diagram must be convex (see for instance Bijlsma, Reference Bijlsma1975, p. 30) and that the equality sign for the Legendre condition, being an immediate consequence of the condition of Weierstrass, is excluded so that(30)which confirms the construction in Figure 1.
Summarizing, we have the following result. Let the functions 
and V ipp(i=1,2) be continuous for 
, where 
is the fuel consumption along an extremal between beginning and end point for a specific value of μ, and let the Legendre condition (30) be valid. Further, let the right-hand sides of equations (4), (5), (6), (24) and (25), where p is given by equation (28), be bounded and satisfy a Lipschitz condition with respect to t,x 1,x 2,λ1 and λ2. Then x i(x 0,a), λi(x 0,a)(i=1,2) and t(x 0,a), 
as solutions of equations (4), (5), (6), (24) and (25) with x i(0)=x i0(i=1,2) and t(0)=0, where p is given by equation (28), are continuously differentiable with respect to x 0 and continuous in their dependence on the parameter a, defined by λ1(0)=cos a and λ2(0)=sin a
This result makes it possible to introduce a numerical method for the solution of this optimal control problem. An optimal route is obtained by integrating the system of equations, varying the parameter a and selecting that extremal which ends closest to the destination. The final optimal route between beginning and end point obtained with a value of μ, which corresponds to the beforehand-specified fuel consumption , is found by computing a set of optimal routes for different values of μ and by using a proper iterative method. The method appears to be highly suitable in practical applications because the requirements contained in the above two theorems can be satisfied rather simply. The practical aspects of the method are discussed in the next section.
4. AN OUTLINE OF THE COMPUTATIONAL PROCEDURE
We consider an orthogonal grid coinciding with the (x 1,x 2) coordinate system. The mesh size of the grid is of the order of magnitude of the distance that can be covered by the ship in 6 or 12 hours, usually the times that wave charts are available. Differential distances on the earth surface are multiplied by the map factor of stereographic projection in order to convert them into differential distances in the (x 1,x 2) plane. Distances are measured in mesh units. At any time significant wave heights and wave directions are assumed to be known at grid points and obtained by linear interpolation at intermediate points. The same interpolation procedure could be applied to the approximation of the spatial derivatives in the equations that are computed at grid points by means of central differences. In practice the ship's speed, maximizing relation (23), is computed for a range of wave heights in the case of following, beam and head waves so that by interpolation for each wave height at a particular grid point a polar velocity diagram of elliptic form can be constructed. An optimal route is obtained by integrating the set of equations (4), (5), (6), (24) and (25) starting from the point of departure with initial values λ1(0)=cosa, λ2(0)=sina and p(0) given by relation (28), varying the parameter a and selecting that extremal, which ends closest to the destination. The above set of equations can be rewritten in the following way giving the differentials of the time and space variables, and the Lagrange multipliers at each integration step.
After computation of new values for t, x 1, x 2, λ1 and λ2 a following integration step is started with the computation of the wave height and wave direction in a specific point, which is determined by t, x 1 and x 2, and with the construction of a polar velocity diagram. Then the course p is computed with the new values of λ1 and λ2 by means of the construction of Figure 1. Once the speed and course are known the above set of equations can be applied, and so on. The continuous dependence of t,x 1, x 2, λ1 and λ2 on the initial values of the Lagrange multipliers means that we may start a new extremal between two neighbouring extremals for a specific value of the fuel consumption if the distance between these neighbours becomes too large for that value of the fuel consumption. If this distance is chosen sufficiently small the starting values of the new extremal can be obtained by linear interpolation between the corresponding values of its neighbours. The numerical procedure to compute an optimal route between the beginning and end point for a specific value of the parameter μ described by the above set of equations follows closely the computation of a minimal-time route as shown in Figure 2, except for two points: the time step is not fixed but variable corresponding to the fixed energy step, and the speed is not the maximum speed leading to a minimal-time route but the speed maximizing relation (23) leading to a minimal-time route for a restricted amount of fuel. For more details concerning practical problems the flow diagram and computer program in Bijlsma (Reference Bijlsma1975) might be helpful. The final optimal route between beginning and end point with the fuel consumption is found by repeating the optimal-route computations for different values of μ and by using a proper iterative procedure. To accelerate convergence it is convenient to choose at each stage of the iterative procedure two values of μ corresponding with optimal routes arriving at the end point with fuel consumptions , which lie on opposite sides of the solution using for instance the method of false position (see Noble, Reference Noble1964, p. 51) so that in practice probably a couple of iterations suffice.
Figure 2. One-parameter family of extremals along which the sailing time is minimized using a fixed time step.
5. CONCLUSION
Air emissions from shipping are significant and are expected to constitute a larger share of total emissions, especially if Europe and the United States continue to reduce emissions from land-based sources. Methods have been developed to reduce air emissions from ships, more or less aimed at the choice of fuel and the related air emissions. However, the emission of particulates, sulphur and carbon dioxide, which contribute to the greenhouse effect are not only related to the choice of fuel but also to the amount of fuel consumed in the combustion process of the main engines of large ocean-going ships. This paper proposes an additional method that can contribute to the reduction of the air pollution of ships by decreasing the fuel consumption on an ocean crossing in a verifiable way. This is done by specifying the amount of fuel that can be consumed on a specific ocean crossing and by computing a minimal-time route for that given amount of fuel. In a sense the method can be compared with the introduction of speed limits on freeways to reduce the emission of greenhouse gases such as carbon dioxide, the emission of which is directly proportional to the fuel consumption and therefore related to the driving speed of vehicles.
The implementation of the method in a ship routing program is relatively simple because the computation of a minimal-time route with previously-specified fuel consumption is straightforward. An additional advantage of the method is that it could also be used for checking illegal dumping of oil at sea because any disappearance of oil can be traced, certainly in combination with a stricter surveillance on the observance of environmental laws.
Finally, it should be noted that the quality of the present weather forecasts is such that a start can be made with the implementation of the method, all the more since it will probably take a long time before the use of cleaner fuel in combination with engine modifications to reduce the environmental effects from shipping has been regulated.
