| Article ID: | iaor20115211 |
| Volume: | 19 |
| Issue: | 5 |
| Start Page Number: | 741 |
| End Page Number: | 750 |
| Publication Date: | Aug 2011 |
| Journal: | Transportation Research Part C |
| Authors: | Gendreau Michel, Archetti Claudia, Feillet Dominique, Grazia Speranza M |
| Keywords: | computational analysis, graphs |
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).