A Survey of Heuristics for the Vehicle Routing Problem Part II: Demand Side Extensions

This survey paper presents a review of the recent heuristic and metaheuristic solution techniques for different extensions of the well-known capacitated Vehicle Routing Problem (VRP) that are related to the demand type. Among the discussed topics are VRP with backhauls, pickup and delivery problems, dial-a-ride problems, period- and inventory routing, time window constraints, split deliveries as well as dynamic and stochastic routing problems. An introduction to each extension is provided and the recent heuristic and metaheuristic solution methods are shortly described. 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 different practical extensions of the VRP. The purpose of this two-part survey is to review the recent heuristic and metaheuristic solution methods for different multi-vehicle variants of the VRP. We concentrate on papers written in 1995 or after that. For earlier methods, we refer to previous survey papers. This second part focuses on extensions related to demand side, i.e., the customer. Oppdragsgiver: The Research Council of Norway