System and method of vessel scheduling for product distribution

Patent metadata

Field	Value
Publication number	US-9665845-B2
Application number	US-201514635906-A
Country	US
Kind code	B2
Filing date	Mar 2, 2015
Priority date	Jun 23, 2006
Publication date	May 30, 2017
Grant date	May 30, 2017

Abstract

A system, computer-implemented method, and software for automatically planning and scheduling ocean-going vessels for oil distribution is provided. The scheduling of the vessels is based on a filtered beam search and greedy heuristic. A server can be used for receiving a schedule request and one or more constraints for scheduling one or more vessels from one or more users. An optimization engine can be used for generating a schedule based at least in part on the one or more constraints using a beam search algorithm.

First claim

What is claimed is:

1. A system for assigning products to transportation compartments, comprising:
one or more transportation compartments configured to hold one or more products;
a computer comprising a processor configured to receive a schedule request and one or more constraints for compartment packing of the one or more products in the one or more transportation compartments and generate a packing plan comprising one or more transportation compartment assignments based on the one or more constraints using a combinatorial search that generates a solution represented by a vector V=(v_1, . . . , v_n), an ith component of the vector being a product and an amount assigned to an ith transportation compartment, the combinatorial search:
constructs a partial solution with elements fixed for the first k elements of the vector where k is less than or equal to n;
constructs the set of possible candidates S for the (k+1)st position;
constructs an extension by adding the next element from S to the partial solution; and
constantly checks the extension to determine whether the extension yields a partial solution, wherein the processor continues to extend the partial solution as long as the extension yields a partial solution, and when S is empty, the processor backtracks to v_k and replaces v_k with a next candidate; and

at least one of the one or more products is assigned to be packed into at least one of the one or more transportation compartments based on the generated packing plan.

2. The system of claim 1 , wherein the combinatorial search further comprises a solution representing an amount of the one or more products assigned to the one or more transportation compartments.

3. The system of claim 2 , wherein the combinatorial search further comprises an input comprising:
a capacity of the one or more transportation compartments; and
inventory data.

4. The system of claim 1 , wherein the combinatorial search further comprises an output comprising:
an indication if a feasible packing plan exists; and
the transportation compartment assignment comprises a product and an amount of the one or more transportation compartments.

5. The system of claim 1 , wherein the packing plan further comprises:
a schedule comprising one or more vehicle assignments to one or more terminals based on the one or more constraints using a beam search algorithm comprising a branch-and-bound algorithm with a greedy heuristic estimating the desirability of one or more nodes, the branch-and-bound algorithm using possible vehicle assignments as branches and ordering terminal/product pairs according to criticality.

6. The system of claim 5 , wherein the beam search algorithm comprises evaluating a vehicle candidate includes generating a schedule for a predetermined number of days d using the following heuristic:
(1) set End Date=Current Date +d days;
(2) select a critical terminal;
(3) rank vehicle candidates for the selected terminal based on feasibility and unit cost and schedule the best vehicle candidate; and
(4) go back to step 2 when a next run-out date is before the End Date.

7. A computer-implemented method for assigning products to transportation compartments, comprising:
receiving, by a computer comprising a processor, a schedule request and one or more constraints for compartment packing of one or more products in one or more transportation compartments;
generating, by the processor, a packing plan comprising one or more transportation compartment assignments based on the one or more constraints using a combinatorial search, the combinatorial search:
generating a solution represented by a vector V=(v_1, . . . , v_n), an ith component of the vector being a product and an amount assigned to an ith transportation compartment;
constructing a partial solution with elements fixed for the first k elements of the vector where k is less than or equal to n;
constructing the set of possible candidates S for the (k+1)st position;
constructing an extension by adding the next element from S to the partial solution; and
constantly checking the extension to determine whether the extension yields a partial solution, wherein the processor continues to extend the partial solution as long as the extension yields a partial solution, and when S is empty, the computer backtracks to v_k and replaces v_k with a next candidate; and

assigning at least one of the one or more products to be packed into at least one of the one or more transportation compartments based on the generated packing plan.

8. The computer-implemented method of claim 7 , wherein the combinatorial search further comprises a solution representing an amount of the one or more products assigned to the one or more transportation compartments.

9. The computer-implemented method of claim 8 , wherein the combinatorial search further comprises an input comprising:
a capacity of the one or more transportation compartments; and
inventory data.

10. The computer-implemented method of claim 7 , wherein the combinatorial search further comprises an output comprising:
an indication if a feasible packing plan exists; and
the transportation compartment assignment comprises a product and an amount for the one or more transportation compartments.

11. The computer-implemented method of claim 7 , wherein the packing plan further comprises:
a schedule comprising one or more vehicle assignments to one or more terminals based on the one or more constraints using a beam search algorithm comprising a branch-and-bound algorithm with a greedy heuristic estimating the desirability of one or more nodes, the branch-and-bound algorithm using possible vehicle assignments as branches and ordering terminal/product pairs according to criticality.

12. The computer-implemented method of claim 11 , wherein the beam search algorithm comprises evaluating a vehicle candidate includes generating a schedule for a predetermined number of days d using the following heuristic:
(1) set End Date=Current Date +d days;
(2) select a critical terminal;
(3) rank vehicle candidates for the selected terminal based on feasibility and unit cost and schedule the best vehicle candidate; and
(4) go back to step 2 when a next run-out date is before the End Date.

13. A non-transitory computer-readable medium embodied with software for assigning products to transportation compartments, the software when executed by one or more computers is configured to:
receive a schedule request and one or more constraints for compartment packing of one or more products in one or more transportation compartments;
generate a packing plan comprising one or more transportation compartment assignments based on the one or more constraints using a combinatorial search that generates a solution represented by a vector V=(v_1, . . . v_n), an ith component of the vector being a product and an amount assigned to an ith transportation compartment, the combinatorial search:
constructs a partial solution with elements fixed for the first k elements of the vector where k is less than or equal to n;
constructs the set of possible candidates S for the (k+1)st position;
constructs an extension by adding the next element from S to the partial solution; and
constantly checks the extension to determine whether the extension yields a partial solution, wherein the processor continues to extend the partial solution as long as the extension yields a partial solution, and when S is empty, the processor backtracks to v_k and replaces v_k with a next candidate; and

assign at least one of the one or more products to be packed into at least one of the one or more transportation compartment

Assignees

• Jda Software Group Inc

Inventors

• Ye Jian
• Hartge Mark

Classifications

• G06Q10/08

  Logistics, e.g. warehousing, loading or distribution; Inventory or stock management · CPC title

• G06Q10/1097

  using calendar-based scheduling for task assignment · CPC title

• G06Q10/0875

  Itemisation or classification of parts, supplies or services, e.g. bill of materials · CPC title

• G06Q10/083 Primary

  Shipping · CPC title

• B61L27/0027

  Operations & Transport · mapped topic