Source: http://www.google.com/patents/US8165905?dq=5,646,839
Timestamp: 2017-03-25 21:51:31
Document Index: 322568396

Matched Legal Cases: ['art 102', 'art 105', 'art 103', 'art 104', 'art 105', 'art 106', 'art 101', 'art 102', 'art 105', 'art 102', 'art 104', 'art 101', 'art 104', 'art 104', 'art 103', 'art 105']

Patent US8165905 - Data processing unit, data processing method, and program product for ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA data processing unit, a data processing method, and a program product for determining a transhipment method are provided. The data processing unit may include a solution search processor for performing solution search processing of a plurality of physical objects. In the data processing unit, a data...http://www.google.com/patents/US8165905?utm_source=gb-gplus-sharePatent US8165905 - Data processing unit, data processing method, and program product for determining a transshipment methodAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS8165905 B2Publication typeGrantApplication numberUS 10/866,038Publication dateApr 24, 2012Filing dateJun 14, 2004Priority dateJun 13, 2003Fee statusPaidAlso published asUS20050004849Publication number10866038, 866038, US 8165905 B2, US 8165905B2, US-B2-8165905, US8165905 B2, US8165905B2InventorsMasashi YamamotoOriginal AssigneeNs Solutions CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (11), Non-Patent Citations (25), Classifications (10), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetData processing unit, data processing method, and program product for determining a transshipment method
US 8165905 B2Abstract
A data processing unit, a data processing method, and a program product for determining a transhipment method are provided. The data processing unit may include a solution search processor for performing solution search processing of a plurality of physical objects. In the data processing unit, a data representation of a loading state of an object may have a corresponding variable which takes as a value an identification number of a heap at a predetermined physical location. The data representation of the loading state may include a coordinate value indicating a loading order of the object in the heap. The data processing unit may also include an initial condition inputter. The solution search processor may perform the solution search processing by constructing a search tree.
This application is based upon and claims the benefit of priority from the prior Japanese Patent Application Nos. 2003-169686, filed on Jun. 13, 2003 and 2004-164620, filed on Jun. 2, 2004, the entire contents of which are incorporated herein by reference.
Three loading locations, namely, a location A, location B, and location C are envisaged as loading locations for a steel product or the like. The location A is a place where physical objects for transshipment (hereinafter simply referred to as “object”) are initially loaded, while the location C is a final place for loading the objects. The location B is along a transfer path of the objects between the location A and location C, and is a place to transship the objects temporarily from the location A thereto, and transship the objects therefrom to the location C into a desired loading state.
The present invention is made in light of the above problem, and it is an object of the present invention to provide a data processing unit, data processing method, and program which can considerably reduce the size of a solution space compared to a prior one consisting of a set of solution candidates simulating object transferring orders, such that the solution search processing time is significantly shortened and the practical utility value of the processing is enhanced.
FIG. 1 is an explanatory diagram of an example of a modeling of a constraint satisfaction problem that applies the present invention;
The following description relates to a preferable embodiment to which the present invention is applied, with reference to the drawings attached hereto.
Note that here, the “heap” means a lump of objects formed of plural objects piled up as shown in FIG. 1, however, even a case of a single object structure is handled within the concept of “heap”.
Further, terms used in the following descriptions, namely, “heap number variable”, “transferring order variable”, “solution”, “partial solution”, and “partial solution candidate” are defined as follows:
P A(1)=2 (formula 1)
H A(1)=2 (formula 2)
P A(2)=1 (formula 3)
H A(2)=1 (formula 4)
P A(3)=2 (formula 5)
H A(3)=1 (formula 6)
P A(4)=1 (formula 7)
H A(4)=2 (formula 8)
P C(1)=1 (formula 9)
H C(1)=4 (formula 10)
P C(2)=1 (formula 11)
H C(2)=2 (formula 12)
P C(3)=1 (formula 13)
H C(3)=3 (formula 14)
P C(4)=1 (formula 15)
H C(4)=1 (formula 16)
S AB(4)<S AB(2) (formula 17)
S AB(1)<S AB(3) (formula 18)
S BC(4)<S BC(2) (formula 19)
S BC(4)<S BC(3) (formula 20)
S BC(4)<S BC(1) (formula 21)
S BC(2)<S BC(3) (formula 22)
S BC(2)<S BC(1) (formula 23)
S BC(3)<S BC(1) (formula 24)
(∀i, j:i≠j)((P B(i)=(P B(j) S BC(i)<S BC(j)) S AB(i)>S AB(j)) (formula 47)
(∀i, j:i≠j)((P B(i)=(P B(j) S AB(i)<S AB(j) S BC(i)>S BC(j)) (formula 48)
Further, by examining a contradiction between the constraint condition (2) on SAB, SBC, and the constraint condition (1) on SAB, SBC, stored in the constraint condition storing part 102, the constraint investigating part 105 judges whether the partial solution candidate satisfies the constraints. Note that in the formula 47 and the formula 48, the anteroposterior relation of the transferring orders SAB, SBC, is inverse for the objects sharing the same heap number in a predetermined location.
“200” represents a system bus which is a transmission path to transmit data among units, and to transmit control data. Each unit which is present in a case of the data processing unit is connected through the system bus 200. Hereinafter, each unit will be explained. A central processing unit (hereinafter called “CPU”) 201 performs various controls and computations of the data processing unit, and has functions corresponding to the constraint condition deriving part 103, the solution search processing part 104, the constraint investigating part 105, and the output controlling part 106 in FIG. 2.
A random access memory (hereinafter referred to as “RAM”) 202 functions as a main memory of the CPU 201, and as a storing region of an executing program, an execution area and data area of a program. Other than that, the RAM 202 has functions corresponding to the initial condition storing part 101 and the constraint condition storing part 102 in FIG. 1, as well as a function to temporarily retain a computation result of the constraint satisfaction solution investigating part 105. A read-only memory (hereinafter referred to as “ROM”) 203 stores a basic program to control each unit in the data processing unit, namely BIOS (basic input/output system), and data necessary for the data processing unit to operate.
A group of units to input and output data (hereinafter referred simply to “FDD”) 204 inputs and outputs data in a detachable external storage medium such as a flexible disk and a CD-ROM. A network interface (hereinafter referred simply to as “NETIF”) 205 connects to an external network through a modem 206 described below, or connects to a LAN 207 described below. The NETIF 205 judges controlling and connecting states to transfer data between data processing units through a network.
A video RAM (hereinafter referred to as “VRAM”) 208 holds an image data operated to be displayed on a CRT 209 described below. The CRT 209 is a displaying device such as a display.
The constraint condition storing part 102 stores the derived constraint condition (1) on SAB, SBC. Subsequently, the solution search processing part 104 determines, by referring to data showing “the number of heaps formable in the location B being two” stored in the initial condition storing part 101, that the objects 1 to 4 can be transshipped to the heap 1 or heap 2 respectively in the location B, and executes solution search using a branch-and-bound technique by updating the combination of values for variables indicating the heap numbers in the location B (step S402). Incidentally, if an identification data on the heaps are inputted as an initial condition, the solution search processing part 104 may judge from the identification data that the objects 1 to 4 are transshippable to the heap 1 or 2 respectively in the location B.
Here, the values for SAB(1), SAB(2) exist which satisfy the constraint conditions of the formulas 17 to 18 and the formula 26 such as “SAB(1)=1, SAB(2)=2” or “SAB(1)=2, SAB(2)=3”. In addition, as to the constraint condition on SBC, since there is no constraint condition (2) on SBC, a contradiction between constraint conditions cannot exist, so that the solution search processing part 104 continues to select a value for PB(3) (in the case hereof, PB(3)=1) (step S410, step S411). Then, the constraint condition deriving part 103 similarly derives a constraint condition (2), while the constraint investigating part 105 similarly judges presence of a contradiction between the constraint conditions.
S AB(1)<S AB(3) (formula 33) (derived from the formulas 24 and 47)
S AB(1)<S AB(2) (formula 34) (derived from the formulas 23 and 47)
S AB(1)<S AB(4) (formula 35) (derived from the formulas 21 and 47)
S AB(3)<S AB(2) (formula 36) (derived from the formulas 22 and 47)
S AB(3)<S AB(4) (formula 37) (derived from the formulas 20 and 47)
S AB(2)<S AB(4) (formula 38) (derived from the formulas 19 and 47)
S BC(3)<S BC(1) (formula 41) (derived from the formulas 18 and 48)
S BC(2)<S BC(4) (formula 42) (derived from the formulas 17 and 48)
S AB(1)<S AB(3) (formula 43)
S AB(1)<S AB(2) (formula 44)
S AB(3)<S AB(2) (formula 45)
S AB(1)<S AB(3) (formula 18(formula 43))
S BC(3)<S BC(1) (formula 24 (formula 46))
Next, another modeling example for constraint satisfaction problem conceived by the inventor will be explained. In order to compare with the above-described embodiment, this comparative example refers to the modeling example of the constraint satisfaction problem in FIG. 1.
The following explanation cites a solution candidate of “1A−1B”, “1A−1B”, “2A−2B”, “2A−2B”. This indicates, as shown in FIG. 7, that: upon the first transfer, an object 4 loaded on a heap 1 in a location A is transshipped to a heap 1 in a location B (“1A−1B”); upon the second transfer, an object 2 loaded on the heap 1 in the location A is transshipped to the heap 1 in the location B (“1A−1B”); upon the third transfer, an object 1 loaded on a heap 2 in the location A is transshipped to a heap 2 in the location B (“2A−2B”); and upon the fourth transfer, an object 3 loaded on the heap 2 in the location A is transshipped to the heap 2 in the location B (“2A−2B”)
Next, the constraint condition of the comparative example is specifically explained with reference to the object 1 and object 3 as examples. In the example of FIG. 1, the object 2 is loaded on an upper level compared to the object 4 in the location C (HC(2)>HC(4)). To actualize that loading state, it is conditioned that at least the object 2 and object 4 are loaded on different heaps in the location B (PB(2)≠ PB(4)) or are loaded on the same heap with the object 4 being loaded on an upper level compared to the object 2 (PB(2)=PB(4) and HB(4)>HB(2)). Accordingly, the solution candidate “1A−1B”, “1A−1B”, “2A−2B”, “2A−2B” shown in FIG. 7 is detected as infringing the constraints.
On the other hand, the solution space for the comparative example is a set of solution candidates which can specify in what order the objects 1 to 4 are shipped from the heap 1 or 2 in the location A, and which heap in the location B the objects 1 to 4 being shipped are loaded on. Accordingly, solution candidates of 24×4C2=96 patterns exist in the solution space thereof. Hence, the solution space for the above-described embodiment is considerably narrower than that for the comparative example. As the number of objects for transshipping or the number of heaps in the location A increases, the size difference between the solution spaces of the above-described embodiment and the comparative example widens exponentially, and such trend becomes increasingly significant.
Further, in many cases, each object to be transferred (“object”) has physical properties such as size, length, weight, and so forth, according to which the number of objects transferable at one time by transferring means such as a crane or a forklift varies. Based on such a constraint by the equipment, the “object” in the above description on the embodiment does not necessarily indicate a singular object, so that all or a part of the above-described “object” may be handled as a set of objects in units loadable at one time or in units conveyable at one time by a transfer means.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5733098 *Oct 11, 1996Mar 31, 1998Hk Systems, Inc.Case picking systemUS5803502 *Dec 23, 1994Sep 8, 1998Noll; VirginiaMethod and structure for properly positioning freight in a trailer, container or other freight receptacleUS5809489 *Jun 21, 1996Sep 15, 1998Schema-Evolutionary Algorithms Ltd.Method for determining a stowage planUS6031984 *Mar 9, 1998Feb 29, 2000I2 Technologies, Inc.Method and apparatus for optimizing constraint modelsUS6567788 *Aug 5, 1998May 20, 2003The United States Of America As Represented By The Secretary Of The NavyProgrammed logistic system and method for transportation and reception of commoditiesUS6698655 *Mar 21, 2003Mar 2, 2004Honda Giken Kogyo Kabushiki KaishaSuper cross-dock logistics system and methodUS6845909 *Mar 28, 2003Jan 25, 2005United Parcel Service Of America, Inc.Systems and methods of inventory management utilizing unattended facilitiesUS7047710 *Jun 20, 2003May 23, 2006Logistik + Informatik GmbhApparatus for depositing a packing unit at a desired position on a load carrierUS7426484 *Feb 4, 2003Sep 16, 2008United Parcel Service Of America, Inc.Consolidated shipping and distribution of multiple orders with returnsUS20030171962 *Oct 28, 2002Sep 11, 2003Jochen HirthSupply chain fulfillment coordinationUS20040143465 *Dec 18, 2003Jul 22, 2004Kouji ImanishiConsolidated air cargo management system* Cited by examinerNon-Patent CitationsReference1 *A. E. Rizzoli, L. M. Gambardella, M. Zaffalon, and M. Mastrolilli, 1999, "Simulation for the Evaluation of Optimised Operations Policies in a Container Terminal" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=?doi=10.1.1.42.7389 N1-CiteSeerX-Scientific Literature Digital Library and Search Engine [http://citeseerx.ist.psu.edu/oai2] (United S.2 *A. E. Rizzoli, L. M. Gambardella, M. Zaffalon, and M. Mastrolilli, 1999, "Simulation for the Evaluation of Optimised Operations Policies in a Container Terminal" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=?doi=10.1.1.42.7389 N1—CiteSeerX—Scientific Literature Digital Library and Search Engine [http://citeseerx.ist.psu.edu/oai2] (United S.3 *Andel, Tom ("Software Helps You Take Loads Off Your Fleet," Transportation and Distribution, Jul. 1991, pp. 39-44).4 *Bontempi G., Gambardella L.M., Rizzoli A.E. "Simulation and Optimization for Management of Intermodal Terminals," European Simulation Multiconference 1997, Instanbul, Jun. 1-4, 1997.5 *Gambardella, L. M.; Mastrolilli, M.; Rizzoli, A. E.; and Zaffalon, M. "An optimization methodology for intermodal terminal management," Journal of Intelligent Manufacturing, vol. 12, No. 5; 2001, SN 0956-5515, UL http://dx.doi.org/10.1023/A:1012208605758; DO 10.1023/A:1012208605758.6 *Hock Chan, Sen. "Dynamic AGV-Container Job Deployment Strategy." HPCES Programme, Singapore-MIT Alliance. 2002.7 *Hock Chan, Sen. "Dynamic AGV-Container Job Deployment Strategy." Master's Thesis, National University of Singapore, 2000.8 *Katta G. Murty, Jiyin Liu, Yat-Wah Wan, Chuqian Zhang, Maria C. L. Tsang, and Richard Linn. "DSS (Decision Support Systems) for Operations in a Container Shipping Terminal." Dec. 29, 2000.9 *Knut Alicke ("Modeling and optimization of the intermodal terminal Mega Hub," OR Spectrum (2002) 24: 1 17, Feb. 1, 2002).10 *Knut Alicke ("Modeling and optimization of the intermodal terminal Mega Hub," OR Spectrum (2002) 24:1 17, Feb. 1, 2002).11 *Li, Chung-Lun; George L. Vairaktarakis. "Loading and unloading operations in container terminals." IIE Transactions. Institute of Industrial Engineers, Inc. (IIE). Apr. 1, 2004. Retrieved Mar. 4, 2011 from HighBeam Research.12 *P.A. Ioannou, E.B. Kosmatopoulos, K. Vukadinovic, Chin-I Liu, H.Pourmohammadi and Edmond Dougherty, Jr. "Real Time Testing and Verification of Loading and Unloading Algorithms Using Grid Rail (GR) Final Report." for the Center for Commercial Deployment of Transportation Technologies, University of Southern California, Center for Advanced Transporta.13Patent Abstracts of Japan, Publication No. 05028126 A, Feb. 5, 1993 * Abstract.14Patent Abstracts of Japan, Publication No. 05173999 A, Jul. 13, 1993 * Abstract.15Patent Abstracts of Japan, Publication No. 05233597 A, Sep. 10, 1993 * Abstract.16Patent Abstracts of Japan, Publication No. 06332908 A, Dec. 2, 1994 * Abstract.17Patent Abstracts of Japan, Publication No. 07064967 A, Mar. 10, 1995 * Abstract.18 *Photograph, Dortmund terminal, downloaded from PhotographersDirect.com on Jun. 26, 2010.19 *Pimpawat C. and N. Chaiyaratana ("Using a co-operative co-evolutionary genetic algorithm to solve a three dimensional container loading problem," Proceedings of the 2001 Congress on Evolutionary Computation, 2001, May 27-30, 2001).20 *Rebello, M.,; Julian, V.; Carrascosa, C.; Botti, V. ("A Multi-Agent system for the Automation of a Port Container Terminal," Autonomous Agents 2000 workshop on Agents in Industry, Barcelona, Spain, 2000).21 *Rebollo, M., Vicente, J., Carrascosa, C., Botti, V., 2001. "A MAS approach for port container terminal management." In: Third Iberoamerican Workshop on DAI-MAS Atiaia, Sao Paulo, Brazil, pp. 83-94.22 *Rebollo, M., Vicente, J., Carrascosa, C., Botti, V., 2001. "A MAS approach for port container terminal management." In: Third Iberoamerican Workshop on DAI-MAS, Atiaia, Sao Paulo, Brazil, pp. 83-94.23 *Staff Report ("Computers Get to the route of the Problem," Chilton's Distribution, May 1990, pp. 68-74).24 *Steenken, Dirk; Vobeta, Stefan; and Stahlbock, Robert. "Container terminal operation and operations research-a classification and literature review." OR Spectrum, vol. 26, No. 1, 3-49. Jan. 1, 2004, Springer Berlin / Heidelberg. SN 0171-6468. http://dx.doi.org/10.1007/s00291-003-0157-z. DO 10.1007/s00291-003-0157-z.25 *Steenken, Dirk; Voβ, Stefan; and Stahlbock, Robert. "Container terminal operation and operations research—a classification and literature review." OR Spectrum, vol. 26, No. 1, 3-49. Jan. 1, 2004, Springer Berlin / Heidelberg. SN 0171-6468. http://dx.doi.org/10.1007/s00291-003-0157-z. DO 10.1007/s00291-003-0157-z.* Cited by examinerClassifications U.S. Classification705/7.12International ClassificationG06Q10/00, G06N5/04, B65G63/00Cooperative ClassificationG06Q10/087, G06Q10/08, G06Q10/0631European ClassificationG06Q10/08, G06Q10/0631, G06Q10/087Legal EventsDateCodeEventDescriptionJun 14, 2004ASAssignmentOwner name: NS SOLUTIONS CORPORATION, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:YAMAMOTO, MASASHI;REEL/FRAME:015481/0615Effective date: 20040607Oct 26, 2015FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services