Математический аппарат для решения задач оптимизации логистики активно развивался в годы второй мировой войны и послевоенное время.

Благодаря научным работам Леонида Викторовича Канторовича (в 1939 году) и Джорджа Данцига (в 1947 году) часть задач оптимизации решается с помощью аппарата линейного программирования и применения симплекс-метода, которые существенно сократили время, необходимое для поиска решения.

Разработанный индийским математиком Нарендрой Кармаркаром в 1984 году метод внутренней точки существенно ускорил процесс, но для ряда сложных задач поиск решения занимает очень много времени, все еще недоступного современным компьютерам.

Для решения задач с целыми значениями параметров были разработаны методы "ветвей и границ" (в 1960 году) или "алгоритм Гомори" (1950-е годы).

Активные исследования искусственного интеллекта дали другие алгоритмы, например, генетический алгоритм, описанный Джоном Холландом в 1975 году, позволяющие ускорить процесс поиска приемлемого решения, правда, к сожалению, не обязательно самого оптимального.

Почему задача оптимизации так сложна?

Решение задач оптимизации логистики является сложной вычислительной задачей, которая может потребовать очень много машинного времени для ее разрешения.

Например, для составления оптимального графика ремонтов 10 нефтебаз в течение 10 лет "в лоб" потребуется проверить 1010 вариантов, что еще под силу современным компьютерам.

Если количество нефтебаз увеличить всего лишь в три раза до 30 (среднее количество нефтебаз крупнейших российских ВИНК), то количество вариантов драматически вырастет до 1030 (1 000 000 000 000 000 000 000 000 000 000 - у этого числа есть свое название - "нониллион"), что уже потребует вычислительного времени существенно больше, чем осталось нашей Вселенной до ее тепловой смерти (по оценкам астрономов - 150 триллионов лет) если мы будем проверять варианты со скоростью 200 миллионов вариантов в секунду.

Поиск решений существенно усложняется при условии, если параметры принимают только целочисленные значения, например, при анализе бинарных вариантов вида "да-нет" (например, использование или консервация нефтебазы) или выбора одного из нескольких вариантов ремонта или модернизации.