A combined ant colony optimization with Levy flight mechanism for the probabilistic traveling salesman problem with deadlines

Abstract

У цій статті нас цікавить ймовірнісна задача комівояжера з дедлайнами (PTSPD), де з клієнтами необхідно зв'язатися, окрім їхньої випадкової доступності, до встановленого дедлайну. Головна мета полягає в тому, щоб знайти оптимальний маршрут, який охоплює випадкову підмножину відвідувачів у тому ж порядку, в якому вони з'являються в турі, намагаючись зробити шлях якомога коротшим. ♯P-складною. Оптимізація колонії мурах (ACO) часто застосовується для вирішення цієї складної задачі оптимізації. Однак у цьому дослідженні ми пропонуємо вдосконалений ACO з використанням алгоритму польоту Леві. Це дозволяє деяким мурахам здійснювати довші стрибки на основі розподілу Леві, допомагаючи їм виходити з локальних оптимумів. Наші обчислювальні експерименти з використанням стандартних наборів даних демонструють, що запропонований алгоритм є ефективнішим і точнішим, ніж традиційний ACO.In this paper, we are interested in the Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) where clients must be contacted, in addition to their random availability before a set deadline. The main objective is to find an optimal route that covers a random subset of visitors in the same order as they appear on the tour, attempting to keep the path as short as possible. This problem is regarded as being ♯P-hard. Ant Colony Optimization (ACO) has been frequently employed to resolve this challenging optimization problem. However, we suggest an enhanced ACO employing the Levy flight algorithm in this study. This allows some ants to take longer jumps based on the Levy distribution, helping them escape from local optima situations. Our computational experiments using standard benchmark datasets demonstrate that the proposed algorithm is more efficient and accurate than traditional ACO.