Core area territory planning for optimizing driver familiarity and route flexibility

• US 7,840,319 B2
• Filed: 12/08/2009
• Issued: 11/23/2010
• Est. Priority Date: 08/22/2002
• Status: Active Grant

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Zhong, Hongsheng
• Primary Examiner(s): To; Tuan C
• Application Number:
  US12/633,114
• Publication Number:
  US 20100088146A1
• Time in Patent Office: 350 Days
• Field of Search: 701/25, 342/357.07, 342/357.08, 702/31, 702/32, 702/181, 455/446, 455/418, 455/456.1, 706/13, 700/217
• US Class Current: 701/25
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management

Abstract

Route planning methods for use by a package delivery service provider are disclosed that satisfy a stochastic daily demand while taking advantage of drivers'"'"' route familiarity over time. A model for estimating the value of driver familiarity is disclosed along with both an empirical and a mathematical model for estimating the value of route consistency, along with a Core Area Route Design which involves the concepts of combinatorial optimization, meta-heuristic algorithms, tabu search heuristics, network formulation modeling, and multi-stage graph modeling. In one embodiment, a service territory is divided into unassigned cells associated with a grid segment involving prior driver delivery stops, and a driver from a pool of unassigned drivers is assigned to a route based on examining each driver'"'"'s grid segment visiting frequency limit with respect to a minimum limit so as to optimize driver selection based on of each driver'"'"'s familiarity with the route.

Claims

1. A computer program product comprising at least one computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

an executable portion configured to select a new driver from a pool of unassigned drivers;

an executable portion configured to identify a plurality of cells, wherein each of the plurality of cells comprises (i) a portion of a service territory and (ii) a group of one or more stops;

an executable portion configured to classify one or more of the plurality of cells as core cells in response to a known service volume for each of the core cells exceeding a minimum service volume;

an executable portion configured to establish one or more core areas, wherein each of the one or more core areas comprises a localized cluster of the one or more core cells;

an executable portion configured to select a new core area from the one or more core areas based upon a known driver visit frequency by the new driver to each of the one or more core areas;

an executable portion configured to assign the new driver to service the new core area after selecting the new core area; and

an executable portion configured to classify the new driver as an assigned driver after assigning the new driver to service the new core area.

2. The computer program product of claim 1 further comprising:

an executable portion configured to classify any cell located outside any of the new core areas as a daily cell;

an executable portion configured to select a proximately assigned driver based upon a proximity factor relating each of the new core areas to the daily cell; and

an executable portion configured to assign the daily cell to the proximately assigned driver.

3. The computer program product of claim 2 further comprising:

an executable portion configured to classify any stop located outside any of the new core areas or outside any of the daily cells as a daily stop;

an executable portion configured to select a proximately assigned stop driver based upon a stop proximity factor relating each of the new core areas to the daily stop; and

an executable portion configured to assign the daily stop to the proximately assigned stop driver.

4. The computer program product of claim 2, wherein in order to identify a plurality of cells, the executable portion is further configured to identify a plurality of cells comprising one or more stops located within an area suitable for service by the new driver during a finite workday.

5. The computer program product of claim 2, wherein the proximity factor comprises at least one of a distance element or a time element.

6. The computer program product of claim 3, wherein the stop proximity factor comprises at least one of a distance element or a time element.

7. The computer program product of claim 1, wherein in order to identify a plurality of cells, the executable portion is further configured to assign one or more core cells to respective core areas based at least in part on one or more of a travel time associated with serving respective core cells, a cell-to-cell travel time associated with respective core areas, or a maximum workday duration.

8. The computer program product of claim 7, wherein the travel time associated with serving respective core cells is determined based at least in part on one or more of a learning curve factor associated with a driver assigned to the core cell, an average time per stop within the core cell, or a mean demand associated with the core cell.

9. The computer program product of claim 7, wherein the cell-to-cell travel time is determined based at least in part on a learning curve factor associated with a driver assigned to the core area.

10. A computer-implemented method comprising:

selecting, via one or more processors, a new driver from a pool of unassigned drivers;

identifying, via the one or more processors, a plurality of cells, wherein each of the plurality of cells comprises (i) a portion of a service territory and (ii) a group of one or more stops;

classifying, via the one or more processors, one or more of the plurality of cells as core cells in response to a known service volume for each of the core cells exceeding a minimum service volume;

establishing, via the one or more processors, one or more core areas, wherein each of the one or more core areas comprises a localized cluster of the one or more core cells;

selecting, via the one or more processors, a new core area from the one or more core areas based upon a known driver visit frequency by the new driver to each of the one or more core areas;

assigning, via the one or more processors, the new driver to service the new core area after selecting the new core area; and

classifying, via the one or more processors, the new driver as an assigned driver after assigning the new driver to service the new core area.

11. The computer-implemented method of claim 10 further comprising:

classifying, via the one or more processors, any cell located outside any of the new core areas as a daily cell;

selecting, via the one or more processors, a proximately assigned driver based upon a proximity factor relating each of the new core areas to the daily cell; and

assigning, via the one or more processors, the daily cell to the proximately assigned driver.

12. The computer-implemented method of claim 11 further comprising:

classifying, via the one or more processors, any stop located outside any of the new core areas or outside any of the daily cells as a daily stop;

selecting, via the one or more processors, a proximately assigned stop driver based upon a stop proximity factor relating each of the new core areas to the daily stop; and

assigning, via the one or more processors, the daily stop to the proximately assigned stop driver.

13. The computer-implemented method of claim 10, wherein the step of identifying a plurality of cells further comprises identifying a plurality of cells comprising one or more stops located within an area suitable for service by the new driver during a finite workday.

14. The computer-implemented method of claim 11, wherein the proximity factor comprises at least one of a distance element or a time element.

15. The computer-implemented method of claim 12, wherein the stop proximity factor comprises at least one of a distance element or a time element.

16. The computer-implemented method of claim 10, wherein establishing one or more core areas further comprises assigning one or more core cells to respective core areas based at least in part on one or more of a travel time associated with serving respective core cells, a cell-to-cell travel time associated with respective core areas, or a maximum workday duration.

17. The computer-implemented method of claim 16, wherein the travel time associated with serving respective core cells is determined based at least in part on one or more of a learning curve factor associated with a driver assigned to the core cell, an average time per stop within the core cell, or a mean demand associated with the core cell.

18. The computer-implemented method of claim 16, wherein the cell-to-cell travel time is determined based at least in part on a learning curve factor associated with a driver assigned to the core area.