Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.
Исследование моделей целочисленного программирования для задачи маршрутизации буровых установок с возвратами и временными окнами
2022-12-08
Рассматривается задача маршрутизации транспортных средств с временными окнами, возникающая на практике при маршрутизации буровых установок для бурения скважин на множестве объектов с различным географическим положением. Каждый объект содержит скважины, которые необходимо обработать в течение заданного временного окна. Одна буровая установка может посещать объект несколько раз, но общее количество посещений объекта ограничено сверху. Каждая скважина бурится одной буровой установкой без прерываний. Требуется найти маршруты буровых установок, минимизирующие суммарную длительность перемещений. Исследуются свойства двух математических моделей для этой задачи: модели, основанной на классическом подходе к построению задач частично целочисленного линейного программирования для маршрутизации транспортных средств, и модели, основанной на точках событий. Построен алгоритм адаптации настраиваемых параметров пакета программ частично целочисленного линейного программирования и проведена оптимизация этих параметров. Приводятся результаты экспериментальных исследований на тестовых примерах различной структуры.
Ссылка для цитирования:
Еремеев А. В., Заозерская Л. А., Захарова Ю. В. 2022. Исследование моделей целочисленного программирования для задачи маршрутизации буровых установок с возвратами и временными окнами. PREPRINTS.RU. https://doi.org/10.24108/preprints-3112582
Список литературы
1. Кулаченко И.Н., Кононова П.А. Гибридный алгоритм решения задачи маршрутизации буровых установок. Дискретн. анализ и исслед. опер., Т. 28, Вып. 2, 2021, С. 35–59.
2. Borisovsky, P., Eremeev, A., Kovalenko, Y., Zaozerskaya, L. Rig routing with possible returns and stochastic drilling times. In: Pardalos, P., Khachay, M., Kazakov, A. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2021. Lecture Notes in Computer Science, vol 12755. P.
3. 51–66, Springer, Cham. (2021)
4. Hutter, F., Hoos, H.H., Leyton-Brown, K. Automated Configuration of Mixed Integer Programming Solvers. In: Lodi, A., Milano, M., Toth, P. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2010. Lecture Notes in Computer Science, vol 6140. pp. 186–202. Springer, Berlin, Heidelberg. (2010)
5. Ierapetritou, M.G., Floudas, C.A.: Effective continuous-time formulation for short-term scheduling: I. Multipurpose batch process. Ind. Eng. Chem. Res. 37(11) 4341–4359 (1998)
6. Cordeau, J.-F., Desaulniers, G., Desrosiers J., Solomon, M.M., Soumis, F. VRP with time windows. In: The vehicle routing problem / edited by P. Toth, D. Vigo, SIAM Monographs on Discrete Mathematics and Applications, SIAM, pp. 157–193 (2002)
