A Survey of Heuristics for the Vehicle Routing Problem Part I: Basic Problems and Supply Side Extensions

This survey paper reviews the recent heuristic and metaheuristic solution methods for the well-known capacitated vehicle routing problem and arc routing problem as well as several extensions of the basic problems related to the supply side. Among the discussed extensions are time dependent travel times, multiple use of vehicles, tactical fleet size and mix problem and location-allocation routing. An introduction is provided for each topic and recent heuristic and metaheuristic solution techniques are briefly discussed. For earlier approaches, we refer to previous survey articles. The Vehicle Routing Problem (VRP) is one of the most well-known combinatorial optimization problems, and holds a central place in distribution management and logistics. The objective of the VRP is to deliver or supply a set of customers with known demands on minimum-cost vehicle routes originating and terminating at a central depot. Motivated by significant practical importance as well as considerable computational difficulty, there has been a huge amount of research on VRP and its different practical extensions. The purpose of this two-part survey is to review the recent heuristic solution methods for different multi-vehicle variants of the VRP. We focus on papers written in 1995 or after that. For earlier methods, we refer to previous survey papers. This first part reviews the methods for the basic capacitated vehicle routing problem and arc routing problem, as well as different supply side related extensions such as the fleet size and mix determination and the location of the support facilities. Extensions related to the demand side are discussed in the second part of this surve