Automated Partitioning of Transportation Routing Problems

• US 20130151435A1
• Filed: 12/10/2012
• Published: 06/13/2013
• Est. Priority Date: 12/13/2011
• Status: Active Grant

• Current Assignee: Maplebear Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Hocquette, Amelie, Kong, Viu-Long, Michel, Stephane
• Granted Patent: US 10,387,823 B2
• Time in Patent Office: Days
• US Class Current: 705/338
• CPC Class Codes: G06Q 10/083 Shipping
• CPC Class Codes: G06Q 10/08355 Routing methods

Abstract

Method and system are provided for automated partitioning of transportation routing problems. The method includes: determining a threshold number of shipments per partition; selecting a geographic centre; mapping delivery and/or pickup sites at geographic locations;

scanning radially around the geographic centre to determine the sparsest or densest region of sites and selecting a starting point in this region; and progressing from the starting point radially around the geographic centre aggregating sites into partitions with a maximum of the threshold number of shipments in a partition. The method may include: solving each partitioned instance of a problem to generate one or more optimized routes; and creating a union of all the instances solutions.

Claims

1. A method for automated partitioning of transportation routing problems, comprising:

determining a threshold number of shipments per partition;

selecting a geographic centre;

mapping delivery and/or pickup sites at geographic locations;

scanning radially around the geographic centre to determine the sparsest or densest region of sites and selecting a starting point in this region; and

progressing from the starting point radially around the geographic centre aggregating sites into partitions with a maximum of the threshold number of shipments in a partition.

2. The method as claimed in claim 1, wherein determining a threshold number of shipments per partition is determined dynamically based on a heuristic function.

3. The method as claimed in claim 1, wherein the geographic centre is one of:

a warehouse, a collection/delivery hub, any location from which shipments are picked up and/or delivered, and a location computed geometrically from existing sites.

4. The method as claimed in claim 1, wherein scanning radially around the geographic centre to determine the sparsest or densest region of sites comprises:

binning all the sites into predetermined sized bins according to the angle they form between a selected line and the site location with respect to the geographic centre and determining the smallest bin or the largest bin in the predetermined sized bins.

5. The method as claimed in claim 1, further comprising:

solving each partitioned instance of a problem to generate one or more optimized routes; and

creating a union of all instances solutions.

6. The method as claimed in claim 5, further comprising:

performing a local search optimization on the union of all instances solutions.

7. The method as claimed in claim 1, wherein if a problem has more than one geographic centre, initially dividing the problem into geographic centres.

8. The method as claimed in claim 1, wherein if a problem has time constraints for shipments, initially dividing the problem temporally.

9. The method as claimed in claim 8, wherein dividing the problem temporally comprises:

sorting the shipments by ascending pickup or delivery times; and

grouping the shipments in groups of consecutive items.

10. The method as claimed claim 1, further comprising:

receiving as inputs one or more identifiers of pickup or delivery sites, one or more identifiers of geographic centres, one or more vehicle capacity constraints, and one or more temporal constraints;

calculating one or more problem space sizes based on the number of said geographic centres and said one or more vehicle capacity constraints;

for each problem space of size greater than a predetermined size;

partitioning said one or more problem spaces by said number of said geographic centres;

further creating one or more partitions of said problem spaces according to said any temporal constraints;

iteratively creating an aggregation of said one or more pickup or delivery sites within each partition of said problem space until said aggregation reaches said predetermined size of said problem space; and

selecting said one or more optimised vehicle routes according to said aggregation.

18. A computer program stored on a computer readable storage device and loadable into the internal memory of a digital computer, comprising software code portions for performing, when said program is run on a computer, the method of claim 1.

11. A system for automated partitioning of transportation routing problems, comprising:

a processor;

a threshold constant component that is configured to determine a threshold number of shipments per partition;

a centre selection component that is configured to select a geographic centre;

a site mapping component that is configure to for map delivery and/or pickup sites at geographic locations;

a radially scanning component that is configured to scan radially around the geographic centre to determine the sparsest or densest region of sites and selecting a starting point in this region; and

a site aggregating component that is configured to progress from the starting point radially around the geographic centre aggregating sites into partitions with a maximum of the threshold number of shipments in a partition.

12. The system as claimed in claim 11, wherein the threshold constant component includes a dynamic threshold adjusting component that is configured to determine a threshold number of shipments per partition dynamically based on a heuristic function.

13. The system as claimed in claim 11, wherein the radially scanning component is configured to bin all the sites into predetermined sized bins according to the angle they form between a selected line and the site location with respect to the geographic centre and determine the smallest bin or the largest bin in the predetermined sized bins.

14. The system as claimed in f claims 11, further comprising a transport routing system configured to solve each partitioned instance of a problem to generate one or more optimized routes and create a union of all instances solutions.

15. The system as claimed in claim 14, further comprising a search optimization component configured to perform a local search optimization on the union of all instances solutions.

16. The system as claimed in claim 11, further comprising a centre partitioning component configured to divide a problem into geographic centres if the problem has more than one geographic centre.

17. The system as claimed in claim 11, further comprising a temporal partitioning component configured to divide a problem temporally if the problem has time constraints for the shipments.