Core area territory planning for optimizing driver familiarity and route flexibility

• US 7,660,651 B2
• Filed: 12/21/2007
• Issued: 02/09/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:
  US11/962,871
• Publication Number:
  US 20080147473A1
• Time in Patent Office: 781 Days
• Field of Search: 701/25, 342/357.07, 342/357.08, 702/31, 702/32, 702/181
• 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 system comprising one or more memory storage areas and one or more processors, the one or more processors configured to:

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

(b) electronically 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;

(c) electronically classify one or more of said plurality of cells as core cells in response to a known service volume for each of said core cells exceeding a minimum service volume;

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

(e) electronically 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) electronically assign said new driver to service said new core area after selecting said new core area; and

(g) electronically 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 the one or more processors are further configured to:

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

electronically select a proximately 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 proximately assigned driver.

3. The system of claim 2, wherein the one or more processors are further configured to:

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

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

electronically assign said daily stop to said proximately assigned stop driver.

4. The system of claim 1, wherein in order to identify a plurality of cells, the one or more processors are 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 one or more processors are further configured to:

electronically 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.