The multi-commodity flow problem with outsourcing decisions

Abstract

We introduce a new prize-collecting problem involving the routing of commodities in a network composed of predefined hub and non-hub nodes. In this setting, the service of non-hub nodes is outsourced to third-party carriers. This study is motivated by the growing prevalence of outsourcing practices in real-world transportation systems, where new entrants or local suppliers increasingly take over parts of the transportation chain – enabling higher volumes and broader network coverage. The problem is modeled as a Stackelberg game: a major firm (the leader) chooses a subset of commodities to serve. The leader aims to outsource the first and last legs of the transportation services to smaller carriers (the followers), assigning at most one carrier to each non-hub node. Each carrier seeks to maximize its own profit, which depends on the offers made by the leader. The goal of the leader is to determine the optimal outsourcing fees, along with the allocation of carriers to the non-hub nodes, so that the profit from the routed commodities is maximized. The optimal response of the followers must be taken into account, as the followers may reject assignments that do not align with their profit-maximizing goals. We also consider two alternative settings: one in which outsourcing fees are fixed, and another where carriers accept any offer yielding non-negative profit. We demonstrate that the set of feasible outsourcing fees can be discretized and formulate the problem as single-level mixed-integer (non)linear program. For all problem variants, we prove NP-hardness and conduct a computational study of various singlelevel MIP reformulations. Our benchmark instances cover various applications in transportation, such as air transportation, postal delivery and freight transportation. We assess the scalability of proposed formulations and analyze the impact of different carrier reservation prices on solution quality. Finally, by comparing the alternative problem settings, we extract valuable managerial insights.