Constraint Programming and Operations Research: Comments from an Operations Researcher

This paper relates the author's personal experience with constraint programming and gives a personal assessment of the relationships between constraint programming and operations research.     

Strategic analysis of the dairy transportation problem

The dairy transportation problem (DTP) consists of determining the best routes to be performed for collecting milk from farms and delivering it to processing plants. We study the particular case of the province of Quebec, where the Fédération des producteurs de lait du Québec is responsible for negotiating the transportation costs on behalf of producers. Several issues are highlighted in the actual process of designing contracts such as using historical data. We propose an approach based on scenario analysis that consists of revising both the steps and the information used to construct the routes. We develop a generalized tabu search algorithm that integrates the different characteristics of the DTP.     

A simulation-based approach for fleet design in a technician dispatch problem with stochastic demand

We address the problem of developing policies for selecting the proper number of technicians to hire (fleet size) for an on-call repair service operating over a yearly planning horizon in an environment where the number of requests to be serviced each day can vary significantly from day to day and on a seasonal basis. We propose a new approach based on the simulation of a large number of sampled weekly instances and the application of a previously developed optimization procedure for the daily dispatch of technicians. The sampled instances are derived from an extensive statistical analysis of demand data with respect to several key parameters. The results of the simulations are utilized to adjust performance curves in function of fleet size that are then used in an economic analysis of the trade-offs between service quality and cost. Efficient policies for fleet design are then deducted from this analysis.     

Implicit depot assignments and rotations in vehicle routing heuristics

Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.     

Heuristics for multi-attribute vehicle routing problems: A survey and synthesis

The attributes of vehicle routing problems are additional characteristics or constraints that aim to better take into account the specificities of real applications. The variants thus formed are supported by a well-developed literature, including a large variety of heuristics. This article first reviews the main classes of attributes, providing a survey of heuristics and meta-heuristics for Multi-Attribute Vehicle Routing Problems (MAVRP). It then takes a closer look at the concepts of 64 remarkable meta-heuristics, selected objectively for their outstanding performance on 15 classic MAVRP with different attributes. This cross-analysis leads to the identification of “winning strategies” in designing effective heuristics for MAVRP. This is an important step in the development of general and efficient solution methods for dealing with the large range of vehicle routing variants.     

Path Relinking, Cycle-Based Neighbourhoods and Capacitated Multicommodity Network Design

In this paper, we propose a path relinking procedure for the fixed-charge capacitated multicommodity network design problem. Cycle-based neighbourhoods are used both to move along paths between elite solutions and to generate the elite candidate set by a tabu-like local search procedure. Several variants of the method are implemented and compared. Extensive computational experiments indicate that the path relinking procedure offers excellent results. It systematically outperforms the cycle-based tabu search method in both solution quality and computational effort and offers the best current meta-heuristic for this difficult class of problems.     

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.     

A hybrid dynamic programming - Tabu Search approach for the long-term hydropower scheduling problem

Computational Management Science - The long-term energy scheduling of a large hydroelectric power system is studied in this paper. The problem aims at defining a policy that provides the best...     

Diversification strategies in tabu search algorithms for the maximum clique problem

The purpose of this study is to develop some understanding of the benefits that can be derived from the inclusion of diversification strategies in tabu search methods. To do so, we discuss the implementation of various diversification strategies in several tabu search heuristics developed for the maximum clique problem. Computational results on a large set of randomly generated test problems are reported and compared to assess the impact of these techniques on solution quality and running time.