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.
On the Power of Lookahead in On-line Vehicle Routing Problems / Allulli, L; Ausiello, Giorgio; L., Laura. - 3595:(2005), pp. 728-736. (Intervento presentato al convegno COCOON 2005 tenutosi a Kunming; China nel August 2005) [10.1007/11533719_74].
On the Power of Lookahead in On-line Vehicle Routing Problems
AUSIELLO, Giorgio;
2005
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
