A Solution of a stochastic pickup and delivery problem with time windows by the adaptive large neighborhood search
Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie) · 01.10.2026 · 27 (4) · 666-689
DOI: 10.26089/nummet.v27r441 ↗Kurz gefasst
Fachartikel in der Zeitschrift Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie), online erschienen am 01.10.2026. Verfasst von Nikita V. Tsarkov. Die Arbeit nennt 26 Literaturangaben.
Abstract (Originalsprache)
The paper considers a stochastic pickup and delivery problem with time windows, where the travel time depends on the departure time and is a random variable, and the service time is also assumed to be random. A heuristic algorithm based on the adaptive large neighborhood search is proposed. Its route-feasibility test accounts for time windows, vehicle capacity, the probabilities of on-time arrival at each node, and the probabilities of successfully completing all routes. Computational experiments show that the proposed approach is substantially faster than an exact mixed-integer linear programming model and, in comparable scenarios, yields solutions with the same objective value or a small relative deviation. The impact of hyperparameters, stochasticity, speed profiles, and reliability requirements on the computation time and solution quality is analyzed. В работе рассматривается задача о приемке и доставке грузов с временными ограничениями, в которой время проезда между пунктами зависит от момента выезда и является случайной величиной, а время обслуживания в пунктах также считается случайным. Для решения задачи предлагается эвристический алгоритм на основе адаптивного поиска в больших окрестностях. При проверке выполнимости маршрута в алгоритме учитываются временные окна, ограничения на вместимость, вероятности своевременного прибытия в каждый пункт и вероятности успешного выполнения всех маршрутов. Вычислительные эксперименты показывают, что предложенный подход существенно быстрее точной смешанно-целочисленной линейной модели и на сопоставимых сценариях дает решения с тем же значением целевой функции либо с малым относительным отклонением. Проводится анализ влияния гиперпараметров, стохастичности, функций скорости и требований к надежности на время счета и качество решения.
Zitieren
APA
Tsarkov, N. V. (2026). A Solution of a stochastic pickup and delivery problem with time windows by the adaptive large neighborhood search. Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie), 27(4), 666-689. https://doi.org/10.26089/nummet.v27r441
Vancouver
Tsarkov NV. A Solution of a stochastic pickup and delivery problem with time windows by the adaptive large neighborhood search. Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie). 2026;27(4):666-689. doi:10.26089/nummet.v27r441
BibTeX
@article{Tsarkov2026,
author = {Tsarkov, Nikita V.},
title = {A Solution of a stochastic pickup and delivery problem with time windows by the adaptive large neighborhood search},
journal = {Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie)},
year = {2026},
volume = {27},
number = {4},
pages = {666--689},
doi = {10.26089/nummet.v27r441}
}
EUVIMED