已知多个地点经纬度的最优路径规划

Qifei

Python

发布于：2020年10月18日

次浏览

1：为什么规划路线

这是统一美团饿了么订单后的后续工作，要求对多个指定的配送地点进行统计，并计算出从花店出发，到配送完所有地点返回花店的可能路程，并得出最优的路线。。

2：设计思想

假设有四个配送点ABCD，配送的路线会有24种可能，枚举所有可能，并计算从花店到第一个配送点，依次再有三个配送点，然后返回花店的距离。比较这二十四种路线的距离，距离最少的，选为最优路线。

在Python中，使用itertools迭代库中的permutations方法，对路径可能进行排列。通过haversine公式计算两个经纬度之间的距离。

3：Python程序

# -*- encoding: utf-8 -*-
'''
@file_name    :shortest_dist.py
@description  :
@time         :2020/10/18 20:24:21
@author       :Qifei
@version      :1.0
'''
from math import radians, cos, sin, asin, sqrt
from itertools import permutations

class Route():
    def __init__(self,data):
        self.data = data
        self.home = {'lng':'104.270910','lat':'30.876583'}
        self.distances = []
        self.routes = []
        #排列各种可能的路线
        self.iter_routes = permutations(data,len(data))
        #将排列后的迭代类型数据转为列表类型
        for iter_route in self.iter_routes:
            self.routes.append(list(iter_route))
    #返回最优路线的列表排序
    def best_route(self):
        for route in self.routes:
            distance = 0
            if len(route) > 1:
                for i in range(len(route)-1):
                    distance += self.calc_distance(route[i+1]['lng'],route[i+1]['lat'],route[i]['lng'],route[i]['lat'])
            distance += self.calc_distance(self.home['lng'],self.home['lat'],route[0]['lng'],route[0]['lat'])
            distance += self.calc_distance(self.home['lng'],self.home['lat'],route[-1]['lng'],route[-1]['lat'])
            self.distances.append(distance)
        return self.routes[self.distances.index(min(self.distances))]

	#计算两个经纬度之间的距离
    def calc_distance(self,lon1, lat1, lon2, lat2):
        # 将十进制度数转化为弧度
        lon1, lat1, lon2, lat2 = map(radians, [float(lon1), float(lat1), float(lon2), float(lat2)])
        # haversine公式
        dlon = lon2 - lon1 
        dlat = lat2 - lat1 
        a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
        c = 2 * asin(sqrt(a)) 
        r = 6371 # 地球平均半径，单位为公里
        return c * r * 1000

if __name__ == '__main__':
    data = [{'name':'大弯中学','lng':'104.278184','lat':'30.879862'},{'name':'怡湖公园','lng':'104.261332','lat':'30.878314'},{'name':'大弯小学','lng':'104.270611','lat':'30.880657'},{'name':'长河郡','lng':'104.278201','lat':'30.872356'}]
    route = Route(data)
    # print(route.calc_distance(data[0]['lng'],data[0]['lat'],data[0]['lng'],data[0]['lat']))
  
    best_route = route.best_route()
    print(best_route)
    # print(route.distances)