Return to results
Journal articles (2011), Transportation Research Part C: Emerging Technologies, 19 (5), pp. 741-750

Complexity of the VRP and SDVRP

ARCHETTI Claudia , Feillet Dominique, Gendreau Michel, Speranza Maria Grazia

In this paper we study the computational complexity of the vehicle routing problem (VRP) and of the split delivery vehicle routing problem (SDVRP) on some special classes of instances, characterized by special structures of the underlying graph, namely a line, a star, a tree and a circle. We both study the problems in the case of unlimited fleet (UF) and under the constraint that a limited fleet is available (LF). Link to the article

ARCHETTI, C., FEILLET, D., GENDREAU, M. and SPERANZA, M.G. (2011). Complexity of the VRP and SDVRP. Transportation Research Part C: Emerging Technologies, 19(5), pp. 741-750.

Keywords : #Vehicle-routing-problem, #Split-delivery-vehicle-routing-problem, #Computational-complexity-on-line, #TreeStar, #Circle