Advertisement
Published in:
2007 | OriginalPaper | Chapter
On the On-Line k-Taxi Problem with Limited Look Ahead
Authors : Weimin Ma, Ting Gao, Ke Wang
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Based on some new results concerning
k
-taxi problem, a new variant of the problem, namely the on-line
k
-taxi problem with limited look ahead (OTLLA) is proposed by our team. Compared with the traditional
k
-taxi problem, in which only the start and end points of the current service request are known at each step, the OTLLA has a basic realistic consideration: the start point of the first service request is given before the whole service sequence plays, and at each step the end of the current service request and the start point of the next service request are known. In this paper, after the formulation of the model of the OTLLA, some results concerning the competitive analysis for some special cases of OTLLA are given: the competitive algorithm so called Partial Greedy Algorithm (PGA) is designed and the competitive ratios are obtained. Furthermore, some comparisons between some on-line algorithms are developed. Finally, some conclusions are given and some future research directions are discussed.