Consolidation of Less-Than-Truckload Shipments in Long-Haul Transportation Networks

Martin Baumung^*

Hub-and-spoke structures play a crucial role in the design of long-haul transportation networks for postal service providers, when considering less-than-truckload shipments. Substantial cost reduction can then be achieved by routing flows via hubs which serve as sorting, crossdocking and consolidation centers instead of having direct connections between all nodes of the network. Lower unit cost of transportation between hub nodes and therefore lower total transportation costs as a result of economies of scale is a fundamental characteristic of this type of network. Hub-and-spoke network design models address the question where to locate the hubs and how to allocate the non-hub nodes to the hubs such that the total transportation costs are minimized. In most of nowaday's models, for the sake of simplicity, unit transportation costs are assumed to be independent of the actual flow and are discounted by a constant factor $0<\alpha<1$ on interhub links to take account of economies of scale. This simplified approach however contradicts the very idea of flow consolidation leading to economies of scale. Not only do these models yield wrong total transportation costs, but as a consequence may lead to wrong location and allocation decisions as well. We present a different kind of approach where transportation costs are not directly incurred by flows but by vehicles operating between the nodes of the network. This way consolidation of flows can not only be achieved on interhub links but on any link of the network where flows belonging to different origin/destination pairs can be allocated to the same vehicle. We propose a MILP model deciding upon the location of hubs, the allocation of non-hub nodes to the hubs, the flows through the network and the number of vehicles operating between every two nodes of the network, such that the total costs are minimized. We improve lower bounds on the MILP by adding different valid inequalities and solving a Lagrangian dual problem via subgradient optimization, leading to good quality solutions within a reasonable amount of time.

Mathematics Subject Classification: 90B06

Keywords: Transportation Networks; Hub location; Economies of Scale; Lagrangean relaxation

Minisymposion: Integration of Optimization, Modeling and Data Analysis for Solving Real World Problems