System and method suitable for optimizing linehaul operations

• US 20080140597A1
• Filed: 07/03/2007
• Published: 06/12/2008
• Est. Priority Date: 07/04/2006
• Status: Active Grant

• Current Assignee: University of New Brunswick
• Original Assignee: University of New Brunswick
• Inventors: Christie, James S., Satir, Salim
• Granted Patent: US 8,046,319 B2
• Time in Patent Office: Days
• US Class Current: 706/46
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

The linehaul optimization algorithm is a hybrid algorithm incorporating the basic structure of the Hungarian Assignment algorithm or equivalent and an improvement heuristic. However, in this particular case there is not a direct application of the existing, well-known Hungarian Assignment algorithm or equivalent in conjunction with a heuristic. The structure of the assignment model being used here is based on the Hungarian Assignment algorithm or equivalent but has been revised and enhanced to identify systematically (by using grouping) a number of equivalent optimal solutions (that give the same optimal, minimum cost for a particular iteration). A heuristic is then used to identify the ‘best’ optimal solution, of the many identified, that would contribute the most incremental cost reduction in future iterations of the heuristic. There is no method at present that finds all possible combinations using the Hungarian Assignment algorithm or equivalent because for most applications any optimal solution is sufficient. However, this optimization model uses an iterative procedure where the outcome of each iteration affects the next iteration significantly and a simple application of the original Hungarian Assignment algorithm or equivalent is not acceptable and does not provide the overall optimum. At each iteration, a leg assignment is made (where a trailer is moved over more than one leg) or a reassignment is made to move a trailer in a different time period by either an owner-operator (i.e. company) tractor or a broker (i.e. outside company) tractor. Furthermore, the original Hungarian Assignment algorithm or equivalent is not designed to solve a scheduling problem; it is designed to solve an assignment problem. In other words the algorithm has been revised and combined with a heuristic to solve a scheduling problem.

Claims

1. A method suitable for optimizing a linehaul operation, the method comprising the steps of:

(a) providing at least one assignment algorithm designed to solve an assignment problem;

(b) providing at least one heuristic;

(c) combining the at least one heuristic with the at least one assignment algorithm to solve the scheduling problem, the combining step comprising the following acts;

(i) identifying at least one equivalent assignment solution to an instantaneous assignment problem using the at least one assignment algorithm; and

(ii) using the at least one heuristic to select one assignment solution from the at least one equivalent assignment solution such that the selected one assignment solution reduces the cost of at least one other instantaneous assignment solution.

2. The method as recited in claim 1, wherein the combining step further comprises the act of finding all possible solutions to the instantaneous assignment problem using the at least one assignment algorithm.

3. The method as recited in claim 1, wherein the combining step further comprises the act of finding a subset of all possible solutions to the instantaneous assignment problem using the at least one assignment algorithm.

4. The method as recited in claim 1, further comprising an iterating step wherein the selection of a first assignment solution obtained by using the at least one heuristic at a first iteration improves the quality of a second assignment solution achieved at a second iteration in relative comparison to the quality of a third assignment solution obtained as a result of the application of the assignment algorithm without the use of the at least one heuristic.

5. The method as recited in claim 4, further comprising the act of making a leg assignment at an iteration whereby a unit is routed over at least two legs.

6. The method as recited in claim 5, wherein the unit is a trailer.

7. The method as recited in claim 5, wherein the unit is a container.

8. The method as recited in claim 5, wherein the unit is a car load.

9. The method as recited in claim 5, wherein the act of making a leg assignment is made for an owner-operator tractor.

10. The method as recited in claim 5, wherein the act of making a leg assignment is made for a broker tractor.

11. The method as recited in claim 1, wherein the at least one heuristic includes a routing heuristic.

12. The method as recited in claim 4, further comprising the act of making a reassignment at each iteration whereby a unit is moved from one time period to another time period.

13. The method as recited in claim 12, wherein the unit is a trailer.

14. The method as recited in claim 12, wherein the unit is a container.

15. The method as recited in claim 12, wherein the unit is a car load.

16. The method as recited in claim 12, wherein the act of making a reassignment is made by an owner-operator tractor.

17. The method as recited in claim 12, wherein the act of making a reassignment is made by a broker tractor.

18. The method as recited in claim 1, wherein the at least one heuristic includes a scheduling heuristic.

19. The method as recited in claim 1, wherein the at least one assignment algorithm includes the Hungarian Assignment algorithm.

20. The method as recited in claim 1, wherein the at least one assignment algorithm includes the revised Hungarian Assignment algorithm.

21. The method as recited in claim 1, wherein the at least one assignment algorithm includes an assignment algorithm which is not the Hungarian Assignment algorithm.

22. The method as recited in claim 1, wherein the at least one heuristic includes a heuristic to find all possible optimum solution combinations by grouping jobs and tractors.

23. The method as recited in claim 1, wherein the at least one heuristic includes a heuristic to determine the preferred optimum solution in such a way that company tractors and owner-operators tractors end up at the preferred locations thereby lowering the operating cost for the next iteration and for the next day.