Good Laboratory Practice for optimization research

Good Laboratory Practice has been a part of non-clinical research for over 40 years. Optimization Research, despite having many papers discussing standards being published over the same period of time, has yet to embrace standards that underpin its research. In this paper we argue the need to adopt standards in optimization research. Building on previous papers, many of which have suggested that the optimization research community should adopt certain standards, we suggest a concrete set of recommendations that the community should adopt. We also discuss how the proposals in this paper could be progressed.     

Vehicle Routeing with Multiple Use of Vehicles

The vehicle routeing problem with multiple use of vehicles is a variant of the standard vehicle routeing problem in which the same vehicle may be assigned to several routes during a given planning period. A tabu search heuristic is developed for this problem. It is shown to produce high quality solutions on a series of test problems.     

Solving the frequency assignment problem with polarization by local search and tabu

In the Frequency Assignment Problem with Polarization (FAPP), a given set of links must each be assigned a frequency and a polarization, while respecting given radio-electric compatibility constraints defined on pairs of links. In this paper, we propose a tabu search algorithm for the FAPP. A specialized neighborhood is proposed for the problem. Other key features of the algorithm are an adaptive technique to adjust the tabu tenure, an original diversification technique, and a pre-processing procedure based on arc-consistency techniques. The algorithm is tested on the 40 instances of the ROADEF Challenge 2001. It reaches the best known feasibility level for all instances and finds or improves on the best known solutions of the Challenge for a majority of the instances.Received: July 2003 / Revised version: September 2004MSC classification: 90B18, 68T20All correspondence to: Philippe Galinier     

A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods

This paper proposes a new pro-active real-time control approach for dynamic vehicle routing problems in which the urgent delivery of goods is of utmost importance. Without assuming any distribution, stochastic knowledge about future requests is generated using past request information. The generated knowledge is integrated into the transportation process, which is controlled by a Tabu Search algorithm, in order to actively guide vehicles to request-likely areas before requests arrive there. By analyzing the results attained for various test settings, we identify structural diversity as a crucial criterion for classifying the quality of stochastic knowledge attainable from past request information. This criterion provides a promising starting point for assessing the quality of past request information in order to efficiently use the derived stochastic knowledge in real-time control approaches. We prove the efficiency of our approach by a direct comparison with a deterministic approach on test scenarios with varying structural diversity. Thanks to the proposed classification of structural diversity, differences in results obtained among the tested scenarios become explainable.     

A dynamic vehicle routing problem with multiple delivery routes

This paper considers a vehicle routing problem where each vehicle performs delivery operations over multiple routes during its workday and where new customer requests occur dynamically. The proposed methodology for addressing the problem is based on an adaptive large neighborhood search heuristic, previously developed for the static version of the problem. In the dynamic case, multiple possible scenarios for the occurrence of future requests are considered to decide about the opportunity to include a new request into the current solution. It is worth noting that the real-time decision is about the acceptance of the new request, not about its service which can only take place in some future routes (a delivery route being closed as soon as a vehicle departs from the depot). In the computational results, a comparison is provided with a myopic approach which does not consider scenarios of future requests.     

A General Approach to the Physician Rostering Problem

This paper presents a hybridization of a Constraint Programming (CP) model and search techniques with Local Search (LS) and some ideas borrowed from Genetic Algorithms (GA). The context is the physician rostering problem, whose instances can vary greatly and for which almost no general tool has been developed. It is hoped that the combination of the three techniques will lead to an algorithm that has sufficient flexibility to solve most instances with a small amount of customization. To achieve this goal we also introduce Generic constraints: these constraints are used to model several types of ergonomic constraints that are found amongst physician rostering problems.     

Tabu Search heuristics for the Vehicle Routing Problem with Time Windows

This paper surveys the research on the Tabu Search heuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes for a fleet of vehicles from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed. This work was partially supported by the Emil Aaltonen Foundation, Liikesivistysrahasto Foundation, the Canadian Natural Science and Engineering Research Council and the TOP program funded by the Research Council of Norway. This support is gratefully acknowledged.     

Stéréochimie de la substitution d'un éther allylique par un organomagnésien en présence de sel cuivreux

The nucleophilic substitution of allyl ethers by an organomagnesium reagent in the presence of a catalytic amount of copper(I) salt occurs by antarafacial attack, either with or without allylic rearrangement. It can be compared to the substitution of allyl esters by lithium organocuprates. The leaving group must be quasi orthogonal to the plane of the double bond. A mechanism is postulated.     

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.