A rich vehicle routing problem dealing with perishable food: a case study

This paper presents a successful application of operations research techniques in guiding the decision making process to achieve a superior operational efficiency in core activities. We focus on a rich vehicle routing problem faced by a Portuguese food distribution company on a daily basis. This problem can be described as a heterogeneous fleet site dependent vehicle routing problem with multiple time windows. We use the adaptative large neighbourhood search framework, which has proven to be effective to solve a variety of different vehicle routing problems. Our plans are compared against those of the company and the impact that the proposed decision support tool may have in terms of cost savings is shown. The algorithm converges quickly giving the planner considerably more time to focus on value-added tasks, rather than manually correct the routing schedule. Moreover, contrarily to the necessary adaptation time of the planner, the tool is quite flexible in following market changes, such as the introduction of new customers or new products.     

A multi-depot period vehicle routing problem arising in the utilities sector

This paper considers the resource planning problem of a utility company that provides preventive maintenance services to a set of customers using a fleet of depot-based mobile gangs. The problem is to determine the boundaries of the geographic areas served by each depot, the list of customers visited each day and the routes followed by the gangs. The objective is to provide improved customer service at minimum operating cost subject to constraints on frequency of visits, service time requirements, customer preferences for visiting on particular days and other routing constraints. The problem is solved as a Multi-Depot Period Vehicle Routing Problem (MDPVRP). The computational implementation of the complete planning model is described with reference to a pilot study and results are presented. The solution algorithm is used to construct cost-service trade-off curves for all depots so that management can evaluate the impact of different customer service levels on total routing costs.     

A guide to vehicle routing heuristics

Several of the most important classical and modern heuristics for the vehicle routing problem are summarized and compared using four criteria: accuracy, speed, simplicity and flexibility. Computational results are reported.     

Polyhedral study of the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes.This work was supported in part by NSF grant DDM-8901495.     

Stochastic vehicle routing

The purpose of this review article is to provide a summary of the scientific literature on stochastic vehicle routing problems. The main problems are described within a broad classification scheme and the most important contributions are summarized in table form.     

A branch-and-cut algorithm for vehicle routing problems

We present a branch-and-cut algorithm for the identical customer Vehicle Routing Problem. Transforming the problem into an equivalent Path-Partitioning Problem allows us to exploit its polyhedral structure and to generate strong cuts corresponding to facet-inducing inequalities. By using cuts defined by multistars, partial multistars and generalized subtour elimination constraints, we are able to consistently solve 60-city problems to proven optimality and are currently attempting to solve problems involving a hundred cities. We also present details of the computer implementation and our computational results.     

A Lagrangean relaxation heuristic for vehicle routing

This paper presents a new heuristic algorithm for the vehicle routing problem (VRP) which makes use of Lagrangean relaxation to transform the VRP into a modified m-traveling salesman problem. Application of the proposed algorithm to test problems from the literature has produced new best-known solutions.     

Stochastic vehicle routing: A comprehensive approach

A vehicle routing problem is stochastic when the demands at individual delivery (pickup) locations behave as random variables, and the routes must be defined before the values of these random variables become known. This paper presents several formulations and heuristic algorithms for solving this complex problem.     

Multi-objective vehicle routing problems

Routing problems, such as the traveling salesman problem and the vehicle routing problem, are widely studied both because of their classic academic appeal and their numerous real-life applications. Similarly, the field of multi-objective optimization is attracting more and more attention, notably because it offers new opportunities for defining problems. This article surveys the existing research related to multi-objective optimization in routing problems. It examines routing problems in terms of their definitions, their objectives, and the multi-objective algorithms proposed for solving them.     

The vehicle routing problem: A book review

We review the recent book, edited by Paolo Toth and Daniele Vigo, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications 2002, ISBN: 0-89871-498-2, price: 95 USD.     

Scheduling issues in vehicle routing

Scheduling often plays an important role in vehicle routing. This paper describes several applications in which the author has been involved in recent years. These arise in the dial-a-ride problem, speed optimization in routing problems, the pollution-routing problem, long-haul vehicle routing and scheduling with working hour rules, and synchronization in arc routing.     

Probabilistic time-dependent vehicle routing problem

Central European Journal of Operations Research - The probabilistic time-dependent vehicle routing problem is presented in this paper. It is a novel variant of the vehicle routing problem. The...     

A reactive tabu search for the vehicle routing problem

The classical vehicle routing problem (VRP) involves determining a fleet of homogeneous size vehicles and designing an associated set of routes that minimizes the total cost. Our tabu search (TS) algorithm to solve the VRP is based on reactive tabu search (RTS) with a new escape mechanism, which manipulates different neighbourhood schemes in a very sophisticated way in order to get a balanced intensification and diversification continuously during the search process. We compare our algorithm with the best methods in the literature using different data sets and report results including new best known solutions for several well-known benchmark problems.     

A savings based method for real-life vehicle routing problems

This paper describes a Savings Based algorithm for the Extended Vehicle Routing Problem. This algorithm is compared with a sequential insertion algorithm on real-life data. Besides the traditional quality measures such as total distance travelled and total workload, we compare the routing plans of both algorithms according to non-standard quality measures that help to evaluate the ‘visual attractiveness’ of the plan. Computational results show that, in general, the savings based algorithm not only performs better with respect to these non-standard quality measures, but also with respect to the traditional measures.     

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 unified solution framework for multi-attribute vehicle routing problems

Vehicle routing attributes are extra characteristics and decisions that complement the academic problem formulations and aim to properly account for real-life application needs. Hundreds of methods have been introduced in recent years for specific attributes, but the development of a single, general-purpose algorithm, which is both efficient and applicable to a wide family of variants remains a considerable challenge. Yet, such a development is critical for understanding the proper impact of attributes on resolution approaches, and to answer the needs of actual applications. This paper contributes towards addressing these challenges with a component-based design for heuristics, targeting multi-attribute vehicle routing problems, and an efficient general-purpose solver. The proposed Unified Hybrid Genetic Search metaheuristic relies on problem-independent unified local search, genetic operators, and advanced diversity management methods. Problem specifics are confined to a limited part of the method and are addressed by means of assignment, sequencing, and route-evaluation components, which are automatically selected and adapted and provide the fundamental operators to manage attribute specificities. Extensive computational experiments on 29 prominent vehicle routing variants, 42 benchmark instance sets and overall 1099 instances, demonstrate the remarkable performance of the method which matches or outperforms the current state-of-the-art problem-tailored algorithms. Thus, generality does not necessarily go against efficiency for these problem classes.     

A self-tuning heuristic for a multi-objective vehicle routing problem

In this study, a heuristic free from parameter tuning is introduced to solve the vehicle routing problem (VRP) with two conflicting objectives. The problem which has been presented is the designing of optimal routes: minimizing both the number of vehicles and the maximum route length. This problem, even in the case of its single objective form, is NP-hard. The proposed self-tuning heuristic (STH) is based on local search and has two parameters which are updated dynamically throughout the search process. The most important advantage of the algorithm is the application convenience for the end-users. STH is tested on the instances of a multi-objective problem in school bus routing and classical vehicle routing. Computational experiments, when compared with the prior approaches proposed for the multi-objective routing of school buses problem, confirm the effectiveness of STH. STH also finds high-quality solutions for multi-objective VRPs.     

The multi-trip vehicle routing problem

The basic vehicle routing problem is concerned with the design of a set of routes to serve a given number of customers, minimising the total distance travelled. In that problem, each vehicle is assumed to be used only once during a planning period, which is typically a day, and therefore is unrepresentative of many practical situations, where a vehicle makes several journeys during a day. The present authors have previously published an algorithm which outperformed an experienced load planner working on the complex, real-life problems of Burton's Biscuits, where vehicles make more than one trip each day. This present paper uses a simplified version of that general algorithm, in order to compare it with a recently published heuristic specially designed for the theoretical multi-trip vehicle routing problem.