CN111507577A - Crowdsourcing task allocation method based on K-means clustering algorithm - Google Patents

Abstract

The invention discloses a crowdsourcing task allocation method based on a K-means clustering algorithm, which comprises order task clustering analysis and distribution personnel current position clustering analysis. The method has the advantage that the approximate optimal solution with the shortest global path as the target can be quickly and efficiently obtained.

Description

A Crowdsourcing Task Assignment Method Based on K-means Clustering Algorithm

technical field

The invention belongs to the technical field of logistics, and relates to a crowdsourcing task assignment method based on a K-means clustering algorithm.

Background technique

With the rapid development of the Internet industry, e-commerce has also entered a high-speed development mode. In recent years, e-commerce platforms represented by Tmall and JD.com have created huge transaction volume. In 2018, the express delivery business volume exceeded 50 billion pieces. As the basic attribute of e-commerce, logistics distribution has also been challenged unprecedentedly. It is an area that enterprises must overcome in order to improve the platform level and service quality. Terminal logistics is the closest part to the user experience. The convenience, timeliness and safety of distribution will become the direct factors for users to evaluate an e-commerce platform. The traditional distribution mode still has a series of problems such as difficulty in ensuring timeliness, heavy traffic pressure, shortage of distribution manpower and material resources, and weak ability to deal with emergencies. Based on the concept of crowdsourcing, the integration and utilization of idle social distribution resources is the core idea and approach to solve the shortage of human and material resources in this paper. The intelligent matching module uses the K-means clustering algorithm to perform cluster analysis on the location of the cargo and the rider, and then uses the genetic algorithm to obtain the approximate optimal solution with the goal of the shortest global path. The path information is obtained by calling the path planning business of Baidu Maps. . The hitchhiker distribution module makes full use of the idle resources of the society and the advantages of the road, such as delivery on the way to and from get off work, which reduces the scheduling pressure and traffic pressure.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a crowdsourcing task assignment method based on the K-means clustering algorithm, and the beneficial effect of the present invention is to quickly and efficiently obtain an approximate optimal solution aiming at the shortest global path.

The technical scheme adopted by the present invention includes cluster analysis of order tasks and cluster analysis of the current position of delivery personnel.

Further, 1) cluster analysis of order tasks: the server performs cluster analysis for all order tasks to be matched, first query the database to obtain the receiving addresses of all order tasks to be matched, call Baidu Map API address code to obtain the corresponding latitude and longitude coordinates, randomly Select K points as the initial cluster center, traverse all points to obtain the accumulation center with the smallest Euclidean distance, and join the cluster, recalculate the cluster center, and traverse the point set again to determine the cluster to which it belongs, until each cluster is The center coordinates do not change, and the clustering result is obtained;

2) Cluster analysis of the current location of the delivery personnel: The server obtains the current location of the delivery personnel, and calls the Baidu map API address code to obtain the corresponding latitude and longitude coordinates, obtains the cluster analysis result of the order task, traverses the cluster center point set, and calculates the Euclidean The distance judges the cluster to which the delivery person belongs, and writes the cluster information into the matching pool data table;

3) The server-side background prints out the latitude and longitude coordinates of the user's location, and the minimum distance from each cluster center, and finally obtains the clustering result.

Detailed ways

The present invention will be described in detail below with reference to specific embodiments.

The realization process of K-means clustering algorithm is divided into the following four steps:

①Initialize the sample, and randomly select K points from the sample as the initial centroid.

② Calculate the distance from each sample point to each centroid, select the centroid closest to the sample point and add the cluster to which the centroid belongs.

③ Recalculate the centroid points of each cluster.

④ Determine whether the centroid point of each cluster has changed, repeat ②③ if it changes, and get the result if there is no change.

The invention integrates the algorithm into the server side, and only needs to replace the original random coordinate point data set with the latitude and longitude coordinate values of the address to be received in the general cargo package. When the target user initiates a request for a new general package of goods, the K-means algorithm is called once to determine the cluster to which the new order package belongs. When a delivery person initiates a task matching request, according to the user's current positioning information, the Baidu map address coding API is called to obtain the latitude and longitude coordinates of their location. Based on the latitude and longitude coordinates and the cluster analysis results of existing orders, determine the cluster where the delivery personnel are located, and the delivery personnel will assign tasks under the cluster.

The crowdsourcing task assignment method based on the K-means clustering algorithm of the present invention includes the cluster analysis of order tasks and the cluster analysis of the current position of delivery personnel;

1) Cluster analysis of order tasks

The server side performs cluster analysis for all order tasks to be matched. First, query the database to obtain the receiving addresses of all the order tasks to be matched, and call the Baidu Map API address code to obtain the corresponding latitude and longitude coordinates. Randomly select K points as the initial cluster center, traverse all points to obtain the accumulation center with the smallest Euclidean distance, and join the cluster. Recalculate the cluster center, traverse the point set again to determine the cluster to which it belongs, until the coordinates of each cluster center do not change, and obtain the clustering result.

2) Cluster analysis of the current positioning of delivery personnel

The server obtains the current location of the delivery personnel, and calls the Baidu Map API address code to obtain the corresponding latitude and longitude coordinates. Obtain the cluster analysis result of the order task, traverse the cluster center point set, calculate the Euclidean distance to determine the cluster to which the delivery person belongs, and write the cluster information into the matching pool data table.

3) The server-side background prints out the latitude and longitude coordinates of the user's location, and the minimum distance from each cluster center, and finally obtains the clustering result.

The above is only a preferred embodiment of the present invention, and does not limit the present invention in any form. Any simple modifications, equivalent changes and modifications made to the above embodiments according to the technical essence of the present invention belong to the present invention. within the scope of the technical solution of the invention.

Claims (2)

1. A crowd-sourced task allocation method based on a K-means clustering algorithm is characterized by comprising the following steps: the method comprises the steps of order task cluster analysis and distribution personnel current position cluster analysis.

2. The crowdsourcing task allocation method based on the K-means clustering algorithm as claimed in claim 1, wherein: the 1) order task clustering analysis: the server side carries out cluster analysis on all order tasks to be matched, firstly, a database is inquired to obtain receiving addresses of all order tasks to be matched, corresponding longitude and latitude coordinates are obtained by calling Baidu map API address codes, K points are randomly selected to serve as initial cluster centers, all the points are traversed to obtain an accumulation center with the minimum distance between the points and the European-odd-meter-degree distance of the accumulation center, the cluster is added, the cluster centers are recalculated, the cluster sets are traversed again to judge the clusters to which the points belong until the coordinates of all the cluster centers are unchanged, and a cluster result is obtained;

2) and (3) carrying out current positioning clustering analysis on distribution personnel: the server side obtains the current location of the distribution personnel, calls an API address code of a Baidu map to obtain corresponding longitude and latitude coordinates, obtains an order task clustering analysis result, traverses a clustering center point set, calculates the Euclidean distance to judge the cluster to which the distribution personnel belong, and writes the clustering information into a matching pool data table;

3) and the server side background prints and outputs the longitude and latitude coordinates of the position where the user is located and the minimum distance between the server side background and each clustering center, and finally obtains the clustering result of the user.