System and method of vessel scheduling for product distribution
View Patent ↗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.
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 compartments based on the generated packing plan.
14. The non-transitory computer-readable medium of claim 13 , 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.
15. The non-transitory computer-readable medium of claim 13 , wherein the combinatorial search further comprises an input comprising:
a capacity of the one or more transportation compartments; and
inventory data.
16. The non-transitory computer-readable medium of claim 13 , 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.
17. The non-transitory computer-readable medium of claim 16 , 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.