Формализации задач погрузки и доставки

Аннотация

Задачи маршрутизации типа «one-to-one» или Traveling Salesman Problem with Pickup and Delivery (TSPPD) заключаются в формировании цикла минимальной длины, обеспечивающего доставку грузов от производителей потребителям при условии доставки груза от каждого производителя конкретному потребителю. Такая задача, в частности, возникает при доставке пассажиров (например, таксопарком). Установлены некоторые свойства поставленной задачи. Построен ряд квадратичных, линейных целочисленных и частично целочисленных формализаций таких задач, в которых число ограничений растет полиномиально с ростом числа пунктов. В частности, в качестве переменных используются булевы элементы матрицы перестановки, двухиндексные и трехиндексные переменные, описывающие отношение предшествования и некоторые другие. При таких формализациях возможно непосредственное использование оптимизационных пакетов. В частности, был проведен вычислительный эксперимент с использованием пакета CPLEX 12.6. Рекордной по производительности на случайно сгенерированных данных оказалась линейная смешанная трехиндексная модель. Установлено, что добавление некоторых дополнительных ограничений существенно повышает эффективность решения, в то время, как использование некоторых других ограничений эффективность снижают. В ряде случаев фактором, препятствующим решению задачи большей размерности, явилась ограниченность оперативной памяти.

При некоторых дополнительных ограничениях задача решалась для множеств пунктов, предлагаемых библиотекой, предложенной в университете г. Гейдельберга (Германия). В этом случае при использовании линейной смешанной трехиндексной модели получены решения задач весьма большой размерности (до 391 пары пунктов). Перспективы применения моделей, предложенных в статье, заключаются в расширении оперативной памяти компьютеров и совершенствовании оптимизационного пакета CPLEX. Некоторые исследователи отмечают, что CPLEX 11 (2007) работает почти в 30 000 раз быстрее, чем CPLEX 1 (1991).