MULTIPLE CAPACITY VEHICLE-ROUTING ON PATHS

Consider the problem of transporting a set of objects between the vert ices of a simple graph by a vehicle that traverses the edges of the gr aph. The problem of finding a shortest tour for the vehicle to transpo rt all objects from their initial vertices to their destination vertic es is called the vehicle routing problem. The problem is multiple capa city if the vehicle can handle more than one objects at a time. The pr oblem is preemptive if objects can be unloaded at the intermediate ver tices. In this paper, we present an O(kn + n(2)) time algorithm for mu ltiple capacity preemptive vehicle routing problem on paths, where k i s the number of objects to be moved and n is the number of vertices in the path.