一般的，路径规划是指在一定的环境模型和约束条件（如路程最短、时间最快、费用最小等）下，寻找一条从起点到终点的最优路径。在此基础上，多点路径规划旨在为用户或车辆提供一条经过多个指定地点的最优行驶路线。其在共享出行、物流配送、公共交通规划等领域有着广泛的应用前景。
定制公交作为共享出行的一种创新模式，正逐步成为城市交通体系中不可或缺的一部分。它通过精准匹配乘客需求与公交线路，有效缓解了城市拥堵问题，同时也为乘客提供了更为便捷、舒适的出行体验。在公交降本增效的背景下，定制公交以其高效、灵活的特点，成为优化公交资优配置，提升公交系统的运营效率，降低运营成本的重要途径。在公交资源供需匹配的过程中即定制公交路线规划过程中，多点路径规划成为需要解决的核心问题。
高德地图开放平台的路径规划API是一项功能强大的服务，它能够为开发者提供包括驾车、步行、骑行、公交等多种出行方式的路线规划能力。这里以此驾车路径规划API为核心，结合旅行商路径优化算法，实现多点路径规划方案，本质上是通过算法对需求点进行初步排序，进而通过多段叠加的方式，实现多点的路径规划。整体过程如下：
实现细节
为了充分演示和验证该技术方案，这里以python FastAPI为后端框架，结合高德地图开放平台进行功能开发和演示。
开发过程主要分为3个部分，一是基于python的旅行商算法和后处理过程，其中后处理主要是对多段路径进行合并，并对走回头路等异常现象进行处理；二是基于FastAPI的后端服务开发，主要实现前端数据的接收和处理；三是前端页面开发，主要用于处理用户的交互逻辑，比如需求点的点选和显示，规划路径的显示等。
1️⃣ 算法处理，文件名称 ialgo.py
# -*- coding:utf-8 -*-
import itertools
from geopy.distance import geodesic
from shapely.geometry import LineString
from pygeoops import centerline
import geopandas as gpd
import requests
import logging
from shapely.geometry import MultiPoint, MultiLineString, MultiPolygon
logging.basicConfig(level=logging.DEBUG)
class TravelingSalesman:
# 旅行商问题
# 输入：经纬度点列表
# 输出：排序好的点列表
def __init__(self, points):
self.points = points # 经纬度点列表
self.min_distance = float('inf') # 最小距离初始化为无穷大
self.best_path = [] # 最优路径
def calculate_distance1(self, point1, point2):
"""计算两点间的欧几里得距离"""
print(point1[::-1], point2[::-1])
return geodesic(point1[::-1], point2[::-1]).m
def calculate_distance(self, point1, point2):
"""计算两点间的欧几里得距离"""
print(point1)
print(point2)
p1=[point1['lat'],point1['lng']]
p2=[point2['lat'],point2['lng']]
# 检查输入参数是否为元组或列表
if not (isinstance(p1, (tuple, list)) and isinstance(p2, (tuple, list))):
raise ValueError("Points must be tuples or lists")
# 检查每个点是否包含两个元素
if len(p1) != 2 or len(p2) != 2:
raise ValueError("Each point must contain exactly two elements (latitude, longitude)")
# 计算距离
distance = geodesic(p1, p2).m
# 记录日志
logging.debug(f"Calculating distance between {p1} and {p2}")
logging.debug(f"Distance: {distance} meters")
return distance
def find_shortest_path(self):
"""找到旅行商问题的最短路径"""
# 生成所有可能的路径
for path in itertools.permutations(self.points):
distance = self.calculate_total_distance(path)
if distance < self.min_distance:
self.min_distance = distance
self.best_path = path
return self.best_path
def calculate_total_distance(self, path):
"""计算给定路径的总距离"""
total_distance = 0
for i in range(len(path) - 1):
total_distance += self.calculate_distance(path[i], path[i + 1])
return total_distance
class iCenterline:
def __init__(self, points, crs='epsg:4525'):
# points 经纬度点列表
self.gps = gpd.GeoSeries(LineString(points), crs=4326).to_crs(crs)
self.crs = crs
def iSampleLine(self):
sline = self.gps.geometry.values[0]
sline = sline.buffer(30).buffer(-15)
cline = centerline(sline)
if cline.geom_type != "LineString":
cls = [_.length for _ in cline.geoms]
idx = cls.index(max(cls))
cline = cline.geoms[idx]
gps = gpd.GeoSeries(cline, crs=self.crs).to_crs(4326)
# gps.to_file('vector/cline.geojson', driver='GeoJSON')
# return [{'lng': lng, 'lat': lat} for lng, lat in gps.geometry.values[0].coords]
return [{'lng': lng, 'lat': lat} for lng, lat in extract_coords(gps.geometry.values[0])]
def extract_coords(geometry):
if isinstance(geometry, (MultiPoint, MultiLineString, MultiPolygon)):
return [coord for part in geometry.geoms for coord in part.coords]
else:
return list(geometry.coords)
class AmapDriving:
def __init__(self, api_key):
self.api_key = api_key
self.url = "https://restapi.amap.com/v3/direction/driving"
def get_driving_route(self, origin, destination):
params = {
'key': self.api_key,
'origin': origin, # 起点经纬度，格式为"经度,纬度"
'destination': destination # 终点经纬度，格式为"经度,纬度"
}
print(params)
response = requests.get(self.url, params=params)
route_info = response.json()
if route_info.get('status') == '1':
path_segments = route_info.get('route').get('paths')[0].get('steps')
path = []
for ipath in path_segments:
path.append(ipath.get('polyline'))
path = ';'.join(path)
else:
path = ''
print("驾车路线信息:", path)
return path
2️⃣ 后端服务，文件名称app.py
# -*- coding:utf-8 -*-
from fastapi import FastAPI, Body
from fastapi.responses import FileResponse
from pydantic import BaseModel
from typing import List
from ialgo import TravelingSalesman
from ialgo import AmapDriving
from ialgo import iCenterline
app = FastAPI()
class iloc(BaseModel):
lat: float
lng: float
class Location(BaseModel):
pts: List[iloc]
@app.post("/location/")
async def receive_location(location: Location):
# 处理前端传入的坐标点
pnts = [{"lat": _.lat, "lng": _.lng} for _ in location.pts]
otravel = TravelingSalesman(pnts)
pnts = otravel.find_shortest_path() # 点排序
path = [] # 高德规划路径 多段
for fp, tp in zip(pnts, pnts[1:]):
oAmap = AmapDriving('****') # 这里为高德web服务API，需替换为有效的API-key
print(fp, tp)
org = '{},{}'.format(fp['lng'], fp['lat'])
tpg = '{},{}'.format(tp['lng'], tp['lat'])
amap_path = oAmap.get_driving_route(org, tpg)
path.append(amap_path)
path = ';'.join(path) # 高德路径拼接
print(path)
path = [eval(_) for _ in path.split(';')]
print("=============================================")
print(path)
oline = iCenterline(path) # 计算中心线 防止回头路
res = oline.iSampleLine()
# 格式同 Location
coords = [(item['lng'], item['lat']) for item in res]
return coords
@app.get("/")
async def iclick_html():
return FileResponse('templates/pathBaseMultiPoint.html')
if __name__ == "__main__":
import uvicorn
uvicorn.run(app, host="0.0.0.0", port=8000)
3️⃣ 前端页面 pathBaseMultiPoint.html 该演示工作该文件位于 templates文件夹下
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>高德地图示例</title>
<style>
#map {
height: 600px;
}
#p2p {
position: absolute;
top: 10px;
/* 调整按钮的垂直位置 */
left: 130px;
/* 调整按钮的水平位置 */
z-index: 1000;
/* 确保按钮在地图之上 */
padding: 10px;
background-color: white;
border: 1px solid #ccc;
border-radius: 5px;
box-shadow: 0 2px 5px rgba(0, 0, 0, 0.3);
}
#clean {
position: absolute;
top: 10px;
/* 调整按钮的垂直位置 */
left: 30px;
/* 调整按钮的水平位置 */
z-index: 1000;
/* 确保按钮在地图之上 */
padding: 10px;
background-color: white;
border: 1px solid #ccc;
border-radius: 5px;
box-shadow: 0 2px 5px rgba(0, 0, 0, 0.3);
}
#path {
position: absolute;
top: 10px;
/* 调整按钮的垂直位置 */
left: 30px;
/* 调整按钮的水平位置 */
z-index: 1000;
/* 确保按钮在地图之上 */
padding: 10px;
background-color: white;
border: 1px solid #ccc;
border-radius: 5px;
box-shadow: 0 2px 5px rgba(0, 0, 0, 0.3);
}
</style>
</head>
<body>
<div id="map"></div>
<button id="p2p" , class="btn">高德路径</button>
<button id="clean" , class="btn">清除路径</button>
<script
src="https://webapi.amap.com/maps?v=1.4.15&key=YourAmapKey&plugin=AMap.Driving"></script>
<script> //更换自己的API key js端的
var map = new AMap.Map('map', {
center: [113.5, 34.8], // 经度, 纬度
zoom: 13 // 缩放级别
});
let points = [];
let markers = [];
let polyline;
map.on('click', function (e) {
var lat = e.lnglat.lat;
var lng = e.lnglat.lng;
console.log('点击位置: ', lat, lng);
points.push({ 'lat': lat, 'lng': lng });
var marker = new AMap.Marker({
position: e.lnglat
});
map.add(marker);
markers.push(marker);
var infoWindow = new AMap.InfoWindow({
content: `点击位置: ${lat.toFixed(5)}, ${lng.toFixed(5)}`,
position: e.lnglat
});
infoWindow.open(map, e.lnglat);
});
document.getElementById("clean").addEventListener('click', function () {
console.log('清除点');
points = [];
if (polyline) {
map.remove(polyline);
};
if (markers) {
markers.forEach(marker => {
map.remove(marker);
});
};
});
document.getElementById('p2p').addEventListener('click', async function () {
console.log('排序被点击');
if (points.length === 0) {
console.log('没有可用的路径点');
return;
}
const result = await sendLocationToBackend(points);
console.log('规划的路径点:', result);
// 创建折线
polyline = new AMap.Polyline({
path: result, // 设置折线经过的坐标点数组
strokeColor: "#FF33FF", // 线颜色
strokeOpacity: 1, // 线透明度
strokeWeight: 3, // 线宽
strokeStyle: "solid", // 线样式
strokeDasharray: [10, 5], // 自定义线段样式，格式为[线段长度, 空白长度]
lineJoin: 'round', // 折线拐点连接处样式
isOutline: false // 是否绘制边线外轮廓
});
// 将折线添加到地图上
map.add(polyline);
});
async function sendLocationToBackend(points) {
const jsonData = {
pts: points
};
try {
const response = await fetch('http://localhost:8000/location', {
method: 'POST',
headers: {
'Content-Type': 'application/json'
},
body: JSON.stringify(jsonData)
});
const data = await response.json();
console.log('Success:', data);
return data;
} catch (error) {
console.error('Error:', error);
}
};
</script>
</body>
</html>
效果如下
参考：https://lbs.amap.com/api/javascript-api/guide/services/navigation
标签：distance,self,路径,API,lat,path,lng,高德 From： https://www.cnblogs.com/ddzhen/p/18515555