Heuristic strategies for a multi-allocation problem in LTL logistics

We consider a "Less than truckload" (LTL) network with n depots and given shipping volumes between each two of them. For every connection between two depots, we also know the transport cost d(i, j) per truck. Every shipping volume w(i, j) can be transported directly from depot i to depot j or turned over at most twice at other depots. For this, depots have to be equipped with transshipment capacities (for which we have to pay); those depots are then called hubs. A priori every depot can be equipped with such capacities, but later we consider a restricted problem where only some of the depots have this ability. Our aim is make strategic planning decisions (transshipment capacities, number of trucks in each depots, etc.) with the help of average data, so that we allow long computation times. Since transport costs on an edge mostly depend on the number of trucks (and not just on the volume), we introduce integer truck variables. As the number of possible paths for transport is of order 0(n4), we cannot get reasonable results for n > 50 by using Cplex. Therefore, we developed a heuristic approach using shipping trees (detailed in Sect. 3). It can be used in two ways: To get a primal bound and to get information about the "best hubs". If, in step 2, we restrict the problem to those best hubs (i.e. forbid turnover for all other hubs), we can improve the heuristic results. Furthermore, this restricted problem allows us to find good feasible solutions with Cplex. In Sect. 4, we show how to find a lower bound from a strengthened LP relaxation. Evidence for the potential of our method will be given by the three real world test instances shown in Sect. 5.