Press "Enter" to skip to content

用Python计算一组站点根据其坐标的距离矩阵

轻松估算任意一对站点之间的距离,以地理坐标作为解决路由问题的有效垫脚石

Photo by Bruno Wolff on Unsplash

👁️ 这是系列文章中的第4篇,涵盖了项目“python智能旅游决策支持系统”,我鼓励你阅读一下,对整个项目有一个总体了解。如果你只对创建距离矩阵感兴趣,那么这篇文章就足够了,它是自成一体的。如果你还想将距离矩阵应用于实际问题,那么这个系列文章对你也会有兴趣。

本文继续我们的旅程,从第三个冲刺结束的地方开始。在第四个冲刺中,我们从建模中做了一个简要的偏离,并开发了一个带有地理空间功能的类,当我们尝试解决一般的旅行推销员问题时非常方便,即对于我们可能没有距离数据的任意站点的问题。我们在上一个冲刺中提到了这个“要求”,并且在这个冲刺中将构建一个子系统来满足这个要求。

目录

1. 上一个冲刺回顾

2. 读取输入数据

3. 根据位置数据创建距离矩阵

  • 3.1. 我应该额外付出一点努力来获得更多的收益吗?
  • 3.2. 使用geopy实用工具的地理位置
  • 3.3. 前往目标地点
  • 3.4. 从坐标到距离矩阵

4. 封装起来!(在一个类中)

  • 4.1. GeoAnalyzer类设计
  • 4.2. 类的使用演示

5. 结论(或下一个冲刺的计划)

1. 上一个冲刺回顾

在上一篇文章中,也就是第三个冲刺的文章中,我们进行了一个概念验证,证明我们可以解决一组站点的旅行推销员问题(TSP),前提是我们拥有每个可能站点之间的距离作为距离矩阵。这个距离矩阵是由于在那个冲刺中,我们的重点是建模,而不是数据处理。然而,一旦模型准备好了,我们注意到我们需要一种方法来解决一般的TSP问题,也就是说,对于任意一组站点的TSP问题。这种泛化是为了创建一个真正有用的最小可行产品(Minimum Viable Product)。因此,我们得出结论,下一个自然的步骤是找到一种方法自动从我们感兴趣的站点的坐标中获取距离矩阵,我们将在本文中介绍这个步骤。

这样做的话,我们的新的基本输入将简单得多,只需要我们希望访问的站点的地理坐标:

Figure 1. Coordinates of the sites of interest. (Image by author)

输出结果将是我们用作TSP模型输入的数据帧,用于输入站点的距离矩阵:

图2. 给定一组站点的期望距离矩阵。 (图片作者提供)

为了保持一致,我们将继续使用我们之前考虑的巴黎站点。在下一篇文章中,我们将将此功能与旅行推销员问题的优化模型集成在一起,得到一个更多功能的MVP。

🎯 以最终目标为导向

让我们退后一步,简要回顾一下我们为什么这样做。我们渴望解决的原始现实生活问题被称为旅行游客问题(TTP),即为普通旅游者创建最佳行程计划的问题,同时考虑她个人的“数据”(偏好,预算等)和旅行的“环境”数据(距离,价格,交通方式等)。

鉴于这个现实生活问题被认为过于复杂,我们在第1次冲刺中简化了它,以启动解决方案的设计。这个“本质问题”被证明是旅行推销员问题(TSP),其中我们将访问的点视为城市中旅游者的“兴趣点”。通过本文中开发的功能,我们离TTP的整体解决方案更近了一步,而TSP则是解决方案的核心。

2. 读取输入数据

我们的基本输入现在是我们在旅行中想要访问的站点的地理坐标。我们将把“酒店”视为一种不同类型的场所,因为酒店本身不是“兴趣点”,而是我们在多天旅行中必须访问以休息的地方。在不同的旅行或不同的情况下,我们选择的酒店可能不同,而城市中的兴趣点在很大程度上是各种旅行指南都同意的“不变”地点。当我们准备探索更高级的应用时,这种区别的有用性将变得更加明显。

因此,我将我们酒店的坐标存储在一个名为location_hotel.csv的CSV文件中,并将“兴趣点”的坐标存储在单独的CSV文件sites_coordinates.csv中。这两个CSV文件具有相同的结构,因此我们将它们读取并合并到一个包含所有站点的数据帧中:

import pandas as pdprint(f"版本 pandas: {pd.__version__}")DATA_FOLDER = ("https://raw.githubusercontent.com/carlosjuribe/"               "traveling-tourist-problem/main/data")FILE_LOCATION_HOTEL = "location_hotel.csv"FILE_LOCATION_SITES = "sites_coordinates.csv"df_sites = pd.concat([    pd.read_csv(f"{DATA_FOLDER}/{FILE_LOCATION_SITES}", index_col='site'),    pd.read_csv(f"{DATA_FOLDER}/{FILE_LOCATION_HOTEL}", index_col='site')])display(df_sites)

用Python计算一组站点根据其坐标的距离矩阵 四海 第4张

ℹ️ 如何快速准备您自己的位置数据

如果您想使用自己的站点列表跟随本文,您需要复制我获取坐标的步骤:

1. 进入Google 地图并搜索列表中的每个站点。

2. 每个站点将显示为地图上的一个点。右键单击每个点。出现的第一个元素是一对数字:您点击的点的纬度和经度。

3. 点击这些数字,它们将保存到您的剪贴板中,准备粘贴到文件中,同时选择为该点选择的名称。

4. 为您的所有站点重复上述第1至3步,您将得到一个类似于sites_coordinates.csv的文件。

这个过程对于少量站点来说效果不错,但是如果有数百甚至数十个站点,它会变得非常繁琐。在[未来的一篇文章]中,我们将创建一种自动化这项手工工作的方法,这称为地理定位。

3. 从位置数据中创建距离矩阵

要创建距离矩阵,我们需要获取任意两个位置之间的距离。听起来很简单,但是“距离”实际上取决于上下文。我们是否考虑到了地图应用程序(如Google地图)报告的距离,这些应用程序考虑了街道网络、桥梁、公园等因素?如果是这样,我们是考虑行人步行的距离还是汽车行驶的距离?还是只考虑连接两点的直线长度?显然,我们有许多可能的距离选项可供选择,其准确度也不尽相同。我们首先要回答的问题是:在我们问题的特定背景下,我们应该如何定义“距离”并且在这个阶段选择哪种方式?

3.1. 我是否要为了多走一码而多付出一点努力?

很自然地,我们会感到想要使用准确的数据。毕竟,我们都知道准确性本身就有价值,因此我们倾向于追求准确的数据,越多越好。但是我们也必须记住,更准确的数据意味着更复杂的代码和依赖关系,因此需要更多的开发时间和维护工作。由于我们遵循敏捷方法,我们不会让最好的东西成为好的东西的敌人,因此我们将尽可能简单地开始,然后逐渐增加复杂性,只有在合理的情况下才会添加。

在需要在位置之间查找距离的这一点上,我们可以像许多人一样,直接跳到基于第三方API的解决方案,这些解决方案需要应用程序密钥、凭据,甚至是云服务提供商的信用卡号码。这种方法是可以接受的,但往往效率低下,因为我们可能会忽视准确信息提供了附加价值,但也伴随着额外的成本。

👁️ 没有“免费准确性”这样的东西

记住,通常情况下,我们获得准确数据时都“付出代价”(这与信息价值Value of Information的概念密切相关)的事实,是采取敏捷方法解决问题的另一个原因。通过在我们自己的问题数据上根据“所需准确度的水平”进行简单假设,并验证其在我们自己问题数据上的有效性,我们可以确保,如果我们最终需要提高我们的数据准确性,我们所付出的“代价”将是值得的(预期的)改进结果

所以让我们从非常简单的方式开始。我们有坐标。 第一个想法:这些坐标分布在与地球半径相比非常小的地球区域,所以我们可以将纬度视为Y坐标,经度视为X坐标,在二维平面上计算欧氏距离(通常的“直线”)。

  • 优点:简单的距离公式,没有新的依赖项或数据,位置之间的空间关系被保留。
  • 缺点:纬度和经度是无量纲数,因此当解决问题时,我们得到的数字不是实际距离。这意味着我们关心的一些信息,如总行驶距离,将不可用,即使我们可以获得最佳路线。

缺点超过了优点,因此我们需要一个更复杂的方法(但仍然简单)。 第二个想法:将坐标视为它们所代表的地球上的点,但将地球近似为一个球体。球体没有熟悉的欧几里得几何,因此我们需要使用一个非平凡的公式,考虑到球面几何学,计算两点之间的“直线”距离。所以现在只是一个实现那个公式,使用地球的半径。我们可以这样做,但相反我们将依赖于一个已经做到这一点,甚至更好的著名库。

3.2. 使用geopy的地理位置工具

如果这个文章系列专门关注地理空间数据科学,花时间解释和实现大圆距离的公式将是有价值的,这是一个计算球面上点之间“直线”距离的良好基准选择。但是,这个文章系列讨论的是一个基于优化的旅游规划系统的创建,因此我们不会自己编写地理空间工具的公式,而是依赖于Geopy来为我们处理繁重的工作。这样,我们可以将重点放在快速达到解决方案上。

通过在Anaconda提示符中运行以下命令来安装它(或在我们在第一篇文章中创建的conda环境中运行,如果你创建了它):

conda install -y -c conda-forge geopy=2.3.0

现在,让我们用geopy在两个位置之间进行演示。

3.3. 到达目标点

给定两个点的坐标,geopygeodesic函数计算连接它们的测地线在地球表面上的距离。在几何学中,测地线是在给定的度量空间上点之间的最小距离路径。在我们熟悉的欧几里得空间中,直线是测地线。在球形空间中,大圆弧是测地线。Geopy的geodesic函数所考虑的底层“空间”是地球的一个精确椭球体模型

👁 一个大圆弧真的很好,但一个椭圆更好

前面我说过,我们将地球视为一个球体,因为这是最简单的可行近似。实际上,地球不是一个球体,而是一个具有更复杂几何的椭球体。现在,geopy将使我们免于编写我们自己的非欧几里得几何函数,我们可以升级我们对地球的近似,并使用两点之间更准确的椭球面距离,而不是大圆距离。换句话说,这是相同代码行数的更好地球模型。这确实免费提高了准确性,为什么不利用呢?

这是一个计算点1和点2之间椭圆面距离的函数,单位是米:

from geopy.distance import geodesicdef ellipsoidal_distance(p1, p2) -> float:    """ 计算点p1和p2之间的距离(以米为单位),其中    每个点表示为(lat, lon) """    return geodesic(p1, p2).meters

埃菲尔铁塔和卢浮宫之间的距离是多少?

p1 = df_sites.loc['Tour Eiffel']p2 = df_sites.loc['Louvre']ellipsoidal_distance(p1, p2)  # 输出:3173.119635531859

3173米,约3.2公里。Google地图显示为3.5公里。计算的距离比“真实”距离低8.6%。然而,对于预计整天在大城市四处走动的游客来说,我们的腿只关心距离的绝对误差,而在这种情况下,相对于预计距离只多走了330米,并不像一个显著的误差。

埃菲尔铁塔和Suffren港之间的距离是多少?

ellipsoidal_distance(    df_sites.loc['Tour Eiffel'],    df_sites.loc['Port de Suffren'])  # 输出:328.3147101635456

328米,这次比Google地图提供的350米短(只少了22米)。这在应用一个公式时并不糟糕。如我们所预期的,两点之间越接近,街道就越不可能曲折,拐弯也越少,因此椭球体模型产生的误差越低。对于我们目前的目的来说,这看起来足够好

现在我们必须将这个函数应用于所有位置对,从而得到TSP模型所需的距离矩阵。

3.4. 从坐标到距离矩阵

这是简单部分,我们只需循环两次遍历所有站点,并计算和存储每对之间的距离。下面的函数就是这样做的。请注意,距离度量作为一个可选参数传递,而椭圆面距离是我们之前使用的默认距离度量。我们为将来可以传递更好的距离度量方式留下了余地。

“`html

def compute_distance_matrix(df_sites, dist_metric=ellipsoidal_distance):    """ 创建一个N x N的距离矩阵,使用包含纬度列和经度列的N个位置的数据框作为输入 """    df_dist_matrix = pd.DataFrame(index=df_sites.index,                                   columns=df_sites.index)    for orig, orig_loc in df_sites.iterrows():  # 对于每一个起始点        for dest, dest_loc in df_sites.iterrows():  # 对于每一个目的地            df_dist_matrix.at[orig, dest] = dist_metric(orig_loc, dest_loc)    return df_dist_matrixdf_distances = compute_distance_matrix(df_sites)display(df_distances)
Figure 3. 使用椭球模型计算的距离矩阵结果。 (图片由作者提供)

就是这样!如预期的一样,矩阵的对角线是零,矩阵是对称的。输出数据框的索引和列包含输入站点的名称。

功能演示完毕。现在我们可以更好地完成对这个函数的使用。让我们将这个功能方便地包装到一个类中,以便轻松重复使用,更重要的是,以便与我们在前一轮中构建的TSP优化模型更容易地集成。

4. 包装起来!(放入一个类中)

4.1. GeoAnalyzer类设计

让我们创建一个新的类GeoAnalyzer,专门用于处理路径问题中可能出现的地理空间工具。因此,我们的函数compute_distance_matrix自然地适用作为一个方法。该类的主要部分目前包括:

  • 一个包含位置信息的数据框,名为_df_locations
  • 纯粹的函数ellipsoidal_distance
  • 方法get_distance_matrix,与先前的函数compute_distance_matrix等效,但使用实例属性_df_locations来计算距离。

由于用户可能希望随时将新的位置添加到地理位置列表中,我们包括接受地理坐标数据框并将其附加到先前现有位置的方法add_locations

下面是GeoAnalyzer的定义。注意这里还有其他方便的方法和属性没有在此处提到。

from typing import Tupleimport pandas as pdfrom geopy.distance import geodesicclass GeoAnalyzer:    """ 用于地理位置信息和处理的工具 """      _GeoPoint = Tuple[float, float]        def __init__(self):        """ 使用方法`add_locations`将一些位置存储在内部         并开始使用地理工具 """        self._df_locations = pd.DataFrame(columns=['latitude', 'longitude'])            #####################   distances   #####################    @staticmethod    def ellipsoidal_distance(point1: _GeoPoint, point2: _GeoPoint) -> float:        """ 计算点1和点2之间的椭球距离(以米为单位),其中每个点表示为元组(纬度,经度) """        return geodesic(point1, point2).meters    #########################################################        @property    def locations(self):        return self._df_locations        @property    def num_locations(self):        return len(self._df_locations)            def add_locations(self, df_locations: pd.DataFrame):        """ 分析所需的地理位置数据。        参数        ----------        df_locations : pd.DataFrame            具有第一列命名为'latitude'和第二列命名为'longitude'的地理坐标数据框        """        df_updated = pd.concat([self._df_locations, df_locations.copy()])        # 以防万一用户添加了重复的位置,删除重复的位置        self._df_locations = df_updated.drop_duplicates()            def get_distance_matrix(self) -> pd.DataFrame:        """ 基于提供的位置数据计算距离矩阵,以数据框的形式返回 """        df_locations = self._df_locations        dist_metric = self.ellipsoidal_distance  # 只有一个可用的距离        # 初始化距离矩阵        df_dist_matrix = pd.DataFrame(index=df_locations.index,                                       columns=df_locations.index)        # 对于每一个起始点和目的地点对,计算距离        for orig, orig_loc in df_locations.iterrows():            for dest, dest_loc in df_locations.iterrows():                  df_dist_matrix.at[orig, dest] = dist_metric(orig_loc,                                                            dest_loc)        # 一点元数据也没坏处        df_dist_matrix.distance_metric = dist_metric.__name__        return df_dist_matrix            def __repr__(self):        """ 显示当前被考虑的位置数量 """        return f"{self.__class__.__name__}(n_locs={self.num_locations})"

“`

4.2. 类的使用示例

让我们稍微探索一下类的主要功能。我们创建一个实例,并从巴黎添加我们感兴趣的站点:

geo_analyzer = GeoAnalyzer()geo_analyzer.add_locations(df_sites)

我们检查当前实例的表示形式,它告诉我们我们已提供了9个位置,我们可以通过属性locations检查其详细信息:

display(geo_analyzer)display(geo_analyzer.locations)

用Python计算一组站点根据其坐标的距离矩阵 四海 第6张

当然,我们可以从对象中提取距离矩阵,这在现在已经很熟悉了:

df_distances = geo_analyzer.get_distance_matrix()display(df_distances)

用Python计算一组站点根据其坐标的距离矩阵 四海 第7张

最后,如果我们想知道这些值来自哪里,我们可以从数据框本身进行检查:

print(f"使用的距离度量:{df_distances.distance_metric}")# [Out]: 使用的距离度量:椭球面距离

如果有更多的距离度量可用,这将更有价值,这是我们将在未来的开发周期中探讨的内容。

5. 结论(或下一个迭代的计划)

我们的工作结果是一个名为GeoAnalyzer的类,它具有方便的方法,可以帮助我们将旅行推销员问题(TSP)推广到任意一组站点。 这种泛化将是我们下一个迭代的确切目标,我们将在其中创建一个类似于估计器的类,用于隐藏在迭代2中涵盖的模型构建步骤,并以所要访问的站点的地理坐标作为输入。 GeoAnalyzer类将是这个新估计器类的关键组成部分,使我们构建的TSP优化模型能够得到真正通用的使用方式。 这个新的估计器类结合了GeoAnalyzer的灵活性和TSP模型的广泛性,将成为我们解决更一般的旅行游客问题的核心。继续访问下一个迭代来了解真实情况!

欢迎关注我,向我提问,给我反馈,或在LinkedIn上与我联系。感谢阅读!📈😊

Leave a Reply

Your email address will not be published. Required fields are marked *