Data processing: vehicles – navigation – and relative location – Vehicle control – guidance – operation – or indication – Automatic route guidance vehicle
Reexamination Certificate
2008-04-22
2008-04-22
To, Tuan C (Department: 3663)
Data processing: vehicles, navigation, and relative location
Vehicle control, guidance, operation, or indication
Automatic route guidance vehicle
C340S992000, C342S465000
Reexamination Certificate
active
07363126
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.
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: 5983198 (1999-11-01), Mowery et al.
patent: 6184823 (2001-02-01), Smith 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: 6891500 (2005-05-01), Hall et al.
patent: 7020863 (2006-03-01), Teig et al.
patent: 7197500 (2007-03-01), Israni et al.
patent: 2002/0046073 (2002-04-01), Indseth et al.
patent: 2002/0082772 (2002-06-01), Okano
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/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
Kuhn, H.W.; “The Hungarian Method for the Assignment Problem,” Naval Research Logistics Quarterly (1955); pp. 83-97, vol. 2.
Beardwood, Jillian, et al.; “The Shortest Path Through Many Points,” Proceedings of the Cambridge Philosophical Society (Mar. 1958); pp. 299-328, vol. 55.
Gillett, Billy E., et al.; “A Heuristic Algorithm for the Vehicle-Dispatch Problem,” Operations Research (Apr. 1971); pp. 340-349, vol. 22.
Fisher, M.L., et al.; “A Generalized Assignment Heuristic for Vehicle Routing,” NETWORKS (1981); pp. 109-124, vol. 11.
Christofides, Nicos, et al.; “State-Space Relaxation Procedures for the Computation of Bounds to Routing Problems,” NETWORKS (1981); pp. 145-164, vol. 11.
Beasley, J.E., “Fixed Routes,” Journal of the Operational Research Society (1984); pp. 49-55, vol. 35, No. 1.
Daganzo, Carlos F.; “The Distance Traveled to Visit N Points With a Maximum of C Stops Per Vehicle: An Analytical Model and An Application,” Transportation Science (Nov. 1984); pp. 331-350; vol. 18, No. 4.
Dror, M., et al.; “Stochastic Vehicle Routing With Modified Savings Algorithm,” European Journal of Operational Research (1986); pp. 228-235; vol. 23.
Daganzo, Carlos F.; “One-to-Many Distribution With Trans-Shipments,” Logistics Systems Analysis (3rd Ed. 1999, Springer-Verlag, Berlin); Chapter 5; pp. 163-210.
Daganzo, Carlos F.; “Many-to-Many Distribution,” Logistics Systems Analysis (3rd Ed. 1999, Springer-Verlag, Berlin); Chapter 6; pp. 211-273.
Osman, Ibrahim H., et al.; “Meta-Heuristics: An Overview,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 1; pp. 1-21.
Al-Mahmeed, Ahmed S.; “Tabu Search, Combination and Integration,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 20; pp. 319-330.
Battiti, Roberto, et al.; “Vector Quantization with the Reactive Tabu Search,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 21; pp. 331-342.
Castelino, Diane, et al.; “Tabu Thresholding for the Frequency Assignment Problem,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 22; pp. 343-359.
Dell'Amico, Mauro, et al.; “A New Tabu Search Approach to the 0-1 Equicut Problem,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 23; pp. 361-377.
Dowsland, Kathryn, A.; “Simple Tabu Thresholding and the Pallet Loading Problem,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 24; pp. 379-405.
Glover, Fred, et al.; “Critical Event Tabu Search for Multidimensional Knapsack Problems,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 25; pp. 407-427.
Glover, Fred, et al.; “Solving Dynamic Stochastic Control Problems in Finance Using Tabu Search with Variable Scaling,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 26; pp. 429-448.
Hanafi, S., et al.; “Comparison of Heuristics for the 0-1 Multidimensional Knapsack Problem,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 27; pp. 449-465.
Løkketangen, Arne, et al.; “Probabilistic Move Selection in Tabu Search for Zero-One Mixed Integer Programming Problems,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 28; pp. 467-487.
Sondergeld, Lutz, et al.; “A Star-Shaped Diversification Approach in Tabu Search,” Meta-Heuristics: Theory & Applications (1996 , Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 29; pp. 489-502.
Toulouse, Michel, et al.; “Communication Issues in Designing Cooperative Multi-Thread Parallel Searches,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 30; pp. 503-522.
Tseng, Fan; “A Study on Algorithms for Selecting r Best Elements from An Array,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 31; pp. 523-535.
Valls, Vicente, et al.; “A Modified Tabu Thresholding Approach for the Generalised Restricted Vertex Colouring Problem,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 32; pp. 537-553.
Woodruff, David L.; “Chunking Applied to Reactive Tabu Search,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 33; pp. 555-569.
Zachariasen, Martin et al.; “Tabu Search on the Geometric Traveling Salesman Problem,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 34; pp. 571-587.
Charon, Irène, et al.; “Mixing Different Components of Metaheuristics,” Meta-Heuristics: Theory & Applications (1996, Kluwer Academic Publishers, Boston; I.H. Osman and J.P. Kelly, Editors); Chapter 35; pp. 58
Zaret David
Zhong Hongsheng
Alston & Bird LLP
To Tuan C
United Parcel Service of America
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-2777406