Data processing: vehicles – navigation – and relative location – Vehicle control – guidance – operation – or indication – Automatic route guidance vehicle
Reexamination Certificate
2009-12-08
2010-11-23
To, Tuan C (Department: 3663)
Data processing: vehicles, navigation, and relative location
Vehicle control, guidance, operation, or indication
Automatic route guidance vehicle
C342S357490, C702S031000, C702S032000, C702S181000, C455S446000, C455S456100, C706S013000
Reexamination Certificate
active
07840319
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.
REFERENCES:
patent: 5122959 (1992-06-01), Nathanson et al.
patent: 5197009 (1993-03-01), Hoffman, Jr. et al.
patent: 5255349 (1993-10-01), Thakoor et al.
patent: 5272638 (1993-12-01), Martin et al.
patent: 5568381 (1996-10-01), Hara et al.
patent: 5970481 (1999-10-01), Westerlage et al.
patent: 5974317 (1999-10-01), Duuknic et al.
patent: 5983198 (1999-11-01), Mowery et al.
patent: 6084547 (2000-07-01), Sanderford et al.
patent: 6184823 (2001-02-01), Smith et al.
patent: 6232915 (2001-05-01), Dean et al.
patent: 6236365 (2001-05-01), LeBlanc et al.
patent: 6272483 (2001-08-01), Joslin et al.
patent: 6418398 (2002-07-01), Dueck et al.
patent: 6510384 (2003-01-01), Okano
patent: 6529821 (2003-03-01), Tomasi et al.
patent: 6532417 (2003-03-01), Hatano
patent: 6650284 (2003-11-01), Mannings et al.
patent: 6823257 (2004-11-01), Clapper
patent: 6891500 (2005-05-01), Hall et al.
patent: 7020863 (2006-03-01), Teig et al.
patent: 7123893 (2006-10-01), Austin et al.
patent: 7197500 (2007-03-01), Israni et al.
patent: 7379959 (2008-05-01), Hinni et al.
patent: 2002/0046073 (2002-04-01), Indseth et al.
patent: 2002/0082772 (2002-06-01), Okano
patent: 2002/0188486 (2002-12-01), Gil et al.
patent: 2003/0014286 (2003-01-01), Cappellini
patent: 2003/0028319 (2003-02-01), Khavakh et al.
patent: 2003/0033083 (2003-02-01), Nakashima et al.
patent: 2003/0060924 (2003-03-01), Ye et al.
patent: 2003/0065625 (2003-04-01), Rosenbaum et al.
patent: 2003/0084011 (2003-05-01), Shetty
patent: 2003/0093391 (2003-05-01), Shackleford
patent: 2003/0135304 (2003-07-01), Sroub et al.
patent: 2003/0233190 (2003-12-01), Jones
patent: 2004/0123260 (2004-06-01), Teig et al.
patent: 2004/0204821 (2004-10-01), Tu
patent: 2000 112925 (2000-04-01), None
Solomon, F.; “Algorithms for the Vehicle Routing and Scheduling Problems With Time Window Constraints;” Operations Research; Mar.-Apr. 1987, pp. 254-265, vol. 35, No. 2; Operations Research Society of America.
Gendreau, M., et al.; “A Tabu Search Heuristic for the Vehicle Routing Problem With Stochastic Demands and Customers;” Operations Research; May-Jun. 1996; pp. 469-477, vol. 44, No. 3; Informs.
Hall, R., et al.; “Use of Continuous Approximations within Discrete Algorithms for Routing Vehicles: Experimental Results and Interpretation;” Networks; 1994; pp. 43-56, vol. 24; John Wiley & Sons, Inc.
Laguna, M., et al.; “Tabu Search for the Multilevel Generalized Assignment Problem;” European Journal of Operational Research; 1995; pp. 176-189; vol. 82; Elsevier Science B.V.
Russell, R.; “Hybrid Heuristics for the Vehicle Routing Problem with Time Windows;” Transportation Science; May 1995; pp. 156-166, vol. 29, No. 2; Institute for Operations Research and the Management Sciences.
Laporte, G.; “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms;” European Journal of Operational Research; 1992; pp. 345-358; vol. 59; Elsevier Science Publishers B.V.
Kall, P.; “Stochastic Programming;” European Journal of Operational Research; 1982; pp. 125-130; Vol. 10; North-Holland Publishing Company.
Potvin, J., et al.; “A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows;” European Journal of Operational Research; 1993; pp. 331-340; vol. 66; Elsevier Science Publishers B.V.
Stewart, Jr., W., et al.; “Stochastic Vehicle Routing: A Comprehensive Approach;” European Journal of Operational Research; 1983; pp. 371-385; vol. 14; Elsevier Science Publishers B.V.
Dror, M., et al.; “Vehicle Routing With Stochastic Demands: Properties and Solution Frameworks;” Transportation Science; Aug. 1989; pp. 166-176, vol. 23, No. 3; Operations Research Society of America.
Laporte, G., et al.; “Models and Exact Solutions for a Class of Stochastic Location-Routing Problems;” European Journal of Operational Research; Feb. 1988; pp. 71-78; vol. 39; Elsevier Science Publishers B.V.
Bertsimas, D., et al.; “A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane;” Operations Research; Jul.-Aug. 1991; pp. 601-615, vol. 39, No. 4; Operations Research Society of America.
Hall, R.; “Graphical Interpretation of the Transportation Problem;” Transportation Science; Feb. 1989; pp. 37-45, vol. 23, No. 1; Operations Research Society of America.
Bertsimas, D., et al.; “Computational Approaches to Stochastic Vehicle Routing Problems;” Transportation Science; Nov. 1995; pp. 342-352, vol. 29, No. 4; Institute for Operations Research and the Management Sciences.
Gendreau, M. et al.; “Invited Review: Stochastic Vehicle Routing;” European Journal of Operational Research; 1996; pp. 3-12; vol. 88; Elsevier Science B.V.
Bertsimas, D.; “A Vehicle Routing Problem With Stochastic Demand;” Operations Research; May-Jun. 1992; pp. 574-585, vol. 40, No. 3; Operations Research Society of America.
Savelsbergh, M., et al.; “A Comparison of the Efficiency of Fixed Versus Variable Vehicle Routes;” Journal of Business Logistics; 1995; pp. 163-187, vol. 16, No. 1.
Beasley, J., et al.; “Vehicle Routing With a Sparse Feasibility Graph;” European Journal of Operational Research; 1997; pp. 499-511; vol. 98; Elsevier Science Publishers B.V.
Wong, K., et al.; “Vehicle Routing Using Fixed Delivery Areas;” Omega International Journal of Management Science; 1984; pp. 591-600, vol. 12 No. 6; Pergamon Press Ltd.
Hall, R.; “Design for Local Area Freight Networks;” Transportation Research—B; 1993; pp. 79-81, vol. 27B No. 2; Pergamon Press Ltd.
Hall, R., et al.; “On the Road to Efficiency;” OR/MS Today; Jun. 1997; pp. 38-47.
Hall, R.; “Pickup and Delivery Systems for Overnight Carriers;” Transportation Research—A; 1996; pp. 173-187, vol. 30, No. 3; Elsevier Science Ltd.
Kamoun, M., et al.; “Design of Express Mail Services for Metropolitan Regions;” Journal of Business Logistics; 1996; pp. 265-302, vol. 17, No. 2.
Dror, M.; “Modeling Vehicle Routing with Uncertain Demands as a Stochastic Program: Properties of the Corresponding Solution;” European Journal of Operational Research; 1993; pp. 432-441; vol. 64; Elsevier Science Publishers B.V.
Waters, C.; “Vehicle-Scheduling Problems with Uncertainty and Omitted Customers;” Journal of the Operational Research Society; 1989; pp. 1099-1108, vol. 40, No. 12; Operational Research Society Ltd.
Gendreau, M., et al.; “An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers;” Transportation Science; May 1995; pp. 143-155, vol. 29, No. 2; Institute for Operations Research and the Management Sciences.
Haughton, M.; “The Performance of Route Modification and Demand Stabilization Strategies in Stochastic Vehicle Routing;” Transportation Research—B; 1998; pp. 551-566, vol. 32, No. 8; Elsevier Science Ltd.
Lorena, L.; et al.; “Relaxation Heuristics for a
Alston & Bird LLP
To Tuan C
United Parcel Service of America Inc.
LandOfFree
Core area territory planning for optimizing driver... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Core area territory planning for optimizing driver..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Core area territory planning for optimizing driver... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4243658