Search

Many seaports worldwide are equipped with one-way navigation channel, in which only one direction is allowed to sail through at a time and vessels thus have to queue up to enter and leave the port alternately. This paper proposes a mixed-integer linear programming (MILP) model for integrated planning of berth allocation and vessel sequencing in such a one-way navigation channel seaport, aiming to minimize weighted dwelling time of all vessels. A tailored adaptive large neighborhood search algorithm is developed for solving the model within a reasonable time. To evaluate the solution quality, a lower bound of the solution of the problem is given by a column generation algorithm that solves a set-partitioning model adapted from the MILP model. Numerical experiments on Jingtang port of China show that (i) the integrated planning model can reduce 20.90%-29.21% of the weighted dwelling time of vessels compared to the current port scheduling schemes; and (ii) the proposed adaptive large neighborhood search algorithm outperforms the GUROBI solver and some existing methods, solving all problem instances within 3 minutes with a 4.83% average optimality gap. Some managerial insights are offered to guide the port operations in a one-way navigation channel seaport.

Green scheduling is an important means to achieve sustainable industrial development and enhance the green efficiency of enterprises. Given the characteristics of a modern crude oil supply system, the shuttle tanker fleet green scheduling problem (FGSP) is discussed considering a carbon tax and variable tanker speed factor. To minimize the green operating cost (i.e., sum of general operating cost and carbon tax) of the tanker fleet, an integer programming model for shuttle tanker fleet green scheduling (FGSM) is established. The FGSM optimizes the number and sizes of tankers, the number and positions of floating production storage and offloading units (FPSO) at which to berth and the scheduling plan (i.e., berthing order and sailing speed) of each tanker in the fleet. Based on the column generation algorithm, a shuttle tanker fleet green scheduling algorithm is designed to solve the above model accurately. The experimental results show that considering the speed factor, the green operating cost of an example fleet decreases. For different carbon tax rates, speed optimization is an effective way to reduce the green operating cost of the fleet. The above results also show that the FGSM and algorithm can effectively solve the FGSP, improve the operation level and efficiency, and reduce the green operating cost of oil companies.

This paper studies limited-stop operations for rail transit systems and presents an optimization model, which aims to minimize passengers’ travel times and on-board crowdedness. The model combines the design of service itinerary for each vehicle and the allocation of vehicles of various types among multiple lines. Three methods are proposed including a mixed-integer program and two column generation algorithms. Numerical results on generic scenarios show that the column generation algorithm can provide sub-optimal solutions and is computationally efficient. In a case study on Melbourne’s railway network, its solution significantly improves in the passenger travel time compared to the current practice.

This paper presents the congested location-pricing problem under customers’ choice behavior. In the choice-based congested location-pricing problem (CCLPP), the appropriate facilities are selected for offering service by deciding about their fare classes during consecutive time periods. The customer choosing behavior is captured by the discrete choice models. The dominant factors in the customers' decision are proximity and service fare classes offered by the facilities. In the congested systems with immobile facilities, customer waiting time for getting service is important and the M / M / 1 / k queuing system is used for capturing facilities queue in this paper. Customers can choose the competitors for getting service according to the no-service utility. The obtained mathematical model for solving this problem is a nonlinear mixed integer model which is extremely hard to solve and therefore, the alternative modeling approach is developed for solving the problem by the column generation algorithm. The subproblem in this approach determines configurations including open facilities and their fare classes and the master problem specifies the number of time periods for offering each configuration. We also develop a hybrid heuristic including greedy and metaheuristic algorithms for solving the subproblem. The numerical experiments and sensitivity analysis are carried out for demonstrating the efficiency of the proposed algorithm. This analysis indicates that the total profit is the most sensitive to the offering fare classes and available resources.

In the context of large-scale linear programs solved by a column generation algorithm, we present a primal algorithm for handling the master problem. Successive approximations of the latter are created to converge to optimality. The main properties are that, for every approximation except the last one, the cost of the solution decreases whereas the sum of the variable values increases. Moreover, the minimum reduced cost of the variables also increases and converges to zero with a super-geometric growth rate.

Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100–150 vehicles and 400 requests in about 10s to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within 10s. One way out are simplified reoptimization models. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new models ShadowPrice and ZIBDIPdummy can keep up with ZIBDIP.

An exact column generation algorithm for integer programs with a large (implicit) number of columns is presented. The family of problems that can be treated includes not only standard partitioning problems such as bin packing and certain vehicle routing problems in which the columns generated have 0 - 1 components and a right hand side vector of 1 's, but also the cutting stock problem in which the columns and right hand side are nonnegative integer vectors. We develop a combined branching and subproblem modification scheme that generalizes existing approaches, and also describe the use of lower bounds to reduce tailing-off effects.

When a dual-based procedure is used to solve a geometric programming problem, the presence of inactive constraints at the primal optimum reduces the amount of information available about the relationship between the optimal primal and dual vectors. In certain situations one must resort to solving one or more subsidiary problems to recover solution from the dual optimum. This paper reviews such situations and presents an alternative formulation of the dual as a generalized linear program, along with a column generation algorithm based on the same. The algorithm avoids subsidiary problems, and the formulation provides more information than the traditional dual when recovering the primal optimum.