System and method of vessel scheduling for product distribution

• US 8,972,304 B2
• Filed: 10/22/2012
• Issued: 03/03/2015
• Est. Priority Date: 06/23/2006
• Status: Expired due to Fees

• Current Assignee: Blue Yonder Group, Inc. (Panasonic Holdings Corporation)
• Original Assignee: JDA Software Group Incorporated (RedPrairie Holding Incorporated)
• Inventors: Ye, Jian, Hartge, Mark
• Primary Examiner(s): Gart, Matthew
• Assistant Examiner(s): Masud, Rokib
• Application Number:
  US13/657,129
• Publication Number:
  US 20130046705A1
• Time in Patent Office: 862 Days
• Field of Search: 705/16, 705/36, 705/338
• US Class Current: 705/338
• CPC Class Codes: B61L 27/16 Trackside optimisation of vehicle or train operation
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/083 Shipping
• CPC Class Codes: G06Q 10/0875 Itemisation or classification of parts, supplies or services, e.g. bill of materials
• CPC Class Codes: G06Q 10/1097 Task assignment

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.

Claims

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.