海量坐标点求最短距离新探索

目录

一、前言

二、思路

三、实现

四、小结

一、前言

   多点路径距离最短问题是一个提出很久的课题，实际应用范围很广，快递配送方面、无人机运输投送，线路安排、点位分配等，最短距离的探索与研究成果可转化为实际应用，目前已经有很多成熟的算法，本文将从另一个思路，对100万虚拟坐标点，结合实际需求，进行最短距离的探索，分享与大家参考。

二、思路

1、随机生成100万个坐标点，供测试，因数据太大，使用 pickle 格式来保存生成的100万个数据，升序排列，格式【x,y,m】代表x、y坐标值和该点位名称，x、y值范围均是0至1000，保留两位小数。

def test_all(n,url):  # 生成虚拟数据 
    val=[[int(random.random()*100000)/100,int(random.random()*100000)/100,int(1+i)] for i in range(n)]
    pd.DataFrame(sorted(val)).to_pickle(url)

2、因点位数量太大，结合快递投递的实际情况，对这100万个坐标位置进行分组，便于分配给相应的投递站，本文以大约每组100个坐标点的设想，进行分组，各组坐标点均按顺时针顺序排序后保存于另一个 pickle 文档中，供后续程序使用。

def fenzu_pickle(url,to_url):    #以Pickle方式读取总表数据、分组、再保存  
    list_A=pd.read_pickle(url).values.tolist()
    list_B = [[] for _ in range(10000)]
    for s in list_A:
        n=int(s[0]/10)*100+int(s[1]/10)
        list_B[n].append(s)
    list_B_1=[shun(s) for s in list_B if len(s)>0]   # shun(s) 是顺时针排列的自定义函数
    pd.DataFrame(list_B_1).to_pickle(to_url)

3、求各组中所有坐标点相连的最短距离，每组坐标点大约100个，有人采用“蚁群算法”、“遗传算法”、“贪心算法”，都是很成功的算法，本文将采用对已按顺时针顺序排列的坐标点分段（每段5至8个坐标点）求出每组中最短距离的排列，将各组最短距离排列重新连接成新排列。期间使用 itertools.permutations（）方法，生成各段坐标点的全部排列顺序，并计算各个排列顺序的距离，将距离最短的排列顺序及距离保存下来。 

def zhuiduan(fz):  # 取得几个坐标点之间最短距离
    f1=fz[:1]
    f_1=fz[-1:]
    lisA1_1 = list(itertools.permutations(fz[1:-1]))
    for s in lisA1_1:
        smm=10000
        sk=f1+list(s)+f_1
        ji_sm=round(jishuan_list(sk),2)
        if ji_sm<smm:
            smm=ji_sm
            ju_lu=sk
    return smm,ju_lu

三、实现

1、导入所需的库 

import time,math,operator,glob,itertools,os,random
from functools import reduce
import matplotlib.pyplot as plt
from numba import njit
import pandas as pd

2、完整代码：

@njit
def jishuan(a,b): # 计算任意两点之间距离公式
    x1,y1=a[0],a[1]
    x2,y2=b[0],b[1]
    juli=((x1-x2)**2+(y1-y2)**2)**0.5
    return juli

def jishuan_list(list_s1):  # 计算一个列表所有坐标之间的距离
    ju=0
    for i in range(len(list_s1)-1):
        ju+=jishuan(list_s1[i],list_s1[i+1])
    return ju

def test_all(n,url):  # 生成总虚拟数据
    val=[[int(random.random()*100000)/100,int(random.random()*100000)/100,int(1+i)] for i in range(n)]
    pd.DataFrame(sorted(val)).to_pickle(url)

def shun(listA): # 顺时针排序
    coords=[]
    for a in listA:
        coords.append((a[0],a[1],int(a[2])))
    center = tuple(map(operator.truediv, reduce(lambda x, y: map(operator.add, x, y), coords), [len(coords)] * 2))
    ss=sorted(coords, key=lambda coord: (-135 - math.degrees(math.atan2(*tuple(map(operator.sub, coord, center))[::-1]))) % 360)
    return ss  

def fenzu_pickle(url,to_url):    #以Pickle方式读取总表数据,并分组  
    list_A=pd.read_pickle(url).values.tolist()
    list_B = [[] for _ in range(10000)]
    for s in list_A:
        n=int(s[0]/10)*100+int(s[1]/10)
        list_B[n].append(s)
    list_B_1=[shun(s) for s in list_B if len(s)>0]
    pd.DataFrame(list_B_1).to_pickle(to_url)

def dir_pick(path): # 获取目录下所有csv文件个数
    files = glob.glob(path+'/*.csv')
    return len(files)

def zhuiduan(fz):  # 取得几个坐标点之间最短距离
    f1=fz[:1]
    f_1=fz[-1:]
    lisA1_1 = list(itertools.permutations(fz[1:-1]))
    for s in lisA1_1:
        smm=10000
        sk=f1+list(s)+f_1
        ji_sm=round(jishuan_list(sk),2)
        if ji_sm<smm:
            smm=ji_sm
            ju_lu=sk
    return smm,ju_lu

def to_list_f(lis,m):  #计算最短距离
    lis.append(lis[0])
    ms=len(lis)
    nn=int(ms/m) if ms%m<2 else int(ms/m)+1
    list_fz=[lis[i*m:(i+1)*m+1]  for i in range(nn)]
    ju_ju = []
    sm=0
    for j,fz in enumerate(list_fz):
        len_a=len(list_fz)
        len_fz=len(fz)
        if len_fz>3:
            ju_li=zhuiduan(fz)
            if j<len_a-1:
                ju_ju+=ju_li[1][:-1]
            else:
                ju_ju+=ju_li[1]
            sm+=ju_li[0]
        else:
            sm+=round(jishuan_list(fz),2)
            ju_ju+=fz
    return [(sm,0,0)]+ju_ju

def yin_yon(url,m,file_na):   # 读取各组数据，计算最短距离，
    file_s=dir_pick(file_na)
    fen_list=pd.read_pickle(url).values.tolist()
    f_0=[[s for s in fen_list[i] if s is not None] for i in range(10000)]
    nn=len(f_0)
    for i in range(file_s,nn):
        to_to=min([to_list_f(f_0[i],m-k) for k in range(4)])
        pd.DataFrame(to_to).to_csv(file_na+f'\\p_{i}.csv',index=False,header=False)

if __name__=='__main__':
    nn=1000000  #生成虚拟数据数量
    ms=8     # 分段计算各点位全部组合距离
    all_url=r'p9999\p_all\p_all.pickle'    #创建该目录
    fen_url=r'p9999\p_all\p_fen.pickle'   #保存 所有数据按坐标范围分组
    duan_path=r'p9999\duochu'  #创建该目录，用于储存计算好的最短距离和点位顺序
    start = time.time()
    # test_all(nn,all_url)  # 第一步：运行后生成虚拟数据
    # fenzu_pickle(all_url,fen_url)   # 第二步：读取总表数据,并按坐标位置分组  
    # yin_yon(fen_url,ms,duan_path)   # 第三步：读取各组数据，计算各组最短距离，分别储存
    end = time.time()    
    print(end - start)

四、小结

1、本方法是一个个人尝试，供大家测试参考，作为一种思路来探索，本文的总体思路是化整为零，按坐标分组，按顺时针方向排序后分段求解再合并，最后完成最短距离的解决方案。

2、由于分为10000个组，各组进行最短距离求解，所需时间较长，我测试的时间是大约7000秒，在设计时 使用 dir_pick(path):函数 获取保存最短距离排列数据的文件夹下文件个数，来判断已求得最短距离的组个数，这样就不必一次求解10000组解值，中途可以退出程序，再次运行求解函数，不会从头开始求解，而是只对后面未求解的组，继续求解。