On the Power of Lookahead in On-line Vehicle Routing Problems

Vehicle Routing Problems are generalizations of the well known Traveling Salesman Problem; we focus on the on-line version of these problems, where requests are not known in advance and arrive over time. We introduce a model of lookeahead for this class of problems, the time lookahead Δ, which allows an on-line algorithm to foresee all the requests that will be released during next Δ time units. We present lower and upper bounds on the competitive ratio of known and studied variants of the OLTsP; we compare these results with the ones from the literature. Our results show that the effectiveness of lookahead varies significantly as we consider different problems. © Springer-Verlag Berlin Heidelberg 2005