A General Variable Neighborhood Search for Logistic Network Flow Design with Nonlinear Edge Costs and Transshipment Capacities
Abstract
We study the problem of routing multiple commodities through a logistic transport network so as to minimise the joint cost of vehicle movements and of transshipment (reload) operations at intermediate storages. The problem combines two features that are common in practice but rarely treated together: edge costs that are nonlinear in the transported volume, because freight is carried by vehicles of fixed capacity, and hard upper bounds on the volume that can be reloaded at each node. We formulate the problem as a mixed integer linear program in both an arc-based and a path-based form, derive its linear relaxation, and propose a metaheuristic solver based on General Variable Neighborhood Search (GVNS). The method works in the path space and relies on three problem-specific neighborhoods that generate new candidate paths by (i) shortest paths under a reload-aware metric, (ii) edges carrying partially loaded vehicles, and (iii) detours around congested storages. We evaluate the method on our open benchmark for this problem (arXiv:2606.20653): a corpus of realistic logistic networks calibrated on real road graphs of nine European countries, five U.S. states and the European part of Russia, with near-planar topology (Zipf city sizes, a spatial-network budget model, and a doubly constrained gravity demand model). On 35 synthetic and 15 real-geometry instances with up to 150 storages, GVNS returns solutions within about one percent of the best dual bound on small networks -- a branch-and-bound lower bound substantially tighter than the LP relaxation -- is stable across random seeds, and for a comparable wall-clock budget is up to 55% better than a time-limited exact solver on the medium instances.
Related
- A doubly nonlinear parabolic problem with variable exponents, homogeneous Neumann boundary conditions and generalized logistic source
- Fully Nonlinear Logistic Equations with Sanctuary Regions and Nonlocal Diffusion
- On the homogenization of a class of nonlinear operators with variable periodic rapidly oscillating exponent
- A Generalized Scalar Auxiliary Variable Method for Structure-Preserving and Efficient Integration of Nonlinear port-Hamiltonian DAEs
- A Viscoelastic Wave Equation with Nonlinear Damping and Supercritical Variable-Exponent Logarithmic Sources
BibTeX
@misc{kovaleva2026general,
title = {{A General Variable Neighborhood Search for Logistic Network Flow Design with Nonlinear Edge Costs and Transshipment Capacities}},
author = {Varvara Kovaleva and Alexander Ponomarenko},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30139},
eprint = {2610.30139},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30139},
}
RIS
TY - UNPB
TI - A General Variable Neighborhood Search for Logistic Network Flow Design with Nonlinear Edge Costs and Transshipment Capacities
AU - Varvara Kovaleva
AU - Alexander Ponomarenko
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.30139
UR - https://arxiv.org/abs/2610.30139
AB - We study the problem of routing multiple commodities through a logistic transport network so as to minimise the joint cost of vehicle movements and of transshipment (reload) operations at intermediate storages. The problem combines two features that are common in practice but rarely treated together: edge costs that are nonlinear in the transported volume, because freight is carried by vehicles of fixed capacity, and hard upper bounds on the volume that can be reloaded at each node. We formulate the problem as a mixed integer linear program in both an arc-based and a path-based form, derive its linear relaxation, and propose a metaheuristic solver based on General Variable Neighborhood Search (GVNS). The method works in the path space and relies on three problem-specific neighborhoods that generate new candidate paths by (i) shortest paths under a reload-aware metric, (ii) edges carrying partially loaded vehicles, and (iii) detours around congested storages. We evaluate the method on our open benchmark for this problem (arXiv:2606.20653): a corpus of realistic logistic networks calibrated on real road graphs of nine European countries, five U.S. states and the European part of Russia, with near-planar topology (Zipf city sizes, a spatial-network budget model, and a doubly constrained gravity demand model). On 35 synthetic and 15 real-geometry instances with up to 150 storages, GVNS returns solutions within about one percent of the best dual bound on small networks -- a branch-and-bound lower bound substantially tighter than the LP relaxation -- is stable across random seeds, and for a comparable wall-clock budget is up to 55% better than a time-limited exact solver on the medium instances.
ER -