An Efficient Approximation Algorithm for the Fixed Routes Problem

The Fixed Routes Problem is a variation of the Vehicle Routing Problem in which the routes that have to be constructed will be operated unchanged for an extended period of time while the customer demands within that period will vary. If, in a delivery scenario, a vehicle cannot satisfy the demand of a customer it musts return to the depot for replenishment before continuing its route. The fixed routes problem can be modeled as a vehicle routing problem with stochastic demands, which in turn can be solved with a stochastic programming model with recourse. An effective and efficient approximate algorithm to generate fixed routes is presented. It is based on the generalized assignment model for the standard vehicle routing problem. The algorithm consists of two phases. In the first phase, customer demands are considered deterministic and a standard vehicle routing problem is solved to construct an initial set of routes. In the second phase, customer demands are again stochastic and local search methods are applied to find an improved set of routes. Computational experiments show that the algorithm is able to solve realistic problem sizes with acceptable computational times. They also indicate that the travel distance of the fixed routes being generated increases only modestly when the variance of the customer demands is increased. Furthermore, the algorithm compares favorably to the two methods for the vehicle routing with stochastic demands published in the literature.