The book is divided into three parts, preceded by an introductory chapter in which we present an overview of the VRP family, define the most important variants of the problem,and introduce the main mathematical models. The first part covers the basic and extensively studied version of the VRP, known as capacitated VRP. Three chapters examine the main exact approaches, while two other chapters review traditional heuristic approaches and metaheuristics,respectively.The second part covers three main variants of the VRP: the VRP with time windows, the VRP with backhauls, and the VRP with pickup and delivery. In each chapter, both exact and heuristic methods are examined. Finally, in the third part, the issues arising in real-world VRP applications, as the presence of dynamic and stochastic components, are discussed by analyzing relevant case studies and presenting software packages.

In the field of combinatorial optimization problems, the Vehicle Routing Problem (VRP) is one of the most challenging. Defined more than 40 years ago, the problem involves designing the optimal set of routes for fleets of vehicles for the purpose of serving a given set of customers . Interest in VRP is motivated by its practical relevance as well as its considerable difficulty.

The Vehicle Routing Problem covers both exact and heuristic methods developed for the VRP and some of its main variants, emphasizing the practical issues common to VRP. The book is composed of three parts containing contributions from well-known experts.The first part covers basic VRP, known more commonly as capacitated VRP. The second part covers three main variants of VRP: with time windows, backhauls, and pickup and delivery. The third part covers issues arising in real-world VRP applications and includes both case studies and references to software packages.

This book will be of interest to both researchers and graduate-level students in the communities of operations research and mathematical sciences. It focuses on a specific family of problems while offering a complete overview of the effective use of the most important techniques proposed for the solution of hard.combinatorial problems. Practitioners will find this book particularly useful.

Reader need a basic knowledge of the main methods for the solution of combinatorial optimization problems.

List of Contributors

Preface

An Overview of Vehicle Routing Problems

1.1 Introduction

1.2 Problem Definition and Basic Notation

  1.2.1 Capacitated and Distance-Constrained VRP

  1.2.2 VRP with Time Windows

  1.2.3 VRP with Back, hauls

  1.2.4 VRP with Pickup and Delivery

1.3 Basic Models for the VRP

  1.3.1 Vehicle Flow Models

  1.3.2 Extensions of Vehicle Flow Models

  1.3.3 Commodity Flow Models

  1.3.4 Set-Partitioning Models

1.4 Test Instances for the CVRP and Other VRPs

Bibliography

Ⅰ Capacitated Vehicle Routing Problem

Ⅱ Important Variants of the Vehicle Routing Problem

Ⅲ Applications and Case Studies