Fleet assignment and routing with schedule synchronization constraints

This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing problems and it proposes an optimal solution approach. This approach is based on Dantzig–Wolfe decomposition/column generation. The resulting master problem consists of flight covering constraints, as in usual applications, and of schedule synchronization constraints. The corresponding subproblem is a shortest path problem with time windows and linear costs on the time variables and it is solved by an optimal dynamic programming algorithm. This column generation procedure is embedded into a branch and bound scheme to obtain integer solutions. A dedicated branching scheme was devised in this paper where the branching decisions are imposed on the time variables. Computational experiments were conducted using weekly fleet routing and scheduling problem data coming from an European airline. The test problems are solved to optimality. A detailed result analysis highlights the advantages of this approach: an extremely short subproblem solution time and, after several improvements, a very efficient master problem solution time.     

A penalty function heuristic for the resource constrained shortest path problem

The resource constrained shortest path problem (RCSP) consists of finding the shortest path between two nodes of an assigned network, with the constraint that traversing an arc of the network implies the consumption of certain limited resources. In this paper we propose a new heuristic for the solution of the RCSP problem in medium and large scale networks. It is based on the extension to the discrete case of the penalty function heuristic approach for the fast ε-approximate solution of difficult large-scale continuous linear programming problems. Computational experience on test instances has shown that the proposed penalty function heuristic (PFH) is very effective in the solution of medium and large scale RCSP instances. For all the tests reported it provides very good upper bounds (in many cases the optimal solution) in less than 26 iterations, where each iteration requires only the computation of a shortest path.     

Analysis of relaxations for the multi-item capacitated lot-sizing problem

The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. We show that the problem is strongly NP-hard. To explain why one of the most popular among exact and approximate solution methods uses a Lagrangian relaxation of the capacity constraints, we compare this approach with every alternate relaxation of the classical formulation of the problem, to show that it is the most precise in a rigorous sense. The linear relaxation of a shortest path formulation of the same problem has the same value, and one of its Lagrangian relaxations is even more accurate. It is comforting to note that well-known relaxation algorithms based on the traditional formulation can be directly used to solve the shortest path formulation efficiently, and can be further enhanced by new algorithms for the uncapacitated lot-sizing problem. An extensive computational comparison between linear programming, column generation and subgradient optimization exhibits this efficiency, with a surprisingly good performance of column generation. We pinpoint the importance of the data characteristics for an empirical classification of problem difficulty and show that most real-world problems are easier to solve than their randomly generated counterparts because of the presence of initial inventories and their large number of items.Supported by NSF Grant ECS-8518970 and NSERC Grant OGP 0042197.     

Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach

We study a vehicle routing problem with soft time windows and stochastic travel times. In this problem, we consider stochastic travel times to obtain routes which are both efficient and reliable. In our problem setting, soft time windows allow early and late servicing at customers by incurring some penalty costs. The objective is to minimize the sum of transportation costs and service costs. Transportation costs result from three elements which are the total distance traveled, the number of vehicles used and the total expected overtime of the drivers. Service costs are incurred for early and late arrivals; these correspond to time-window violations at the customers. We apply a column generation procedure to solve this problem. The master problem can be modeled as a classical set partitioning problem. The pricing subproblem, for each vehicle, corresponds to an elementary shortest path problem with resource constraints. To generate an integer solution, we embed our column generation procedure within a branch-and-price method. Computational results obtained by experimenting with well-known problem instances are reported.     

A column generation approach for location-routing problems with pickup and delivery

In this paper we formulate an integer programming model for the Location and Routing Problem with Pickup and Delivery. We propose a column generation scheme and implement, for the subproblem, a label-setting algorithm for the shortest path with pickup and delivery and time windows problem. We also propose a set of heuristics to speed up this process. To validate the model, we implement the column generation scheme and test it on different instances developed in this paper. We also provide an analysis of how the costs of opening depots and the fixed cost of routes affect the optimal solution.     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

Arc routing problems with time-dependent service costs

This paper studies an arc routing problem with capacity constraints and time-dependent service costs. This problem is motivated by winter gritting applications where the “timing” of each intervention is crucial. The exact problem-solving approach reported here first transforms the arc routing problem into an equivalent node routing problem. Then, a column generation scheme is used to solve the latter. The master problem is a classical set covering problem, while the subproblems are time-dependent shortest path problems with resource constraints. These subproblems are solved using an extension of a previously developed algorithm. Computational results are reported on problems derived from a set of classical instances of the vehicle routing problem with time windows.     

The shortest path problem with forbidden paths

We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.     

A generalized linear programming model for nurse scheduling

This paper presents a 0–1 column generation model with a resource constrained shortest path auxiliary problem for nurse scheduling. The master problem finds a configuration of individual schedules to satisfy the demand coverage constraints while minimizing salary costs and maximizing both employee preferences and team balance. A feasible solution of the auxiliary problem is an acceptable schedule for a given nurse, with respect to collective agreement requirements such as seniority, workload, rotations and days off. We define a new resource structure in the auxiliary problem in order to take into account the complex collective agreement rules specific to the nurse scheduling problem. This model generalizes further the previous formulations discussed in the literature and can be viewed as a general scheme for complex personnel scheduling problems, especially in the context of organizations which operate around the clock. Solution methods and preliminary test results are discussed.     

An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles

The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows.     

A column generation method for inverse shortest path problems

In this paper we formulate an inverse shortest path problem as a special linear programming problem. A column generation scheme is developed that is able to keep most columns of the LP model implicit and to generate necessary columns by shortest path algorithms. This method can get an optimal solution in finitely many steps. Some numerical results are reported to show that the algorithm has a good performance.The authors gratefully acknowledge the partial support of Croucher Foundation.     

A branch-and-price algorithm for a vehicle routing with demand allocation problem

We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.     

Dynamic graph generation for the shortest path problem in time expanded networks

In discrete optimization problems the progress of objects over time is frequently modeled by shortest path problems in time expanded networks, but longer time spans or finer time discretizations quickly lead to problem sizes that are intractable in practice. In convex relaxations the arising shortest paths often lie in a narrow corridor inside these networks. Motivated by this observation, we develop a general dynamic graph generation framework in order to control the networks’ sizes even for infinite time horizons. It can be applied whenever objects need to be routed through a traffic or production network with coupling capacity constraints and with a preference for early paths. Without sacrificing any information compared to the full model, it includes a few additional time steps on top of the latest arcs currently in use. This “frontier” of the graphs can be extended automatically as required by solution processes such as column generation or Lagrangian relaxation. The corresponding algorithm is efficiently implementable and linear in the arcs of the non-time-expanded network with a factor depending on the basic time offsets of these arcs. We give some bounds on the required additional size in important special cases and illustrate the benefits of this technique on real world instances of a large scale train timetabling problem.     

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.     

Shortest path problem with forbidden paths: The elementary version

This paper addresses the elementary shortest path problem with forbidden paths. The main aim is to find the shortest paths from a single origin node to every other node of a directed graph, such that the solution does not contain any path belonging to a given set (i.e., the forbidden set). It is imposed that no cycle can be included in the solution. The problem at hand is formulated as a particular instance of the shortest path problem with resource constraints and two different solution approaches are defined and implemented. One is a Branch & Bound based algorithm, the other is a dynamic programming approach. Different versions of the proposed solution strategies are developed and tested on a large set of test problems.     

A branch and bound method for the job-shop problem with sequence-dependent setup times

This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time windows are also solved to perform additional pruning. The traveling salesman problem is formulated as an elementary shortest path problem with resource constraints and solved through dynamic programming. This method allows to close previously unsolved benchmark instances of the literature and also provides new lower and upper bounds.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

Multi-Item, Multi-Facility Supply Chain Planning: Models, Complexities, and Algorithms

We propose a planning model for products manufactured across multiple manufacturing facilities sharing similar production capabilities. The need for cross-facility capacity management is most evident in high-tech industries that have capital-intensive equipment and a short technology life cycle. We propose a multicommodity flow network model where each commodity represents a product and the network structure represents manufacturing facilities in the supply chain capable of producing the products. We analyze in depth the product-level (single-commodity, multi-facility) subproblem when the capacity constraints are relaxed. We prove that even the general-cost version of this uncapacitated subproblem is NP-complete. We show that there exists an optimization algorithm that is polynomial in the number of facilities, but exponential in the number of periods. We further show that under special cost structures the shortest-path algorithm could achieve optimality. We analyze cases when the optimal solution does not correspond to a source-to-sink path, thus the shortest path algorithm would fail. To solve the overall (multicommodity) planning problem we develop a Lagrangean decomposition scheme, which separates the planning decisions into a resource subproblem, and a number of product-level subproblems. The Lagrangean multipliers are updated iteratively using a subgradient search algorithm. Through extensive computational testing, we show that the shortest path algorithm serves as an effective heuristic for the product-level subproblem (a mixed integer program), yielding high quality solutions with only a fraction (roughly 2%) of the computer time.     

A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling

We develop a heuristic procedure for solving the discrete time/resource trade-off problem in the field of project scheduling. In this problem, a project contains activities interrelated by finish-start-type precedence constraints with a time lag of zero, which require one or more constrained renewable resources. Each activity has a specified work content and can be performed in different modes, i.e. with different durations and resource requirements, as long as the required work content is met. The objective is to schedule each activity in one of its modes in order to minimize the project makespan. We use a scatter search algorithm to tackle this problem, using path relinking methodology as a solution combination method. Computational results on randomly generated problem sets are compared with the best available results indicating the efficiency of the proposed algorithm.     

Heuristics for multimode scheduling problems with dedicated resources

We study scheduling problems with multiple modes and dedicated resources arising in production and project management, which constitute a special class of the general multimode resource-constrained project scheduling problem. A task may require simultaneously a set of discrete, renewable resources to be processed and the processing can be performed in different modes, that is with different resource sets, processing times, or costs. Precedence constraints can exist among tasks. The total budget that can be allocated to the project can be limited. The problem consists of identifying a mode for each task and a starting time for its processing respecting precedence, resource, and budget constraints. A graph model and an iterative solution scheme are presented. Specific heuristic algorithms for the cases with and without budget constraints are given and computational results are discussed.