Аннотация:
Рассматриваются задачи построения маршрута коммивояжера по критерию минимума суммарных потерь, связанных со стоимостью переезда из пункта $i$ в $j$, и потерями, возникающими из-за окончания обслуживания пункта $i$ во время $T_i$. На маршруты коммивояжера накладываются ограничения, связанные с обслуживанием некоторых пунктов не позднее заданного срока. Данная задача имеет большое количество приложений в теории расписаний, организации ремонтных работ и маршрутизации перевозок. Устанавливаются свойства этих задач и предлагаются алгоритмы решения методом ветвей и границ.