Розрахунок відстаней між двома точками по дорогах може стане в нагоді в самих різних сферах, я ж розгляну це питання з точки зору класичної прикладної задачі в транспортній логістиці - заповнення відрізків подорожніх листів.
Як правило, в якості облікового відстані приймається показання одометра водія. Однак потрібно розуміти, що показання приладу не завжди на 100% об'єктивні - вони можуть не збігатися з розрахунковим, навіть якщо автомобіль не відхилявся від маршруту. Справа в тому, що показання приладу засновані на підрахунку кількості оборотів обода колеса під час руху. Формула має такий вигляд:
де n-кількість обертів колеса, R-радіус шини.
Таким чином, в показаннях виникають похибки, які залежать від ходової частини автомобіля, а також пов'язані з прямим втручанням водія в тарировки приладу. З практики відомо, що зміна радіуса колеса на 5 мм, внаслідок невідповідності з попередньо встановленими заводом-виготовлювачем шинами, призведе до зміни показань пробігу на одометрі і тахографі приблизно на 2%. Також на показання одометра впливатиме зношеність шин, тиск у них (при низькому тиску зменшується кут кочення колеса, що призводить до завищення показань), а також власна похибка приладу.
Саме тому, з метою контролю, я рекомендую перевіряти ці відстані за допомогою веб-сервісу Google Maps.
Алгоритм знаходження відстані між точками заснований на вирішенні двох підзадач:
- Геокодування - процес визначення географічних координат картографічних об'єктів. Цими об'єктами можуть бути населені пункти, вулиці, будинку, поштові індекси тощо
- Побудова оптимального маршруту між двома точками, засноване на теорії графів.
Якщо описувати метод в спрощеній формі, то його суть зводиться до визначення мінімальної суми графів (тобто відрізків доріг) між початковою і кінцевою точкою з усіх можливих. Алгоритми Google Maps враховують також пропускну здатність доріг, якість їх покриття, наявність платних ділянок і т.д.
Весь шлях ділиться на величезну кількість мікроотрезков, сума відстаней між якими і складає точну довжину маршруту. Потрібно врахувати, що ці відрізки знаходяться на сферичної поверхні Землі, тому формула розрахунку має такий вигляд:
L = arcos (sin (x1) * sin (x2) + cos (x1) * cos (x2) * cos (y1 -y2)) * R,
де x1, y1-то ширина й довжина першої точки в радіанах; x2, y2-то ширина й довжина другої точки в радіанах; R-середній радіус Землі (6372,8 км).
Приклади запитів і результати представлені в таблиці.
Корпорація Google накладає обмеження на безкоштовне використання свого сервісу: 2500 запитів на добу. Лічильник обнуляється о 24 годині за тихоокеанським часом (Pacific Time Zone), тобто о 10 годині дня за мінським.