ORDER GROUP ALLOCATION METHOD AND DEVICE

• US 20200134762A1
• Filed: 12/27/2019
• Published: 04/30/2020
• Est. Priority Date: 06/29/2017
• Status: Abandoned Application

• Current Assignee: Beijing Xiaodu Information Technology Co., Ltd.
• Original Assignee: Beijing Xiaodu Information Technology Co., Ltd.
• Inventors: CHEN, Jinqing, XU, Mingquan, HUANG, Shaojian, XIAN, Ke, YANG, Qiuyuan, RAO, Jiajia
• Application Number:
  US16/728,611
• Publication Number:
  US 20200134762A1
• Time in Patent Office: Days
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/083 Shipping

Abstract

An order group allocation method and apparatus are disclosed. The order group allocation method includes: determining, based on a matching score between each of a plurality of to-be-processed order groups and each of a plurality of delivery persons, an order group with a lowest matching score corresponding to each delivery person; dividing the to-be-processed order groups and the delivery persons into a plurality of non-intersecting sub-combinations; and allocating the to-be-processed order group based on an order group allocation process for each sub-combination, so that each to-be-processed order group in each sub-combination is allocated to a delivery person in a corresponding sub-combination. The method of the present disclosure improves order group allocation efficiency.

Claims

1. An order group allocation method, comprising:

determining, based on a matching score between each of a plurality of to-be-processed order groups and each of a plurality of delivery persons, a to-be-processed order group with a lowest matching score corresponding to each delivery person;

dividing, based on the to-be-processed order group with the lowest matching score corresponding to each delivery person, the to-be-processed order groups and the delivery persons into a plurality of non-intersecting sub-combinations, wherein “

non-intersecting”

means that there is no overlapping to-be-processed order groups and no overlapping delivery persons between the sub-combinations; and

allocating, based on an order group allocation process for each sub-combination, the to-be-processed order groups, so that each to-be-processed order group in each sub-combination is allocated to a delivery person in a corresponding sub-combination.

2. The method of claim 1, further comprising:

calculating the matching score between each to-be-processed order group and each delivery person based on one or more factors of a distance between an estimated delivery location of each delivery person and a start address of each to-be-processed order group, a time difference between an estimated delivery time of each delivery person and an expected arrival time of each to-be-processed order group, a degree of familiarity with the start address of each to-be-processed order group by each delivery person, a degree of familiarity with a destination address of each to-be-processed order group by each delivery person, an estimated completion time in which each delivery person completes delivery of each to-be-processed order group, and an emergency degree of each to-be-processed order group.

3. The method of claim 1, wherein dividing the to-be-processed order groups and the delivery persons into a plurality of non-intersecting sub-combinations comprises:

traversing, using a traversal algorithm, each to-be-processed order group and each delivery person, and dividing, using the to-be-processed order group with the lowest matching score corresponding to each delivery person as a constraint condition, the to-be-processed order groups and the delivery persons into a plurality of non-intersecting sub-combinations,

wherein the traversal algorithm comprises a breadth-first traversal algorithm or a depth-first traversal algorithm.

4. The method of claim 3, wherein traversing, using a traversal algorithm, each to-be-processed order group and each delivery person, and dividing, using the to-be-processed order group with the lowest matching score corresponding to each delivery person as a constraint condition, the to-be-processed order groups and the delivery persons into a plurality of non-intersecting sub-combinations comprises:

establishing, using the to-be-processed order groups and the delivery persons as nodes, a network topology, wherein a link between each to-be-processed order group and each delivery person represents a corresponding matching score;

traversing, using a lowest matching score between the nodes as a constraint condition, all associated nodes of each node, determining, for each node, an associated node with a lowest matching score, and deleting, for each node, a link between the node and the associated node with the lowest matching score; and

dividing the network topology into a plurality of non-intersecting sub-networks, wherein there is no overlapping links in the plurality of non-intersecting sub-networks,

wherein the plurality of non-intersecting sub-networks are the corresponding plurality of non-intersecting sub-combinations.

5. The method of claim 1, wherein allocating, based on an order group allocation process for each sub-combination, the to-be-processed order groups, so that each to-be-processed order group in each sub-combination is allocated to a delivery person in a corresponding sub-combination comprises:

performing, for each sub-combination, a maximum weight matching operation on each to-be-processed order group and each delivery person in each sub-combination to determine a delivery person with a highest matching score corresponding to each to-be-processed order group,

wherein the maximum weight matching operation comprises;

sequentially traversing all the to-be-processed order groups in the sub-combination in different order group sequences, and for each traversed to-be-processed order group, determining, from unmatched delivery persons, a delivery person with a highest matching degree with each to-be-processed order group to obtain M allocation lists, wherein M is an integer greater than or equal to 1;

calculating, for each allocation list, a sum of matching scores corresponding to all the to-be-processed order groups to obtain a list score of each allocation list; and

allocating, based on an allocation list with a highest list score, each to-be-processed order group to a corresponding delivery person.

11. An electronic device, comprising one or more memories and one or more processors, wherein the one or more memories are configured to store one or more computer instructions, and wherein upon being executed by the one or more processors, the one or more computer instructions cause the one or more processors to perform the method of claim 1.

12. A computer-readable storage medium that stores a computer program, wherein upon being executed by a computer, the computer program causes the computer to perform the method of claim 1.

6. An order group allocation apparatus, comprising:

a determining module, configured to determine, based on a matching score between each of a plurality to-be-processed order groups and each of a plurality delivery persons, a to-be-processed order group with a lowest matching score corresponding to each delivery person;

a division module, configured to divide, based on the to-be-processed order group with the lowest matching score corresponding to each delivery person, the to-be-processed order groups and the delivery persons into a plurality of non-intersecting sub-combinations, wherein “

non-intersecting”

means that there is no overlapping to-be-processed order groups and no overlapping delivery persons between the sub-combinations; and

an allocation module, configured to allocate, based on an order group allocation process for each sub-combination, the to-be-processed order groups, so that each to-be-processed order group in each sub-combination is allocated to a delivery person in a corresponding sub-combination.

7. The apparatus of claim 6, further comprising:

a calculation module, configured to calculate the matching score between each to-be-processed order group and each delivery person based on one or more factors of a distance between an estimated delivery location of each delivery person and a start address of each to-be-processed order group, a time difference between an estimated delivery time of each delivery person and an expected arrival time of each to-be-processed order group, a degree of familiarity with the start address of each to-be-processed order group by each delivery person, a degree of familiarity with a destination address of each to-be-processed order group by each delivery person, an estimated completion time in which each delivery person completes delivery of each to-be-processed order group, and an emergency degree of each to-be-processed order group.

8. The apparatus of claim 6, wherein the division module is configured to:

traverse, using a traversal algorithm, each to-be-processed order group and each delivery person, and divide, using the to-be-processed order group with the lowest matching score corresponding to each delivery person as a constraint condition, the to-be-processed order groups and the delivery persons into a plurality of non-intersecting sub-combinations,

wherein the traversal algorithm comprises a breadth-first traversal algorithm or a depth-first traversal algorithm.

9. The apparatus of claim 8, wherein the division module comprises:

an establishing submodule, configured to establish, using the to-be-processed order groups and the delivery persons as nodes, a network topology, wherein a link between each to-be-processed order group and each delivery person represents a corresponding matching score;

a determining submodule, configured to traverse, using a lowest matching score between the nodes as a constraint condition, all associated nodes of each node, determine, for each node, an associated node with a lowest matching score, and delete, for each node, a link between the node and the associated node with the lowest matching score; and

a division submodule, configured to divide the network topology into a plurality of non-intersecting sub-networks, wherein there is no overlapping links in the plurality of non-intersecting sub-networks, and the plurality of non-intersecting sub-networks are the corresponding plurality of non-intersecting sub-combinations.

10. The apparatus of claim 6, wherein the allocation module is configured to:

perform, for each sub-combination, a maximum weight matching operation on each to-be-processed order group and each delivery person in each sub-combination to determine a delivery person with a highest matching score corresponding to each to-be-processed order group,

wherein the maximum weight matching operation comprises;

sequentially traversing all the to-be-processed order groups in the sub-combination in different order group sequences, and for each traversed to-be-processed order group, determining, from unmatched delivery persons, a delivery person with a highest matching degree with each to-be-processed order group, to obtain M allocation lists, wherein M is an integer greater than or equal to 1;

calculating, for each allocation list, a sum of matching scores corresponding to all the to-be-processed order groups, to obtain a list score of each allocation list; and

allocating, based on an allocation list with a highest list score, each to-be-processed order group to a corresponding delivery person.