Vehicle routing problems with road-network information: State of the art

Vehicle routing problems have drawn researchers' attention for more than 50 years. Most approaches found in the literature address these problems using the so-called customer-based graph, a complete graph representing the road network, where a node is introduced for every point of interest (eg, customers, depot...) and an arc represents the best path between two points. In many situations, this representation induces negative effects on the solution quality or efficiency. A growing number of works in the literature investigate these issues and propose modeling taking account of more detailed information from the road-network. In this article, we review these works and classify them with respect to the type of negative effects provoked by the customer-based graph.