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

• US 8,321,354 B2
• Filed: 06/23/2006
• Issued: 11/27/2012
• 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): Zare, Scott
• Assistant Examiner(s): Masud, Rokib
• Application Number:
  US11/474,317
• Publication Number:
  US 20080010357A1
• Time in Patent Office: 2,349 Days
• Field of Search: 414/807, 700/100, 700/217, 701/117, 701/209, 703/14, 705/8, 705/40, 705/1, 707/100, 707/102, 364/424.01, 364/424.02, 364/436, 364/461
• 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 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.