Search

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.

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.

Multi-microgrid (MMG) system is a new method that concurrently incorporates different types of distributed energy resources, energy storage systems and demand responses to provide reliable and independent electricity for the community. However, MMG system faces the problems of management, real-time economic operations and controls. Therefore, this study proposes an energy management system (EMS) that turns an infinite number of MMGs into a coherence and efficient system, where each MMG can achieve its goals and perspectives. The proposed EMS employs a cooperative game to achieve efficient coordination and operations of the MMG system and also ensures a fair energy cost allocation among members in the coalition. This study considers the energy cost allocation problem when the number of members in the coalition grows exponentially. The energy cost allocation problem is solved using a column generation algorithm. The proposed model includes energy storage systems, demand loads, real-time electricity prices and renewable energy. The estimate of the daily operating cost of the MMG using a proposed deep convolutional neural network (CNN) is analyzed in this study. An optimal scheduling policy to optimize the total daily operating cost of MMG is also proposed. Besides, other existing optimal scheduling policies, such as approximate dynamic programming (ADP), model prediction control (MPC), and greedy policy are considered for the comparison. To evaluate the effectiveness of the proposed model, the real-time electricity prices of the electric reliability council of Texas are used. Simulation results show that each MMG can achieve energy cost savings through a coalition of MMG. Moreover, the proposed optimal policy method achieves MG's daily operating cost reduction up to 87.86% as compared to 79.52% for the MPC method, 73.94% for the greedy policy method and 79.42% for ADP method.

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.

This study concerns the use of automatic classification techniques for the purpose of self-tuning an exact optimization algorithm: in particular, the purpose is to automatically select the critical resource in a dynamic programming pricing algorithm within a branch-and-cut-and-price algorithm for the Electric Vehicle Routing Problem.

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.

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.

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.

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

This article addresses three problems that arise in coverage scheduling for wireless sensor networks subject to bandwidth constraints. The first problem focuses on minimizing the total breach under a lifetime constraint, where a breach occurs when some targets are not covered by active sensors. The second problem aims at maximizing the network lifetime under a breach constraint. Finally, the problem of computing the possible trade-offs between breach and lifetime offered by the sensor network is also addressed. An exact approach based on a column generation algorithm is proposed for solving these problems, and a heuristic is also derived from it and briefly presented. The use of a genetic algorithm within the column generation scheme appears to significantly decrease computation time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012 © 2012 Wiley Periodicals, Inc.

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.

This paper addresses one of the key operational decision problems in the steel industry which is related to the allocation of orders to stock materials in the surplus inventory. The meta slab allocation problem can be stated as the ‘multi-stage multiple knapsack problem’ where the problem is to design slabs using orders with similar properties (the first stage) and allocating these designed slabs into the existing meta slabs in the inventory yard (the second stage). The objective of the problem is to maximise the allocated order weights in slabs and meta slabs. For the given problem, we propose a column generation algorithm, where a column in the master problem represents meta slabs and the sub problem is to design ‘bins’, here slabs with the given orders. The sub problem itself also becomes a multiple knapsack problem and we proposed a practical set-partitioning heuristic. The proposed algorithm was tested with daily operation data given from an integrated steel company in the Asia Pacific. The computati...

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

We propose a new algorithm for the stochastic unit commitment problem which is based on the Lagrangian relaxation and the column generation approach. This problem is formulated as a multi-stage non...

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.

In this paper we introduce a length constrained user equilibrium model. In our model, people consider two criteria, path time and path length, when selecting their routes. They only travel on "acceptable paths", the paths whose length are not too long for them. Each user will try to minimize his own path time when he seeking which "acceptable path" to travel. It is shown that this problem can be stated as a convex optimization model, and a column generation algorithm is proposed for its solution. The applications of our model in congestion pricing is also discussed in this paper.

We develop a set-covering type formulation for a crew planning problem that determines the minimum sufficient crew size for a region over a finite planning horizon where the periodic repeatability of crew schedules is considered as well. The resulting problem formulation cannot be solved with a traditional column generation algorithm. We propose a column-and-row generation algorithm and present preliminary computational results.

In this paper we present a novel column generation (CG) formulation and a branch-and-price (BP) algorithm for the Vehicle Routing Problem with Cross-Docking (VRPCD). Our BP algorithm is compared with a previous algorithm to solve the VRPCD and the computational results show that our approach dominates the other in terms of the quality of lower and upper bounds and also can evaluate optimal solutions faster.

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.

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.