The Multi-Commodity Flow Problem with Outsourcing Decisions

E. Fernández, I. Ljubic, N. Zerega Oyarzún

We address a new prize-collecting routing problem in a network with a given set of hub nodes where service to non-hub nodes is outsourced to third-party carriers. The problem is modeled as a Stackelberg game: a leader selects commodities to serve and offers outsourcing fees to carriers, who act as followers maximizing their own profits. The goal is to determine optimal outsourcing fees and carrier assignments to maximize the leader’s profit. The followers' responses impact service levels, as they may reject unprofitable offers. We study two alternative settings: one with fixed outsourcing fees and another one where carriers accept any offer that ensures a non-negative profit. For both settings, we show that outsourcing fees can be discretized, propose a single-level mixed-integer nonlinear formulation and prove NP-Hardness. We compare different MIP formulations and their scalability. Finally, we assess the impact of carrier reservation prices, providing interesting managerial insights.

Keywords: Multicommodity Flows, Bilevel Optimization, Network Optimization, Pricing, MINLP

Location
June 11, 2025  10:30 AM
Mr 2

L. Amorosi, J. Puerto Albandoz, C. Valverde Martín

J. F. Correcher, M. Landete, J. Peiró, H. Yaman

I. Martin Melero, M. Landete Ruiz, J. C. Gonçalves Dosantos, J. Sanchez Soriano