| The problem of optimally assigning highway trailers to railcar hitches in intermodal transportation is studied. The importance of the problem is evidenced by the fact that a small improvement in operating efficiency, such as a one percent increase in hitch utilization, translates into several hundred thousand dollars in cost savings per years for an intermodal rail yard.;Two different integer-linear programming formulations are constructed. The first is based on the explicit dimensions of the equipment and yields a large optimization program. It is solved via a branch-and-bound approach employing Lagrangean relaxation and subgradient optimization to find lower bounds and a simple 2-exchange heuristic to obtain upper bounds.;The problem is cast as a set cover in the second formulation. Given an enumeration of the different types of trailers that can be loaded onto the different types of railcars, the formulation finds a minimum cost set of railcars that cover (i.e. load) all trailers. The second formulation is very small in comparison to the first, and possesses a tight linear programming relaxation in practice. This allows it to be solved by a general purpose branch-and-bound code.;The second formulation also provided the basis for the development of a greedy randomized adaptive search procedure (GRASP). This heuristic is observed to be extremely fast. Empirically, it finds the optimal solution to all of the problem instances furnished by Consolidated Rail Corporation. |
