СИСТЕМА ОПРЕДЕЛЕНИЯ МАРШРУТА

1. Система определения оптимизированного маршрута, содержащая:
по меньшей мере один энергонезависимый читаемый компьютером носитель для хранения информации, имеющий набор команд;
по меньшей мере один процессор, осуществляющий связь с указанным по меньшей мере одним энергонезависимым читаемым компьютером носителем для хранения информации, при этом при исполнении команд указанный по меньшей мере один процессор выполнен с возможностью:
выстраивать в цепочки множество узлов для генерирования множества первых маршрутов-кандидатов, причем указанное множество узлов определяется на основе одного или более запросов, причем указанное множество первых маршрутов-кандидатов удовлетворяет первому условию относительно указанного множества узлов;
определять географическую длину каждого из указанного множества первых маршрутов-кандидатов на основе географических расстояний между любыми двумя из указанного множества узлов;
определять референсный маршрут из указанного множества первых маршрутов-кандидатов, причем географическая длина референсного маршрута является наименьшей из указанного множества первых маршрутов-кандидатов;
определять навигационную длину референсного маршрута на основе одной или более навигационных длин, каждая из которых расположена между парой соседних узлов на референсном маршруте;
определять один или более вторых маршрутов-кандидатов из указанного множества первых маршрутов-кандидатов на основе географической длины каждого из указанного множества первых маршрутов-кандидатов и навигационной длины референсного маршрута, причем географическая длина любого из вторых маршрутов-кандидатов меньше навигационной длины референсного маршрута;
определять навигационную длину каждого из указанного одного или более вторых маршрутов-кандидатов; и
определять целевой маршрут из указанного одного или более вторых маршрутов-кандидатов на основе одной или более навигационных длин указанного одного и более вторых машрутов-кандидатов, причем навигационная длина целевого маршрута является наименьшей из указанного одного или более вторых маршрутов-кандидатов.
2. Система по п. 1, в которой каждый запрос содержит указание стартового узла и узла назначения, причем первое условие состоит в том, что приоритет стартового узла на любом из первых маршрутов-кандидатов выше, чем приоритет узла назначения на указанном первом маршруте-кандидате.
3. Система по п. 1, в которой для генерирования указанного множества первых маршрутов-кандидатов указанный по меньшей мере один процессор дополнительно выполнен с возможностью:
определять первоначальный контур на основе указанного множества узлов, причем первоначальный контур представляет собой эйлеров контур с первой последовательностью узлов;
определять множества вторых последовательностей узлов на основе первой последовательности узлов и указанного первого условия относительно указанного множества узлов;
определять указанное множество первых маршрутов-кандидатов на основе указанного множества вторых последовательностей узлов.
4. Система по п. 3, в которой эйлеров контур определяется на основе алгоритма Кристофидеса.
5. Система по п. 3, в которой указанное множество вторых последовательностей узлов определяется на основе алгоритма 2-opt.
6. Система по п. 1, в которой для определения одного или более вторых маршрутов-кандидатов из указанного множества первых маршрутов-кандидатов указанный по меньшей мере один процессор дополнительно выполнен с возможностью:
определять множество первых разностей между географической длиной референсного маршрута и географической длиной каждого из указанного множества первых маршрутов-кандидатов;
определять первый параметр на основе разности между навигационной длиной референсного маршрута и географической длиной референсного маршрута;
назначать соответствующий первый маршрут-кандидат вторым маршрутом-кандидатом, если первая разность для указанного соответствующего первого маршрута-кандидата меньше первого параметра.
7. Система по п. 1 или 6, в которой:
каждый из вторых маршрутов-кандидатов содержит один или более отрезков, причем каждый отрезок соединяет два соседних узла на указанном втором маршруте-кандидате,
при этом для определения навигационной длины референсного маршрута указанный по меньшей мере один процессор дополнительно выполнен с возможностью:
получать набор референсных отрезков, содержащий множество отрезков референсного маршрута, и
определять навигационную длину каждого отрезка в указанном наборе референсных отрезков для определения навигационной длины референсного маршрута.
8. Система по п. 7, в которой:
для определения навигационной длины каждого из указанного одного или более вторых маршрутов-кандидатов указанный по меньшей мере один процессор дополнительно выполнен с возможностью:
определять один или более отличающихся отрезков между референсным маршрутом и указанным вторым маршрутом-кандидатом;
добавлять указанный один или более отличающихся отрезков в набор референсных отрезков; и
определять навигационную длину указанного второго маршрута-кандидата на основе набора референсных отрезков.
9. Система по п. 8, в которой отрезок указанного второго маршрута-кандидата не является отличающимся отрезком, если:
последовательность узлов указанного отрезка указанного второго маршрута-кандидата противоположна последовательности узлов отрезка референсного маршрута и
разность между навигационной длиной и географической длиной указанного отрезка не превышает пороговой величины.