System, computer-implemented method, and software for 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 that generates a schedule for delivery of products via an ocean-going vessel, the system comprising:
a computer system comprising a processor that receives a schedule request and one or more constraints for scheduling one or more vessels; and
an optimization engine tangibly embodied on the computer system, the optimization engine generating a schedule comprising one or more vessel 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 uses possible vessel assignments as branches and orders terminal/product pairs according to criticality,
the optimization engine further verifies short term feasibility of a vessel candidate using a backtracking algorithm and determines the one or more vessel assignments according to a recursive process that includes determining the feasibility of assigning each of a plurality of vessel candidates to the one or more terminals.
2. The system of claim 1 , wherein the optimization engine further determines a vessel packing schedule using a depth-first with backtracking algorithm.
3. The system of claim 2 , wherein the optimization engine further uses a recursive function to assign products to vessel compartments in order to obtain an optimal vessel packing schedule.
4. The system of claim 1 , wherein the beam search algorithm comprises evaluating a vessel 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 vessel candidates for the selected terminal based on feasibility and unit cost and schedule the best one; and
(4) go back to step 2 when a next run-out date is before the End Date.
5. A method of generating a schedule for delivery of products via an ocean-going vessel, the method comprising:
receiving, by a computer system comprising a processor, a schedule request and one or more constraints for scheduling one or more vessels;
generating, by the computer system, a schedule comprising one or more vessel 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 vessel assignments as branches and ordering terminal/product pairs according to criticality; and
verifying, by the computer system, short term feasibility of a vessel candidate using a backtracking algorithm and determining the one or more vessel assignments according to a recursive process that includes determining the feasibility of assigning each of a plurality of vessel candidates to the one or more terminals.
6. The method of claim 5 , further comprising:
determining a vessel packing schedule using a depth-first with backtracking algorithm.
7. The method of claim 6 , further comprising:
using a recursive function to assign products to vessel compartments in order to obtain an optimal vessel packing schedule.
8. The method of claim 5 , wherein the beam search algorithm comprises evaluating a vessel 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 vessel candidates for the selected terminal based on feasibility and unit cost and schedule the best one; and
(4) go back to step 2 when a next run-out date is before the End Date.
9. A non-transitory computer-readable media embodied with software that generates a schedule for delivery of products via an ocean-going vessel, the software when executed by one or more computers is configured to:
receive a schedule request and one or more constraints for scheduling one or more vessels;
generate a schedule comprising one or more vessel 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 uses possible vessel assignments as branches and orders terminal/product pairs according to criticality; and
verify short term feasibility of a vessel candidate using a backtracking algorithm and determine the one or more vessel assignments according to a recursive process that includes determining the feasibility of assigning each of a plurality of vessel candidates to the one or more terminals.
10. The computer-readable media of claim 9 , wherein the software is further configured to determine a vessel packing schedule using a depth-first with backtracking algorithm.
11. The computer-readable media of claim 10 , wherein the software is further configured to use a recursive function for assigning products to vessel compartments in order to obtain an optimal vessel packing schedule.
12. The computer-readable media of claim 9 , wherein the beam search algorithm comprises evaluating a vessel 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 vessel candidates for the selected terminal based on feasibility and unit cost and schedule the best one; and
(4) go back to step 2 when a next run-out date is before the End Date.