DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2026.15

Large Scale Middle Mile Network Design Through Efficient Local Search

Authors: Carlo S. Sartori, Jian Shen, Anastasia Kireeva, Mattia Neroni, and Philipp Loick

Published in: OASIcs, Volume 147, 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)

Abstract

E-commerce competition has intensified in recent years, further raising the delivery speed and cost efficiency standards that companies must meet. The middle mile network that connects fulfillment centers to local distribution centers plays a decisive role in achieving these standards. In this paper, we study the Middle Mile Network Design Problem, which determines optimal network investments that balance the trade-off between fastest delivery speed and minimal operational costs. The problem requires computing truck schedules, shipment routes, and parcel flows through intermediate facilities subject to complex capacity constraints. Two key challenges make this problem computationally hard to solve for standard exact and heuristic approaches: (i) the use of complex black-box evaluations to predict operational outcomes, and (ii) problem instances involving over 200,000 commodities that must be solved within hours for operational planning. We propose a metaheuristic based on variable neighborhood search with specialized local search operators alongside lazy neighborhood evaluation that enable efficient exploration of the high-dimensional solution space. Our algorithm achieves up to 7.6% solution improvement over an incumbent heuristic while reducing runtime by up to 44%.

Cite as

Carlo S. Sartori, Jian Shen, Anastasia Kireeva, Mattia Neroni, and Philipp Loick. Large Scale Middle Mile Network Design Through Efficient Local Search. In 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026). Open Access Series in Informatics (OASIcs), Volume 147, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{sartori_et_al:OASIcs.ATMOS.2026.15,
  author =	{Sartori, Carlo S. and Shen, Jian and Kireeva, Anastasia and Neroni, Mattia and Loick, Philipp},
  title =	{{Large Scale Middle Mile Network Design Through Efficient Local Search}},
  booktitle =	{26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)},
  pages =	{15:1--15:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-453-6},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{147},
  editor =	{Cacchiani, Valentina and Funke, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2026.15},
  URN =		{urn:nbn:de:0030-drops-278110},
  doi =		{10.4230/OASIcs.ATMOS.2026.15},
  annote =	{Keywords: Network design, Middle mile logistics, Black-box evaluation, Local search, Variable Neighborhood Search}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2021.1

Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes

Authors: Carlo S. Sartori, Pieter Smet, and Greet Vanden Berghe

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract

Vehicle routing and scheduling problems with interdependent routes arise when some services must be performed by at least two vehicles and temporal synchronization is thus required between the starting times of these services. These problems are often coupled with time window constraints in order to model various real-world applications such as pickup and delivery with transfers, cross-docking and home care scheduling. Interdependent routes in these applications can lead to large idle times for some drivers, unnecessarily lengthening their working hours. To remedy this unfairness, it is necessary to balance the duration of the drivers' routes. However, quickly evaluating duration-based equity functions for interdependent vehicle routes with time windows poses a significant computational challenge, particularly when the departure time of routes is flexible. This paper introduces models and algorithms to compute two well-known equity functions in flexible departure time settings: min-max and range minimization. We explore the challenges and algorithmic complexities of evaluating these functions both from a theoretical and an experimental viewpoint. The results of this paper enable the development of new heuristic methods to balance the workload of interdependent vehicle routes with time windows.

Cite as

Carlo S. Sartori, Pieter Smet, and Greet Vanden Berghe. Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sartori_et_al:OASIcs.ATMOS.2021.1,
  author =	{Sartori, Carlo S. and Smet, Pieter and Vanden Berghe, Greet},
  title =	{{Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.1},
  URN =		{urn:nbn:de:0030-drops-148703},
  doi =		{10.4230/OASIcs.ATMOS.2021.1},
  annote =	{Keywords: Vehicle scheduling, Workload balancing, Route duration, Interdependent routes, Time windows}
}

Search Results

Documents authored by Sartori, Carlo S.

Large Scale Middle Mile Network Design Through Efficient Local Search

Abstract

Cite as

Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes

Abstract

Cite as

Thanks for your feedback!

Could not send message