Задача комівояжера (ЗК) - це задача, за якої комівояжер відправляється з вихідного вузла і повертається до нього таким чином, що кожен вузол у мережі вузлів відвідується один раз, а загальна пройдена відстань зводиться до мінімуму. Вважається, що ефективного алгоритму для ЗК не існує. ЗК класифікується як NP-важка задача і розробка ефективного вирішення для неї буде означати NP = P. Наведено постановку задачі комівояжера з фіктивними елементами. Для цього виключаються всі субтури в мережі ЗК із використанням мінімально можливої кількості обмежень. Оскільки для формування субтура потрібно мінімум 3 вузли, мережа ЗК розділяється за допомогою вертикальних і горизонтальних ліній таким чином, щоб між вертикальними або горизонтальними лініями було не більше трьох вузлів. Множина всіх вузлів між будь-якою парою вертикальних або горизонтальних ліній називається блоком. Фіктивні вузли використовуються для з'єднання одного блоку з наступним. Потім реконструйована ЗК використовується для постановки ЗК як задачі цілочислового лінійного програмування. У разі використання алгоритмів розгалуження немає ніякої гарантії, що кількість підзадач не злетить до некерованих рівнів. Евристичні або апроксимувальні алгоритми, які іноді використовуються для прийняття швидких рішень для практичних моделей ЗК, мають серйозні економічні проблеми. Різниця між точним рішенням і приблизними в грошовому вираженні дуже велика для практичних завдань, таких як доставка листів із використанням транспортного засобу в Пекіні, Токіо, Вашингтоні і т. д. Модель ЗК має безліч промислових застосувань, таких як свердління друкованих плат (ДП), капітальний ремонт газотурбінних двигунів, рентгенівська кристалографія, підключення комп'ютерів, комплектація замовлень на складах, складання маршрутів транспортних засобів, нанесення масок під час виробництва ДП і т. д.

 Наукова періодика України 

---

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"