The problem under study in this paper is a situation where taxis are scattered in the city and a dispatch center receives customers' requests and assigns them to taxis. In this problem, we assume that customers are ready for pickup as soon as they call and we also assume that each customer needs exactly one taxi and has exactly one destination. Also, we assume that taxis always accept the mission according to dispatch center's command.
The classic method for this problem divides the city to some regions and makes a queue from taxis in each region (Silva, 2003). When a new request is received, the dispatch center selects the first taxi from the queue of the region. If there is no taxi available in the caller's region, the center chooses a taxi from top of the queue of one of the neighboring regions. When a taxi fulfills a request, it notifies the center and the taxi is put at the end of the queue of its current region.
Global Positioning Systems (GPS) can provide a modern means for location discovery. Using GPS, the dispatch center may pinpoint the exact location of each taxi at all times. In this method the center does not require to use the queue anymore and when a new request is received, it chooses the nearest taxi to the customer (Lee et al., 2004).