This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints. Given the intrinsic difficulty of this problem class, approximation methods seem to offer the most promise for practical size problems. After describing a variety of heuristics, we conduct an extensive computational study of their performance. The problem set includes routing and scheduling environments that differ in terms of the type of data used to generate the problems, the percentage of customers with time windows, their tightness and positioning, and the scheduling horizon. We found that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.

The vehicle routing problem with time windows (VRPTW) is a generalization of the vehicle routing problem where the service of a customer can begin within the time window defined by the earliest and the latest times when the customer will permit the start of service. In this paper, we present the development of a new optimization algorithm for its solution. The LP relaxation of the set partitioning formulation of the VRPTW is solved by column generation. Feasible columns are added as needed by solving a shortest path problem with time windows and capacity constraints using dynamic programming. The LP solution obtained generally provides an excellent lower bound that is used in a branch-and-bound algorithm to solve the integer set partitioning formulation. Our results indicate that this algorithm proved to be successful on a variety of practical sized benchmark VRPTW test problems. The algorithm was capable of optimally solving 100-customer problems. This problem size is six times larger than any reported to date by other published research.

This paper proposes a new framework for the solution of interactive multiobjective group decision-making problems with interval parameters. Its novelty stems from a learning phase where decision makers (DMs) explore the structural characteristics of the specific Multiple Criteria Decision Making (MCDM) problem. This provides important and timely feedback to the DMs. Its core consists of four indices and their relationships. The solution framework consists of three stages. In the first, each DM provides the limits of variation for each problem parameter. These are subsequently combined into a unique interval of variation. Then, the stochastic multiobjective problem is transformed into a deterministic one. In the second stage, DMs use the four MCDM characteristics to familiarize themselves with the problem before expressing their preferences for nondominated solutions. The DMs are then guided through an interactive procedure to find their best nondominated solutions. In the last stage, all best nondominated solutions provided by the DMs are combined using a twofold approach to find the best-compromise nondominated solution. This final choice represents the opinion of the group of DMs. Our results show that the learning phase is beneficial to DMs in judging the quality of solutions, leading to better informed decisions.

In this paper we examine computational complexity issues and develop algorithms for a class of “shoreline” single-vehicle routing and scheduling problems with release time constraints. Problems in this class are interesting for both practical and theoretical reasons. From a practical perspective, these problems arise in several transportation environments. For instance, in the routing and scheduling of cargo ships, the routing structure is “easy” because the ports to be visited are usually located along a shoreline. However, because release times of cargoes at ports generally complicate the routing structure, the combined routing and scheduling problem is nontrivial. For the straight-line case (a restriction of the shoreline case), our analysis shows that the problem of minimizing the maximum completion time can be solved exactly in quadratic time by dynamic programming. For the shoreline case we develop and analyze heuristic algorithms. We derive data-dependent worst-case performance ratios for these heuristics that are bounded by constant. We also discuss how these algorithms perform on practical data.

The problem of assigning locomotives to trains consists of selecting the types and number of engines that minimize the fixed and operational locomotive costs resulting from providing sufficient power to pull trains on fixed schedules. The force required to pull a train is often expressed in terms of horsepower and tonnage requirements rather than in terms of number of engines. This complicates the solution process of the integer programming formulation and usually creates a large integrality gap. Furthermore, the solution of the linearly relaxed problem is strongly fractional. To obtain integer solutions, we propose a novel branch-and-cut approach. The core of the method consists of branching decisions that define on one branch the projection of the problem on a low-dimensional subspace. There, the facets of the polyhedron describing a restricted constraint set can be easily derived. We call this approach branch-first, cut-second. We first derive facets when at most two types of engines are used. We then extend the branching rule to cases involving additional locomotive types. We have conducted computational experiments using actual data from the Canadian National railway company. Simulated test-problems involving two or more locomotive types were solved over 1-, 2-, and 3-day rolling horizons. The cuts were successful in reducing the average integrality gap by 52% for the two-type case and by 34% when more than 25 types were used. Furthermore, the branch-first, cut-second approach was instrumental in improving the best known solution for an almost 2,000-leg weekly problem involving 26 locomotive types. It reduced the number of locomotives by 11, or 1.1%, at an equivalent savings of $3,000,000 per unit. Additional tests on different weekly data produced almost identical results.

In this paper we consider the daily aircraft routing and scheduling problem (DARSP). It consists of determining daily schedules which maximize the anticipated profits derived from the aircraft of a heterogeneous fleet. This fleet must cover a set of operational flight legs with known departure time windows, durations and profits according to the aircraft type. We present two models for this problem: a Set Partitioning type formulation and a time constrained multicommodity network flow formulation. We describe the network structure of the subproblem when a column generation technique is applied to solve the linear relaxation of the first model and when a Dantzig-Wolfe decomposition approach is used to solve the linear relaxation of the second model. The linear relaxation of the first model provides upper bounds. Integer solutions to the overall problem are derived through branch-and-bound. By exploiting the equivalence between the two formulations, we propose various optimal branching strategies compatible with the column generation technique. Finally we report computational results obtained on data provided by two different airlines. These results show that significant profit improvement can be generated by solving the DARSP using our approach and that this can be obtained in a reasonable amount of CPU time.