A Branch-and-price Algorithm for the Multi-Vehicle Covering Tour Problem

In this paper, we propose a Branch-and-price (BP) algorithm and a Column Generation Heuristic (CGH) for the Multi-Vehicle Covering Tour Problem (m-CTP). Specific dominance and extension pruning rules are introduced to accelerate the resolution of the pricing problems. To the best of our knowledge, this is the first work dedicated to the exact resolution of m-CTP. The algorithm managed to solve about 30% of the instances in our test bed, within a 4 hour CPU time limit. Our preliminary computational experiments suggest that both the lower bounds provided by the formulation behind BP and the CGH upper bounds are of good quality.     

A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries,Selective Pickups and Time Windows

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.     

Aircraft and crew scheduling for fractional ownership programs

Fractional aircraft ownership programs, where individuals or corporations own a fraction of an aircraft, have revolutionized the corporate aviation industry. Fractional management companies (FMC) manage all aspects of aircraft operations enabling the owners to enjoy the benefits of private aviation without the associated responsibilities. We describe here the development of a scheduling decision support tool for a leading FMC. We present mathematical models, exact and heuristic solution methods. Our computational results using real and randomly generated data indicate that these models are quite effective in finding optimal or near-optimal solutions. The first phase of the implementation of one of these models at the FMC led to a significant improvement in effective utilization of the aircraft, reduction of costs due to reduced empty moves, and hence increased profits.     

On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem

In this paper a comparison is made between two decomposition techniques to solve a staff scheduling problem with column generation. In the first approach, decomposition takes place on the staff members, whereas in the second approach decomposition takes place on the activities that have to be performed by the staff members. The resulting master LP is respectively a set partitioning problem and a capacitated multi-commodity flow problem. Both approaches have been implemented in a branch-and-price algorithm. We show a trade-off between modeling power and computation times of both techniques.     

A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times

We consider the problem of scheduling n independent jobs on m unrelated parallel machines with sequence-dependent setup times and availability dates for the machines and release dates for the jobs to minimize a regular additive cost function. In this work, we develop a new branch-and-price optimization algorithm for the solution of this general class of parallel machines scheduling problems. A new column generation accelerating method, termed “primal box”, and a specific branching variable selection rule that significantly reduces the number of explored nodes are proposed. The computational results show that the approach solves problems of large size to optimality within reasonable computational time.     

Column generation for vehicle routing problems with multiple synchronization constraints

Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we focus on operational ground handling planning and model it as an archetype of vehicle routing problems with multiple synchronization constraints, coined as “abstract vehicle routing problem with worker and vehicle synchronization” (AVRPWVS). The AVRPWVS deals with routing workers to ground handling jobs such as unloading baggage or refuelling an aircraft, while meeting each job’s time window. Moreover, each job can be performed by a variable number of workers. As airports span vast distances and due to security regulations, workers use vehicles to travel between locations. Furthermore, each vehicle, moved by a driver, can carry several workers. We propose two mathematical multi-commodity flow formulations based on time-space networks to efficiently model five synchronization types including movement and load synchronization. Moreover, we develop a branch-and-price heuristic that employs both conventional variable branching and a novel variable fixing strategy. We demonstrate that the procedure achieves results close to the optimal solution in short time when compared to the two integer models.     

A branch-and-price approach for large-scale employee tour scheduling problems

We present a new methodology for solving large-scale employee tour scheduling problems. An integer programming model is proposed where tours are decomposed into shifts and start times. This formulation can model complex shift and start time rules for both continuous and discontinuous scheduling problems. A branch-and-price approach is devised to solve this model efficiently. The methodology was tested on the largest tour scheduling problems found in the open literature. In comparison with an alternative implicit model, our approach showed superior computational performance.     

Supply capacity acquisition and allocation with uncertain customer demands

We study a class of capacity acquisition and assignment problems with stochastic customer demands often found in operations planning contexts. In this setting, a supplier utilizes a set of distinct facilities to satisfy the demands of different customers or markets. Our model simultaneously assigns customers to each facility and determines the best capacity level to operate or install at each facility. We propose a branch-and-price solution approach for this new class of stochastic assignment and capacity planning problems. For problem instances in which capacity levels must fall between some pre-specified limits, we offer a tailored solution approach that reduces solution time by nearly 80% over an alternative approach using a combination of commercial nonlinear optimization solvers. We have also developed a heuristic solution approach that consistently provides optimal or near-optimal solutions, where solutions within 0.01% of optimality are found on average without requiring a nonlinear optimization solver.     

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.     

The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies

In the Home Care Crew Scheduling Problem a staff of home carers has to be assigned a number of visits to patients’ homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time windows of the visits must be respected. The challenge when assigning visits to home carers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits.