如何基于OpenStreetMap实现两点路线获取及多点最优路径规划？

一、当前现状与问题 #

你正在开发Web应用，目标是实现城市内n个点位的最短时间遍历。已放弃付费的Google Maps API，改用OpenStreetMap，并通过以下OpenLayers代码成功加载地图：

function initMap() {
   map = new OpenLayers.Map("map");
   var mapnik         = new OpenLayers.Layer.OSM();
   var fromProjection = new OpenLayers.Projection("EPSG:4326");   // Transform from WGS 1984
   var toProjection   = new OpenLayers.Projection("EPSG:900913"); // to Spherical Mercator Projection
   var position       = new OpenLayers.LonLat(long, lat).transform( fromProjection, toProjection);
   var zoom           = 14; 

   map.addLayer(mapnik);
   map.setCenter(position, zoom );
}

$(document).ready(function() {
    initMap();
});

你计划用贪心算法生成遍历顺序：选定起点，每次选择当前点到未访问点中耗时最短的点位，重复直到遍历所有点。但目前遇到的问题：

• 不知道如何获取两点间的路线、距离或耗时
• 不清楚如何将生成的点位序列转换为可展示的路线
• 对OpenStreetMap生态工具不熟悉，缺乏地理编码经验

二、分步解决方案 #

1. 获取两点间的路线与耗时 #

OpenLayers本身不提供路由计算能力，需借助基于OpenStreetMap的免费路由服务（如OpenRouteService）。这类服务可返回两点间的行驶路线、距离和耗时，调用示例如下：

// 传入起点和终点的经纬度（EPSG:4326格式，即[经度, 纬度]）
async function getRoute(startLonLat, endLonLat) {
  // 需先注册获取API密钥
  const apiKey = "你的API密钥";
  const response = await fetch(
    `https://api.openrouteservice.org/v2/directions/driving-car?api_key=${apiKey}&start=${startLonLat.join(',')}&end=${endLonLat.join(',')}`
  );
  const data = await response.json();
  
  // 提取路线的GeoJSON数据、距离（米）和耗时（秒）
  const routeGeoJSON = data.features[0];
  const { distance, duration } = data.features[0].properties.summary;
  
  return { routeGeoJSON, distance, duration };
}

2. 实现贪心算法的多点位遍历顺序 #

基于你的思路，用代码实现贪心策略生成遍历序列：

// 参数：startPoint为起点（格式{lon: 数值, lat: 数值}），points为所有待遍历点位列表
async function generateGreedyRoute(startPoint, points) {
  const visited = [startPoint];
  let currentPoint = startPoint;
  // 复制并排除起点的未访问列表
  const unvisited = [...points.filter(p => !(p.lon === startPoint.lon && p.lat === startPoint.lat))];

  while (unvisited.length > 0) {
    let minDuration = Infinity;
    let nextTarget = null;

    // 遍历未访问点位，找到耗时最短的目标
    for (const point of unvisited) {
      const { duration } = await getRoute(
        [currentPoint.lon, currentPoint.lat],
        [point.lon, point.lat]
      );
      if (duration < minDuration) {
        minDuration = duration;
        nextTarget = point;
      }
    }

    if (nextTarget) {
      visited.push(nextTarget);
      unvisited.splice(unvisited.indexOf(nextTarget), 1);
      currentPoint = nextTarget;
    }
  }

  return visited;
}

3. 在OpenLayers地图上绘制路线 #

拿到路由返回的GeoJSON数据后，可将其转换为OpenLayers矢量图层添加到地图：

// 将GeoJSON格式的路线添加到地图
function renderRoute(map, routeGeoJSON) {
  // 创建矢量图层
  const routeLayer = new OpenLayers.Layer.Vector("Route");
  // 解析GeoJSON为OpenLayers Feature
  const geoJsonFormat = new OpenLayers.Format.GeoJSON();
  const routeFeature = geoJsonFormat.read(routeGeoJSON);
  
  routeLayer.addFeatures([routeFeature]);
  map.addLayer(routeLayer);
}

4. 地址转坐标（地理编码） #

如果需要通过地址获取点位经纬度，可使用OpenStreetMap的Nominatim服务：

// 根据地址获取经纬度（EPSG:4326格式）
async function geocodeAddress(address) {
  const response = await fetch(
    `https://nominatim.openstreetmap.org/search?format=json&q=${encodeURIComponent(address)}`
  );
  const results = await response.json();
  
  if (results.length > 0) {
    return {
      lon: parseFloat(results[0].lon),
      lat: parseFloat(results[0].lat)
    };
  }
  return null;
}

三、关键注意事项 #

• 免费路由/地理编码服务有请求频率限制，需合理控制调用次数，避免触发限流
• 贪心算法是近似最优解，仅适合点位数量较少的场景（如n<20）；若需全局最优解，可考虑遗传算法、模拟退火等TSP专用算法
• OpenLayers地图使用的是EPSG:900913投影，若从服务获取的是EPSG:4326坐标，需用transform方法转换后再使用

内容的提问来源于stack exchange，提问作者dademurphy