Metaheuristics for Vehicle Routing Problems

Introduction

Unlike heuristics, which are problem-dependent techniques which try to take full advantage of the features of the problem at hand but which usually get trapped in a local optimum when followed by a local search, metaheuristics can be defined as solution methods that control the exploration of a solution space by problem-independent techniques with higher level strategies. This allows them to explore the solution space more extensively with the aim of escaping from local optima and thus a hopefully obtain a better solution. These approaches include any scheme that resorts, for example, to one or more neighborhood structures, building or destroying procedures or combining components of several solutions. Notwithstanding their general structure, it is necessary to adapt the techniques according to the problem to solve by some fine-tuning of their intrinsic parameters. Metaheuristic methods have proved to be particularly effective for solving many types of complex problems.

This book is dedicated to these methods developed to one of the most important and studied categories of combinatorial optimization problems: the family of vehicle routing problems (VRPs). The aim of the basic version also called capacitated VRP (CVRP) is to determine the optimal set of routes to be performed by a fleet of capacitated vehicles to serve the demand of a given customer set.

More than 15 years have elapsed since Dantzig and Ramser introduced the problem in 1959 [DAN 59], and the number of models and solution methods has experienced a strong growth as exposed in [LAP 09]. Although the CVRP still attracts researchers, many variants are now investigated. This interest is motivated by two main concerns:

– this class of problems has a high practical relevance;

– it is challenging to solve given its considerable difficulty.

Despite the abundant activity on VRPs, the current exact methods are limited to problems of about 100 customers [BAL 08a], while real cases can reach 1,000 clients.

Therefore, a large number of metaheuristics have been proposed to solve very different problems of vehicle routing, as stated by the surveys periodically published on the subject. From procedures with tabu to hybrid approaches combining heuristic and exact methods, metaheuristics remain the favorite methods for dealing with realistic cases.

Several books are available on either metaheuristics [DRÉ 03, SIA 14] or VRPs [TOT 02] but, to the best of our knowledge, the only books addressing these two topics simultaneously are published PhD dissertations [EUC 12] or books with contributed chapters [GOL 08]. The aim here is more to provide a book for people wishing to discover and quickly master metaheuristics dedicated to VRPs. The particularity is to combine a tutorial with algorithms, examples, and a quick overview of the state-of-the art for such methods developed in the last decades for the CVRP and some of its main variants.

The key points are to present:

– a progressive approach, from the basics to several recent and efficient methods;

– different metaheuristics for the same VRP and, conversely, the way of adapting the same metaheuristic template to several problems;

– algorithms allowing the readers to implement the methods on a computer;

– an up-to-date bibliography focusing on the references which have a real interest.

The book consists of five chapters. After this introduction, the first chapter gives a general presentation that intends to make the readers more familiar with the related fields of logistics and combinatorial optimization.

This preamble is followed, in Chapter 2, with a description of significant heuristic methods classically applied to provide feasible solutions quickly, and local improvement moves widely used to search for enhanced solutions. The overview of these fundamentals allows appreciating the core of the work devoted to an analysis of metaheuristic methods for VRPs. Those methods are exposed according to their feature of working either on a sequence of single solutions, or on a set of solutions, or even by hybridizing metaheuristic approaches with other kinds of methods (mixed integer programs, mathematical decompositions, etc.).

Thus, Chapter 3 begins with the class that works on a single solution at a time, making it evolve through a particular iterative process. This kind of exploration requires us to define at least one neighborhood to jump from an incumbent solution to another area of the solution space. Eight approaches are presented in this chapter, namely simulated annealing, greedy adaptive search procedure, tabu search, variable neighborhood search, iterated local search, guided local search, adaptive large neighborhood search and transitional forms such as evolutionary local search.

Chapter 4 exposes methods operating on a set of solutions. Their feature is to generate new solutions by either combining existing ones or by making agents cooperate through a learning process. Two main variants are put forward: those that combine solutions selected from a population such as genetic algorithms, memetic algorithms, scatter search and path relinking; the ones that make cooperate homogenous agents in their environment such as particle swarm optimization and ant colony optimization.

Chapter 5 is devoted to two main classes of hybrid methods: either by combining components from several stand alone metaheuristics, or by crossing exact algorithms with metaheuristics (leading to the so called matheuristics). The main motivation of this trend is to take advantage of the complementarity of different optimization strategies and cooperate in synergy.

Finally, the Conclusion closes the book and draws up some perspectives of the research on VRPs. In the three chapters detailing the different class of metaheuristics, several selected implementations of methods dedicated to typical VRPs are given as illustrative examples.

1

General Presentation of Vehicle Routing Problems

Vehicle routing problems (VRPs) represent an important family of problems encountered in the fields of logistics, as well as in many other applications. In general, a number of customers have to be served with a fleet of vehicles. They can be modeled as an integer programming problem, solved by combinatorial optimization tools. However, exact methods cannot solve instances that consider a large set of customers, as encountered in most real cases. It is, therefore, often necessary to resort to approximate paradigms generally carried out through metaheuristics.

This first chapter introduces what the logistics management and the combinatorial optimization are, before giving a formal definition of the CVRP, with notations useful throughout the remainder of the book.

1.1. Logistics management and combinatorial optimization

In the last few decades, a great interest has grown up in the area of logistics among both industry and academia, for different reasons [BRA 98]. First, companies are facing fierce competition in today’s global markets. They need to innovate to keep their position, and they realize the savings that can be achieved by a better planning and management of their logistic systems.

Furthermore, the evolution of lifestyles is significant. Modes of consumption are changing and expectations of consumers switch to products with short lifecycles, and the advancement in communications and transportation technologies, such as mobile communication and overnight delivery, motivates continuous development of the management of logistic systems.

These changes attract attention of the academic community, whose approach consists of determining characteristics of the problems and developing solution methodologies, as well as providing specific guarantees of effectiveness.

1.1.1. History of logistics

Logistics is not a recent trend in managing the flow of goods from an origin to a destination, with the aim to meet some requirements. Logistics made an important stride during the construction of the pyramids in ancient Egypt, for example. It played a key role in global sea trade with the invention of rowing vessels around 300 B.C. Logistics was also one of the main factors for the victory of most wars throughout history.

In military context, logistics is responsible for supplying the troops. It deals with the inventory management and transportation. However, this type of requirement also predominates in carriers and wholesalers activities. Thus, it is natural that modern logistics appears in industry.

Figure 1.1. Example of a supply chain

Nowadays, the function extends from production to distribution, leading to the supply chain (Figure 1.1). In this chain, upstream activities take place prior to a particular link, when the latter orders for material to suppliers in the aim to bring its added value. On the contrary, downstream activities involve the sale of a material to other businesses, governments or private individuals. The extreme link in the upstream part usually concerns raw materials, while the extreme downstream link is related to the final customer. However, each other link in the midstream is both customer of predecessor actors and supplier of successors. Midstream can be a manufacturer, a cooperative warehouse, a regional consolidation center, a city hub, local depot, etc.

Most of the freight transport in the chain is carried in containers, although bulk transport is used more for large volumes of durable goods. The reason is that this option is often the most efficient and cost-effective way to supply the products. However, for the smaller quantities generally required at the final destination, the supply chain is often less efficient. This characteristic is known as the last mile problem, which can represent up to 28% of the total cost to move goods. In addition, if transport plays an important role in economic growth and globalization, it causes air pollution and a large amount of traffic. Hence, a good transport planning is essential to control the costs, as well as the flow and limit nuisances.

Figure 1.2. Possible outline of a reverse logistics chain

In an even more global view, the network also integrates reverse flows. These cover all operations related to the recycling of products and materials thrown away by the public or by industries (obsolete products, mixed waste and even hazardous). The so-called reverse logistics brings together the movements of products from consumers to producers through a distribution chain (Figure 1.2). The growing concern for integrating environmental requirements into green supply chain management concepts and practices makes it even more relevant. The reverse logistics process refers to activities undertaken to reduce, manage and dispose of waste from industrial activities. It meets the need to decommission the products after use and treat the destruction, by transforming or recycling in order to reduce costs, and valuing the recovered products. Several related activities, therefore, involve: collecting waste, the location of recycling points/storage, inventory management and integration of products from the collection at the related industries. It also includes the optimization of the Ecodesign to facilitate future recycling.

Other issues have arisen recently about city logistics which are obviously related to the last mile problem described before. In fact, the freight distribution in urban area has to deal with several aspects. First, traffic may be difficult because of congestion at some rush hours, which makes the travel time dependent on the time of the day. Another particularity is the accessibility constraint. It might be quite complicated to deliver the goods in some areas because of the lack of parking for example, or because of city restrictions on the use of trucks in favor to smaller vehicles. In the same vein, economic and environmental problem concerns might lead to choose alternative types of transport for urban freight distribution (such as electric vehicles), as well as to adopt new commercialization behaviors. For example, the growth of e-commerce brings new questions and some retail companies have studied the use of drones to deliver online purchased goods to consumers.

Hence, many activities are involved in the supply chain, from the network design, to logistics of transportation, passing through warehouse management, international commerce or information systems. Transportation is one of the main parts of logistics. It can be made through several modes such as air, rail, road, water, cable, pipeline and space and may require particular infrastructures (Figure 1.3). These include links in the network (roads, railways, canals or pipelines, for instance) and terminals such as airports, railway stations, warehouses and depots. A wide range of issues emerges in this context, sweeping topics as diverse as the routing, inventory, cross-docking or network structure.

Figure 1.3. Example of transportation modes

1.1.2. Logistics as a science

The logistics function has risen to such an important place that it is now a profession in itself, and even a science. The goal in logistics management is to be efficient and cost-effective across the entire system [BRA 98]. Therefore, the objective is not simply to minimize locally transportation cost or reducing inventories. Every facility that has an impact on system effectiveness must be taken into consideration, from suppliers to retailers through manufacturing facilities, warehouses and distribution centers.

In fact, logistics management encompasses many of the firm’s activities, from the strategic level through the tactical to the operational level:

– the strategic level deals with decisions that have usually a long-term effect. Concerning logistics, this includes, for instance, decisions regarding the number, location and capacities of warehouses and manufacturing plants;

– the tactical level typically includes decisions that are updated anywhere between once every quarter and once every year. This includes purchasing and production decisions, inventory policies and transportation strategies including the frequency with which customers are visited;

– the operational level refers to day-to-day decisions such as scheduling, routing and loading trucks.

Therefore, logistics activities obviously deserve to be recognized as a science, and this has begun to be true from the middle of the 20th Century [TAY 07].

1.1.3. Combinatorial optimization

The science of logistics can be seen as the study of the physical flow of products and services through the supply chain. Therefore, the chain can be seen as a network, or a graph, in which a flow has to go through, with some constraints that need to be encounter and an objective, often relative to a cost function, to optimize. Thus, most of the decision-making to manage the logistics can be taken by modeling the problem in terms of a mathematical program to optimize.

Optimization is a branch of mathematics particularly applied in operations research and management science. It consists of finding one or more best (optimal) solutions from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. The latter case is known as a combinatorial optimization problem. Solving such problems can be a difficult task. The difficulty arises from the fact that feasible solutions belong to a finite but high cardinality set. In fact, finding a global optimum to the problem requires proving that a particular solution dominates all feasible points by arguments other than the calculus based on derivative approaches of convex programming. Therefore, different approaches exist. The simplest one relies on the enumerative techniques, but an exhaustive search is often not possible due to the time required. Other options are, for example, relaxation and decomposition techniques, and cutting planes approaches based on polyhedral combinatorics. An algorithm is usually required to search the solution space, and most often, it cannot find and prove the optimality in polynomial time. In such a case, the problems are said to be NP-hard (non-deterministic polynomial-time hard).

In fact, in many cases, combinatorial optimization problems are NP-hard. Consequently, metaheuristics are mainly developed for real-world problems, which often attain notably high levels of complexity, although they are not able to certify the optimality of the solutions they find.

1.2. Vehicle routing problems

Vehicle routing problems are well-spread combinatorial optimization problems. They can be encountered in various areas, even if their main application stands on logistics of transportation.

1.2.1. Problems in transportation optimization

Truckload transportation from sources to destinations represents a first family of transportation problems, where the amount of goods fully fills a vehicle (or a vehicle carries goods directly from the source to the destination, without any other service on the way). The shortest paths between these sources and destinations are computed, mainly through a graph where vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment, for instance. Then, a typical transportation problem deals with sources, where a supply of some commodity is available, and destinations where the commodity is demanded. The first studies on this subject appeared in the 1930s. An example is Tolstoi who published an article called Methods of finding the minimal total kilometrage in cargo-transportation planning in space, for the freight between sources and destinations along the railway network of the Soviet Union [TOL 30].

In this book, transportation is considered as less-than-truckload: vehicle capacity is large enough to allow servicing several customers without returning to the depot. This leads to interesting combinatorial optimization problems which need to handle routing aspects. In fact, the classical vehicle routing problem (capacitated VRP – CVRP) is an important problem in the fields of logistics and transportation. It consists of the determination of the optimal set of routes to be performed by a vehicle fleet to serve the demand of a given set of customers. With the traveling salesman problem (TSP), it is one of the most important and studied combinatorial optimization problems. Theoretical research on vehicle routing started in 1959 by Dantzig and Ramser with the truck dispatching problem, and it was the beginning of a proliferation of work in this field.

1.2.2. Vehicle routing problems in other contexts

In fact, VRPs belong to a family of problems outreaching the field of transportation optimization, with applications in additional areas, particularly services. In such contexts, a vehicle is more a generic term to represent a mobile that visits a number of sites in order to complete certain tasks. The latter can be pick up or delivery tasks, as well repairs, meter reading or any other activity.

Therefore, a problem can be seen as a VRP when allowed movements describe a graph, and the result must be to visit some arcs or nodes by one or several circuits in this graph, especially with the same start and end point, while respecting a set of constraints. Nowadays, many more examples arise, from helicopters sent to evacuate the casualties after a disaster, to a laser beam that engraves transistors making up the integrated circuits, including inspection of three-dimensional (3D) structures (such as bridge girders) by a robot.

With these numerous applications, utilization of optimization software, based on operations research and mathematical programming techniques, extends to efficiently manage the supply of goods and services. Technological innovations such as geographic information systems, radio frequency identification and