A Dedicated Subnetwork (DSN) refers to a subset of lanes with associated loads in a shipper’s transportation network, for which a fleet of resources – trucks, drivers, and other equipment – is exclusively assigned to carry out all shipping requirements. The resources assigned to a DSN are not shared for shipping in the rest of the shipper’s network. Thus, a DSN is an autonomously operated subnetwork of the shipper’s network, which could be subcontracted to a third party. In this study, we address a novel problem of identifying a “good” DSN that satisfies the capacity restrictions of a subcontractor. The shipper’s objective is to maximize the savings realized by subcontracting the DSN. In their pure form, the defining conditions of a DSN are often too restrictive to enable the extraction of a sizeable subnetwork. We consider two notions – deadheading and lane-sharing – that aid in improving the size of the DSN. Informally, deadheading allows trucks to travel empty while lanesharing allows the shipping volume on a lane to be shared by both the shipper and the subcontractor. The combined use of these two options is also considered. We first show that all the problems involved are both strongly NP-hard and APX-hard, and then demonstrate several polynomially-solvable special cases arising from topological properties of the network and parametric relationships. Next, we develop a network flow-based heuristic that can provide near-optimal solutions to practical problem instances in reasonable time. Finally, using a representative test bed based on real-world data obtained from a national 3PL company, we demonstrate the substantial monetary impact of subcontracting a DSN and offer several useful managerial insights. Two key measures that help understand the relevant tradeoffs are the marginal cost of deadheading and lane-sharing, per unit of cost saving provided by the DSN. The marginal cost of deadheading is a convex and decreasing function of density. At a low network density, this marginal cost decreases as the subcontractor’s cost advantage (over the shipper) increases. When density is high and the size of the network is large, this marginal cost increases as the subcontractor’s cost advantage increases. The marginal cost of lane-sharing is a concave function of density. As the subcontractor’s cost advantage increases, the benefit of lane-sharing progressively increases if there is an opportunity to use cheap deadheading as well. This complementary use of lanesharing and deadheading is particularly strong at high network densities. The benefit of merging the networks of two shippers to obtain a better combined DSN depends on the extent of overlap between the two networks, their sizes and densities. When the sizes of the networks are large (resp., small), the benefit of merging them decreases (resp., increases) as their overlap increases. Also, the benefit of merging two networks decreases as the difference between their densities increases
