On-Line Taxi Problem on the Benefit-Cost Graphs
Weimin Ma, Ke Wang · 2006
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