2026-07-20T05:13:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24765 2026-02-09T07:37:57Z ddc:004 open_access

Speed-Aware Network Design: A Parametric Optimization Approach Rosolia, Ugo Almagro, Marc Bataillou Iosifidis, George Gross, Martin Paschos, Georgios Network Design Transportation Networks Mixed-Integer Programming Speed-Coverage Parametric Optimization Network design problems have been studied from the 1950s, as they can be used in a wide range of real-world applications, e.g., design of communication and transportation networks. In classical network design problems, the objective is to minimize the cost of routing the demand flow through a graph. In this paper, we introduce a generalized version of such a problem, where the objective is to tradeoff routing costs and delivery speed; we introduce the concept of speed-coverage, which is defined as the number of unique items that can be sent to destinations in less than 1-day. Speed-coverage is a function of both the network design and the inventory stored at origin nodes, e.g., an item can be delivered in 1-day if it is in-stock at an origin that can reach a destination within 24 hours. Modeling inventory is inherently complex, since inventory coverage is described by an integer function with a large number of points (exponential to the number of origin sites), each one to be evaluated using historical data. To bypass this complexity, we first leverage a parametric optimization approach, which converts the non-linear joint routing and speed-coverage optimization problem into an equivalent mixed-integer linear program. Then, we propose a sampling strategy to avoid evaluating all the points of the speed-coverage function. The proposed method is evaluated on a series of numerical tests with representative scenarios and network sizes. We show that when considering the routing costs and monetary gains resulting from speed-coverage, our approach outperforms the baseline by 8.36% on average. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ugo Rosolia and Marc Bataillou Almagro and George Iosifidis and Martin Gross and Georgios Paschos 2025 Is Part Of OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2025.9 urn:nbn:de:0030-drops-247655 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode