{"ID":6536511,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-14T19:39:24.033168704Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10459","arxiv_id":"2607.10459","title":"A column generation-based fixed-point heuristic for the service-aware multi-commodity flow problem","abstract":"We study the Service-Aware Multi-Commodity Flow (SAMCF) problem, in which demand is elastic and governed by a logit choice model while routing is subject to hard capacity constraints. In a centralized, system-optimal setting, the network operator jointly determines how much demand to serve and how to route it. We formulate the SAMCF as a nonlinear program and propose an iterative fixed-point heuristic that alternates between solving an inelastic MCF via column generation and updating demand from the resulting service levels. Two linear approximations based on piecewise-linear demand functions and McCormick envelopes serve as benchmarks, while a piecewise-linear outer-approximation of the demand function is used to provide valid lower bounds. Computational experiments on public transport instances show that the heuristic finds near-optimal solutions in under two seconds - orders of magnitude faster than the benchmark methods - while matching their solution quality on all instances they can solve within a ten-minute time limit.","short_abstract":"We study the Service-Aware Multi-Commodity Flow (SAMCF) problem, in which demand is elastic and governed by a logit choice model while routing is subject to hard capacity constraints. In a centralized, system-optimal setting, the network operator jointly determines how much demand to serve and how to route it. We formu...","url_abs":"https://arxiv.org/abs/2607.10459","url_pdf":"https://arxiv.org/pdf/2607.10459v1","authors":"[\"Siv Marie Cartland Hansen\",\"Richard Martin Lusby\"]","published":"2026-07-11T19:48:51Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}