Optimization Of Urban Taxi Dispatch Using Distributed Computation Intelligence

Nowadays,taxi has become a major choice for the public,since taxi ride is convenient,safety and comfortable.With the progress of the GPS and wireless communication technology,some enterprises have established a taxi dispatch system to dispatch the taxis instead of roaming for the passengers to gain more profit and enhance QoS.The scheduling algorithm plays an important role in the taxi dispatch system.Currently,the greedy algorithms have been adopted widely by some taxi dispatch systems.However,the greedy strategy still has shortcomings.There still exist some room to improve the experience of passengers and the profit.In this paper,we have innovatively developed a two-stage framework for the taxi dispatch system: first,a multi-criteria based taxi-passenger matching degree measurement has been performed,then the optimal matching process is conducted based on the measurement result.Based on this framework,we have proposed a novelty taxi dispatch algorithm.In the first stage,we have designed a fuzzy logic system to assign a priority score for each taxi-passenger pair in real time.Moreover,we have extracted three critical attributes from the taxi hailing process to enhance the quality of service and profit.In addition,the fuzzy logic system is optimized by an offline differential evolution method.We have designed a new individual representation method to represent the membership functions.Each individual is companied with a medium-state fuzzy rule table,which is determined automatically by the parameter association scheme.This way,the membership functions and the fuzzy rule base are optimized simultaneously,which can overcome the traditional shortcomings of optimizing a single part.To tackle the long computing time deficiency,we implement this optimizing algorithm in a parallel way by adopting a master-slave parallel model.Then,in the second stage,we regard the taxi-passenger priority scores as a bipartite graph,and apply the Kuhn-Munkres algorithm to find the max weight perfect matching.Finally,we dispatch the taxis based on the matching results.The simulation results also validate the efficiency and the flexibility.The algorithm can provide better experience of the passengers,and gain more profit for the taxi company.