Parallel solution generation
AssigneeProcomp Solutions Oy
InventorOlli Braysy
Life of this patent
Estimating the term…
Abstract
The application describes parallel solution generation. A data processing apparatus includes a memory including a computer program code, and at least two processors configured to execute the computer program code. The computer program code includes a component program run in parallel on at least two processors to generate solution components compiled in parallel of points, and to store the added solution components in the memory; and a solution program run in parallel on at least two processors to generate a solution by adding one solution component at a time, read from the memory, to the solution based on a key point, and to store the added solution component to the solution in the memory.
Claims19
A data processing apparatus comprising a memory including a computer program code, and at least two processors which are configured to execute the computer program code, said computer program code comprising:
- a component program that forms solution components compiled of points from a total set of points, and stores the formed solution components in the memory;
- and
- a solution program that generates a solution by adding one solution component at a time, read from the memory, to the solution based on a key point, and stores the added solution component to the solution in the memory,
- wherein each solution component begins and ends at a node comprising a terminal, depot, or warehouse,
- wherein the solution indicates a route through the total set of points,
- wherein the key point is defined as a point that is the closest to any point within a set of previously selected solution components,
- wherein the solution program adds a subsequent solution component to the solution based at least in part on a determination that the subsequent solution component includes the key point,
- wherein the at least two processors comprise a plurality of N processors within a multicore central processing unit and an N+1 processor within a graphics processor on a separate graphics card,
- wherein the graphics card comprises its own memory in which the solution components are stored,
- wherein the component program is run in parallel on each of the N processors within the multicore central processing unit and the N+1 processor within the graphics processor, and
- wherein the solution program is run in parallel on each of the N processors within the multicore central processing unit and the N+1 processor within the graphics processor.
A non-transitory computer-readable medium containing computer program code for execution by at least two processors, the computer program code comprising:
- a component program that forms solution components compiled of points from a total set of points, and stores the formed solution components in a memory;
- and
- a solution program that generates a solution by adding one solution component at a time, read from the memory, to the solution based on a key point, and stores the added solution component to the solution in the memory,
- wherein each solution component begins and ends at a terminal, depot, or warehouse,
- wherein the solution indicates a route through the total set of points,
- wherein the key point is defined as a point that is the closest to any point within a set of previously selected solution components, and
- wherein the solution program adds a subsequent solution component to the solution based at least in part on a determination that the subsequent solution component includes the key point,
- wherein the at least two processors comprise a plurality of N processors within a multicore central processing unit and an N+1 processor within a graphics processor on a separate graphics card,
- wherein the graphics card comprises its own memory in which the solution components are stored,
- wherein the component program is run in parallel on each of the N processors within the multicore central processing unit and the N+1 processor within the graphics processor, and
- wherein the solution program is run in parallel on each of the N processors within the multicore central processing unit and the N+1 processor within the graphics processor.
Dependencies are inferred from the claim text.