Routing a fleet of M vehicles to/from a central facility

Abstract

Abstract In a previous paper, algorithms for optimally routing a single vehicle were presented. In this paper, the problem of routing a fleet of M vehicles serving fixed demand for transportation from many origins to a single destination is considered. The M vehicle General Routing Problem (abbreviated M‐GRP) is the core of many real routing problems, such as school bus routing for a single school (many‐to‐one) and garbage truck routing to a central dump. It is shown that the M‐GRP on a given graph is equivalent to a GRP on a modified graph. From this result, it is shown that single vehicle routing algorithms can be applied to the M vehicle routing problem.