Optimal operating strategy for a long-haul liner service route

This paper proposes an optimal operating strategy problem arising in liner shipping industry that aims to determine service frequency, containership fleet deployment plan, and sailing speed for a long-haul liner service route. The problem is formulated as a mixed-integer nonlinear programming model that cannot be solved efficiently by the existing solution algorithms. In view of some unique characteristics of the liner shipping operations, this paper proposes an efficient and exact branch-and-bound based ε-optimal algorithm. In particular, a mixed-integer nonlinear model is first developed for a given service frequency and ship type; two linearization techniques are subsequently presented to approximate this model with a mixed-integer linear program; and the branch-and-bound approach controls the approximation error below a specified tolerance. This paper further demonstrates that the branch-and-bound based ε-optimal algorithm obtains a globally optimal solution with the predetermined relative optimality tolerance ε in a finite number of iterations. The case study based on an existing long-haul liner service route shows the effectiveness and efficiency of the proposed solution method.     

飞越北极

本文对“飞机从北京出发、飞越北极直达底特律的所需时间 ,可比原航线节省多少时间”的问题进行讨论 ,并将航线选择归结为寻求曲面上的最短弧 .应用“曲面上最短弧为测地线”的事实进行了讨论 .模型 (一 )假设地球是球体 ,我们可通过单位向量的点乘与夹角的关系 ,加以解决 ;对于模型 (二 )设地球是旋转椭球体 ,我们利用微分几何学中测地线方程加以解决 ,并且把球面的纬度转化为旋转椭球面纬度 .对于 4组较特殊的点 ,纬度几乎相等或相近 ,或者两者之间的经度差过大时 ,用测地线计算比较困难 ,我们用椭圆弧 (长 )代替测地线长 ,结合数学软件 Mathematica的数值积分功能 ,可求得测地线长     

Designing robust liner shipping schedules: Optimizing recovery actions and buffer times

It is important for liner shipping companies to maintain cost efficient and robust liner shipping networks. Regularly, they set up pro-forma schedules, yet it is difficult to stay on time. We consider the problem of managing the delays. Therefore, we need to determine an optimal recovery policy and buffer time allocation to the ship route in order to minimize the total costs associated with delays and recovery actions, such as increasing sailing speed. We introduce a general framework consisting of a mixed integer programming formulation to solve discrete stochastic decision problems with short and long term decisions and apply this framework to the above described problem. Furthermore, we propose and test four heuristics for this problem. We compared the results of our method with an existing liner shipping route schedule and found a cost decrease of 28.9% after optimizing the buffer time distribution compared to the cost of sailing the current route schedule at constant speed.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

A prototype column generation strategy for the multiple container loading problem

The multiple container loading cost minimization problem (MCLCMP) is a practical and useful problem in the transportation industry, where products of various dimensions are to be loaded into containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally formulated as a set cover problem and solved using column generation techniques, which is a popular method for handling huge numbers of variables. However, the direct application of column generation is not effective because feasible solutions to the pricing subproblem is required, which for the MCLCMP is NP-hard. We show that efficiency can be greatly improved by generating prototypes that approximate feasible solutions to the pricing problem rather than actual columns. For many hard combinatorial problems, the subproblem in column generation based algorithms is NP-hard; if suitable prototypes can be quickly generated that approximate feasible solutions, then our strategy can also be applied to speed up these algorithms.     

基于可变航速的支线集装箱船舶调度优化模型与算法

随着航运市场的竞争不断加剧和集装箱船舶大型化的发展,越来越多的航运企业选择轴-辐式航运网络模式。支线船舶调度问题作为轴-辐式航运网络的重要组成部分受到研究者的高度关注。本文研究了可变航速和经济航速两种情境下的支线船舶调度问题,同时考虑枢纽港和喂给港的取送箱时间窗限制,以航运企业运营成本最小化为目标函数建立非线性混合整数规划模型。首先使用专业的规划求解器进行小规模算例的求解,验证了模型的准确性。同时运用改进的遗传算法对大规模支线船舶优化调度模型进行求解。为了提高求解效果,进一步设计了多智能体进化算法进行求解。数值结果表明,可变航速的运营成本低于经济航速的运营成本;在算法效率方面,改进遗传算法收敛速度较快,多智能体进化算法则可以提高求解精度。     

Alternative approaches for one-dimensional slitting problems

Dynamic programming has been used to find the optimal solution for one-dimensional slitting problems in which the value of a piece is nonlinearly dependent on both the width of the piece and the number of defects on it. In this paper, linear programming is proposed to solve this problem. Additionally, it is shown that this problem can be converted to be a shortest path problem and can be solved easily by an acyclic algorithm. Either a linear programming approach or a shortest path approach are both simpler and faster than the use of dynamic programming.     

A parametric total order on fuzzy numbers and a fuzzy shortest route problem

A parametric total order relation is introduced in the form of a certain modification of the "fuzzy max" order on the class of fuzzy numbers generated by a shape function. By the parametric relation. fuzzy numbers unordered with respect of the fuzzy max order can be ordered according either to their value of center or the size of ambiguity. A fuzzy shortest route problem in which are distances are given by fuzzy numbers is discussed under the criterion of the parametric total order, and solved by the dynamic programming approach. A method is proposed to find all of fuzzy routes mimmal in the sense of the fuzzy max order.     

A global optimization approach for solving three-dimensional open dimension rectangular packing problems

The three-dimensional open dimension rectangular packing problem (3D-ODRPP) aims to pack a set of given rectangular boxes into a large rectangular container of minimal volume. This problem is an important issue in the shipping and moving industries. All the boxes can be any rectangular stackable objects with different sizes and may be freely rotated. The 3D-ODRPP is usually formulated as a mixed-integer non-linear programming problem. Most existing packing optimization methods cannot guarantee to find a globally optimal solution or are computationally inefficient. Therefore, this paper proposes an efficient global optimization method that transforms a 3D-ODRPP as a mixed-integer linear program using fewer extra 0–1 variables and constraints compared to existing deterministic approaches. The reformulated model can be solved to obtain a global optimum. Experimental results demonstrate the computational efficiency of the proposed approach in globally solving 3D-ODRPPs drawn from the literature and the practical applications.     

Optimizing the woodpulp stowage using Lagrangean relaxation with clusters

The cargo stowage process in ships consists in arranging items into holds. This paper approaches the problem of finding the maximum number of stowed units of woodpulp into holds of dedicated maritime international ships. This problem, essentially three-dimensional, can be reduced to the two-dimensional case due to constraints provided by the transport, and becomes similar to the manufacturer's pallet loading problem. We present in this paper a formulation to the woodpulp stowage solved by a Lagrangean relaxation with clusters (LagClus) that considers the conflict graph generated by overlaps of woodpulp units. Computational tests are performed and compared with the real results obtained in Brazilian ports. The results obtained by LagClus were better than the real results, and consequently it can provide savings if we look at the shipping logistics costs.     

Constraint Programming Based Column Generation for Crew Assignment

Airline crew assignment problems are large-scale optimization problems which can be adequately solved by column generation. The subproblem is typically a so-called constrained shortest path problem and solved by dynamic programming. However, complex airline regulations arising frequently in European airlines cannot be expressed entirely in this framework and limit the use of pure column generation. In this paper, we formulate the subproblem as a constraint satisfaction problem, thus gaining high expressiveness. Each airline regulation is encoded by one or several constraints. An additional constraint which encapsulates a shortest path algorithm for generating columns with negative reduced costs is introduced. This constraint reduces the search space of the subproblem significantly. Resulting domain reductions are propagated to the other constraints which additionally reduces the search space. Numerical results based on data of a large European airline are presented and demonstrate the potential of our approach.     

A multiple period capacitated inventory model for airline fuel management: a case study

One of the major operating cost items of an airline company is fuel, which can amount to approximately 20% of its overall operating cost. This paper presents a decision support model that determines the amount of fuel to be uplifted by a plane at each station along its route over a predetermined planning horizon so as to minimise overall fuel costs. The aforementioned fuel management problem is modelled as a multiple period capacitated inventory problem and solved using linear programming. An example application illustrates the applicability of this model to Middle East Airline's (MEA) operations and summarises the dollar savings obtained by applying it over a one week planning horizon.     

Shortest Paths with Shortest Detours

This paper is concerned with a biobjective routing problem, called the shortest path with shortest detour problem, in which the length of a route is minimized as one criterion and, as second, the maximal length of a detour route if the chosen route is blocked is minimized. Furthermore, the relation to robust optimization is pointed out, and we present a new polynomial time algorithm, which computes a minimal complete set of efficient paths for the shortest path with shortest detour problem. Moreover, we show that the number of nondominated points is bounded by the number of arcs in the graph.     

Impact analysis of maritime cabotage legislations on liner hub-and-spoke shipping network design

Maritime cabotage is a legislation published by a particular coastal country, which is used to conduct the cargo transportation between its two domestic ports. This paper proposes a two-phase mathematical programming model to formulate the liner hub-and-spoke shipping network design problem subject to the maritime cabotage legislations, i.e., the hub location and feeder allocation problem for phase I and the ship route design with ship fleet deployment problem for phase II. The problem in phase I is formulated as a mixed-integer linear programming model. By developing a hub port expanding technique, the problem in phase II is formulated as a vehicle routing problem with pickup and delivery. A Lagrangian relaxation based solution method is proposed to solve it. Numerical implementations based on the Asia–Europe–Oceania shipping services are carried out to account for the impact analysis of the maritime cabotage legislations on liner hub-and-spoke shipping network design problem.     

Computationally Efficient Solution of a Multiproduct,Two-Stage Distribution—Location Problem

A two-stage distribution planning problem, in which customers are to be served with different commodities from a number of plants, through a number of intermediate warehouses is addressed. The possible locations for the warehouses are given. For each location, there is an associated fixed cost for opening the warehouse concerned, as well as an operating cost and a maximum capacity. The demand of each customer for each commodity is known, as are the shipping costs from a plant to a possible warehouse and thereafter to a customer. It is required to choose the locations for opening warehouses and to find the shipping schedule such that the total cost is minimized. The problem is modelled as a mixed-integer programming problem and solved by branch and bound. The lower bounds are calculated through solving a minimum-cost, multicommodity network flow problem with capacity constraints. Results of extensive computational experiments are given.     

Shortest path in the presence of obstacles: An application to ocean shipping

This paper presents the problem of determining the estimated time of arrival (ETA) at the destination port for a ship located at sea. This problem is formulated as a shortest path problem with obstacles, where the obstacles are modelled by polygons representing the coastlines. An efficient solution algorithm is proposed to solve the problem. Instead of generating a complete visibility graph and solving the problem as an ordinary shortest path problem, the algorithm constructs arcs to the ship node during the solution process only when needed. This greatly enhances the algorithmic performance. Computational results based on test problems from an actual dry-bulk shipping operation are provided. The proposed algorithm is implemented in a decision support system for the planning of ship operations and it has successfully been applied on several real life problems.     

Vehicle routing with stochastic demands and restricted failures

This paper considers a class of stochastic vehicle routing problems (SVRPs) with random demands, in which the number of potential failures per route is restricted either by the data or the problem constraints. These are realistic cases as it makes little sense to plan vehicle routes that systematically fail a large number of times. First, a chance constrained version of the problem is considered which can be solved to optimality by algorithms similar to those developed for the deterministic vehicle routing problem (VRP). Three classes of SVRP with recourse are then analyzed. In all cases, route failures can only occur at one of the lastk customers of the planned route. Since in general, SVRPs are considerably more intractable than the deterministic VRPs, it is interesting to note that these realistic stochastic problems can be solved as a sequence of deterministic traveling salesman problems (TSPs). In particular, whenk=1 the SVRP with recourse reduces to a single TSP.     

Routing,ship size,and sailing frequency decision-making for a maritime hub-and-spoke container network

This study formulates a two-objective model to determine the optimal liner routing, ship size, and sailing frequency for container carriers by minimizing shipping costs and inventory costs. First, shipping and inventory cost functions are formulated using an analytical method. Then, based on a trade-off between shipping costs and inventory costs, Pareto optimal solutions of the two-objective model are determined. Not only can the optimal ship size and sailing frequency be determined for any route, but also the routing decision on whether to route containers through a hub or directly to their destination can be made in objective value space. Finally, the theoretical findings are applied to a case study, with highly reasonable results. The results show that the optimal routing, ship size, and sailing frequency with respect to each level of inventory costs and shipping costs can be determined using the proposed model. The optimal routing decision tends to be shipping the cargo through a hub as the hub charge is decreased or its efficiency improved. In addition, the proposed model not only provides a tool to analyze the trade-off between shipping costs and inventory costs, but it also provides flexibility on the decision-making for container carriers.     

Strong planning and forecast horizons for a model with simultaneous price and production decisions

In this paper, we have solved a general inventory model with simultaneous price and production decisions. Both linear and non-linear (strictly convex) production cost cases are treated. Upper and lower bounds are imposed on state as well as control variables. The problem is solved by using the Lagrangian form of the maximum principle. Strong planning and strong forecast horizons are obtained. These arise when the state variable reaches its upper or lower bound. The existence of these horizons permits the decomposition of the whole problem into a set of smaller problems, which can be solved separately, and their solutions put together to form a complete solution to the problem. Finally, we derive a forward branch and bound algorithm to solve the problem. The algorithm is illustrated with a simple example.     

一种基于Dijkstra算法的机器人避障问题路径规划

移动机器人的避障问题是移动机器人控制领域的研究热点.针对给定的移动机器人避障问题,探讨了最短路径及最短时间路径的路径规划问题.对于最短路径问题,建立了简化的路径网格模型,将其抽象为由节点及边构成的两维图,再使用经典的Dijkstra算法获得可行的最短路径.对于最短时间路径问题,通过分析移动机器人弯道运行的速度曲线,基于几何方法得出了移动时间与过渡圆弧圆心之间严格的数学关系,此后借助MATLAB优化函数获得最佳的移动路径.算法可为类似机器人避障问题的解决提供借鉴.