System and method of vessel scheduling for product distribution
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 packing a vehicle by maximizing vehicle utilization subject to compartment constraints, comprising:
a computer comprising a processor that receives a schedule request and one or more constraints for vehicle packing of one or more products in one or more vehicles, the computer processor:
generates a vehicle packing plan comprising one or more 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 compartment;
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.
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 compartments.
3. The system of claim 2 , wherein the combinatorial search further comprises an input comprising:
a capacity of the one or more compartments; and
inventory data.
4. The system of claim 1 , wherein the combinatorial search further comprises an output comprising:
an indication if a feasible vehicle packing plan exists; and
the compartment assignment comprises a product and an amount of the one or more compartments.
5. The system of claim 1 , wherein the vehicle 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:
set End Date=Current Date+d days;
select a critical terminal;
rank vehicle candidates for the selected terminal based on feasibility and unit cost and schedule the best vehicle candidate; and
go back to selecting a critical terminal when a next run-out date is before the End Date.
7. A computer-implemented method packing a vehicle by maximizing vehicle utilization subject to compartment constraints, comprising:
receiving, by a computer comprising a processor, a schedule request and one or more constraints for vehicle packing of one or more products in one or more vehicle;
generating, by the processor, a vehicle packing plan comprising one or more 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 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.
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 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 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 vehicle packing plan exists; and
the compartment assignment comprises a product and an amount for the one or more compartments.
11. The computer-implemented method of claim 7 , wherein the vehicle 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:
set End Date=Current Date+d days;
select a critical terminal;
rank vehicle candidates for the selected terminal based on feasibility and unit cost and schedule the best vehicle candidate; and
go back to selecting a critical terminal when a next run-out date is before the End Date.
13. A non-transitory computer-readable medium embodied with software for packing a vehicle by maximizing vehicle utilization subject to compartment constraints, the software when executed by one or more computers is configured to:
receive a schedule request and one or more constraints for vehicle packing of one or more products in one or more vehicles;
generate a vehicle packing plan comprising one or more 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 compartment;
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.
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 compartments.
15. The non-transitory computer-readable medium of claim 14 , wherein the combinatorial search further comprises an input comprising:
a capacity of the one or more compartments; and
inventory data.
16. The non-transitory computer-readable medium of claim 13 , wherein the combinatorial search further comprises an output comprising:
an indication if a feasible vehicle packing plan exists; and
the compartment assignment comprises a product and an amount of the one or more compartments.
17. The non-transitory computer-readable medium of claim 13 , wherein the vehicle 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.
18. The non-transitory computer-readable medium of claim 17 , 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:
set End Date=Current Date+d days;
select a critical terminal;
rank vehicle candidates for the selected terminal based on feasibility and unit cost and schedule the best vehicle candidate; and
go back to selecting a critical terminal when a next run-out date is before the End Date.