Research And Implementation Of Online Task Assignment Algorithm In Spatiotemporal Environment

With the rapid development of the mobile Internet,the technology of task assignment plays an important role in modern applications such as Online To Offline(O2O)service platform and sharing economy model.Meanwhile it's an important problem in the field of intelligent transportation.Compared with the traditional task assignment algorithm,the online task assignment problem has the characteristics of large data size and frequent data changes in space-time environment.In view of the above problems,this paper proposes the algorithm OSBM(Optimal Static Buffer Match),SDBM(Sketch based Dynamic Buffer Maintenance)and TMATCH(Task Match).The paper first proposes an online task allocation algorithm based on the buffer idea to solve the one-to-one task allocation problem.In order to manage dynamic data effectively,the algorithm proposes a strategy of merge and split which based on the results of the grid division and establishes a multi-resolution grid.At the same time,it improves the data management efficiency by pre-processing the historical order data.Subsequently,a static buffer algorithm OSBM is proposed.The algorithm uses the historical order allocation result to describe the curve relationship between response and matching time which in order to improve the performance of the algorithm.Finally,a dynamic algorithm SDBM is proposed.The algorithm uses the information of data distribution to predict the quality of the matching while reducing the maintenance cost of the data by establishing skeleton and joint block.The paper proposes a distributed task matching framework under the road network to solve the one-to-many task assignment problem.A server random selection algorithm is proposed to reduce the cost of data transmission.The algorithm solves the problem of repeated search by reducing the proportion of passengers and taxis in the area where the server nodes are located.Next,an RTI-Tree index is proposed to maintain server.The index builds an R-Tree based on the location of task destination.The index adds an inverted list to the leaf nodes to ensure data maintenance efficiency and improve matching efficiency.Finally,through the operation of combining the task information maintained in each regional server,the framework searches for the optimal matching result by segmenting the taxi travel path.Compared with the existing algorithms,The algorithm and framework proposed in this paper improve the efficiency of data query and the quality of task allocation.Theoretical analysis and experiments verify the efficiency and stability of the algorithm in this paper.