Metaheuristics for Vehicle Routing Problems

Nacima Labadie, Christian Prins, Caroline Prodhon

• Publisher: Wiley-ISTE
• Year: 2016
• Print ISBN: 9781848218116
• eBook ISBN: 9781119136781
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Engineering
• Index: Computer Science

This book is dedicated to metaheuristics as applied to vehicle routing problems. Several implementations are given as illustrative examples, along with applications to several typical vehicle routing problems.

As a first step, a general presentation intends to make the reader more familiar with the related field of logistics and combinatorial optimization. This preamble is completed with a description of significant heuristic methods classically used 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 vehicle routing problems. 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 others kind of methods.

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 e...

Table of contents

• Cover
• Table of Contents
• Title
• Copyright
• Notations and Abbreviations
• Introduction
• 1 General Presentation of Vehicle Routing Problems
• 2 Simple Heuristics and Local Search Procedures
• 3 Metaheuristics Generating a Sequence of Solutions
• 4 Metaheuristics Based on a Set of Solutions
• 5 Metaheuristics Hybridizing Various Components
• Conclusion
• Bibliography
• Index
• End User License Agreement