Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
2007-07-03
2011-10-25
Holmes, Michael B. (Department: 2129)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
Reexamination Certificate
active
08046319
ABSTRACT:
The methods disclosed comprise the linehaul optimization algorithm which is a hybrid algorithm incorporating the basic structure of the Hungarian Assignment algorithm or equivalent and an improvement heuristic. However, in this particular case there is not a direct application of the existing, well-known Hungarian Assignment algorithm or equivalent in conjunction with a heuristic. The structure of the assignment model being used here is based on the Hungarian Assignment algorithm or equivalent but has been revised and enhanced to identify systematically (by using grouping) a number of equivalent optimal solutions (that give the same optimal, minimum cost for a particular iteration). A heuristic is then used to identify the ‘best’ optimal solution, of the many identified, that would contribute the most incremental cost reduction in future iterations of the heuristic.
REFERENCES:
patent: 2002/0026342 (2002-02-01), Lane et al.
patent: 2004/0172174 (2004-09-01), Julich et al.
patent: 2004/0199415 (2004-10-01), Ho
patent: 2005/0209913 (2005-09-01), Wied et al.
‘Truck delivery scheduling system with a mobile communication feature’: Sawamoto, 2002, International journal of information technology, vol. 8, No. 1, pp. 26-39.
‘Matrix reductions using the Hungarian Method for the generation of school timetables’: Lions, 1966, Communications of the ACM, vol. 9, No. 5, pp. 349-354.
Satir, S. 2003. Applied Vehicle Routing and Scheduling Optimization for Pickup and Delivery Operations at a Trucking Terminal. Master's Thesis, University of New Brunswick.
Smilowitz, K. R., Atamturk, A., and Daganzo, C. F. 2003. Defered item and vehicle routing within integrated networks. Transportation Research Part E, 39: 305-323.
Subramanian, R., Scheff, R.P., Quillinan, J. D., Wiper, D. S., and Marsten, R. E. 1994. Coldstart: Fleet Assignment at Delta Airlines, Interfaces, 24(1): 104-120.
Tan, K.C., Lee, L.H., Zhu, Q.L., and Ou, K. 2000. Heuristic Methods for Vehicle Routing Problem with Time Windows. Artifical Intelligence in Engineering, 15: 281-295.
Taniguchi, E., Thompson, R.G., Yamada, T., and Van Duin, R. 2001. City Logistics: Network Modelling and Intelligent Transport Systems, Pergamon; 5 pages.
TransCAD. 2004. 4.7 User's Guide Supplement, Caliper Corporation.
Transcad. 2006. Available at http://www.caliper.com/TransCAD/ApplicationModules.htm#Routing [cited Apr. 4, 2006].
Transportation in Canada 2004. 2004. Annual Report Transport Canada. [Online]. Available at http://www.tc.gc.ca/ pol/en/report/anre2004/toc—e.htm [Cited Apr. 2, 2006].
Yang, J., Jaillet, P., and Mahmassani, H. 2004. Real-time multivehicle truckload pickup and delivery problems. Transportation Science, 38: 135-148.
Arunapuram, S., Mathur,K., and Solow, D., 2003. Vehicle routing and scheduling with full truckloads. Transportation Science, 37: 170-182.
Atallah, M. (Ed.), (1999). Algorithms and Theory of Computation Handbook. CRC Press, Boca Raton, pp. 7-21, 16 pp.
Barnhart, C., Cohn, A.M., Johnson,E.L., Klabjan, D., Nemhauser, G.L, and Vance, P.N. 2002. Airline crew scheduling. Handbook of Transportation Science (2nd Edition). Randolph W. Hall (editor). Kluwer Academic Publishers, Norwell, MA.
Barnhart, C., Hane, C., Johnson, E., and Sigismondi, G. 1995. A column generation and partitioning approach for multi-commodity flow problems. Telecommunication Systems, 3: 239-258.
Barnhart, C., Hane, C.A., and Vance, P.H. 2000. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research, 48(2): 318-326.
Barnhart, C., Kniker,T., and Lohatepanont, M. 2002. Itinerary-based airline fleet assignment. Transportation Science, 36(2): 199-217.
Barnhart, C., Rexing, B., Kniker, T., Jarrah, A., and Krishnamurthy, N. 2000. Airline fleet assignment with time windows. Transportation Science, 34(1): 1-20.
Brandao, J., and Mercer, A. 1997. A tabu search algorithm for the multi-trip vehicle routing and scheduling problem, European Jourmal of Operational Research..100: 180-191.
Canada's 50 Best Managed Companies. 2005 Winners. [Online]. Available from http://www.canadas50best.com/en/Winners/WinnersBest/2005+winners.htm [Cited Apr. 2, 2006].
Christiansen, M., Fagerholt, K., and Ronen, D. Ship Routing and Scheduling—Status and Perspectives. Transportation Science, 36: 1-18.
Christie, J.S., and Satir, S. 2004. Transport Logistics: Potential Traffic Related Spin-off Benefits, Canadian ITE Annual Conference, Moncton, New Brunswick.
Clarke, G., and Wright, J.W. 1964. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12: 568-581.
Cook, W., Cunningham, W.H., Pulleyblank, W.R. and Schrijver, A. 1998. Combinatorial Optimization, John Wiley & Sons, pp. 241-272, 32 pp.
Corberan, A., Meja G., and Sanchis, J.M. 2005 New Results on the Mixed General Routing Problem. Operations Research, 53: 363-376.
Cordeau, J.F., and Laporte, G. 2002 Tabu search heuristics for the vehicle routing problem. GERAD Technical report G-2002-15, University of Montreal, Canada.
Crainic, T.G, and Laporte, G. 1997. Planning models for freight transportation. European Journal of Operational Research, 97(409): 38.
Desaulniers, G., Lavigne, J., and Soumis, F. 1998. Multi-depot vehicle scheduling problems with time windows and waiting costs. European Journal of Operation Research, 111: 479-494.
Desrosiers, J., Dumas, Y., Solomon, M.M., and Soumis, F. 1995. Time Constrained Routing and Scheduling. Ball,M., Magnanti,T., Monma, C., and Nemhauser, G. (editors).
Eiselt, H. A., Gendreau, M., and Laporte, G. 1995. Arc routing problems, part II: The rural postman problem. Operations Research, 43: 399-414.
Fernández, A.J., and Hill, P.M. Jul. 2000. A comparative study of eight constraint programming languages over the boolean and finite domains. Constraints, 5(3): 275-301.
Fisher, M.L. 1995. Vehicle routing. Ball,M., Magnanti,T., Monma, C., and Nemhauser, G. eds. Handbook in Operations Research and Management Science: Network Routing. Holland, Amsterdam, the Netherlands, pp. 1-33.
Gendreau, M., G. Laporte, J. Potvin. 1997. Vehicle routing: Modern heuristics. E. Aarts, J. Lenstra, eds. Local Search in Combinatorial Optimization, Ch. 9. John Wiley & Sons Ltd., New York, pp. 311-336.
Godfrey, G., and Powell, W. B. 2002, An adaptive, dynamic programming algorithm for stochastic resource allocation problems II: Multi-period travel times. Transportation Science, 36(1): 40-54.
Hall, R. 2004. Vehicle routing: On the road to recovery. ORMS Today.
Christiansen, M. 1999. Decomposition of a combined inventory and time constrained ship routing problem. Transportation Science. 33 (1): 3-16.
Homer, P. 2000. The Sabre storey: The making of OR magic at AMR. ORMS Today.
ILOG Transport PowerOPs. 2006. ILOG PowerOps. [Online]. Available at: http://www.ilog.com/products/transportpowerops/features.cfm [Cited Apr. 4, 2006].
ILOG. 2003. “ILOG Scheduler 6.0 Getting Started”, User Manual.
ILGO. 2003. “ILOG Solver 6.0 User's Manual”, User Manual.
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. 1992. The Travelling Salesman Problem, Wiley.
Liu, J., C. Li, and Chan, C. 2003. Mixed truck delivery systems with both hub-and-spoke and direct shipment. Transportation Research Part E, 39: 325-339.
Merriam-Webster Online Dictionary. Mar. 2006. [Online] Available at http://www.m-w.com/dictionary/optimization. [Cited Apr. 2, 2006].
Powell, W. B., Shapiro, J. A., and Simaõ, H. P. 2002, An adaptive dynamic programming algorithm for the heterogeneous resource allocation problem. Transportation Science, 36(2): 231-249.
Powell, W., and Topaloglu, H. 2005. Fleet management. S. Wallance, W. Ziemba (editors), Applications of Stochastic Programming. MPS-SIAM Series on Optimization, Philadelphia.
Powell, W.B. 1996. A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers. Transportation Science, 30(3): 195-219.
Powell, W.B. 2003. Dynamic Models of Transportation Operations, In Supply Chai
Christie James S.
Satir Salim
Coughlan Peter
Derenyi Eugene F.
Fogler, Rubinoff LLP
Holmes Michael B.
University of New Brunswick
LandOfFree
Methods suitable for optimizing linehaul operations does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods suitable for optimizing linehaul operations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods suitable for optimizing linehaul operations will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4278221