System and method of vessel scheduling for product distribution

1. A system of packing a vessel by maximizing vessel utilization subject to tank capacity constraints at one or more terminals, comprising:

a computer system comprising a processor that receives a schedule request and one or more constraints for vessel packing of one or more products in one or more vessels; and

an optimization engine tangibly embodied on the computer system comprising a processor, the optimization engine:

generates a vessel packing plan comprising one or more compartments based on the one or more constraints using a depth-first search with backtracking algorithm, the depth-first search with backtracking algorithm comprises a solution represented by a vector V=(v_ 1 , . . . , v_n), the ith component of the vector being a product and volume assigned to the 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

checks if the extension yields a partial solution,

when the extension yields a partial solution, the optimization engine continues to extend the partial solution as long as the extension yields a partial solution, and

when S is empty, the optimization engine backtracks to v_k and replaces v_k with a next candidate.

2. The system of claim 1 , wherein the depth-first search with backtracking algorithm further comprises a solution representing a volume of the one or more products assigned to a compartment in the one or more vessels.

3. The system of claim 1 , wherein the depth-first search with backtracking algorithm further comprises an input array comprising:

CompartmentCapacity for each compartment, 1 , . . . , n;

MinimumToShip for each product, 1 , . . . , m;

MaximumToShip for each product, 1 , . . . , m; and

ProductCompartmentAssociation for each product/compartment.

4. The system of claim 1 , wherein the depth-first search with backtracking algorithm further comprises an output comprising:

feasible packing exist: true or false; and

best packing: (product, volume) pair for each vessel compartment.

5. The system of claim 1 , wherein the depth-first search with backtracking algorithm further comprises:

VesselPacking(k) # packing kth compartment:

if k>n and remaining MinimumToShip[i]=0, then feasiblePacking=true; record solution, Return;

Let S be the set of remaining products (i.e. MaximumToShip>0) that can use compartment k;

While S is not empty:

Let p be a product in S;

AssignProductToCompartment(p,k);

VesselPacking(k+1);

UnAssignProductToCompartment(p,k); and

S =S−p; and

End While.

6. The system of claim 5 , wherein AssignProductToCompartment(p,k) comprises:

Volume=min(MaximumToShip[k],CompartmentCapacity[p]);

MinimumToShip[p]=max(0, MinimumToShip[p]-Volume; and

MaximumToShip[p]=MaximumToShip[p]-Volume.

7. A method of packing a vessel by maximizing vessel utilization subject to tank capacity constraints at one or more terminals, comprising:

receiving, by a computer, a schedule request and one or more constraints for vessel packing of one or more products in one or more vessels; and

generating, by the computer, a vessel packing plan comprising one or more compartments based on the one or more constraints using a depth-first search with backtracking algorithm, the depth-first search with backtracking algorithm comprises a solution represented by a vector V=(v_ 1 , . . . , v_n), the ith component of the vector being a product and volume assigned to the ith compartment;

constructing, by the computer, a partial solution with elements fixed for the first k elements of the vector where k is less than or equal to n;

constructing, by the computer, the set of possible candidates S for the (k+1)st position;

constructing, by the computer, an extension by adding the next element from S to the partial solution; and

checking, by the computer, if the extension yields a partial solution,

when the extension yields a partial solution, continuing, by the computer, to extend the partial solution as long as the extension yields a partial solution, and

when S is empty, backtracking, by the computer, to v_k, and replacing v_k with a next candidate.

8. The method of claim 7 , wherein the depth-first search with backtracking algorithm further comprises a solution representing a volume of the one or more products assigned to a compartment in the one or more vessels.

9. The method of claim 8 , wherein a constraint comprises previously scheduled movements of the vessel and sorting one or more of the previously scheduled movements of the vessel by decreasing order of time, and regenerating a vessel packing plan for each of the previously scheduled movements.

10. The method of claim 7 , wherein the depth-first search with backtracking algorithm further comprises an input array comprising:

CompartmentCapacity for each compartment, 1 , . . . , n;

MinimumToShip for each product , 1 , . . . , m;

MaximumToShip for each product, 1 , . . . , m; and

ProductCompartmentAssociation for each product/compartment.

11. The method of claim 7 , wherein the depth-first search with backtracking algorithm further comprises an output comprising:

feasible packing exist: true or false

best packing: (product, volume) pair for each vessel compartment.

12. The method of claim 7 , wherein the depth-first search with backtracking algorithm further comprises:

VesselPacking(k) #packing kth compartment:

if k>n and remaining MinimumToShip[i]=0, then feasiblePacking=true; record solution, Return;

Let S be the set of remaining products (i.e. MaximumToShip>0) that can use compartment k;

While S is not empty:

Let p be a product in S;

AssignProductToCompartment(p,k);

VesselPacking(k+1);

UnAssignProductToCompartment(p,k); and

S=S−p; and

End While.

13. A non-transitory computer-readable medium embodied with software that generates a packing plan for a vessel by maximizing vessel utilization subject to tank capacity constraints at one or more terminals, the software when executed by one or more computers is configured to:

receive a schedule request and one or more constraints for vessel packing of one or more products in one or more vessels; and

generate a vessel packing plan comprising one or more compartments based on the one or more constraints using a depth-first search with backtracking algorithm, the depth-first search with backtracking algorithm comprises a solution represented by a vector V=(v_ 1 , . . . , v_n), the ith component of the vector being a product and volume assigned to the ith compartment:

construct a partial solution with elements fixed for the first k elements of the vector where k is less than or equal to n;

construct the set of possible candidates S for the (k+1)st position;

construct an extension by adding the next element from S to the partial solution; and

check if the extension yields a partial solution,

when the extension yields a partial solution, continue to extend the partial solution as long as the extension yields a partial solution; and

when S is empty, backtrack to v_k and replaces v_k with a next candidate.

14. The non-transitory computer-readable medium of claim 13 , wherein the depth-first search with backtracking algorithm further comprises a solution representing a volume of the one or more products assigned to a compartment in the one or more vessels.

15. The non-transitory computer-readable medium of claim 13 , wherein the depth-first search with backtracking algorithm further comprises an input array comprising:

CompartmentCapacity for each compartment, 1 , . . . , n;

MinimumToShip for each product, 1 , . . . , m;

MaximumToShip for each product, 1 , . . . , m; and

ProductCompartmentAssociationforeachproduct/compartment.

16. The non-transitory computer-readable medium of claim 13 , wherein the depth-first search with backtracking algorithm further comprises an output comprising:

feasible packing exist: true or false; and

best packing: (product, volume) pair for each vessel compartment.

17. The non-transitory computer-readable medium of claim 13 , wherein the depth-first search with backtracking algorithm further comprises:

VesselPacking(k) #packing kth compartment:

if k>n and remaining MinimumToShip[i]=0, then feasiblePacking=true; record solution, Return;

Let S be the set of remaining products (i.e. MaximumToShip>0) that can use compartment k;

While S is not empty:

Let p be a product in S;

AssignProductToCompartment(p,k);

VesselPacking(k+1);

UnAssign ProductToCompartment(p,k); and

S=S−p; and

End While.