Планируем путешествие — задача коммивояжера (TSP) для построения оптимального маршрута

[masteryoda73]

Хороши бы еще рассчитать оптимальный маршрут - что-то среднее между ценой и скоростью.

[Lozkins]

Это можно сделать. Вопрос в том, чтобы все поставить на одни весы. Либо деньги перевести во время, либо время в деньги. Последний переход наиболее распространенный.

[Maxim_Santalov]

Интересная статья , спасибо.

Где можно подробнее почить про логику сокращения переменных на этапе presolve в cp-sat и gurobi ?

[Lozkins]

К сожалению, концентрированной информации по presolve не нашел. Но есть зацепка по gurobi https://support.gurobi.com/hc/en-us/articles/360024738352-How-does-presolve-work-

Что касается ortools, у них отрытый исходный код, можно в коде посмотреть https://developers.google.com/optimization/reference/sat/cp_model_presolve/CpModelPresolver и https://developers.google.com/optimization/reference/sat/simplification/SatPresolver

Кроме этого, у gurobi проводятся вебинары, где они рассказывают мат.часть в том числе по presolve.

[robuststat]

Довольно хорошая статья от авторов SCIP
https://www.researchgate.net/publication/337127039_Presolve_Reductions_in_Mixed_Integer_Programming

[Lozkins]

Отличный материал по presolve. Только уточню, что в соавторах трое основателей gurobi )

[cry_san]

Запилите сервис.

Пользователь вводит сумму, которую хотел бы потратить на дорогу и проживание. Так же выбирает из списка, что хотелось ему посетить (горы, озера, выставки, музеи и т.д.). Сервис предложит ему несколько маршрутов на выбор.

Вот это, имхо, было бы востребовано.

[Lozkins]

Звучит как стартап - автогенератор туров, спасибо за идею!

[cry_san]

Если реализуете - буду первым на тест )

[yarbabin]

А как собирались данные для графа допустимых передвижений? https://github.com/Lozkins/mos/blob/master/data/06_tsp_dist.csv

[Lozkins]

Самым очевидным и прямым методом, вручную

[VladimirFarshatov]

В построении маршрутов (ветвей графа) как-то не увидел "стоимости" ветки в загруженности линии. Скажем из А в Б можем переместиться 3 маршрутами: авто, ж/д, авиа. Последний - самый быстрый, первый - самый дешевый. Как формируется весовая функция по этим трем маршрутам? А если первый попадает в условную "пробку" неожиданно, а последний в "нелетные условия"?

[Lozkins]

В случае рассмотрения трех видов транспорта, матрицу переходов из одного узла в другой можно сформировать на основе минимального значения. Если оптимизирует длительность маршрута, то скорее всего граф будет содержать только авиа перемещения.

Что касается неопределенности в данных. Здесь можно рассматривать ожидаемую длительность или стоимость перемещения по ребру. Т.е. оперировать средними величинами. Если нужно робастное решение, то можно рассмотреть более сложную постановку задачи ЛП в условиях неопределенности: https://habr.com/ru/articles/751226/