Задача нахождения оптимального маршрута

Abstract

Задача о нахождении кратчайшего пути является одной из главных классических задач теории графов. Очевидно, что задача построения оптимального маршрута курьера является одной из множества интерпретаций данной задачи. В работе рассматривается алгоритм построения оптимального маршрута для использования в системе Яндекс.Еда курьером для доставки заказов. Алгоритм выполняет нахождение кратчайшего пути из пункта А (место приема заказа, может быть любым) через несколько пунктов (заведения, в которых приобретаются заказы, исходя из предпочтений клиента) в пункты доставки заказов.

The problem of finding the shortest path is one of the main classical problems of graph theory. It is obvious that the problem of constructing the optimal courier route is one of many interpretations of this problem. This paper considers an algorithm for constructing the optimal route for use in the Yandex system.Food by courier for delivery of orders. The algorithm finds the shortest path from point A (the place where the order is received, it can be any) through several points (places where orders are purchased, based on the customer's preferences) to the points where orders are delivered.