Матэвристика для минимизации времени ожидания трейлеров при неточных временах прибытия

Матэвристика для минимизации времени ожидания трейлеров при неточных временах прибытия

Ратушный А. В., Кочетов Ю. А.
Дискретный анализ и исследование операций, 29, 3, 85-101 (2022)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2022.29.737

Аннотация:

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

Литература:
  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).
     
  10. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 420 с.
     
  11. Кулаченко И. Н., Кононова П. А. Гибридный алгоритм локального поиска для задачи маршрутизации транспортных средств с многократным посещением клиентов // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 2. С. 43–64.
     
  12. Кулаченко И. Н., Кононова П. А. Гибридный алгоритм решения задачи маршрутизации буровых установок // Дискрет. анализ и исслед. операций. 2021. Т. 28, № 2. С. 35–59.
     
  13. Mladenović N., Hansen P. Variable neighborhood search // Comput. Oper. Res. 1997. V. 24, No. 11. P. 1097–1100.
     
  14. 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.

Исследование выполнено при поддержке Российского научного фонда (проект № 21–41–09017).

Ратушный Алексей Владленович
  1. Новосибирский гос. университет,
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: alexeyratushny@gmail.com

Кочетов Юрий Андреевич
  1. Институт математики им. С. Л. Соболева,
    пр. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: jkochet@math.nsc.ru

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

Abstract:

We present a new loading/unloading trailer scheduling problem for a logistics company. There is a building with several warehouses. Each warehouse stores pallets of different types of products in rooms for loading into trailers. Each warehouse has two gates. One gate is for the trailers, the other one is for two forklifts from the central zone (production line). It produces some products which must be placed in the warehouses according to the no wait rule. We assume that the arrival time for each trailer is uncertain. Our goal is to assign all trailers to warehouses and find a schedule for servicing all the trailers with the maximum stability radius under the total waiting time constraint. For this NP-hard problem, we design a two-stage matheuristic. First, we solve the simplified model using the Gurobi solver. Then, the VNS algorithm is used to return the solution into the feasible region taking into account the detailed information about pallets in each warehouse. We generate some test instances using real data from a Dutch logistics company. Computational results for 6 warehouses, 18 types of products, and 90 trailers are discussed. 
Tab. 4, illustr. 4, bibliogr. 15.

References:
  1. E. Carrizosa and S. Nickel, Robust facility location, Math. Methods Oper. Res. 58, 331–349 (2003).
     
  2. E. Carrizosa, A. Ushakov, and I. Vasilyev, Threshold robustness in discrete facility location problems: A bi-objective approach, Optim. Lett. 9, 1297–1314 (2015).
     
  3. P. Borisovsky and O. Battaïa, MIP-based heuristics for a robust transfer lines balancing problem, in Optimization and Applications (Proc. Int. Conf. OPTIMA 2021, Petrovac, Montenegro, Sep. 27–Oct. 1, 2021) (Springer, Heidelberg, 2021), pp. 123–135 (Lect. Notes Comput. Sci., Vol. 13078).
     
  4. T. Andersen, J. H. Hove, K. Fagerholt, and F. Meisel, Scheduling ships with uncertain arrival times through the Kiel Canal, Maritime Transp. Res. 2, ID 100008 (2021).
     
  5. A. Ben-Tal and A. Nemirovski, Robust optimization-methodology and applications, Math. Program. 92, 453–480 (2002).
     
  6. J. García and A. Peña, Robust optimization: Concepts and applications, in Nature-Inspired Methods for Stochastic, Robust and Dynamic Optimization (IntechOpen, London, 2018), pp. 7–22.
     
  7. Eh. N. Gordeev and V. K. Leont’ev, A general approach to the study of the stability of solutions in discrete optimization problems, Zh. Vychisl. Mat. Mat. Fiz. 36 (1), 66–72 (1996) [Russian] [Comput. Math. Math. Phys. 36 (1), 53–58 (1996)].
     
  8. E. Gurevsky, O. Battaïa, and A. Dolgui, Stability measure for a generalized assembly line balancing problem, Discrete Appl. Math. 161 (3), 377–394 (2013).
     
  9. A. Rossi, E. Gurevsky, O. Battaïa, and A. Dolgui, Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations, Discrete Appl. Math. 208, 123–136 (2016).
     
  10. Gurobi Optimizer Reference Manual (Gurobi Optimization, Beaverton, 2021). Available at www.gurobi.com/documentation/9.5/refman/index.html (accessed May 16, 2022).
     
  11. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
     
  12. I. N. Kulachenko and P. A. Kononova, A hybrid local search algorithm for consistent periodic vehicle routing problem, Diskretn. Anal. Issled. Oper. 27 (2), 43–64 (2020) [Russian] [J. Appl. Ind. Math. 14 (2), 339–351 (2020)]. 
     
  13. I. N. Kulachenko and P. A. Kononova, A hybrid algorithm for the drilling rig routing problem, Diskretn. Anal. Issled. Oper. 28 (2), 35–59 (2021) [Russian] [J. Appl. Ind. Math. 15 (2), 261–276 (2021)].
     
  14. N. Mladenović and P. Hansen, Variable neighborhood search, Comput. Oper. Res. 24 (11), 1097–1100 (1997). 
     
  15. A. E. Smith and D. W. Coit, Penalty functions, in Handbook of Evolutionary Computation (Oxford Univ. Press, New York, 1997), pp. C5.2:1–C5.2:6.