A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern

The integrated vehicle-crew-roster problem with days-off pattern aims to simultaneously determine minimum cost vehicle and daily crew schedules that cover all timetabled trips and a minimum cost roster covering all daily crew duties according to a pre-defined days-off pattern. This problem is formulated as a new integer linear programming model and is solved by a heuristic approach based on Benders decomposition that iterates between the solution of an integrated vehicle-crew scheduling problem and the solution of a rostering problem. Computational experience with data from two bus companies in Portugal and data from benchmark vehicle scheduling instances shows the ability of the approach for producing a variety of solutions within reasonable computing times as well as the advantages of integrating the three problems.     

Computing the metric dimension of graphs by genetic algorithms

In this paper we consider the NP-hard problem of determining the metric dimension of graphs. We propose a genetic algorithm (GA) that uses the binary encoding and the standard genetic operators adapted to the problem. The feasibility is enforced by repairing the individuals. The overall performance of the GA implementation is improved by a caching technique. Since the metric dimension problem up to now has been considered only theoretically, standard test instances for this problem do not exist. For that reason, we present the results of the computational experience on several sets of test instances for other NP-hard problems: pseudo boolean, crew scheduling and graph coloring. Testing on instances with up to 1534 nodes shows that GA relatively quickly obtains approximate solutions. For smaller instances, GA solutions are compared with CPLEX results. We have also modified our implementation to handle theoretically challenging large-scale classes of hypercubes and Hamming graphs. In this case the presented approach reaches optimal or best known solutions for hypercubes up to 131072 nodes and Hamming graphs up to 4913 nodes.     

Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods

The integrated crew scheduling (ICS) problem consists of determining, for a set of available crew members, least-cost schedules that cover all flights and respect various safety and collective agreement rules. A schedule is a sequence of pairings interspersed by rest periods that may contain days off. A pairing is a sequence of flights, connections, and rests starting and ending at the same crew base. Given its high complexity, the ICS problem has been traditionally tackled using a sequential two-stage approach, where a crew pairing problem is solved in the first stage and a crew assignment problem in the second stage. Recently, Saddoune et al. (2010b) developed a model and a column generation/dynamic constraint aggregation method for solving the ICS problem in one stage. Their computational results showed that the integrated approach can yield significant savings in total cost and number of schedules, but requires much higher computational times than the sequential approach. In this paper, we enhance this method to obtain lower computational times. In fact, we develop a bi-dynamic constraint aggregation method that exploits a neighborhood structure when generating columns (schedules) in the column generation method. On a set of seven instances derived from real-world flight schedules, this method allows to reduce the computational times by an average factor of 2.3, while improving the quality of the computed solutions.     

A Decision Support System for Crew Planning in Passenger Transportation Using a Flexible Branch-and-Price Algorithm

This paper discusses a decision support system for airline and railway crew planning. The system is a state-of-the-art branch-and-price solver that is used for crew scheduling and crew rostering. Since it is far from trivial to build such a system from the information provided in the existing literature, technical issues about the system and its implementation are covered in more detail. We also discuss several applications. In particular, we focus on a specific aircrew rostering application. The computational results contain an interesting comparison of results obtained with the approach in which crew scheduling is carried out before crew rostering, and an approach in which these two planning problems are solved in an integrated manner.     

Analysis,modeling and solution of the concrete delivery problem

This paper describes a specific local search approach to solve a problem arising in logistics which we prove to be NP-hard. The problem is a complex scheduling or vehicle routing problem where we have to schedule the tours of concrete mixer vehicles over a working day from concrete-producing depots to concrete-demanding customers and vice versa. We give a general mixed integer programming model which is too hard to solve for state of the art mixed integer programming optimizers in the case of the usually huge problem instances coming from practice. Therefore we present a certain local search approach to be able to handle huge practical problem instances.     

A Queueing Framework for Routing Problems with Time-dependent Travel Times

Assigning and scheduling vehicle routes in a dynamic environment is a crucial management problem. Despite numerous publications dealing with efficient scheduling methods for vehicle routing, very few addressed the inherent stochastic and dynamic nature of travel times. In this paper, a vehicle routing problem with time-dependent travel times due to potential traffic congestion is considered. The approach developed introduces the traffic congestion component based on queueing theory. This is an innovative modelling scheme to capture the stochastic behavior of travel times as it generates an analytical expression for the expected travel times as well as for the variance of the travel times. Routing solutions that perform well in the face of the extra complications due to congestion are developed. These more realistic solutions have the potential to reduce real operating costs for a broad range of industries which daily face routing problems. A number of datasets are used to illustrate the appropriateness of the novel approach. Moreover it is shown that static (or time-independent) solutions are often infeasible within a congested traffic environment which is generally the case on European road networks. Finally, the effect of travel time variability (obtained via the queueing approach) is quantified for the different datasets.      

Vehicle routing with dynamic travel times: A queueing approach

Transportation is an important component of supply chain competitiveness since it plays a major role in the inbound, inter-facility, and outbound logistics. In this context, assigning and scheduling vehicle routes is a crucial management problem. In this paper, a vehicle routing problem with dynamic travel times due to potential traffic congestion is considered. The approach developed introduces mainly the traffic congestion component based on queueing theory. This is an innovative modeling scheme to capture travel times. The queueing approach is compared with other approaches and its potential benefits are described and quantified. Moreover, the optimization of the starting times of a route at the distribution center is evaluated. Finally, the trade-off between solution quality and calculation time is discussed. Numerous test instances are used, both to illustrate the appropriateness of the approach as well as to show that time-independent solutions are often unrealistic within a congested traffic environment, which is usually the case on European road networks.     

Airline Crew Scheduling: State-of-the-Art

The airline industry is faced with some of the largest scheduling problems of any industry. The crew scheduling problem involves the optimal allocation of crews to flights. Over the last two decades the magnitude and complexity of crew scheduling problems have grown enormously and airlines are relying more on automated mathematical procedures as a practical necessity. In this paper we survey different approaches studied and discuss the state-of-the-art in solution methodology for the airline crew scheduling problem. We conclude with a discussion about promising areas for further work to make it possible to get very good solutions for the crew scheduling problem.     

A metaheuristic based on a pool of routes for the vehicle routing problem with multiple trips and time windows

This paper studies the vehicle routing problem with multiple trips and time windows, in which vehicles are allowed to perform multiple trips during a scheduling period and each customer must be served within a given time interval. The problem is of particular importance for planning fleets of hired vehicles in common practices, such as e-grocery distributions, but this problem has received little attention in the literature. As a result of the multi-layered structure characteristic of the problem solution, we propose a pool-based metaheuristic in which various routes are first constructed to fill a pool, following which some of the routes are selected and combined to form vehicle working schedules. Finally, we conduct a series of experiments over a set of benchmark instances to evaluate and demonstrate the effectiveness of the proposed metaheuristic.     

A hybrid scatter search heuristic for personalized crew rostering in the airline industry

The crew scheduling problem in the airline industry is extensively investigated in the operations research literature since efficient crew employment can drastically reduce operational costs of airline companies. Given the flight schedule of an airline company, crew scheduling is the process of assigning all necessary crew members in such a way that the airline is able to operate all its flights and constructing a roster line for each employee minimizing the corresponding overall cost for personnel. In this paper, we present a scatter search algorithm for the airline crew rostering problem. The objective is to assign a personalized roster to each crew member minimizing the overall operational costs while ensuring the social quality of the schedule. We combine different complementary meta-heuristic crew scheduling combination and improvement principles. Detailed computational experiments in a real-life problem environment are presented investigating all characteristics of the procedure. Moreover, we compare the proposed scatter search algorithm with optimal solutions obtained by an exact branch-and-price procedure and a steepest descent variable neighbourhood search.     

Integrated machine scheduling and vehicle routing with time windows

This paper integrates production and outbound distribution scheduling in order to minimize total tardiness. The overall problem consists of two subproblems. The first addresses scheduling a set of jobs on parallel machines with machine-dependent ready times. The second focusses on the delivery of completed jobs with a fleet of vehicles which may differ in their loading capacities and ready times. Job-dependent processing times, delivery time windows, service times, and destinations are taken into account. A genetic algorithm approach is introduced to solve the integrated problem as a whole. Two main questions are examined. Are the results of integrating machine scheduling and vehicle routing significantly better than those of classic decomposition approaches which break down the overall problem, solve the two subproblems successively, and merge the subsolutions to form a solution to the overall problem? And if so, is it possible to capitalize on these potentials despite the complexity of the integrated problem? Both questions are tackled by means of a numerical study. The genetic algorithm outperforms the classic decomposition approaches in case of small-size instances and is able to generate relatively good solutions for instances with up to 50 jobs, 5 machines, and 10 vehicles.     

The crane scheduling problem: models and solution approaches

In this paper, we study the crane scheduling problem for a vessel after the vessel is moored on a terminal and develop both exact and heuristic solution approaches for the problem. For small-sized instances, we develop a time-space network flow formulation with non-crossing constraints for the problem and apply an exact solution approach to obtain an optimal solution. For medium-sized instances, we develop a Lagrangian relaxation approach that allows us to obtain tight lower bounds and near-optimal solutions. For large-sized instances, we develop two heuristics and show that the error bounds of our heuristics are no more than 100%. Finally, we perform computational studies to show the effectiveness of our proposed solution approaches.     

Two-level decomposition algorithm for crew rostering problems with fair working condition

A typical railway crew scheduling problem consists of two phases: a crew pairing problem to determine a set of crew duties and a crew rostering problem. The crew rostering problem aims to find a set of rosters that forms workforce assignment of crew duties and rest periods satisfying several working regulations. In this paper, we present a two-level decomposition approach to solve railway crew rostering problem with the objective of fair working condition. To reduce computational efforts, the original problem is decomposed into the upper-level master problem and the lower-level subproblem. The subproblem can be further decomposed into several subproblems for each roster. These problems are iteratively solved by incorporating cuts into the master problem. We show that the relaxed problem of the master problem can be formulated as a uniform parallel machine scheduling problem to minimize makespan, which is NP-hard. An efficient branch-and-bound algorithm is applied to solve the master problem. Effective valid cuts are developed to reduce feasible search space to tighten the duality gap. Using data provided by the railway company, we demonstrate the effectiveness of the proposed method compared with that of constraint programming techniques for large-scale problems through computational experiments.     

A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints

We address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem of optimal scheduling of sparse tree-like instances can be solved in polynomial time. However, if we admit dense instances then the problem becomes NP-hard, even if there are only two machines.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem

This paper investigates the construction of an automatic algorithm selection tool for the multi-mode resource-constrained project scheduling problem (MRCPSP). The research described relies on the notion of empirical hardness models. These models map problem instance features onto the performance of an algorithm. Using such models, the performance of a set of algorithms can be predicted. Based on these predictions, one can automatically select the algorithm that is expected to perform best given the available computing resources. The idea is to combine different algorithms in a super-algorithm that performs better than any of the components individually. We apply this strategy to the classic problem of project scheduling with multiple execution modes. We show that we can indeed significantly improve on the performance of state-of-the-art algorithms when evaluated on a set of unseen instances. This becomes important when lots of instances have to be solved consecutively. Many state-of-the-art algorithms perform very well on a majority of benchmark instances, while performing worse on a smaller set of instances. The performance of one algorithm can be very different on a set of instances while another algorithm sees no difference in performance at all. Knowing in advance, without using scarce computational resources, which algorithm to run on a certain problem instance, can significantly improve the total overall performance.     

A time–space network based exact optimization model for multi-depot bus scheduling

The vehicle scheduling problem, arising in public transport bus companies, addresses the task of assigning buses to cover a given set of timetabled trips with consideration of practical requirements, such as multiple depots and vehicle types as well as depot capacities. An optimal schedule is characterized by minimal fleet size and minimal operational costs including costs for unloaded trips and waiting time. This paper discusses the multi-depot, multi-vehicle-type bus scheduling problem (MDVSP), involving multiple depots for vehicles and different vehicle types for timetabled trips. We use time–space-based instead of connection-based networks for MDVSP modeling. This leads to a crucial size reduction of the corresponding mathematical models compared to well-known connection-based network flow or set partitioning models. The proposed modeling approach enables us to solve real-world problem instances with thousands of scheduled trips by direct application of standard optimization software. To our knowledge, the largest problems that we solved to optimality could not be solved by any existing exact approach. The presented research results have been developed in co-operation with the provider of transportation planning software PTV AG. A software component to support planners in public transport was designed and implemented in context of this co-operation as well.     

Surgical case scheduling as a generalized job shop scheduling problem

Surgical case scheduling allocates hospital resources to individual surgical cases and decides on the time to perform the surgeries. This task plays a decisive role in utilizing hospital resources efficiently while ensuring quality of care for patients. This paper proposes a new surgical case scheduling approach which uses a novel extension of the Job Shop scheduling problem called multi-mode blocking job shop (MMBJS). It formulates the MMBJS as a mixed integer linear programming (MILP) problem and discusses the use of the MMBJS model for scheduling elective and add-on cases. The model is illustrated by a detailed example, and preliminary computational experiments with the CPLEX solver on practical-sized instances are reported.     

Iterated local search for workforce scheduling and routing problems

The integration of scheduling workers to perform tasks with the traditional vehicle routing problem gives rise to the workforce scheduling and routing problems (WSRP). In the WSRP, a number of service technicians with different skills, and tasks at different locations with pre-defined time windows and skill requirements are given. It is required to find an assignment and ordering of technicians to tasks, where each task is performed within its time window by a technician with the required skill, for which the total cost of the routing is minimized. This paper describes an iterated local search (ILS) algorithm for the WSRP. The performance of the proposed algorithm is evaluated on benchmark instances against an off-the-shelf optimizer and an existing adaptive large neighbourhood search algorithm. The proposed ILS algorithm is also applied to solve the skill vehicle routing problem, which can be viewed as a special case of the WSRP. The computational results indicate that the proposed algorithm can produce high-quality solutions in short computation times.     

Economic lot sizes and vehicle scheduling

In this paper a relationship between the vehicle scheduling problem and the dynamic lot size problem is considered. For the latter problem we assume that order quantities for different products can be determined separately. Demand is known over our n-period production planning horizon. For a certain product our task is to decide for each period if it should be produced or not. If it is produced, what is its economic lot size? Our aim here is to minimize the combined set-up and inventory holding costs. The optimal solution of this problem is given by the well-known Wagner-Whitin dynamic lot size algorithm. Also many heuristics for solving this problem have been presented. In this article we point out the analogy of the dynamic lot size problem to a certain vehicle scheduling problem. For solving vehicle scheduling problems the heuristic algorithm developed by Clark and Wright in very often used. Applying this algorithm to the equivalent vehicle scheduling problem we obtain by analogy a simple heuristic algorithm for the dynamic lot size problem. Numerical results indicate that computation time is reduced by about 50% compared to the Wagner-Whitin algorithm. The average cost appears to be approximately 0.8% higher than optimum.