Data processing: generic control systems or specific application – Specific application – apparatus or process – Article handling
Reexamination Certificate
2005-12-27
2005-12-27
Walsh, Donald P. (Department: 3653)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Article handling
C700S215000, C700S216000, C700S218000
Reexamination Certificate
active
06980885
ABSTRACT:
A computer-implemented method for routing shipments according to criticality includes accessing an initial solution to an optimization problem of routing multiple shipments to multiple locations using multiple vehicles, the initial solution including multiple loads such that each shipment is routed within exactly one load and a global cost across all loads is minimized, the initial solution being generated independent of the criticality of the shipments. Into each of one or more critical loads in a current solution, one or more non-critical shipments are inserted that are within a neighborhood of the critical load, a critical load being a load containing at least one critical shipment. One or more local search operations are executed to improve the initial solution, the operations including at least one of: (a) splitting each of one or more selected critical loads in a current solution into two new critical loads; (b) for each of one or more selected critical load pairs in a current solution, move a sequence of stops from one critical load in the pair to the other critical load in the pair and/or swap two sequences of stops between the critical loads in the pair; and (c) for each of one or more selected critical loads in a current solution that are indirect critical loads having at least one in-transit stop, break up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and execute operation (b) on each of one or more selected critical load pairs, each selected critical load pair including at least one new direct critical load.
REFERENCES:
patent: 5093794 (1992-03-01), Howie et al.
patent: 5237158 (1993-08-01), Kern et al.
patent: 5403147 (1995-04-01), Tanaka
patent: 5548518 (1996-08-01), Dietrich et al.
patent: 6285951 (2001-09-01), Gaskins et al.
patent: 6401078 (2002-06-01), Roberts et al.
patent: 6571213 (2003-05-01), Altendahl et al.
patent: 6622127 (2003-09-01), Klots et al.
G. Laporte, “CRT-745 The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms,” Centre de recherche sur les transports—Publication #745, 35 pages, Feb. 1991.
C.H. Papadimitrion, K. Steiglitz, “Introduction on Local Search,” Combinational Optimization Algorithms and Complexity, Prentice-Hall, 2 pages, 1982.
R.K. Ahuja et al., “Traveling Salesman Problem,” Chapter 16: Lagrangian Relaxation and Network Optimization, Section 16.5 Applications of Lagrangian Relaxation; textbook titleNetwork Flows: Theory, Algorithms, and Applications, ISBN No. 1-13-02776507, includes textbook cover page, ISBN No. page and pp. 623-625 5 pages total, © date: 1993.
Taiwan, First Office Action, English version, 1 page, Nov. 28, 1002.
Leih Todd Christopher
Lu Pei
Szabady Roy J.
Ye Jian
Harris Brian E.
i2 Technologies US, Inc.
Walsh Donald P.
Walton James E.
LandOfFree
Routing shipments according to criticality does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Routing shipments according to criticality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing shipments according to criticality will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3497216