Dedicated Transportation Subnetworks: Design, Analysis, and Insights

A dedicated subnetwork (DSN) refers to a subset of lanes, with associated loads, in a shipper's transportation network, for which resources–trucks, drivers, and other equipment–are exclusively assigned to accomplish shipping requirements. The resources assigned to a DSN are not shared with the rest of the shipper's network. Thus, a DSN is an autonomously operated subnetwork and, hence, can be subcontracted. We address a novel problem of extracting a DSN for outsourcing to one or more subcontractors, with the objective of maximizing the shipper's savings. In their pure form, the defining conditions of a DSN are often too restrictive to enable the extraction of a sizable subnetwork. We consider two notions–deadheading and lane‐sharing–that aid in improving the size of the DSN. We show that all the optimization problems involved are both strongly NP‐hard and APX‐hard, and 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 provides near‐optimal solutions to practical instances in reasonable time. Finally, using a test bed based on data obtained from a national 3PL company, we demonstrate the substantial monetary impact of subcontracting a DSN and offer useful managerial insights.