Automated partitioning of transportation routing problems

• US 10,387,823 B2
• Filed: 12/10/2012
• Issued: 08/20/2019
• 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
• Primary Examiner(s): Erb, Nathan
• Application Number:
  US13/709,517
• Publication Number:
  US 20130151435A1
• Time in Patent Office: 2,444 Days
• 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 center; mapping delivery and/or pickup sites at geographic locations; scanning radially around the geographic center 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 center 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 by a data processing system, comprising:

determining, by the data processing system, a threshold number of shipments per partition, wherein determining a threshold number of shipments per partition is determined dynamically based on a heuristic function;

initially dividing, by the data processing system, a routing problem into geographic centers to form a plurality of geographic center routing problems for each of the geographic centers;

selecting, by the data processing system, a geographic center from the geographic centers;

mapping, by the data processing system, delivery and/or pickup sites at geographic locations around the geographic center;

scanning, by the data processing system, radially around the geographic center to determine a sparsest or densest region of the sites and selecting a starting point in this region;

progressing, by the data processing system responsive to the scanning, from the starting point radially around the geographic center aggregating the sites into partitions with a maximum of the threshold number of shipments in each partition; and

outputting, for each of the partitions, a set of routes that each comprise a vehicle, a list of shipments for the vehicle, and unload events associated with the vehicle.

2. The method as claimed in claim 1, wherein the geographic center is a location computed geometrically from existing sites.

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

binning, by the data processing system, all the sites into predetermined sized bins according to an angle they form between a selected line and the site location with respect to the geographic center and determining the smallest bin or the largest bin in the predetermined sized bins.

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

solving, by the data processing system, each geographic center routing problem to generate one or more optimized routes; and

creating, by the data processing system, a union of all the partitions.

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

performing, by the data processing system, a local search optimization on the union of all the partitions.

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

temporally dividing, by the data processing system, each of the plurality of geographic center routing problems for the geographic center that have a number of shipments exceeding the threshold number of shipments per partition.

7. The method as claimed in claim 6, wherein temporally dividing the plurality of geographic center routing problems for the geographic center comprises:

sorting, by the data processing system, the shipments by ascending pickup or delivery times; and

grouping, by the data processing system, the shipments in groups of consecutive items.

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

receiving as inputs, by the data processing system, one or more identifiers of pickup or delivery sites, one or more identifiers of geographic centers, one or more vehicle capacity constraints, and one or more temporal constraints;

calculating, by the data processing system, one or more problem space sizes based on the number of said geographic centers and said one or more vehicle capacity constraints; and

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

partitioning, by the data processing system, said problem space by said number of said geographic centers;

further creating, by the data processing system, one or more partitions of said problem space according to said one or more temporal constraints;

iteratively creating, by the data processing system, an aggregation of one or more of the pickup or delivery sites within each partition of said problem space until said aggregation reaches said predetermined size for said problem space; and

selecting, by the data processing system, one or more vehicle routes according to said aggregation.

9. A data processing system for automated partitioning of transportation routing problems, comprising:

a processor coupled to a memory device having executable program code stored therein, wherein the data processing system comprises;

a threshold constant component that is configured to determine a threshold number of shipments per partition, 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;

a center partitioning component that is configured to initially divide a routing problem into geographic centers to form a plurality of geographic center routing problems for each of the geographic centers;

a center selection component that is configured to select a geographic center from the geographic centers;

a site mapping component that is configured to map delivery and/or pickup sites at geographic locations around the geographic center;

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

a site aggregating component that is configured to progress, responsive to the scan, from the starting point radially around the geographic center aggregating the sites into partitions with a maximum of the threshold number of shipments in each partition; and

an output component configured to provide to a transportation routing system, for each of the partitions, a set of routes that each comprise a vehicle, a list of shipments for the vehicle, and unload events associated with the vehicle.

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

11. The data processing system as claimed in claim 9, further comprising a transport routing system configured to solve each geographic center routing problem to generate one or more optimized routes and create a union of all the partitions.

12. The data processing system as claimed in claim 11, further comprising a search optimization component configured to perform a local search optimization on the union of all the partitions.

13. The data processing system as claimed in claim 9, further comprising:

a temporal partitioning component configured to temporally divide the plurality of geographic center routing problems for the geographic center that have a number of shipments exceeding the threshold number of shipments per partition.

14. A non-transitory computer readable storage device storing a computer program thereon which, upon execution by a computer, causes the computer to perform steps comprising:

determining a threshold number of shipments per partition, wherein determining a threshold number of shipments per partition is determined dynamically based on a heuristic function;

initially dividing a routing problem into geographic centers to form a plurality of geographic center routing problems for each of the geographic centers;

selecting a geographic center from the geographic centers;

mapping delivery and/or pickup sites at geographic locations around the geographic center;

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

responsive to the scanning, progressing from the starting point radially around the geographic center, aggregating the sites into partitions with a maximum of the threshold number of shipments in each partition; and

outputting a set of routes, for each of the partitions, that each comprise a vehicle, a list of shipments for the vehicle, and unload events associated with the vehicle.

15. The non-transitory computer readable storage device as claimed in claim 14, wherein scanning radially around the geographic center to determine the sparsest or densest region of the sites comprises:

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