Arxiv/A Tabu Search Algorithm for the Multi-period Inspector Scheduling Problem 2014 1409.5166 — различия между версиями

«A Tabu Search Algorithm for the Multi-period Inspector Scheduling Problem 2014 1409.5166»^{скачать}

Представлена ​​задача планирования многопериодного инспектора (MPISP), что представляет собой новый вариант задачи о маршрутизации многопутевого транспорта со временем. окна (VRPTW). В MPISP каждый инспектор должен выполнить маршрут в заданном многопериодном горизонте планирования. В конце каждого периода каждый инспектор не обязан возвращаться в депо, но должен оставаться в одном из вершины для восстановления сил. Если оставшееся время текущего периода равно недостаточно для того, чтобы инспектор покинул свою текущую вершину А к определенная вершина B, он/она может выбрать либо ожидание в вершине A до начала следующего периода или переход в вершину C, которая ближе к вершине B. Следовательно, на кратчайшее время прохождения между любой парой вершин влияет продолжительность периода и время отправления.

Сначала мы опишем подход вычисление кратчайшего времени прохождения между любой парой вершин с произвольное время отправления. Для решения MPISP мы предлагаем несколько локальных операторы поиска адаптированы из классических операторов для VRPTW и интегрированы их в систему запрета поиска. Кроме того, мы представляем ограниченный модель ранца, которая может дать оценку сверху для задачи. Ну наконец то, мы оцениваем эффективность нашего алгоритма с помощью обширных экспериментов на основе на множестве тестовых экземпляров.

Результаты наших расчетов показывают, что наши подход порождает качественные решения.