按距離優化路線

我正在構建基於Here Maps的Web應用程序。其主要功能包括能夠將電子表格文件（.xls，.xlsx）上載到服務器，並使用文件中的地址計劃路線，最多可達500個航點。按距離優化路線

當然，這些航點並不是以優化的順序，所以我想讓用戶點擊一個「OPTIMIZE ROUTE」按鈕，並按距離優化它。

例如，如果該文件有三個地址：

紐約
舊金山
長島

默認的路徑是從紐約去SF ，然後回到李。

該應用程序將檢查距離和重新排列航點陣列在這樣的方法：

NY - > LI - > SF

我的問題： 有一個內置的路由優化功能在這裏地圖，或者我應該寫我自己的？

來源

2014-03-06 PeterInvincible

我真的很想開始使用HERE地圖這個工作，是[尋找一個簡單的解決方案（HTTP：//計算器。 com/search？q =％5Bhere-api％5D + optimize），但不幸的是，似乎我們不得不轉向Google Maps，因爲顯然這裏的解決方案非常簡單[[在請求中添加'optimize：true]查詢]（https://developers.google。com/maps/documentation/directions/intro＃OptimizeWaypoints） –

**更新**好吧，看起來像這裏的地圖可能實際上有我們需要的東西：[汽車的Waypoints序列]（https://developer.here。 COM/API資源管理器/ REST/routing_waypoints /序列航點車路線）。不知道爲什麼它深入到示例部分。 –

你應該看看Matrix Routing API（需要登錄）。這將計算N x M個位置之間的「實際」距離。有了這些信息，您已將問題簡化爲Travelling Salesman Problem。當然，TSP是NP完全的，所以你不能確定你有最佳的答案，除非你使用強力算法。

我個人認爲最近鄰居解決方案 - 快速，非常簡單的代碼，通常返回一個「合理的」，如果不是最佳的解決方案。你可以升級到更復雜的算法需要：

下面的僞代碼：

開始在A點
矩陣路由請求所有剩餘的點。
找到最近的，這將成爲下一個Waypoint
重複步驟2

來源

2014-03-06 08:52:52

再一次，謝謝。這是迄今爲止我發現的最簡單的方法。 – PeterInvincible

很高興看到你在這裏的地圖的答案。你能幫我一個地圖問題在這裏 - > http://stackoverflow.com/questions/22249057/how-to-display-loading-icon-while-rendering-markers-on-the-map –

這被稱爲旅行商問題。

您需要有一張從任何地方到您支持的任何其他地方的距離表。

一旦你有了，你可以使用任何通用的旅行銷售人員算法。

被警告，他們是非常緩慢。

來源

2014-03-06 08:40:35 avoid3d

按距離優化路線

回答

相關問題