Extensions of the Petal Method for Vehicle Routeing

Abstract

The petal method for vehicle routeing imposes special structure on the form of a feasible route. In this paper we show that by extending the definition of a petal route, more general forms of vehicle route can be generated without invalidating the important underlying property that optimal petal solutions can be produced very easily. It will also be shown that the optimal generalized petal solution can be produced efficiently by multiple applications of a shortest path algorithm.