CN110826968A - Urban crowdsourcing distribution task optimal scheduling method based on path planning - Google Patents

Abstract

The invention proposes an optimal scheduling method for urban crowdsourcing distribution tasks based on path planning. The method includes: constructing a crowdsourcing distribution network diagram; acquiring crowdsourcing riders and crowdsourcing distribution task information; constructing crowdsourcing distribution tasks based on path planning Optimize the scheduling model; solve the initial crowdsourcing task scheduling scheme based on greedy strategy; optimize the scheduling of crowdsourcing distribution tasks based on variable neighborhood search. The invention can formulate an optimized task scheduling scheme according to the position information of riders, merchants and customers, the time constraints of each task and the real-time load constraints of each rider, including the distribution task set and the shortest distribution path sequence for each rider. It can allocate tasks reasonably, reduce the length of the overall distribution path, and reduce the cost of crowdsourcing distribution.

Description

An optimal scheduling method for urban crowdsourcing distribution tasks based on path planning

technical field

The invention belongs to the field of logistics resource scheduling, and in particular relates to an optimal scheduling method and support tool for urban crowdsourcing distribution tasks based on route planning.

Background technique

With the rapid development of Internet-based e-commerce and O2O industry, people have higher and higher requirements for the timeliness of logistics and distribution. Traditional logistics and distribution are completed by full-time couriers of logistics companies. This distribution method is difficult to respond to many people in time. Consumer service needs. In view of the current shortage of logistics distribution resources, the urban crowdsourcing distribution mode has emerged. Urban crowdsourcing distribution transfers the distribution tasks originally undertaken by the full-time courier personnel of the logistics company to the public groups outside the enterprise to complete in a free and voluntary form. This distribution mode can effectively integrate idle resources in society, ease the pressure of terminal distribution, and play a huge role in solving the "last mile" distribution problem. At present, many urban crowdsourcing delivery service providers have emerged, such as Amazon, Uber, Jingdong crowdsourcing, DianwoDa, etc. Through the crowdsourcing delivery platform Amzon Flex, Amazon recruits part-time drivers with private cars to help deliver parcels and pays them accordingly. Uber, together with local express companies and taxi operators, has established an urban distribution network platform where taxi drivers can deliver the last mile of express delivery on the way.

Urban crowdsourcing delivery services mainly involve four categories of participants: service providers, shippers, customers, and freelance couriers (also known as riders). Service providers are responsible for building a crowdsourcing delivery platform that integrates resources from shippers, customers, and riders, and is the core of urban crowdsourcing delivery services. The shipper publishes the delivery task on the platform, the platform matches the delivery task with the available riders, and assigns the delivery task to the most suitable rider for execution. After the rider receives the delivery task, the rider first picks up the goods at the shipper’s location, and then puts the goods. Delivered to the designated customer location, after receiving the goods, the customer can evaluate the quality of the rider's service through the platform. The main functions of the crowdsourcing distribution platform include participant registration, qualification certification, task allocation, task monitoring, and quality evaluation.

There are two modes of crowdsourcing delivery task assignment: order grabbing mode and order dispatching mode. Order grabbing mode is that riders actively choose distribution tasks according to their own preferences, and order dispatching mode is that the platform allocates distribution tasks according to certain strategies. The designated rider to perform.

At present, there are many studies on the optimal scheduling of urban crowdsourcing distribution tasks under the dispatch mode. These studies either optimize task allocation to improve the task allocation rate and thus optimize task distribution, or optimize the matching relationship between tasks and riders. Which riders are more suitable for the task, or optimize the rider's selection scheme, however, some researches only assign tasks at the starting point of the task, ignoring the task end, task merchant service time and task customer service time, etc. Some other factors that affect task allocation and rider delivery . For the crowdsourcing tasks to be distributed in the city, how to use the crowdsourcing mode to perform better task scheduling to minimize the overall cost or the shortest overall distribution path is a problem that needs to be solved at present.

SUMMARY OF THE INVENTION

The present invention makes the overall distribution path the shortest by optimizing the scheduling of urban crowdsourcing distribution tasks in the order dispatch mode. The present invention provides an optimal scheduling method for urban crowdsourcing distribution tasks based on path planning, comprising the following steps:

Step 1: Build a crowdsourcing distribution network diagram;

Step 2: Obtain crowdsourcing rider and crowdsourcing delivery task information;

Step 3: Build a crowdsourcing distribution task optimization scheduling model based on path planning;

Step 4: Solve the initial crowdsourcing task scheduling scheme based on the greedy strategy;

Step 5: Optimizing the scheduling of crowdsourcing distribution tasks based on variable neighborhood search.

In a further technical solution, in the step 1, the construction of a crowdsourcing distribution network diagram is as follows:

The crowdsourcing distribution network graph can be represented as a graph G=(V,E), where V=V _S ∪VC _C is a set of nodes, each node represents a merchant or customer, V _S ={1,2,...,n _s } is the set of merchants, V _C ={n _s +1,n _s +2,...,n _c } is the set of customers, _ns and n _c are the number of merchants and customers respectively; E={(i, j)|i,j∈V} is a set of edges, for each edge (i,j)∈E, d _ij represents the distance between node i and node j, d _ij =d _ji , di _ii =0.

In a further technical solution, in the step 2, the details of obtaining crowdsourcing riders and crowdsourcing delivery task information are as follows:

The crowdsourced riders are denoted as the set K={1,2,…, _nk }, where _nk is the number of crowdsourced riders, for each rider k∈K, Qk denotes the maximum load capacity of rider k, _vk denotes the rider _k The average travel speed of k, d′ _ki represents the distance of rider k from the location to node i∈V;

The crowdsourcing delivery task is represented as a set T={1,2,…,n _t }, where _nt is the number of delivery tasks, and each delivery task t∈T is represented as a hexagram: (s _t ,c _t ,b _t , f _t , e _t , w _t ), where s _t ∈ V _S represents the pickup merchant of task t, c _t ∈ V _C represents the delivery customer of task t, b _t represents the earliest start time of task t, That is, the earliest pickup time from the merchant s _t , ft represents the latest start time of the task _t , that is, the latest pickup time from the merchant s _t , and e _t represents the latest end time of the task t, that is, the delivery of the goods. To the latest end time of customer c _t , w _t represents the cargo weight of task t, and the cargo weight of each delivery task does not exceed the maximum load of any rider, that is, wt _t ≤min{Q _k |k∈K};

For each node i ∈ V, let s _i denote the average service time of each task at node i, if i ∈ V _S , s _i denote the average pickup time of riders at merchant i, and if i ∈ V _C , s _i Represents the average delivery time of the rider at customer i, and the average service time of the task is calculated by mathematical statistics based on historical data.

In a further technical solution, in the step 3, building a crowdsourcing distribution task optimization scheduling model based on path planning is as follows:

Establish a task distribution scheme: A task distribution scheme is expressed as a mapping function a:T→K∪{0} from the crowdsourced delivery task set T to the crowdsourced rider set K, for a task t∈T, if a(t)=k ∈K means that the task t is assigned to the rider k for delivery, if a(t)=0, it means that the task t is not assigned; let T _a (k)={t∈T|a(t)=k,k∈ K} denotes the set of tasks assigned to rider k, if Indicates that no delivery task is assigned to rider k; let T _a denote the set of all assigned tasks, then T _a = ∪ _k∈K T _a (k); there are many assignment schemes from set T to set K, let Ω(T, K) represents the set of all task assignment schemes from T to K;

T_a(k)的一个任务序列为多重集

的一个全排列，表示为：p_ak＝p_ak(1),p_ak(2),…,p_ak(2|T_a(k)|)，其中，p_ak(j)为任务序列p_ak中第j(j＝1,2,…,2|T_a(k)|)个位置所对应的任务；Define the task sequence and delivery path: a is represented as a task assignment scheme, a ∈ Ω(T, K), and the task set assigned to rider k is represented as

A task sequence of T _a (k) is a multiset

A full permutation of , expressed as: p _ak =p _ak (1),p _ak (2),...,p _ak (2|T _a (k)|), where p _ak (j) is the task sequence p _ak The task corresponding to the jth (j=1,2,...,2|T _a (k)|) position;

a∈Ω(T,K) is a task assignment scheme, T _a (k) is a set of tasks assigned to rider k, p _ak ∈ P _a (k) is a task sequence, then the distribution path of p _ak is a sequence starting from the position of rider k and passing through the merchant or customer node corresponding to each task in p _ak in turn, expressed as v _ak = v _ak (0), v _ak (1),..., v _ak ( 2|T _a (k)|), where v _ak (0)=k, represents the position of rider k, and v _ak (j) represents the jth (j ₌ 1, 2,… ,2|T _a (k)|) The nodes corresponding to the tasks, since each task in the task sequence occurs twice - pick up and delivery, we stipulate that the nodes corresponding to the tasks in the front are merchant nodes , the node corresponding to the task in the back row is the client node;

其中，p_ak∈P_a(k)为一个任务序列，v_ak为所对应的配送路径，

表示从骑手k(k＝v_ak(0))到第一个节点v_ak(1)的距离，

表示v_ak中相邻两个节点之间的距离之和，如果两个相邻节点为同一个节点，则其距离为0；The delivery distance function is expressed as

Among them, p _ak ∈ P _a (k) is a task sequence, v _ak is the corresponding delivery path,

represents the distance from rider k (k=v _ak (0)) to the first node v _ak (1),

Represents the sum of the distances between two adjacent nodes in v _ak , if the two adjacent nodes are the same node, the distance is 0;

Set time constraints and load constraints: The time constraint function is expressed as H(p _ak ,t)∈{true,false}, where t∈T _a (k) is a task, and p _ak ∈ P _a (k) is expressed as A task sequence, if task t delivers goods according to the delivery path v _ak corresponding to p _ak and satisfies the constraints of the merchant’s latest pick-up time and the customer’s latest delivery time, then H(p _ak ,t)=true, otherwise , H(p _ak ,t)=false;

The load constraint function is expressed as Q(p _ak )∈{true,false}, where p _ak ∈ P _a (k) is a task sequence, if rider k can deliver goods according to the delivery path v _ak corresponding to the task sequence p _ak . Satisfy its maximum load constraint, then Q(p _ak )=true, otherwise Q(p _ak )=false;

The optimal scheduling model for crowdsourcing distribution tasks based on path planning is defined as:

max∑ _k∈K |T _a (k)| (1)

min∑ _k∈K d(p _ak ) (2)

s.t.

Q(p _ak )=true p _ak ∈P _a (k) (3)

H(p _ak )=true p _ak ∈P _a (k) (4)

p _ak ∈P _a (k)a∈Ω(T,K),k∈K (5)

a∈Ω(T,K )(6).

In a further technical solution, in the step 4, the solution of the initial crowdsourcing task scheduling scheme based on the greedy strategy is as follows:

Define T ⁰ _a (k) as the task set currently assigned to rider k, p ⁰ _ak as the task sequence that rider k currently satisfies the constraints, i∈T-∪ _k∈K T ⁰ _a (k) is an unassigned task sequence If the new task sequence obtained by inserting i into two appropriate positions of p ⁰ _ak still satisfies the load and time constraints, then i is called an extensible task of p ⁰ _ak , T ¹ _a (k)= T ⁰ _a (k)∪{i} is the task set of rider k after inserting task i;

There are two ways to insert task i into task sequence p ⁰ _ak : adjacent and separated; adjacent insertion means that after task i is inserted into p ⁰ _ak , the two positions of task i in the new task sequence are adjacent; Spaced insertion means that after task i is inserted into p ⁰ _ak , the two positions of task i in the new task sequence are not adjacent;

Specific steps are as follows:

Step 1: According to the position of the rider k _i , obtain the distance set S between the rider k _i and all the merchants with undelivered tasks, and obtain the shortest path length set D of all undelivered tasks. Add the corresponding subscript values of the two sets, and press Add and sort from small to large, and save it to the task assignment sequence T ⁰ _a ( _ki );

Step 2: Select the first task t ₁ at T ⁰ _a ( _ki ), add this task to the task delivery sequence p _a ( _ki ) of rider _ki , as the first delivery task of rider _ki , and at the same time The task status is set to delivered status;

Step 3: Add a second task, add each task t ₂ , t ₃ ,..., t _j in T ⁰ _a ( _ki ) to p _a ( _ki ) using adjacent and spaced insertion strategies , if p _a ( _ki ) obtained by one of the insertion strategies satisfies the time constraints of t ₁ and t _j , and the capacity constraints of rider _ki , then save task t _j is added to the rider’s task distribution sequence p according to the insertion strategy The position of _a (k _i ) and the path length are added to the sequence R. After all tasks are inserted once, the sequence R is arranged in ascending order. The task t _j with the smallest path length is used as the second delivery task, and is added to p _a according to the insertion position. In (k _i ), at the same time, the new task distribution sequence _{p a} ( _{k i} ) is used as the task distribution sequence for adding the next task, and the state of t _j becomes distributed; If the constraint is not satisfied, then p _a ( _ki ) is the task distribution sequence of the final rider _ki ;

Step 4: When the sequence R is empty, obtain the V _aki of the rider _ki according to the p _a ( _ki ) and the task relationship diagram, and obtain the path length d (p _aki ) of the rider _ki to deliver the p _a ( _ki ) at the same time; Let i=i+1, return to Step 2;

Step 5: When i=L+1 or the status of all tasks is delivered, the algorithm ends and the initial solution set is obtained.

In a further technical solution, in the step 5, the optimal scheduling of the crowdsourcing distribution task based on the variable neighborhood search includes four neighborhood structures, which are:

(1) Two random riders and two random tasks in their task sequence are exchanged;

(2) Randomly exchange merchant points of two tasks in a rider's task sequence;

(3) Randomly swap the client points of two tasks in a rider's task sequence;

(4) Two random riders, the tasks in the task sequence of one rider are randomly added to the task sequence of the other rider;

Specific steps are as follows:

Step 1: Obtain the initial solution p _ak of rider k, and set the optimal solution to be p _{ak_best} ;

Step 2: Define the neighborhood structure set N _i , i=1,2...,i _max as the perturbation operation, where N _i includes the task of exchanging riders, exchanging task sequence business point operations, exchanging task sequence customer point operations and transferring rider tasks operate;

Step 3: Define the neighborhood structure set N _j , j=1,2...,j _nax as the neighborhood search, where N _j includes the exchange rider task operation, the exchange task sequence merchant point operation, the exchange task sequence customer point operation and the transfer rider task operation;

Step 4: Let i=1, j=1;

Step 5: Use Ni to _perturb p _ak to generate a solution p'_ak;

Step 6: Use N _j to search for p' _ak to generate the solution p"_ak;

Step 7: If d(p' _ak )<d(p" _ak ), then p' _ak =p" _ak , j=1; otherwise, j=j+1;

Step 8: If j<j _nax , jump to Step 6; otherwise, execute Step 9;

Step 9: If d(p” _ak )<d(p _ak ), then p _ak =p” _ak , i=1; otherwise, i=i+1;

Step 10: If i<i _max , then jump to Step 5; otherwise, p _{ak_best} = p” _ak , execute Step 11;

Step 11: Input the optimal solution p _{ak_best} , and the algorithm ends.

The invention also provides a support tool for realizing the optimal scheduling method for urban crowdsourcing distribution tasks based on path planning.

The functional modules of the support tool are mainly divided into the Web side and the App side. It is divided into two modules: basic information management and crowdsourcing task scheduling management.

(1) The functions of basic information management include: user information management, order management and rider information management, etc.

(2) Crowdsourcing task scheduling management is to allocate task orders. The functions include: task scheduling algorithm management, task path planning, real-time task assignment and assignment result management, etc. Customers can place orders on the Web or App, and the support tool assigns tasks to riders through scheduling algorithms. After the rider successfully logs in to the App, he accepts the assigned task and delivers it according to the path planned by the algorithm.

As can be seen from the above technical solutions, the present invention has the following advantages:

The crowdsourcing distribution network diagram can formally map the actual location points to the location points in the coordinate system, analyze the main information of the crowdsourcing riders and the crowdsourcing distribution tasks to ensure the validity of the information, and vividly depict the relationship between the tasks and the riders. and modeling the task sequence, distribution path and distribution path length, determine the relationship between task sequence and task set, analyze the relationship between task sequence and distribution path, set time constraints and load constraints to constrain each task sequence At the same time, define the optimal scheduling model of crowdsourcing distribution tasks based on path planning, determine the optimization objectives and constraints, solve the initial crowdsourcing task scheduling scheme based on the greedy strategy, and optimize the scheduling of crowdsourcing distribution tasks based on variable neighborhood search. Reasonably assign tasks, reduce the length of the overall distribution path, and reduce distribution costs.

Description of drawings

In order to illustrate the technical solutions of the present invention more clearly, the accompanying drawings required in the description will be briefly introduced below. Obviously, the accompanying drawings in the following description are only some embodiments of the present invention, which are not relevant to ordinary skills in the art. As far as personnel are concerned, other drawings can also be obtained from these drawings on the premise of no creative work.

Fig. 1 is the flow chart of the optimal scheduling method for urban crowdsourcing distribution tasks based on route planning;

2 is a schematic diagram of a crowdsourcing distribution network of the present invention;

Fig. 3 is the schematic diagram of obtaining crowdsourcing riders and crowdsourcing distribution tasks of the present invention;

FIG. 4 is a flowchart of an algorithm for solving an initial crowdsourcing task scheduling scheme based on a greedy strategy of the present invention.

FIG. 5 is a flow chart of the optimal scheduling algorithm for crowdsourcing distribution tasks based on variable neighborhood search according to the present invention.

Detailed ways

The present invention provides an optimal scheduling method for urban crowdsourcing distribution tasks based on path planning, as shown in Figures 1 to 5, the method includes:

Step 1: Build a crowdsourcing distribution network diagram;

Step 2: Obtain crowdsourcing rider and crowdsourcing delivery task information;

Step 3: Build a crowdsourcing distribution task optimization scheduling model based on path planning;

Step 4: Solve the initial crowdsourcing task scheduling scheme based on the greedy strategy;

Step 5: Optimizing the scheduling of crowdsourcing distribution tasks based on variable neighborhood search.

In order to make the purpose, features and advantages of the present invention more obvious and understandable, the following will use specific embodiments and accompanying drawings to clearly and completely describe the technical solutions protected by the present invention. Obviously, the implementation described below Examples are only some embodiments of the present invention, but not all embodiments. Based on the embodiments in this patent, all other embodiments obtained by persons of ordinary skill in the art without creative efforts shall fall within the scope of protection of this patent.

Step 1: The crowdsourcing distribution network graph can be expressed as graph G=(V, E), where V=VS _{∪VC C} is a set of nodes, each node represents a merchant or customer, and V _S = {1, 2, ...,n _s } is the set of merchants, V _C ={ _{ns +1,n s +2} ,...,n _c } is the set of customers, _ns and n _c are the number of merchants and customers respectively; E = { (i,j)|i,j∈V} is a set of edges, for each edge (i,j)∈E, d _ij represents the distance between node i and node j, d _ij =d _ji ,d _ii =0.

The present invention maps the actual location points, including merchant points, customer points, etc., into nodes of the graph, and expresses the position of each node with two-dimensional coordinates (x, y). There are edges between nodes, and nodes are connected to The distance between nodes is calculated using the coordinates of the nodes.

Figure 2 depicts the nodes that map the actual locations of merchants and customers into a graph, there are 10 location points in total, including 3 merchants and 7 customers, i.e., V _S ={1,2,3}, V _C ={4,5,...,10}, eg node 1 represents business 1. A diagram of a crowdsourced distribution network is obtained.

Step 2: The crowdsourced riders are denoted as the set K = {1,2,..., _nk }, where _nk is the number of crowdsourced riders, for each rider k∈K, Qk denotes the maximum load capacity of rider _k , v _k represents the average driving speed of rider k, and d′ _ki represents the distance from the location of rider k to node i∈V;

The crowdsourcing delivery task is represented as a set T={1,2,…,n _t }, where _nt is the number of delivery tasks, and each delivery task t∈T is represented as a hexagram: (s _t ,c _t ,b _t , f _t , e _t , w _t ), where s _t ∈ V _S represents the pickup merchant of task t, c _t ∈ V _C represents the delivery customer of task t, b _t represents the earliest start time of task t, That is, the earliest pickup time from the merchant s _t , ft represents the latest start time of the task _t , that is, the latest pickup time from the merchant s _t , and e _t represents the latest end time of the task t, that is, the delivery of the goods. To the latest end time of customer c _t , w _t represents the cargo weight of task t, and the cargo weight of each delivery task does not exceed the maximum load of any rider, that is, wt _t ≤min{Q _k |k∈K};

For each node i ∈ V, let s _i denote the average service time of each task at node i, if i ∈ V _S , s _i denote the average pickup time of riders at merchant i, and if i ∈ V _C , s _i Represents the average delivery time of the rider at customer i, and the average service time of the task is calculated by mathematical statistics based on historical data.

The invention configures crowdsourcing riders and crowdsourcing tasks into a crowdsourcing distribution network diagram, and obtains the position of each rider, basic information of each rider and basic information of each task through Internet technology and Internet of Things technology. The riders and tasks are numbered, and the rider information and task information are stored in the database. According to the task information, the merchant node and customer node of the task will be determined.

Figure 3 depicts a crowdsourcing distribution network diagram after crowdsourcing rider and crowdsourcing task configuration, there are 3 riders in total, namely, K={1, 2, 3}, the main information of the rider includes the rider number, the rider's maximum load and the average speed of the rider is shown in Table 1. There are 7 delivery tasks in total, namely, T={1,2,…,7}. The main information of the task includes task number, merchant, customer, cargo weight, merchant service time, customer service time, earliest pick-up time, latest The pickup time and latest delivery time are shown in Table 2.

Table 1 Rider Main Information Sheet

rider number Maximum load (kg) Average speed (m/s) 1 3 3 2 4 3 3 3 3

Table 2 Task main information table

表示没有给骑手k分配配送任务；令T_a表示所有被分配的任务集合，则T_a＝∪_k∈KT_a(k)；从集合T到集合K存在许多分配方案，令Ω(T,K)表示从T到K的所有任务分配方案的集合；Step 3: Establish a task distribution scheme: A task distribution scheme is expressed as a mapping function a:T→K∪{0} from the crowdsourced delivery task set T to the crowdsourced rider set K, for a task t∈T, if a(t )=k∈K, indicating that task t is assigned to rider k for delivery, if a(t)=0, indicating that task t is not assigned; let T _a (k)={t∈T|a(t)=k ,k∈K} denotes the set of tasks assigned to rider k, if

means that no delivery task is assigned to rider k; let T _a denote the set of all assigned tasks, then T _a = ∪ _k∈K T _a (k); there are many assignment schemes from set T to set K, let Ω(T, K) represents the set of all task assignment schemes from T to K;

T_a(k)的一个任务序列为多重集

的一个全排列，表示为：p_ak＝p_ak(1),p_ak(2),…,p_ak(2|T_a(k)|)，其中，p_ak(j)为任务序列p_ak中第j(j＝1,2,…,2|T_a(k)|)个位置所对应的任务；Define the task sequence and delivery path: a is represented as a task assignment scheme, a ∈ Ω(T, K), and the task set assigned to rider k is represented as

A task sequence of T _a (k) is a multiset

A full permutation of , expressed as: p _ak =p _ak (1),p _ak (2),...,p _ak (2|T _a (k)|), where p _ak (j) is the task sequence p _ak The task corresponding to the jth (j=1,2,...,2|T _a (k)|) position;

a∈Ω(T,K) is a task assignment scheme, T _a (k) is a set of tasks assigned to rider k, p _ak ∈ P _a (k) is a task sequence, then the distribution path of p _ak is a sequence starting from the position of rider k and passing through the merchant or customer node corresponding to each task in p _ak in turn, expressed as v _ak = v _ak (0), v _ak (1),..., v _ak ( 2|T _a (k)|), where v _ak (0)=k, represents the position of rider k, and v _ak (j) represents the jth (j ₌ 1, 2,… ,2|T _a (k)|) The nodes corresponding to the tasks, since each task in the task sequence occurs twice - pick up and delivery, we stipulate that the nodes corresponding to the tasks in the front are merchant nodes , the node corresponding to the task in the back row is the client node;

其中，p_ak∈P_a(k)为一个任务序列，v_ak为所对应的配送路径，

表示从骑手k(k＝v_ak(0))到第一个节点v_ak(1)的距离，

表示v_ak中相邻两个节点之间的距离之和，如果两个相邻节点为同一个节点，则其距离为0；The delivery distance function is expressed as

Among them, p _ak ∈ P _a (k) is a task sequence, v _ak is the corresponding delivery path,

represents the distance from rider k (k=v _ak (0)) to the first node v _ak (1),

Represents the sum of the distances between two adjacent nodes in v _ak , if the two adjacent nodes are the same node, the distance is 0;

Set time constraints and load constraints: The time constraint function is expressed as H(p _ak ,t)∈{true,false}, where t∈T _a (k) is a task, and p _ak ∈ P _a (k) is expressed as A task sequence, if task t delivers goods according to the delivery path v _ak corresponding to p _ak and satisfies the constraints of the merchant’s latest pick-up time and the customer’s latest delivery time, then H(p _ak ,t)=true, otherwise , H(p _ak ,t)=false;

The load constraint function is expressed as Q(p _ak )∈{true,false}, where p _ak ∈ P _a (k) is a task sequence, if rider k can deliver goods according to the delivery path v _ak corresponding to the task sequence p _ak . Satisfy its maximum load constraint, then Q(p _ak )=true, otherwise Q(p _ak )=false;

The optimal scheduling model for crowdsourcing distribution tasks based on path planning is defined as:

max∑ _k∈K |T _a (k)| (1)

min∑ _k∈K d(p _ak ) (2)

s.t.

Q(p _ak )=true p _ak ∈P _a (k) (3)

H(p _ak )=true p _ak ∈P _a (k) (4)

p _ak ∈P _a (k)a∈Ω(T,K),k∈K (5)

a∈Ω(T,K) (6).

The invention defines a crowdsourced distribution task optimization scheduling model based on path planning, and aims to achieve the shortest overall distribution path under the condition that the number of distributed tasks is the largest. The task allocation scheme and task sequence are constructed. The distribution distance function, time constraint function and load constraint function are constructed. Each rider can correspond to multiple task assignment schemes, and each task assignment scheme corresponds to multiple task sequences. The length of the delivery path of the task sequence is determined by the delivery distance function, and then the task sequence with the smaller delivery path is selected by comparing the size. The time constraint function and the load constraint function are used to determine whether each task sequence satisfies the conditions, and if not, it is discarded.

Step 4: Define T ⁰ _a (k) as the task set currently assigned to rider k, p ⁰ _ak as the task sequence that rider k currently satisfies the constraints, i∈T-∪ _k∈K T ⁰ _a (k) is a For an unassigned task, if the new task sequence obtained by inserting i into two appropriate positions of p ⁰ _ak still satisfies the load and time constraints, then i is called a scalable task of p ⁰ _ak , T ¹ _a ( k)=T ⁰ _a (k)∪{i} is the task set of rider k after inserting task i;

There are two ways to insert task i into task sequence p ⁰ _ak : adjacent and separated; adjacent insertion means that after task i is inserted into p ⁰ _ak , the two positions of task i in the new task sequence are adjacent; Spaced insertion means that after task i is inserted into p ⁰ _ak , the two positions of task i in the new task sequence are not adjacent;

Specific steps are as follows:

Step 1: According to the position of the rider k _i , obtain the distance set S between the rider k _i and all the merchants with undelivered tasks, and obtain the shortest path length set D of all undelivered tasks. Add the corresponding subscript values of the two sets, and press Add and sort from small to large, and save it to the task assignment sequence T ⁰ _a ( _ki );

Step 2: Select the first task t ₁ at T ⁰ _a ( _ki ), add this task to the task delivery sequence p _a ( _ki ) of rider _ki , as the first delivery task of rider _ki , and at the same time The task status is set to delivered status;

Step 3: Add a second task, add each task t ₂ , t ₃ ,..., t _j in T ⁰ _a ( _ki ) to p _a ( _ki ) using adjacent and spaced insertion strategies , if p _a ( _ki ) obtained by one of the insertion strategies satisfies the time constraints of t ₁ and t _j , and the capacity constraints of rider _ki , then save task t _j is added to the rider’s task distribution sequence p according to the insertion strategy The position of _a (k _i ) and the path length are added to the sequence R. After all tasks are inserted once, the sequence R is arranged in ascending order. The task t _j with the smallest path length is used as the second delivery task, and is added to p _a according to the insertion position. In (k _i ), at the same time, the new task distribution sequence p _a (k _i ) is used as the task distribution sequence for adding the next task, and the state of t _j becomes distributed; if the p _a (k _i ) obtained by all insertion strategies are If the constraint is not satisfied, then p _a ( _ki ) is the task distribution sequence of the final rider _ki ;

Step 4: When the sequence R is empty, obtain the V _aki of the rider _ki according to the p _a ( _ki ) and the task relationship diagram, and obtain the path length d (p _aki ) of the rider _ki to deliver the p _a ( _ki ) at the same time; Let i=i+1, return to Step 2;

Step 5: When i=L+1 or the status of all tasks is delivered, the algorithm ends and the initial solution set is obtained.

The invention defines an initial crowdsourcing task scheduling scheme solution algorithm based on a greedy strategy, and the core idea is to use the greedy strategy to find the current optimal task scheduling scheme for each rider.

Figure 4 describes the flow of the initial crowdsourcing task scheduling solution solution algorithm based on the greedy strategy.

Step 5: Include four neighborhood structures, namely:

(1) Two random riders and two random tasks in their task sequence are exchanged;

(2) Randomly exchange merchant points of two tasks in a rider's task sequence;

(3) Randomly swap the client points of two tasks in a rider's task sequence;

(4) Two random riders, the tasks in the task sequence of one rider are randomly added to the task sequence of the other rider;

Specific steps are as follows:

Step 1: Obtain the initial solution p _ak of rider k, and set the optimal solution to be p _{ak_best} ;

Step 2: Define the neighborhood structure set N _i , i=1,2...,im _ax as the perturbation operation, where N _i includes the task of exchanging riders, exchanging task sequence merchant point operations, exchanging task sequence customer point operations and transferring rider tasks operate;

Step 3: Define the neighborhood structure set N _j , j=1,2..., _jmax as the neighborhood search, where N _j includes the exchange rider task operation, the exchange task sequence merchant point operation, the exchange task sequence customer point operation and the transfer rider task operation;

Step 4: Let i=1, j=1;

Step 5: Use Ni to _perturb p _ak to generate a solution p'_ak;

Step 6: Use N _j to search for p' _ak to generate the solution p"_ak;

Step 7: If d(p' _ak )<d(p" _ak ), then p' _ak =p" _ak , j=1; otherwise, j=j+1;

Step 8: If j<j _max , then jump to Step 6; otherwise, execute Step 9;

Step 9: If d(p” _ak )<d(p _ak ), then p _ak =p” _ak , i=1; otherwise, i=i+1;

Step 10: If i<i _max , then jump to Step 5; otherwise, p _{ak_best} = p” _ak , execute Step 11;

Step 11: Input the optimal solution p _{ak_best} , and the algorithm ends.

The invention proposes a crowdsourcing distribution task optimization scheduling algorithm based on variable neighborhood search. The core idea is to allocate tasks and calculate the overall distribution path length through three processes of local search, disturbance and neighborhood structure search. The task assignment results are shown in Table 3, the rider distribution task results are shown in Table 4, and the rider distribution path results are shown in Table 5.

Figure 5 depicts the flow of the optimal scheduling algorithm for crowdsourcing distribution tasks based on variable neighborhood search.

Table 3 Task allocation table

rider number task assignment set 1 2, 4, 6 2 3 3 1, 5

Table 4 Rider distribution task table

rider number task sequence 1 6→6→2→4→2→4 2 3→3 3 1→5→1→5

Table 5 Rider distribution route table

rider number path sequence Total path length (m) 1 1→9→3→3→5→7 3543 2 1→6 1921 3 2→2→4→8 2523

The invention also provides a support tool for realizing the optimal scheduling method for urban crowdsourcing distribution tasks based on path planning.

The functional modules of the support tool are mainly divided into the Web side and the App side. It is divided into two modules: basic information management and crowdsourcing task scheduling management.

(1) The functions of basic information management include: user information management, order management and rider information management, etc.

(2) Crowdsourcing task scheduling management is to allocate task orders. The functions include: task scheduling algorithm management, task path planning, real-time task assignment and assignment result management, etc. Customers can place orders on the web or app, and the support tool assigns tasks to riders through scheduling algorithms. After the rider successfully logs in to the App, he accepts the assigned task and delivers it according to the path planned by the algorithm.

The above description of the disclosed embodiments enables any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be implemented in other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein, but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (6)

1. A city crowdsourcing distribution task optimization scheduling method based on path planning is characterized by comprising the following steps:

step 1: constructing a crowdsourcing distribution network graph;

step 2: acquiring crowdsourcing riders and crowdsourcing distribution task information;

and step 3: constructing a crowdsourcing distribution task optimization scheduling model based on path planning;

and 4, step 4: solving the initial crowdsourcing task scheduling scheme based on a greedy strategy;

and 5: and performing optimized scheduling on the crowdsourcing distribution task based on variable neighborhood search.

2. The city crowdsourcing distribution task optimization scheduling method based on path planning as claimed in claim 1, wherein the step 1, the crowdsourcing distribution network graph is constructed as follows:

the crowdsourcing distribution network graph may be represented as graph G ═ (V, E), where V ═ V_S∪V_CFor a collection of nodes, each node representing a merchant or customer, V_S＝{1,2,…,n_sIs the set of merchants, V_C＝{n_s+1,n_s+2,…,n_cIs a set of clients, n_sAnd n_cThe number of merchants and customers, respectively; e { (i, j) | i, j ∈ V } is a set of edges, and each edge (i, j) ∈ E, d_ijRepresents the distance between node i and node j, d_ij＝d_ji，d_ii＝0。

3. The optimal scheduling method for urban crowdsourcing distribution tasks based on path planning as claimed in claim 2, wherein in the step2, the information of crowdsourcing riders and crowdsourcing distribution tasks is obtained as follows:

the crowd-sourced rider is represented as the set K ═ {1,2, …, n_k}，n_kFor crowdsourced rider numbers, K ∈ K, Q for each rider_kRepresents the maximum load capacity, v, of rider k_kRepresents the average running speed of rider k, d'_kiRepresenting the distance from the position of the rider k to the node i ∈ V;

the crowdsourced delivery task is represented as the set T ═ {1,2, …, n_t}，n_tFor the number of delivery tasks, each delivery task te ∈ T is represented as a six-tuple: (s)_t,c_t,b_t,f_t,e_t,w_t) Wherein s is_t∈V_SPick-up merchant, c, representing task t_t∈V_CDelivery client representing task t, b_tIndicating the earliest starting time of task t, i.e. from merchant s_tThe earliest time of starting to take goods, f_tIndicating the latest start of task tFrom merchants s_tThe latest starting time of picking up goods, e_tIndicating the latest end time of task t, i.e. delivery of goods to client c_tLatest end time of, w_tRepresenting the weight of the load at task t, the weight of the load at each delivery task not exceeding the maximum load of any rider, i.e. w_t≤min{Q_k|k∈K}；

For each node i ∈ V, let s_iRepresents the average service time per task at node i if i ∈ V_S，s_iRepresents the average pick-up time of the rider at the merchant i if i ∈ V_C，s_iThe average delivery time of the rider at the client i and the average service time of the task are calculated by a mathematical statistic method according to historical data.

4. The method for optimizing and scheduling urban crowdsourcing distribution tasks based on path planning according to claim 3, wherein in the step 3, the modeling of the optimal scheduling of the crowdsourcing distribution tasks based on path planning is specifically as follows:

establishing a task distribution scheme, namely, expressing a task distribution scheme as a mapping function a from a crowd-sourced task distribution set T to a crowd-sourced rider set K, T → K ∪ {0}, and for a task T epsilon T, if a (T) is equal to K epsilon K, expressing that the task T is distributed to the rider K, and if a (T) is equal to 0, expressing that the task T is not distributed, and enabling T to be expressed as T_a(k) K ∈ K, if the task set is assigned to rider K

Indicating that no delivery task has been assigned to rider k; let T_aRepresents all assigned task sets, then T_a＝∪_k∈KT_a(k) (ii) a There are many allocations from set T to set K, let Ω (T, K) denote the set of all task allocations from T to K;

defining a task sequence and a distribution path: a is expressed as a task allocation scheme, a is equal to omega (T, K), and the task set allocated to the rider K is expressed as

T_a(k) Is a multiple set of task sequences

Is expressed as: p is a radical of_ak＝p_ak(1),p_ak(2),…,p_ak(2|T_a(k) In which p) is_ak(j) For a task sequence p_akJ (j ═ 1,2, …,2| T) th_a(k) |) tasks corresponding to the positions;

a ∈ Ω (T, K) is expressed as a task allocation scheme, T_a(k) Represented as a set of tasks, p, assigned to rider k_ak∈P_a(k) Expressed as a sequence of tasks, then p_akThe distribution path is a path which starts from the position of the rider k and passes through p in sequence_akIs represented by v, the sequence of merchant or customer nodes to which each task in (a) is directed_ak＝v_ak(0),v_ak(1),…,v_ak(2|T_a(k) L) wherein v_ak(0) K denotes the position of the rider k, v_ak(j) Represents P_a(k) J (j) is 1,2, …,2| T_a(k) |) nodes corresponding to tasks, because each task in the task sequence has two times of goods taking and delivery, the nodes corresponding to the tasks arranged in front are specified as merchant nodes, and the nodes corresponding to the tasks arranged in the back are specified as customer nodes;

the distribution distance function is expressed asWherein p is_ak∈P_a(k) Is a sequence of tasks, v_akFor the corresponding distribution route,represents the slave rider k (k ═ v)_ak(0) To the first node v)_ak(1) The distance of (a) to (b),denotes v_akThe sum of the distances between two adjacent nodes, if the two adjacent nodes are the same node, the distance is 0;

setting time constraints and load constraints: the time constraint function is expressed as H (p)_akT) is { true, false }, where T is T_a(k) Denoted as a task, p_ak∈P_a(k) Expressed as a sequence of tasks, if a task t follows p_akThe corresponding distribution route v in_akThe delivered goods meets the merchant's latest pick time and customer's latest delivery time constraints, then H (p)_akT) true, otherwise, H (p)_ak,t)＝false；

The load constraint function is denoted as Q (p)_ak) E { true, false }, where p_ak∈P_a(k) Is a task sequence if the rider k follows the task sequence p_akCorresponding distribution route v_akThe delivered cargo can meet its maximum load constraint, Q (p)_ak) Else Q (p)_ak)＝false；

Defining a crowdsourcing distribution task optimization scheduling model based on path planning as follows:

max∑_k∈K|T_a(k)| (1)

min∑_k∈Kd(p_ak) (2)

s.t.

Q(p_ak)＝true p_ak∈P_a(k) (3)

H(p_ak)＝true p_ak∈P_a(k) (4)

p_ak∈P_a(k) a∈Ω(T,K),k∈K (5)

a∈Ω(T,K) (6)。

5. the optimal scheduling method for urban crowdsourcing distribution tasks based on path planning according to claim 4, wherein in the step 4, the specific method for solving the initial crowdsourcing task scheduling scheme based on the greedy strategy is as follows:

definition of T⁰ _a(k) For the set of tasks currently assigned to rider k, p⁰ _akFor a task sequence for which rider k currently satisfies the constraint, i ∈ T- ∪_k∈KT⁰ _a(k) For an unallocated task, if i is inserted into p⁰ _akThe new task sequence obtained after the two proper positions still meets the load constraint and the time constraint, i is called p⁰ _akAn extensible task of, T¹ _a(k)＝T⁰ _a(k) ∪ { i } is the task set for rider k after task i is inserted;

inserting task i into task sequence p⁰ _akThere are two ways: adjacent and spaced; adjacent insertion refers to the insertion of task i into p⁰ _akThen, two positions of the task i in the new task sequence are adjacent; a spaced insertion refers to a task i inserted into p⁰ _akThen, the two positions of the task i in the new task sequence are not adjacent;

the method comprises the following specific steps:

step 1: according to the rider k_iPosition of rider k is obtained_iObtaining a shortest path length set D completed by all tasks which are not distributed with a distance set S of all business points which are not distributed with the tasks, adding the subscript values corresponding to the two sets, sequencing the two sets from small to large according to the addition and storing the two sets to a task distribution sequence T⁰ _a(k_i)；

Step 2: at T⁰ _a(k_i) Selecting a first task t₁Add the task to rider k_iTask delivery sequence p of_a(k_i) As a rider k_iThe first task is delivered, and meanwhile, the task state is set as the delivered state;

step 3: adding a second task, adding T⁰ _a(k_i) Each task t in₂,t₃,…,t_jBoth add to p with adjacent and spaced insertion strategies_a(k_i) In the first pass, p obtained if some kind of insertion strategy_a(k_i) Satisfy t₁And t_jTime constraint of (1), rider k_iThe capacity constraint of (1) then holdsAffair t_jTask delivery sequence p added to the rider according to this insertion strategy_a(k_i) After all the tasks are inserted into the sequence R, the sequence R is arranged in an ascending order, and the task t with the minimum path length_jAs a second delivery task, add to p according to insertion position_a(k_i) In the meantime, a new task delivery sequence p is delivered_a(k_i) As a task delivery sequence to add the next task, t_jThe state becomes delivered; if all insertion strategies yield p_a(k_i) All do not satisfy the constraint, then p_a(k_i) To the final rider k_iThe task delivery sequence of (1);

step 4: when the sequence R is null, according to p_a(k_i) Task relation graph acquisition rider k_iV of_akiWhile obtaining rider k_iDelivery of p_a(k_i) Path length d (p) of_aki) (ii) a Making i equal to i +1, and returning to Step 2;

step 5: when i-L +1 or the status of all tasks is delivered, the algorithm ends, resulting in an initial solution set.

6. The method as claimed in claim 5, wherein the step 5 of optimally scheduling the crowdsourcing distribution task based on the variable neighborhood search comprises four neighborhood structures, respectively:

(1) two riders are randomized, and tasks in the task sequences of the two riders are randomized and exchanged;

(2) randomly exchanging merchant points of two tasks in a task sequence of a rider;

(3) randomly exchanging client points of two tasks in a task sequence of a rider;

(4) two riders are randomized, tasks in a task sequence of one rider are randomized and added in a task sequence of the other rider;

the method comprises the following specific steps:

step 1: obtaining an initial solution p for rider k_akLet the optimal solution be p_{ak_best}；

Step 2: defining a set of neighborhood structures N_i，i＝1,2…,i_maxAs perturbation operation, where N_iThe method comprises the steps of exchanging task operations of a rider, exchanging task sequence merchant point operations, exchanging task sequence customer point operations and transferring task operations of the rider;

step 3: defining a set of neighborhood structures N_j，j＝1,2…,j_maxAs a neighborhood search, where N_jThe method comprises the steps of exchanging task operations of a rider, exchanging task sequence merchant point operations, exchanging task sequence customer point operations and transferring task operations of the rider;

step 4: let i equal to 1, j equal to 1;

step 5: using N_iTo p_akDisturbing to generate solution p'_ak；

Step 6: using N_jTo p'_akSearch is carried out to generate a solution p'_ak；

Step 7: if d (p'_ak)<d(p”_ak) Then p'_ak＝p”_akJ is 1; otherwise, j is j + 1;

step 8: if j<j_maxJumping to Step 6; otherwise, executing Step 9;

step 9: if d (p) "_ak)<d(p_ak) Then p is_ak＝p”_akI is 1; otherwise, i is i + 1;

step 10: if i<i_maxJumping to Step 5; otherwise, p_{ak_best}＝p”_akExecuting Step 11;

step 11: inputting an optimal solution p_{ak_best}And the algorithm ends.

Images