Optimized Taxi Allocation for Time Bound Taxi Requests

Abstract

In the modern world, taxis are becoming a very popular transportation method especially in developing counties. There are many taxi companies worldwide who own a set of taxis and allocate those taxis to each of the taxi requests they receive. There are 2 types of taxi requests namely immediate and advance (time-bound). Immediate requests are in which customers request a taxi as soon as possible. Advance requests are in which customers request a taxi on a future time. While assigning a taxi for an immediate request is simple and straightforward, optimal taxi allocation for advance requests is not a simple task and with the amount of advance taxi requests grown day by day, it has become a necessity to find more optimized ways to allocate taxis for advance taxi requests. The problem addressed in this research consists of 2 parts, which are the core problem of taxi allocation for a set of advance taxi requests and the practical issues related to it such as road traffic, taxi cancelations, waiting times in customer pick locations etc. This research project re-uses the existing concept called ‘chaining’ for the core problem of taxi allocation and proposes a new improved version of it to address the practical issues mentioned above. For each of the practical issues, many possible solutions were considered and based on their advantages and disadvantages, picked a solution and finally combined to one full solution. Then an existing advance taxi allocation algorithm used by one of the premier taxi companies in Sri Lanka was implemented for comparison purposes. Test cases were prepared from real past data such that test cases represent different contexts and each of the test cases was run against the existing taxi allocation algorithm and the newly developed algorithm. The comparison results showed considerable decrease in cost for the taxi company in each of the scenarios. Based on the results, it can be concluded that using the proposed new algorithm for allocating taxis for advance taxi request, leads to less cost which means more profit. This gives a clear competitive advantage for a taxi company over other companies.