Том 29, номер 3, 2022 г., Стр. 85-101

УДК 519.8
Ратушный А. В., Кочетов Ю. А.
Матэвристика для минимизации времени ожидания трейлеров при неточных временах прибытия

Аннотация:
Рассматривается новая задача планирования погрузки/разгрузки трейлеров на складах логистической компании. Имеется здание с несколькими складами. На каждом складе хранятся поддоны с различными видами продукции для погрузки в трейлеры. Каждый склад имеет ворота с двух противоположных сторон здания. Ворота на одной стороне предназначены для обслуживания трейлеров, ворота на другой стороне — для двух погрузчиков из центральной зоны, которая является производственной линией. Центральная зона производит продукты, которые должны быть размещены на складах сразу же после готовности. Время прибытия каждого трейлера является неопределённым. Требуется распределить все трейлеры по складам и составить расписание их обслуживания с максимальным радиусом устойчивости при ограничении на суммарное время ожидания. Для этой NP-трудной задачи разработана двухэтапная эвристика. На первом этапе решается упрощённая модель с помощью коммерческого решателя Gurobi. Затем используется алгоритм локального поиска, чтобы вернуть решение в допустимую область с учётом информации о наличии поддонов на каждом складе. Для вычислительных экспериментов рассматривается несколько наборов примеров, созданных на основе реальных данных одной голландской компании. Обсуждаются результаты вычислительных экспериментов для 6 складов, 18 видов продукции и 90 трейлеров.
Табл. 4, ил. 4, библиогр. 15.

Ключевые слова: радиус устойчивости, матэвристика, VNS, неопределённость.

DOI: 10.33048/daio.2022.29.737

Ратушный Алексей Владленович ¹
Кочетов Юрий Андреевич ²
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
2. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: alexeyratushny@gmail.com, jkochet@math.nsc.ru

Статья поступила 4 мая 2022 г.
После доработки — 4 мая 2022 г.
Принята к публикации 6 мая 2022 г.

Литература

[1] Carrizosa E., Nickel S. Robust facility location // Math. Methods Oper. Res. 2003. V. 58. P. 331–349.

[2] Carrizosa E., Ushakov A., Vasilyev I. Threshold robustness in discrete facility location problems: A bi-objective approach // Optim. Lett. 2015. V. 9. P. 1297–1314.

[3] Borisovsky P., Battaïa O. MIP-based heuristics for a robust transfer lines balancing problem // Optimization and Applications. Proc. Int. Conf. OPTIMA 2021 (Petrovac, Montenegro, Sep. 27–Oct. 1, 2021). Heidelberg: Springer, 2021. P. 123–135. (Lect. Notes Comput. Sci.; V. 13078).

[4] Andersen T., Hove J. H., Fagerholt K., Meisel F. Scheduling ships with uncertain arrival times through the Kiel Canal // Maritime Transp. Res. 2021. V. 2, ID 100008. 17 p.

[5] Ben-Tal A., Nemirovski A. Robust optimization-methodology and applications // Math. Program. 2002. V. 92. P. 453–480.

[6] García J., Peña A. Robust optimization: Concepts and applications // Nature-inspired methods for stochastic, robust and dynamic optimization. London: IntechOpen, 2018. P. 7–22.

[7] Гордеев Э. Н., Леонтьев В. К. Общий подход к исследованию устойчивости решений в задачах дискретной оптимизации // Журн. вычисл. математики и мат. физики. 1996. Т. 36, № 1. С. 66–72.

[8] Gurevsky E., Battaïa O., Dolgui A. Stability measure for a generalized assembly line balancing problem // Discrete Appl. Math. 2013. V. 161, No. 3. P. 377–394.

[9] Rossi A., Gurevsky E., Battaïa O., Dolgui A. Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations // Discrete Appl. Math. 2016. V. 208. P. 123–136.

[10] Gurobi optimizer reference manual. Beaverton: Gurobi Optimization, 2021. Available at www.gurobi.com/documentation/9.5/refman/index.html (accessed May 16, 2022).

[11] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 420 с.

[12] Кулаченко И. Н., Кононова П. А. Гибридный алгоритм локального поиска для задачи маршрутизации транспортных средств с многократным посещением клиентов // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 2. С. 43–64.

[13] Кулаченко И. Н., Кононова П. А. Гибридный алгоритм решения задачи маршрутизации буровых установок // Дискрет. анализ и исслед. операций. 2021. Т. 28, № 2. С. 35–59.

[14] Mladenovic N., Hansen P. Variable neighborhood search // Comput. Oper. Res. 1997. V. 24, No. 11. P. 1097–1100.

[15] Smith A. E., Coit D. W. Penalty functions // Handbook of evolutionary computation. New York: Oxford Univ. Press, 1997. P. C5.2:1–C5.2:6.