On the Power of Lookahead in On-Line Vehicle Routing Problems Eztended 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 online 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.
Luca Allulli Giorgio Ausiello Luigi Laura
Dip. di Informatica e Sistemistica Universita di Roma La Sapienza Via Salaria, 113 - 00198 Roma Italy
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
728-736
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）