задача математического программирования по определению оптимального маршрута движения коммивояжера, цель которого состоит в том, чтобы посетить все объкты, записанные в задании, за кратчайший срок и с наименьшими затратами. В теории графов З.о к. - это поиск пути, связывающего два или более узла, с использованием критерия оптимальности.
Задача О Коммивояжере
ЗАДАЧА О КОММИВОЯЖЕРЕ (traveling salesman problem)
вид задачи программирования матем., состоит в отыскании наилучшего маршрута для коммивояжера, который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. На языке графов теории 3. о к. формулируется как поиск такого пути, связывающего два или более узла, который минимизирует (или максимизирует) некоторый критерий оптимальности. Па допустимые пути могут быть наложены ограничения: напр., запрет возвращения к уже пройденному узлу. Алгоритмы, позволяющие решать на ЭВМ 3. о к., используются для выбора оптим. маршрутов автотранспорта, при кольцевой доставке продукции потребителям.
Источник: Глоссарий терминов по грузоперевозкам, логистике, таможенному оформлению
Задача о коммивояжере
состоят в отыскании наилучшего маршрута для коммивояжера (бродячего торговца), который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. Казалось бы, странно: головоломка любопытна, но при чем здесь экономика, какое это может иметь для нее значение?
Алгоритмы, позволяющие решать на электронных вычислительных машинах задачу о коммивояжере, используются не только для выбора маршрутов автотранспорта при кольцевой доставке товаров (например, в торговую сеть), но и при решении таких задач, которые на первый взгляд никакого отношения к »задаче коммивояжера» не имеют, например, в планировании производства на конвейерах, выпускающих машины различных моделей. На ЭВМ с помощью таких алгоритмов рассчитывают оптимальные партии, позволяющие выпускать заданный объем продукции с минимумом затрат на переналадку конвейера.
Алгоритмы, позволяющие решать на электронных вычислительных машинах задачу о коммивояжере, используются не только для выбора маршрутов автотранспорта при кольцевой доставке товаров (например, в торговую сеть), но и при решении таких задач, которые на первый взгляд никакого отношения к »задаче коммивояжера» не имеют, например, в планировании производства на конвейерах, выпускающих машины различных моделей. На ЭВМ с помощью таких алгоритмов рассчитывают оптимальные партии, позволяющие выпускать заданный объем продукции с минимумом затрат на переналадку конвейера.
Источник: Популярный экономико-математический словарь. 3-е изд. Знание. 1990