The Capacitated Carrier Transportation Problem: An Application of the Axial Three-Dimensional Transportation Problem with Heuristic

The classic transportation problem assumes that either (1) there is a single carrier who can transport all of the required shipments at the given, per unit O-D costs or (2), there are multiple carriers and each O-D pair can be served by its least cost carrier. These assumptions, however, are unrealistic for logistics problems in which the transportation needs exceed the short-term capacity of any one available carrier. In such cases, it cannot be assumed that every potential O-D pair can be served by its least costly carrier. For example, firms in the paper product and tire industries conduct promotional activities (e.g., specials or truck-load sales). Such activities result in extremely large, short-term peaks in their transportation requirements which cannot be met by their private fleets and/or contracted common carriers within the necessary time constraints. We refer to this problem as the capacitated carrier transportation problem (CCTP).In this paper we formulate the CCTP as an integer version of the axial three-dimensional transportation problem and present a heuristic based upon Lagrangian relaxation for solving it. Test problem results indicate that the heuristic identifies near optimal solutions in reasonable time.