Research Of Task Allocation Problem Based On Spatial And Social Distance

Task allocation problem is a widely studied problem.Task allocation problem based on spatial distance is a typical application in the service based on location,such as express delivery,service and logistics.The problem of task allocation problem based on spatial distance aims at minimizing the expense of spatial distance.However,in practical application,there are a lot of demands that there have social relationship between clients and service providers,which can affect service effectiveness.Usually,strong social relationships are easier for communication and exchange.For example,when selling insurance,if there have a strong social relationship between sales staff and customers at the same space close proximity,that can easier to build relations between sales staff and customers,to facilitate future communication and cooperation.Based on this requirement,this paper will combine social networking space missions related to the matching problem,and then proposed a problem of task allocation problem based on spatial and social distance.This problem is to find an allocation result,which not only to meet the dual constraints of distance and social relations and meet members of capacity constraints and meet the tasks minimum cost.In this paper,the weighted sum of the space distance and the social distance between the nodes is used as a task cost.The basic matching process is to calculate the cost of all service objects and service objects,and then select the least cost.When the number of the service object and the number of the service are large,the matching efficiency is low.Therefore,this problem can converted multiple optimal bipartite graph matching problem,and use bipartite graph construction method to optimization.This paper presents four types of algorithms to realize the process of bipartite graph multiple optimal matching,the complete bipartite graph match algorithm,the complete bipartite graph match by sort algorithm,the heuristic constructing bipartite graph matching algorithm and the dynamic edge construction matching algorithm.Among them,the complete bipartite graph match algorithm constructs the complete bipartite graph between all candidate member and task according to the social distance and spatial distance.Then the bipartite graph are allocated in order to achieve the exact solution.The algorithm needs to traversal the whole of the candidate sets of member and traverses the sets of tasks,and it has large price.Observely,there are a large number of redundant edges in completely bipartite graph.Therefore,how to construct the bipartite graph with few edges has become a research focus and difficulty problem in this paper.In this paper,we propose a heuristic algorithm of bipartite graph construction.It uses the heuristic algorithm to construct the bipartite graph.It can save the time of construction.It has higher search efficiency,but it is difficult to guarantee the quality.After the completion of the bipartite graph construction,the optimization of the allocation of is the key and difficult problem of this paper.Therefore,this paper presents he complete bipartite graph match by sort algorithm,it is the optimazition of the process of complete bipartite graph matching algorithm.In the matching process added sort to reducing the time allocated.In order to improve the efficiency of the query,this paper proposes a dynamic algorithm to construct the edge.This paper conducts extensive experiments to evaluate the performance of different algorithms and the results of queries through real datasets.At the same time,this paper also analyzes the result of three heuristic constructing bipartite graph matching algorithm through change different parameters.Finally,this paper designs and implements the service class task allocation system based on spatial location and social relations.