Technical Note—Optimizing the Schedule for a Fixed Vehicle Path with Convex Inconvenience Costs

Abstract

We present an algorithm that solves the problem of finding the vehicle schedule which minimizes total inconveniences for travel along a fixed path, where service times at nodes are constrained by time windows and where inconvenience is modeled using convex functions of the service times. This problem occurs as the last step or as a sub-problem in many common approaches to solving routing and scheduling problems. We show that the complexity of the algorithm, expressed as a number of unidimensional minimizations, is on the order of the number of nodes for convex inconvenience functions. For linear and quadratic functions, this complexity is linear in the number of nodes. We present extensions to the case where linear costs are applied to waiting time, and also to the case where the service time variables are discrete.