System, computer-implemented method, and software for vessel scheduling for product distribution

• US 20080010357A1
• Filed: 06/23/2006
• Published: 01/10/2008
• Est. Priority Date: 06/23/2006
• Status: Active Grant

• Current Assignee: Blue Yonder Group, Inc. (Panasonic Holdings Corporation)
• Original Assignee: JDA Software Group Incorporated (RedPrairie Holding Incorporated)
• Inventors: Hartge, Mark, Ye, Jian
• Granted Patent: US 8,321,354 B2
• Time in Patent Office: Days
• US Class Current: 709/207
• 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 for generating a schedule for delivery of products via an ocean-going vessel, the system comprising:

a server for receiving a schedule request and one or more constraints for scheduling one or more vessels; and

an optimization engine in communication with the server, the optimization engine for generating a schedule based at least in part on the one or more constraints using a beam search algorithm.

2. The system of claim 1, wherein the beam search algorithm comprises a branch-and-bound algorithm with a greedy heuristic for estimating the desirability of one or more nodes.

3. The system of claim 2, wherein the branch-and-bound algorithm comprises using possible vessel assignments as branches and ordering terminal/product pairs according to criticality.

4. The system of claim 1, wherein the generating of the schedule comprises determining a vessel assignment according to a recursive process that includes determining the feasibility of assigning each of a plurality of vessel candidates to a terminal.

5. The system of claim 1, wherein the generating of the schedule comprises determining a vessel packing schedule using a depth-first with backtracking algorithm.

6. The system of claim 5, wherein the determining of the vessel packing schedule comprises using a recursive function for assigning products to vessel compartments in order to obtain an optimal vessel packing schedule.

7. 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 thus selected terminal based on feasibility and unit cost and schedule the best one; and

(4) go back to step 2 if a next run-out date is before the End Date.

8. A computer-implemented method for generating a schedule for delivery of products via an ocean-going vessel, the method comprising:

receiving a schedule request and one or more constraints for scheduling one or more vessels; and

generating a schedule based at least in part on the one or more constraints using a beam search algorithm.

9. The method of claim 8, wherein the beam search algorithm comprises a branch-and-bound algorithm with a greedy heuristic for estimating the desirability of one or more nodes.

10. The method of claim 9, wherein the branch-and-bound algorithm comprises using possible vessel assignments as branches and ordering terminal/product pairs according to criticality.

11. The method of claim 8, wherein the generating of the schedule comprises determining a vessel assignment according to a recursive process that includes determining the feasibility of assigning each of a plurality of vessel candidates to a terminal.

12. The method of claim 8, wherein the generating of the schedule comprises determining a vessel packing schedule using a depth-first with backtracking algorithm.

13. The method of claim 12, wherein the determining of the vessel packing schedule comprises using a recursive function for assigning products to vessel compartments in order to obtain an optimal vessel packing schedule.

14. The method of claim 8, 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 thus selected terminal based on feasibility and unit cost and schedule the best one; and

(4) go back to step 2 if a next run-out date is before the End Date.

15. Software for generating a schedule for delivery of products via an ocean-going vessel, the software comprising computer-readable instructions for instructing a computer to:

receive a schedule request and one or more constraints for scheduling one or more vessels; and

generate a schedule based at least in part on the one or more constraints using a beam search algorithm.

16. The software of claim 15, wherein the beam search algorithm comprises a branch-and-bound algorithm with a greedy heuristic for estimating the desirability of one or more nodes.

17. The software of claim 16, wherein the branch-and-bound algorithm comprises using possible vessel assignments as branches and ordering terminal/product pairs according to criticality.

18. The software of claim 15, wherein the generating of the schedule comprises determining a vessel assignment according to a recursive process that includes determining the feasibility of assigning each of a plurality of vessel candidates to a terminal.

19. The software of claim 15, wherein the generating of the schedule comprises determining a vessel packing schedule using a depth-first with backtracking algorithm.

20. The software of claim 19, wherein the determining of the vessel packing schedule comprises using a recursive function for assigning products to vessel compartments in order to obtain an optimal vessel packing schedule.

21. The software of claim 15, 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 thus selected terminal based on feasibility and unit cost and schedule the best one; and

(4) go back to step 2 if a next run-out date is before the End Date.