Search

The crew-pairing problem (CPP) is solved in the first step of the crew-scheduling process. It consists of creating a set of pairings (sequence of flights, connections, and rests forming one or multiple days of work for an anonymous crew member) that covers a given set of flights at minimum cost. Those pairings are assigned to crew members in a subsequent crew-rostering step. In this paper, we propose a new integral column-generation algorithm for the CPP, called improved integral column generation with prediction ([Formula: see text]), which leaps from one integer solution to another until a near-optimal solution is found. Our algorithm improves on previous integral column-generation algorithms by introducing a set of reduced subproblems. Those subproblems only contain flight connections that have a high probability of being selected in a near-optimal solution and are, therefore, solved faster. We predict flight-connection probabilities using a deep neural network trained in a supervised framework. We test [Formula: see text] on several real-life instances and show that it outperforms a state-of-the-art integral column-generation algorithm as well as a branch-and-price heuristic commonly used in commercial airline planning software, in terms of both solution costs and computing times. We highlight the contributions of the neural network to [Formula: see text].

In this paper, we investigate the resource-constrained order acceptance and scheduling on unrelated parallel machines that arise in make-to-order systems. The objective of this problem is to simultaneously select a subset of orders to be processed and schedule the accepted orders on unrelated machines in such a way that the resources are not overutilized at any time. We first propose two formulations for the problem: mixed integer linear programming formulation and set partitioning. In view of the complexity of the problem, we then develop a column generation approach based on the set partitioning formulation. In the proposed column generation approach, a differential evolution algorithm is designed to solve subproblems efficiently. Extensive numerical experiments on different-sized instances are conducted, and the results demonstrate that the proposed column generation algorithm reports optimal or near-optimal solutions that are evidently better than the solutions obtained by solving the mixed integer linear programming formulation.

The sustained and stable growth of China’s market economy promotes the continuous improvement of transportation demand and puts forward higher requirements for transportation products. At present, as a new product, high-speed rail freight has played an important role in cold chain logistics and high-value-added transportation, which is of great significance to effectively reduce the pollution caused by road transportation and further promote the sustainable development of economy and logistics industry. In the previous study, we studied the organization optimization method of high-speed rail freight train operation scheme and the compilation method of high-speed rail freight train diagram based on the overall demand of freight transportation but did not consider the influence of different high-speed rail freight transportation products on the organization scheme. Therefore, in order to ensure the sustainable development of high-speed rail freight business, based on the demand of high-speed freight products (the freight product for short in the following text), this paper focuses on the optimization method of high-speed rail freight train organization scheme considering different demands. A two-stage freight demand analysis method considering customers’ choice intention and actual supply capacity was designed, comprehensively considering the relationship between operation cost and income, and a model based on different products in order to meet the needs of large-scale case solving was established. In addition, a column generation algorithm was designed. The computational results are encouraging and demonstrate the effectiveness of the model and solution method.

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 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.

Summary Bus driver scheduling aims to find the minimum number of bus drivers to cover a published timetable of a bus company. When scheduling bus drivers, contractual working rules must be enforced, thus complicating the problem. In this research, we develop a column generation algorithm that decomposes this complicated problem into a master problem and a series of pricing subproblems. The master problem selects optimal duties from a set of known feasible duties, and the pricing subproblem augments the feasible duty set to improve the solution obtained in the master problem. The proposed algorithm is empirically applied to the realistic problems of several bus companies. The numerical results show that the proposed column generation algorithm can solve real-world problems and obtain bus driver schedules that are better than those developed and used by the bus companies. Copyright © 2016 John Wiley & Sons, Ltd.

There is a trade-off between the total penalty paid to customers (TPC) and the total transportation cost (TTC) in depot for vehicle routing problems under uncertainty (VRPU). The trade-off refers to the fact that the TTC in depot inevitably increases when the TPC decreases andvice versa. With respect to this issue, the vehicle routing problem (VRP) with uncertain customer demand and travel time was studied to optimise the TPC and the TTC in depot. In addition, an inverse robust optimisation approach was proposed to solve this kind of VRPU by combining the ideas of inverse optimisation and robust optimisation so as to improve both the TPC and the TTC in depot. The method aimed to improve the corresponding TTC of the robust optimisation solution under the minimum TPC through minimising the adjustment of benchmark road transportation cost. According to the characteristics of the inverse robust optimisation model, a genetic algorithm (GA) and column generation algorithm are combined to solve the problem. Moreover, 39 test problems are solved by using an inverse robust optimisation approach: the results show that both the TPC and TTC obtained by using the inverse robust optimisation approach are less than those calculated using a robust optimisation approach.

The sustained and steady development of China&rsquo, s economy has led to the rapid improvement of the logistics. At the same time, the rise of the e-commerce mode has given rise to a huge demand for express delivery and the express industry has entered a period of boom. Fortunately, China&rsquo, s high-speed rail network has been networked, and the development of a high-speed rail express train has entered the test stage. After the high-speed rail express train is put into use, it could effectively relieve the pressure of highway transportation and significantly reduce transport pollution. To make better use of high-speed rail transport resources and give full play to its green and efficient advantages, this study established a two-stage model of a high-speed rail express train operation plan. In the first stage, a train candidate set generation model aiming for the minimum total cost of train operation was established that considered the high-speed line carrying capacity, section flow capacity, and OD requirement satisfaction constraints, which reduces the scale of train spare parts and improves the efficiency of solution. In addition, a column generation algorithm was designed to solve the model. In the second stage, an accurate flow distribution model aiming for the optimal economic efficiency was established, and then the high-speed express train operation plan was designed completely. The computational results are encouraging and demonstrate the effectiveness of the model and solution method.

This paper aims to optimize high-speed railroad timetables for a corridor. We propose an integer programming model using a time-space network-based approach to consider passenger service demands, train scheduling, and station service demands simultaneously. A modified branch-and-price algorithm is used for the computation. This algorithm solves the linear relaxation of all nodes in a branch-and-bound tree using a column generation algorithm to derive a lower-bound value (LB) and derive an upper-bound value (UB) using a rapid branching strategy. The optimal solution is derived by iteratively updating the upper- and lower-bound values. Three acceleration strategies, namely, initial solution iteration, delayed constraints, and column removal, were designed to accelerate the computation. The effectiveness and efficiency of the proposed model and algorithm were tested using Wuhan-Guangzhou high-speed railroad data. The results show that the proposed model and algorithm can quickly reduce the defined cost function by 38.2% and improve the average travel speed by 10.7 km/h, which indicates that our proposed model and algorithm can effectively improve the quality of a constructed train timetable and the travel efficiency for passengers.

Large-scale evacuations require authorities to decide and stage evacuation routes, mobilize resources, and issue evacuation orders under strict time constraints. These decisions must consider both the capacity of the road network and the evolution of the threat (e.g., a bushfire or a flood). This paper proposes, for the first time, an optimization model that jointly optimizes the mobilization and evacuation planning, taking into account the behavioral response of evacuees and the allocation of resources for communicating and implementing evacuation orders. From a technical standpoint, the model is solved by a column generation algorithm that jointly decides the evacuation route, evacuation time, and the resource allocation for each evacuated area in order to maximize the number of evacuees reaching safety and minimize the total duration of the evacuation.

We present a tactical wood flow model that appears in the context of the Canadian forestry industry, and describe the implementation of a decision support system created for use by an industrial partner. In this problem, mill demands and harvested volumes of a heterogeneous set of log types are given over a multi-period planning horizon. Wood can be stored at the forest roadside before delivery at a financial cost. Rather than solve this as a network linear programme on the basis of out-and-back deliveries, we choose to model this problem as a generalization of a log-truck scheduling problem. By routing and scheduling the trucks in the resolution, this allows us to both anticipate potential backhaul opportunities for cost and fuel savings, and also minimize queuing times at log-loaders, management of which is a major concern in the industry. We model this problem as a mixed integer linear programme and solve it via column generation. The methodology is tested on several case studies.

The planning of outbound baggage handling at international airports is challenging. Outgoing flights have to be assigned and scheduled to handling facilities at which the outgoing baggage is loaded into containers. To avoid disruptions of the system the objective is to minimize workload peaks over the entire system. The resource demand of the jobs that have to be scheduled depends on the arrival process of the baggage. In this paper we present a time-indexed mathematical programming formulation for planning the outbound baggage. We propose an innovative decomposition procedure in combination with a column generation scheme to solve practical problem instances. The decomposition significantly reduces the symmetry effect in the time-indexed formulation and also speeds up the computational time of the corresponding Dantzig–Wolfe formulation. To further improve our column generation algorithm we propose state-of-the-art acceleration techniques for the primal problem and the pricing problem. Computational results based on real data from a major European airport show that the proposed procedure reduces the maximal workloads by more than 60% compared to the current assignment procedure used. The online appendix is available at https://doi.org/10.1287/trsc.2017.0739 .

The biggest challenge when disclosing private data is to share information contained in databases while protecting people from being individually identified. Microaggregation is a family of methods for statistical disclosure control. The principle of microaggregation is that confidentiality rules permit the publication of individual records if they are partitioned into groups of size larger or equal to a fixed threshold value, where none is more representative than the others in the same group. The application of such rules leads to replacing individual values by those computed from small groups (microaggregates), before data publication. This work proposes a column generation algorithm for numerical microaggregation in which its pricing problem is solved by a specialized branch-and-bound. The algorithm is able to find, for the first time, lower bounds for instances of three real-world datasets commonly used in the literature. Furthermore, new best known solutions are obtained for these instances by means of a simple heuristic method with the columns generated.

The exact solution and heuristic solution have their own strengths and weaknesses on solving the Vehicle Routing Problems with Time Windows (VRPTW). This paper proposes a hybrid Column Generation Algorithm with Metaheuristic Optimization (CGAMO) to overcome their weaknesses. Firstly, a Modified Labelling Algorithm (MLA) in the sub-problem of path searching is analysed. And a search strategy in CGAMO based on the demand of sub-problem is proposed to improve the searching efficiency. While putting the paths found in the sub-problem into the main problems of CGAMO, the iterations may fall into endless loops. To avoid this problem and keep the main problems in a reasonable size, two conditions on saving the old paths in the main problem are used. These conditions enlarge the number of constraints considered in the iterations to strengthen the limits of dual variables. Through analysing the sub-problem, we can find many useless paths that have no effect on the objective function. Secondly, in order to reduce the number of useless paths and improve the efficiency, this paper proposes a heuristic optimization strategy of CGAMO for dual variables. It is supposed to accelerate the solving speed from the view of on the dual problem. Finally, extensive experiments show that CGAMO achieves a better performance than other state-of-the-art methods on solving VRPTW. The comparative experiments also present the parameters sensitivity analysis, including the different effects of MLA in the different path selection strategies, the characteristics and the applicable scopes of the two pathkeeping conditions in the main problem. First published online:25 Oct 2013

We present a new column generation algorithm for the determination of a classifier in the two classes LAD (Logical Analysis of Data) model. Unlike existing algorithms who seek a classifier that at the same time maximizes the margin of correctly classified observations and minimizes the amount of violations of incorrectly classified observations, we fix the margin to a difficult-to-achieve target and minimize a piecewise convex linear function of the violation of incorrectly classified observations. Moreover a part of the training set, called control set, is reserved to select, among all feasible classifiers found by the algorithm, the one with highest performance on that set. One advantage of the proposed algorithm is that it essentially does not require any calibration. Computational results are presented that show the effectiveness of this approach.

In this paper, we study a warehouse-retailer network design (WRND) model that simultaneously makes the location, distribution, and warehouse-retailer echelon inventory replenishment decisions. Although a column generation algorithm was proposed recently in the literature, it remains a challenge to solve large size instances of this NP-hard problem efficiently and effectively. The purpose of this paper is to present a greedy algorithm. Computational results demonstrate that our greedy algorithm can solve large-scale WRND problems efficiently with errors within 3%–4% on average.

We survey the main results obtained by the author in his PhD dissertation supervised by Anass Nagih and Lucas Letocart. It was defended in December 2008 at The Computer Science lab of the Paris-Nord University (L.I.P.N.), Villetaneuse, France. The thesis is written in French and is available from http://www-lipn.univ-paris13.fr/~touati/TM_Thesis.pdf. Column generation algorithms are instrumental in many areas of applied optimization, where linear programs with an enormous number of variables need to be solved. Although successfully used in many applications, this method suffers from well-known “instability” issues that somewhat limit its efficiency. This work focuses on accelerating strategies in a column generation scheme; on the first iterations using diversification, on the last iterations using reoptimization and on the overall GC scheme using an improving technique to solve the pricing problems (dynamic programming with blocs). The effectiveness of these approaches is validated on the Vehicle Routing Problem with Time Windows.

Made available in DSpace on 2022-04-28T20:55:12Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-01-01 This article presents a column generation algorithm to calculate new improved lower bounds to the solution of maximal covering location problems formulated as a p-median problem. This reformulation leads to instances that are difficult for column generation methods. The traditional column generation method is compared with the new approach, where the reduced cost criterion used at the column selection is modified by a Lagrangean/surrogate multiplier. The efficiency of the new approach is tested with real data, where computational tests were conducted and showed the impact of sparsity and degeneracy on column generation-based methods. © 2017 Wiley. All rights reserved. FEG/UNESP Department of Mathematics São Paulo State University Engineering College, Guaratinguetá, SP, 12516-410 LAC/INPE Associate Laboratory of Applied Mathematics and Computation Brazilian Institute for Space Research, São José dos Campos, SP, 12201-970 FEG/UNESP Department of Mathematics São Paulo State University Engineering College, Guaratinguetá, SP, 12516-410

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.

Flight disruptions disturb airlines’ routine, causing a lot of troubles to passengers as well as bringing on huge economic losses to airlines. So the irregular flight recovery is made to solve this problem. Irregular flight recovery is a large-scale and integer programming problem, which has complex variables and constraints. In this research, we model in terms of real situation and a column generation algorithm combined with Bellman-Ford algorithm is presented to release the influences resulted from disruptions. Computational experiments show that the proposed algorithm is feasible. Keywords-flight disruptions; airlines;column generation; network optimation

Aircraft dynamic scheduling made a rational organization of surplus aircrafts to generate the optimized aircraft dispatch solution. The approach improved the operation efficiency and aviation enterprise benefits. To describe the complex relationship in aircraft dispatch, according to the characteristics of the airlines operation network, the research constructed an aircraft dynamic time-space network diagram, defined the surplus aircrafts’ routing and constructed corresponding mathematical model. The proposed method found the routings set with heuristic methods in the column generation algorithm sub-problem process. Finally, the given example illustrated the method generate reasonable and practical aircraft solution for airlines in the effective time.

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.

El algoritmo de generación de columnas (GC) se cita usualmente como alternativa para la solución de problemas de optimización de gran escala; este artículo aborda la presentación de dicho algoritmo en el contexto de la asignación de cupos escolares en el sistema de educación pública del distrito de Bogotá. Se discuten algunas de las falencias evidenciadas en la puesta en práctica del algoritmo, presentando estrategias para enfrentarlas. Se ilustra además, la forma como la generación de columnas se acopla dentro del algoritmo Branch and Price para dar solución a problemas de mayor complejidad. The Column Generation Algorithm (CGA) is commonly cited in the bibliography as alternative to solve large scale optimization problems. This article deals with the description of the GC algorithm in the context of the student assignation to the public schools. kSome of the weaknesses and shortcomings encountered in the implementation and application to a real problem are discussed and some strategies to sort it out are presented. This workpointed out how the CGA could be used within a general Branch and Price procedure to solve problems with additional constrains.

This article is about adaptive column generation techniques for the solution of duty scheduling problems in public transit. The current optimization status is exploited in an adaptive approach to guide the subroutines for duty generation, LP resolution, and schedule construction toward relevant parts of a large problem. Computational results for three European scenarios are reported.

In a previous paper, Appelgren (Appelgren, L. 1969. A column generation algorithm for a ship scheduling problem. Trans. Sci. 3 53–68.), a decomposition algorithm for a class of vessel scheduling problems was presented. In some problems, the algorithm gives fractional solutions that cannot be interpreted as feasible schedules. This paper treats two integer programming methods that can be used to resolve these cases. The cutting plane method that was first tested was abandoned because it was not able to solve all the test problems. The second method is a branch-and-bound algorithm, where the branching is performed on one of the “essential” fractional variables and where the bounds are obtained by the decomposition algorithm. All fractional problems that have been found by simulation or in regular use of the algorithm have been solved, mostly with one branching only. There are fundamental difficulties in combining these integer programming methods with the Dantzig-Wolfe decomposition, since the constraints generated in the master program have to be taken into account in the solution of the subprograms. The success in this case is due to the simple structure of the master LP problem.

A column generation algorithm for solving a class of nonlinear traffic assignment problems is presented. The fundamental advantage of the algorithm is that it does not require the a priori generation of all paths joining each origin-destination pair. The algorithm is capable of handling rather large networks. Computational experience that contrasts column generation with the a priori generation of all paths and compares two different quadratic programming algorithms is reported.

An algorithm using column generation and penalty function techniques is presented. A linear program with a uniformly bounded number of columns, similar to the restricted master in generalized programming, is used to reduce the number of constraints included in forming a penalty function. The penalty function is used as a Lagrangian in an unconstrained subproblem.