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 two models 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, and the request lookahead, which allows an on-line algorithm to foresee the next k requests that will be released. 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, from the point of view of competitiveanalysis. Even when it does not yield better competitive ratios, lookahead can be used to improve the empirical performance of algorithms: we present the results of an experimental study on algorithmsendowed with time lookahead.