Том 5, серия 2, номер 1, 1998 г., Стр. 12-18
УДК 519.8
Э. Х. Гимади, Н. И. Глебов, А. И. Сердюков
Об одной задаче выбора циклического маршрута и загрузки транспортного средства
Аннотация:
Исследуется задача выбора такого простого циклического маршрута и такого плана загрузки транспортного средства, когда максимизируется прибыль от купли и продажи загруженных товаров различных видов во всех заданных пунктах обхода. Произведено сведение этой задачи к задаче коммивояжера с матрицей расстояний, удовлетворяющей неравенству треугольника. Предложены полиномиальные алгоритмы решения исходной задачи с гарантированной погрешностью для ряда типов загрузки. Выделены классы задач, когда описанные алгоритмы позволяют получить либо точные, либо асимптотически точные решения.
Библиогр. 11.
Гимади Э. X. 1
Глебов Н. И. 1
Сердюков А. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 9 апреля 1998 г.
