Введение
Постановка задачи
1. Этапы решения
2. Решение задачи в режиме онлайн
2.1. Алгоритм Дейкстры
2.2. Жадный эвристический алгоритм
2.3. Эвристический алгоритм «самый дальний от центра свободный курьер
2.4. Алгоритм Флойда-Уоршелла
2.5. Эвристический алгоритм «ближайший к пункту доставки свободный курьер
3. Эвристические алгоритмы, в которых граф делится на области
3.1. Жадный эвристический алгоритм
3.2. Эвристический алгоритм «ближайший к пункту доставки свободный курьер
3.3. Эвристический алгоритм «ближайший к пункту отправки или к пункту доставки свободный курьер
4. Данные для численного эксперимента
4.1. Численный эксперимент
Заключение
Список использованной литературы
Приложение
В век информационных технологий довольно актуальной проблемой среди фирм, предоставляющих курьерские услуги, является распределение заказов среди курьеров.
Задача заключается в определении курьера, который должен забрать появившийся заказ и вовремя доставить в пункт назначения. Сложность задачи состоит в необходимости выполнения как можно больше заказов, задействовании всех курьеров так, чтобы суммарно курьеры прошли как можно меньше пути, задействовании курьеров так, чтобы каждый курьер выполнил примерно одинаковое количество заказов, в определении оптимального маршрута для доставки заказа (учитывая пробки, ремонтные дороги и прочие помехи на дороге), обеспечении связи между курьером и диспетчером, обеспечении связи между курьером и заказчиком, отслеживании местоположения заказа. Но главной проблемой является то, что заказы поступают в режиме онлайн, и невозможно предугадать, где именно появится новый заказ, соответственно нельзя заранее рассчитать какой курьер выполнит определенный заказ. В случае, когда время заказов известно, данную задачу можно свести к задаче о коммивояжере, которая принадлежит классу NP- полных задач.
Класс NP-полных задач — в теории алгоритмов класс, в котором, любую задачу из этого класса можно свести к другой задаче из этого класса за полиномиальное время. Эти задачи можно решить за полиномиальное время на недетерминированной машине Тьюринга. Учитывая то, что недетерминированную машину Тьюринга, можно промоделировать на детерминированной машине Тьюринга, многократно копируя состояния, такое моделирование займет большое количество времени. При этом неизвестно насколько большое. Поэтому на данный момент для задач из этого класса не найден «полиномиально быстрый» алгоритм решения.
Так как заказы поступают в режиме онлайн, нужно разработать онлайновый алгоритм. Онлайн алгоритмы отличаются от обычных алгоритмов тем, что заказ нужно распределить в тот же момент, когда он появляется. Появление нового заказа никак не влияет на предыдущие заказы. Такие алгоритмы являются более эффективными как по времени, так и по памяти, в случае, когда происходит работа с большим количеством заказов, не надо хранить всю информацию о предыдущих заказах, и более практичными, так как на практике, как правило, в начальный момент времени не известна информация о всех заказах.
Для упрощения задачи, критерием оптимальности будет количество выполненных заказов.
Цель данной работы - разработать, реализовать и сравнить детерминированные онлайн алгоритмы, которые в среднем будут показывать оптимальный результат для решения задачи распределения заказов по курьерам и будут работать за полиномиальное время.
По полученным данным можно сделать вывод, что простой жадный алгоритм в среднем работает эффективней остальных алгоритмов.
Но если разбить граф на подмножества такие, что сумма минимальных весов всех пар вершин этих подмножеств не сильно отличается, эффективней работает жадный алгоритм с разбиением графа на области. Учитывая то что, разбить граф на подмножества, которые удовлетворяют условию выше NP- полная задача, алгоритмы, которые работают при разбиении графа на хорошие области, кажутся непригодными. Однако, на практике граф задается в виде карты и человек может визуально определить, как лучше разбить граф на хорошие области. Поэтому данные алгоритмы будут эффективно работать на практике.
