CORE AREA TERRITORY PLANNING FOR OPTIMIZING DRIVER FAMILIARITY AND ROUTE FLEXIBILITY

• US 20080147473A1
• Filed: 12/21/2007
• Published: 06/19/2008
• Est. Priority Date: 08/22/2002
• Status: Active Grant

• Current Assignee: United Parcel Service of America (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service of America (United Parcel Service Incorporated)
• Inventors: Zaret, David, Zhong, Hongsheng
• Granted Patent: US 7,660,651 B2
• Time in Patent Office: Days
• US Class Current: 705/9
• 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 system configured to:

(a) select a new driver from a pool of unassigned drivers;

(b) identify a plurality of cells, each cell comprising a group of one or more stops;

(c) classify one or more of said plurality of cells as core cells if a known service volume for each of said core cells exceeds a minimum service volume;

(d) establish one or more core areas, each comprising a localized cluster of said one or more core cells;

(e) select a new core area from said one or more core areas based upon a known driver visit frequency by said new driver to each of said one or more core areas;

(f) assign said new driver to service said new core area after selecting said new core area; and

(g) classify said new driver as an assigned driver after assigning said new driver to service said new core area.

2. The system of claim 1, wherein said central processing unit is further configured to:

classify any cell located outside any of said new core areas as a daily cell;

select a nearest assigned driver based upon a proximity factor relating each of said new core areas to said daily cell; and

assign said daily cell to said nearest assigned driver.

3. The system of claim 2, wherein said central processing unit is further configured to:

classify any stop located outside any of said new core areas or outside any of said daily cells as a daily stop;

select a nearest assigned stop driver based upon a stop proximity factor relating each of said new core areas to said daily stop; and

assign said daily stop to said nearest assigned stop driver.

4. The system of claim 1, wherein in order to identify a plurality of cells, the central processing unit is further configured to identify a plurality of cells comprising one or more stops located within an area suitable for service by said new driver during a finite workday.

5. The system of claim 2, wherein said proximity factor comprises at least one of a distance element or a time element.

6. The system of claim 3, wherein said stop proximity factor comprises at least one of a distance element or a time element.

7. The system of claim 1, wherein in order to establish one or more core areas, the central processing unit 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 system 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 system 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 method comprising:

selecting a new driver from a pool of unassigned drivers;

identifying a plurality of cells, each cell comprising a group of one or more stops;

classifying one or more of said plurality of cells as core cells if a known service volume for each of said core cells exceeds a minimum service volume;

establishing one or more core areas, each comprising a localized cluster of said one or more core cells;

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

assigning said new driver to service said new core area after selecting said new core area; and

classifying said new driver as an assigned driver after assigning said new driver to service said new core area

11. The method of claim 10 further comprising:

classifying any cell located outside any of said new core areas as a daily cell;

selecting a nearest assigned driver based upon a proximity factor relating each of said new core areas to said daily cell; and

assigning said daily cell to said nearest assigned driver.

12. The method of claim 11 further comprising:

classifying any stop located outside any of said new core areas or outside any of said daily cells as a daily stop;

selecting a nearest assigned stop driver based upon a stop proximity factor relating each of said new core areas to said daily stop; and

assigning said daily stop to said nearest assigned stop driver.

13. The method of claim 10, wherein 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 said new driver during a finite workday.

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

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

16. The 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 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 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.

19. The method of claim 10 further comprising:

repeating each of the foregoing steps a number of times equal to the number of drivers of said pool of unassigned drivers.

20. A computer program product comprising at least one computer-readable medium having computer executable instructions stored therein, the computer executable instructions comprising:

a first executable instruction for selecting a new driver from a pool of unassigned drivers;

a second executable instruction for identifying a plurality of cells, each cell comprising a group of one or more stops;

a third executable instruction for classifying one or more of said plurality of cells as core cells if a known service volume for each of said core cells exceeds a minimum service volume;

a fourth executable instruction for establishing one or more core areas, each comprising a localized cluster of said one or more core cells;

a fifth executable instruction for selecting a new core area from said one or more core areas based upon a known driver visit frequency by said new driver to each of said one or more core areas;

a sixth executable instruction for assigning said new driver to service said new core area after selecting said new core area; and

a seventh executable instruction for classifying said new driver as an assigned driver after assigning said new driver to service said new core area.