A branch-and-price algorithm for the vehicle routing problem with time windows on a road network

Vehicle routing problems (VRP) concern the pickup and/or the delivery of goods from/to customers with vehicles. In the literature, most approaches consider the road network implicitly. Specifically, so-called customer-based graphs are used where nodes represent customers (plus the depot) and arcs represent best paths between customers. This model can affect solution quality when several attributes are defined on road segments (like travel time and distance). To handle that, two approaches are proposed in the literature. The road network can be represented using a multigraph that extends the customer-based graph and where an arc is introduced for every efficient path between two nodes. Alternatively, the problem can be solved on a graph that mimics the original road network. In this paper, we investigate the latter approach. We consider the VRP with time windows (VRPTW) and we develop a branch-and-price scheme. An extensive computational study based on several types of instances is conducted in order to evaluate this approach compared to the multigraph-based approach. As far as we know, our branch-and-price scheme is the first exact method for the VRPTW with the road-network model. Also, our computational study provides the first comparison between the two models: multigraph and road-network.