Heuristics for vehicle routing on tree-like networks

This paper presents two new heuristics for the vehicle routing problem on tree-like road networks. These networks occur, for example, in rural road systems where the supply (or delivery) nodes are located on rural roads leading off from a few highways which form the ‘trunks’ of a tree-like network. The heuristics have the conventional objective of minimising the total distance travelled by the vehicles. The development of the heuristics takes advantage of the tree-like structure of the network. These two new heuristics and two other heuristics from the published literature are applied to some test problems and computational results are presented. The computational experience indicates that one of the new heuristics provides superior solutions to the existing heuristics and in reasonable computing time. It therefore appears suitable for large-scale practical routing problems.