Core area territory planning for optimizing driver familiarity and route flexibility

• US 7,363,126 B1
• Filed: 08/22/2003
• Issued: 04/22/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
• Primary Examiner(s): To; Tuan C
• Application Number:
  US10/647,062
• Time in Patent Office: 1,705 Days
• Field of Search: 701/23, 701/24, 701/25, 701/26, 701/200, 701/202, 340/992, 342/465
• 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 combinational 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 method of optimizing a route plan having a plurality of routes within a service territory, comprising:

dividing said service territory into a plurality of unassigned cells, wherein a subset of said plurality of unassigned cells is associated with a grid segment;

identifying from among a staff of drivers a most frequent driver for the grid segment based upon a grid segment visiting frequency calculated for said grid segment and each of said drivers during a reference period,

wherein said grid segment visiting frequency represents a comparison between a number of stops in said grid segment by said driver during said reference period and a total number of stops by said driver during said reference period;

establishing a minimum grid segment visiting frequency limit; and

classifying said subset of said plurality of unassigned cells associated with said grid segment as a core cell;

assigning each said core cell to said identified most frequent driver, if said grid segment visiting frequency calculated for said cell and said most frequent driver is greater than said minimum grid segment visiting frequency limit,

wherein said classifying and assigning optimizes said route plan by having each one of said plurality of routes with stops in a cell classified as a core cell served by said most frequent driver that is most familiar with each core cell that comprises said one of said plurality of routes.

2. The method of claim 1, further comprising:

storing computer-executable instructions for performing said steps on a computer-readable medium; and

executing said instructions.

3. The method of claim 1, wherein said territory further comprises a hub, and wherein said step of dividing said service territory further comprises:

classifying one or more of said unassigned cells as a flex zone cell, based upon a proximity factor relating each of said unassigned cells to said hub, wherein said proximity factor comprises at least a distance element.

4. The method of claim 3, wherein said proximity factor further comprises a time element.

5. The method of claim 1, further comprising:

classifying at least one remaining unassigned cell as a daily cell;

selecting a nearby route from said plurality of routes based upon a proximity factor relating each of said plurality of routes to said daily cell, wherein said proximity factor comprises at least a distance element and a time element; and

assigning said daily cell to said nearby route.

6. The method of claim 1, wherein said step of identifying further comprises:

maintaining a record of one or more actual daily routes driven by a corresponding number of drivers during the reference period, said record including for each day in said reference period a route identifier, a driver identifier, a number of total stops, and a cell stop counter;

calculating a daily cell visit frequency for each of said drivers, for each of said one or more actual daily routes, by comparing said cell stop counter to said number of total stops; and

calculating an average cell visit frequency for said reference period, for each of said drivers, for each of said one or more actual daily routes, by averaging said daily cell visit frequencies over said reference period.

7. The method of claim 6, further comprising:

storing computer-executable instructions for performing said steps on a computer-readable medium; and

executing said instructions.

8. A method of optimizing a route plan having a plurality of routes within a service territory having unassigned cells, comprising:

dividing said service territory into a plurality of grid segments, wherein a subset of said unassigned cells is associated with a grid segment;

identifying from among a staff of drivers a most frequent driver for the grid segment based upon a grid segment visiting frequency calculated for said and each of said drivers during a reference period,

wherein said grid segment visiting frequency represents a comparison between a number of stops in said grid segment by said driver during said reference period and a total number of stops by said driver during said reference period;

establishing a minimum grid segment visiting frequency limit; and

classifying said cells contained within said grid segment as a core cell;

assigning each said core cell to said identified most frequent driver, if said grid segment visiting frequency calculated for said corresponding grid segment and said most frequent driver is greater than said minimum grid cell visiting frequency limit,

wherein said classifying and assigning optimizes said route plan by having each one of said plurality of routes with stops in a cell classified as a core cell served by said most frequent driver that is most familiar with each core cell that comprises said one of said plurality of routes.

9. The method of claim 8, wherein said step of identifying further comprises:

maintaining a record of one or more actual daily routes driven by a corresponding number of drivers during the reference period, said record including for each day in said reference period a route identifier, a driver identifier, a number of total stops, and a grid stop counter;

calculating a daily grid segment visit frequency for each of said drivers, for each of said one or more actual daily routes, by comparing said grid stop counter to said number of total stops; and

calculating an average grid segment visit frequency for said reference period, for each of said drivers, for each of said one or more actual daily routes, by averaging said daily grid segment visit frequencies over said reference period.