步行路线优化器近邻搜索异常求助：折线交叉、误选远点

问题根源分析 #

1. 折线交叉：当前仅基于单个参考点的局部最近点选择属于贪心算法的局部最优逻辑，未考虑全局路线的连贯性，容易出现回头走、绕路等导致交叉的情况。
2. 误选远点：大概率是两个原因：一是Haversine公式实现存在单位（弧度/角度转换）或计算错误，导致排序失真；二是时间校验逻辑优先级过高，跳过了符合距离条件的最近点，直接将不符合时间的点设为新参考点。

针对性优化方案 #

一、修复误选远点问题 #

1. 校验并修正Haversine公式实现

确保经纬度正确转换为弧度计算，避免单位错误导致的距离偏差。示例Django模型方法：

from math import radians, sin, cos, sqrt, atan2

class PDV(models.Model):
    latitude = models.FloatField()
    longitude = models.FloatField()

    def haversine_distance(self, other_pdv):
        # 转换为弧度（Haversine公式要求输入为弧度）
        lat1, lon1 = radians(self.latitude), radians(self.longitude)
        lat2, lon2 = radians(other_pdv.latitude), radians(other_pdv.longitude)

        dlat = lat2 - lat1
        dlon = lon2 - lon1

        a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
        c = 2 * atan2(sqrt(a), sqrt(1-a))
        radius = 6371.0  # 地球半径（公里）
        return radius * c * 1000  # 返回距离（米）

同时检查排序逻辑，确保是按距离升序排列候选点，避免搞反排序方向。

2. 调整时间校验逻辑

不要按排序顺序逐个校验后直接切换参考点，而是先筛选所有符合时间条件的候选点，再从中选最近的；若没有符合时间条件的点，再选最近的点重置时间统计：

# 假设remaining_points是未加入路线的点位集合
valid_candidates = [pdv for pdv in remaining_points if check_time_condition(pdv)]
if valid_candidates:
    # 在符合时间条件的点里选最近的
    next_point = min(valid_candidates, key=lambda x: current_ref.haversine_distance(x))
else:
    # 无符合时间条件的点，选最近的作为新参考点
    next_point = min(remaining_points, key=lambda x: current_ref.haversine_distance(x))
    reset_time_stat()

二、解决折线交叉问题 #

1. 给贪心算法加入方向连贯性约束

计算上一段路线的方位角，优先选择与上一段方向夹角较小的点（避免突然回头），再结合距离排序：

import math

def calculate_bearing(point_a, point_b):
    # 计算从a到b的方位角（0-360度）
    lat1, lon1 = radians(point_a.latitude), radians(point_a.longitude)
    lat2, lon2 = radians(point_b.latitude), radians(point_b.longitude)

    dlon = lon2 - lon1
    x = math.cos(lat2) * math.sin(dlon)
    y = math.cos(lat1) * math.sin(lat2) - math.sin(lat1) * math.cos(lat2) * math.cos(dlon)
    bearing = math.degrees(math.atan2(x, y))
    return (bearing + 360) % 360

# 假设上一段路线的起点是prev_point，终点是current_ref
prev_bearing = calculate_bearing(prev_point, current_ref)
valid_candidates = [pdv for pdv in remaining_points if check_time_condition(pdv)]

# 给候选点计算与上一段方向的最小夹角
for candidate in valid_candidates:
    curr_bearing = calculate_bearing(current_ref, candidate)
    angle_diff = abs(curr_bearing - prev_bearing)
    candidate.angle_diff = min(angle_diff, 360 - angle_diff)

# 先按夹角升序，再按距离升序排序
valid_candidates.sort(key=lambda x: (x.angle_diff, current_ref.haversine_distance(x)))
next_point = valid_candidates[0] if valid_candidates else None

2. 引入2-opt局部优化消除交叉

生成初始路线后，用2-opt算法遍历路线中的边对，交换端点来消除交叉并缩短总距离：

def two_opt_optimize(route):
    improved = True
    while improved:
        improved = False
        for i in range(1, len(route)-2):
            for j in range(i+1, len(route)-1):
                # 计算原路径和交换后的路径距离
                old_dist = route[i-1].haversine_distance(route[i]) + route[j].haversine_distance(route[j+1])
                new_dist = route[i-1].haversine_distance(route[j]) + route[i].haversine_distance(route[j+1])
                # 检查交换后是否消除交叉
                if new_dist < old_dist and not edges_intersect(route[i-1], route[i], route[j], route[j+1]):
                    # 反转i到j的路段
                    route[i:j+1] = reversed(route[i:j+1])
                    improved = True
    return route

def edges_intersect(a1, a2, b1, b2):
    # 用跨立实验判断两条线段是否相交
    def ccw(A,B,C):
        return (C.latitude - A.latitude) * (B.longitude - A.longitude) - (B.latitude - A.latitude) * (C.longitude - A.longitude)
    return (ccw(a1,a2,b1) * ccw(a1,a2,b2) < 0) and (ccw(b1,b2,a1) * ccw(b1,b2,a2) < 0)

3. 优化初始点选择

不要仅用最北端的点作为初始点，可同时尝试最北、最南、最东、最西四个候选起点，分别生成路线后选择总距离最短、交叉最少的路线作为最终结果。

三、其他细节优化 #

• 缓存距离计算结果：用字典存储已计算的点对距离，避免重复计算提升性能。
• 可视化调试：每一步生成路线时，绘制当前参考点、候选点及已选路线，快速定位误选或交叉的触发节点。

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