Vehicle scheduling and routing with compartments

• US 8,321,258 B2
• Filed: 08/31/2006
• Issued: 11/27/2012
• Est. Priority Date: 08/31/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Gottlieb, Jens, Engelmann, Thomas, Schumm, Carsten, Eckert, Jochen Christoph
• Primary Examiner(s): Bugg, George
• Assistant Examiner(s): Yacob, Sisay
• Application Number:
  US11/515,111
• Publication Number:
  US 20080065262A1
• Time in Patent Office: 2,280 Days
• Field of Search: 340/568.1, 340/673, 340/5.9, 340/5.92, 340/666, 705/8, 705/9, 705/28, 705/29, 705/64, 705/26, 705/6, 705/1.1, 705/5, 705/7.11, 705/7.12, 705/7.22, 705/7.23, 705/7.26, 705/7.34, 705/7.35, 701/49, 180/271, 700/226, 700/90, 700/213, 414/800, 709/213, 235/384, 220/23.9, 220/23.91, 220/500
• US Class Current: 705/7.26
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083

Abstract

Embodiments of the invention include a system for scheduling the shipment of a set of products. The shipment may be loaded into a set of vehicles and further configured to fit a set of compartments on those vehicles. The system may include attempts to fill each vehicle and the compartments of each vehicle. The system may include evaluating a set of constraints on the shipment. The constraints may include a complex logical statement.

Claims

1. A method comprising:

receiving a transportation order indicating an item to be transported;

determining a first configuration with the item in a first compartment of a first vehicle having a plurality of separate compartments, each compartment having an associated capacity value;

generating, in a computer, an indicator of feasibility for the first configuration based on whether the first configuration meets a first set of transportation constraints;

adjusting, in the computer, the capacity value for the first compartment if the first configuration is not feasible; and

determining, in the computer, if the first configuration is feasible with the capacity value of the first compartment adjusted.

2. The method of claim 1, further comprising:

storing the first configuration in a compartment configuration data structure for the first vehicle.

5. The method of claim 1, further comprising:

serializing a set of transportation orders to determine feasibility of a transportation plan based on whether the set of transportation orders can be distributed across a plurality of compartments of a vehicle.

6. The method of claim 5, wherein the set of transportation orders are serialized in an order based on a predetermined characteristic of the set of transportation orders.

7. The method of claim 1, further comprising:

checking a capacity of the first compartment of the first vehicle.

8. The method of claim 1, further comprising:

determining compatibility of the item with the first compartment.

9. The method of claim 1, further comprising:

determining compatibility of a first set of items with a second set of items in the first compartment.

10. The method of claim 1, further comprising:

determining compatibility of a first item with a second item in the first compartment.

11. The method of claim 1, further comprising:

displaying a set of transportation orders organized by vehicle and compartment.

12. The method of claim 1, further comprising:

verifying that the first configuration does not exceed a capacity of a vehicle.

13. The method of claim 1, further comprising:

verifying that the first configuration does not exceed the capacity of a compartment.

14. The method of claim 1, further comprising:

verifying that transportation orders assigned to the first compartment do not exceed a capacity of the first vehicle.

15. The method of claim 1, further comprising:

verifying that transportation orders assigned to the first vehicle do not exceed vehicle capacity.

16. The method of claim 1, further comprising:

determining a relationship between vehicle capacity usage and number of items placed in the vehicle using a function representing compartment storage characteristics.

3. The method of 1, further comprising:

determining a second configuration with the item in a second compartment of the first vehicle if the first configuration is not feasible.

4. The method of 1, further comprising:

performing a local search to optimize a placement of the item in at least one of the plurality of compartments of the first vehicle.

17. A system comprising:

a demand order generating module, to generate a set of demand orders;

a transportation determination module to receive the set of demand orders and generate a set of transportation orders; and

a compartment determination module to receive a transportation order and generate an indication of feasibility based on compatibility of an assignment of the transportation order to a compartment of a vehicle, wherein the compartment determination module operates transparently to the transportation determination module.

18. The system of claim 17, further comprising:

a user interface module to display vehicle, compartment and transportation order arrangement.

20. The system of claim 17, further comprising:

a serialization module to prepare a set of transportation orders for compartmentalization analysis.

21. The system of claim 17, wherein the set of transportation orders are serialized in an order based on a predetermined characteristic of the set of transportation orders.

19. The system of 17, further comprising:

a storage device to store a compartment configuration data structure of a vehicle with assignments of orders to compartments.

22. A non-transitory machine readable medium having a set of instructions stored therein which when executed cause a machine to perform a set of operations comprising:

receiving a set of transportation orders;

iterating through permutations of the transportation orders distributed across compartments of a set of vehicles;

identifying configurations that meet a set of predetermined constraints related to the compartments and transportation orders; and

generating instructions for sizing the compartments and loading the set of vehicles based on a selected configuration that meets the set of predetermined instructions.

23. The machine readable medium of claim 22, having a further set of instructions stored therein which when executed cause a machine to perform a set of operations further comprising:

generating a configuration of the set of transportation orders distributed across compartments of the set of vehicles.

24. The machine readable medium of claim 22, having a further set of instructions stored therein which when executed cause a machine to perform a set of operations further comprising:

displaying the set of transportation orders organized by vehicle and compartment.

29. The machine readable medium of claim 22, having a further set of instructions stored therein which when executed cause a machine to perform a set of operations further comprising:

performing any one of local search, tabu search, simulated annealing, evolutionary algorithms, mixed integer programming or constraint programming to optimize a placement of a set of items from a transportation order across compartments of a vehicle during each iteration.

25. An apparatus comprising:

means for receiving a set of transportation orders;

means for iterating through permutations of the transportation orders distributed across compartments of a set of vehicles; and

means for adjusting compartment capacity values during iteration through the permutations;

means for identifying configurations that meet a set of predetermined criteria related to the compartments.

26. The apparatus of claim 25, further comprising:

means for generating a configuration of the set of transportation orders distributed across compartments of the set of vehicles.

27. The apparatus of claim 25, further comprising:

means for displaying the set of transportation orders organized by vehicle and compartment.

28. The apparatus of claim 25, further comprising:

means for performing any one of local search, tabu search, simulated annealing, evolutionary algorithms, mixed integer programming or constraint programming to optimize a placement of a set of items from a transportation order across compartments of a vehicle during each iteration.

30. A system comprising:

a demand order generating module to generate a set of demand orders;

a transportation determination module to receive the set of demand orders and generate a set of transportation orders, each of the transportation orders are generated based on a local search which optimizes a placement of a first item in at least one of a plurality of compartments, the transportation determination module determines compatibility of the first item with a second item in the first compartment;

a compartment determination module to receive a transportation order and to generate an indication of feasibility based on compatibility of an assignment of the transportation order to a compartment of a vehicle;

a user interface module to display a set of transportation orders organized by vehicle and compartment; and

a serialization module to prepare a set of transportation orders prior to determining feasibility of a transportation plan based on whether the set of transportation orders can be distributed across a plurality of compartments of a vehicle.