Title :
On-Line Taxi Problem on the Benefit-Cost Graphs
Author :
Ma, Wei-min ; Wang, Ke
Author_Institution :
Sch. of Econ. & Manage., Beijing Univ. of Aeronaut. & Astronaut.
Abstract :
Based on the k-taxi problem, the online taxi problem on benefit-cost graphs is proposed in this paper. The optimization of the problem is to maximize the benefit for finishing the whole request sequence under the condition that all requests are revealed with an online fashion. A relevant model is established and some concepts are formulated. After that, some online algorithms are designed and the relevant competitive ratios are obtained and proved. Furthermore, the criterion of charging in this model is discussed at the end of the paper
Keywords :
competitive algorithms; graph theory; greedy algorithms; transportation; benefit-cost graph; greedy algorithms; online taxi problem; optimization; Algorithm design and analysis; Appraisal; Conference management; Costs; Cybernetics; Finishing; Machine learning; Scheduling; Space technology; Technology management; Competitive analysis; Competitive ratio; Competitive strategy; On-line taxi problem;
Conference_Titel :
Machine Learning and Cybernetics, 2006 International Conference on
Conference_Location :
Dalian, China
Print_ISBN :
1-4244-0061-9
DOI :
10.1109/ICMLC.2006.258494
