EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1581. Speed-aware network design: a parametric optimization approach

Invited abstract in session WA-57: Large-scale Speed-sensitive Network Optimization, stream Optimization at Amazon.

Wednesday, 8:30-10:00
Room: S06 (building: 101)

Authors (first author is the speaker)

1. Ugo Rosolia
2. Marc Bataillou Almagro
Amazon
3. George Iosifidis
TU Delft
4. Amit Kumar
Amazon
5. Georgios Paschos
Amazon

Abstract

Network design problems have been studied from the 1950s, as they have a wide range of real-world applications. In classical network design problems the objective is to minimize the cost of routing goods through a graph.
We introduce a generalised version of such a problem, where the objective is to trade-off the speed at which goods can be sent to their destination nodes and the cost of routing them. Compared to standard time-aware network design problems, where speed is taken into account by adding deadline constraints - i.e., goods have to reach destinations before a target date - we introduce a coverage function mapping the set of goods served by origin-destination pairs for which we offer expedite delivery to the number of unique items for which fast delivery services can be offered. This coverage function models that sets of goods for different origin-destination pairs may not be disjointed, and it allows us to compute the share of unique items for which we can offer expedite delivery services, which we refer to as speed-coverage.
To minimize routing costs while jointly maximizing speed-coverage, we leverage parametric optimization to reformulate the coverage function as a convex program with an exponential number of constraints. Then, we propose a sampling strategy to reduce the dimensionality of such a reformulation. We show that when considering the overall costs given by routing costs minus speed revenues, our approach outperforms the baseline by 8.36% on average

Keywords

Status: accepted

Back to the list of papers