基于ObjectARX 的物流配送最短路径实现方法

唐长铁

AutoCAD作为当前一种最通用的计算机辅助设计软件，在测绘、规划和制图中得到广泛应用，当前几乎所有的城市规划图都是采用AutoCAD软件进行绘制的。ObjectARX是Autodesk公司针对AutoCAD平台的二次开发推出的一个功能强大的软件开发包，它支持面向对象编程，共享AutoCAD的地址空间，与以往的AutoCAD开发工具AutoLisp和VBA开发的应用程序相比，能更快地访问AutoCAD图形数据库，大大提高应用程序的运行速度。

物流配送是现代物流系统的一个重要环节，合理选择配送路径，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。本文通过VC++和ObjectARX的结合实现在AutoCAD图中直接提取道路数据，并确定两点间最短路径，为物流配送方案提供一种有价值的选择。

1 算法基本思路

配送最短路径的实现其主要解决的问题就是道路数据的提取和两点间最短路径的确定。在ObjectARX开发环境中，针对AutoCAD数据库中的数据对象都有相应的类存在，并且每个类都封装了相应的属性和方法供用户使用，利用相应的类就可以实现在AutoCAD图中直接提取道路数据。两点最短路径的确定是计算机科学与地理信息科学等领域研究的热点，最短路径算法有很多种，目前最具有代表性的有Dijkstra算法、A*算法和Floyd算法。本文通过格式化存储提取的道路数据进行相关运算建立道路距离矩阵，改进周文峰等提出的最短距离选择模型，采用Floyd算法，实现两点间最短路径的确定。

2 实现算法

2.1 道路数据提取

AutoCAD是以数据库的方式组织图形数据的，存储在数据库中的数据都是以对象的形式存在。每一个实体对象在创建时数据库都会分配一个唯一的ID号，并返回给用户。通过使用一个对象ID，用户可以获得一个指向一个实际数据库的指针，从而对对象执行操作。因此通过获取道路实体对象ID，就可以实现在道路实体对象上提取所需要的数据。在AutoCAD数据库中，所有的可见几何实体都存储在模型空间块表记录中，因此只要遍历这个块表记录便可获得所有实体对象ID。在ObjectARX中，每个实体对象都有相应的属性和方法，利用相应的方法就可以提到每个实体对象的坐标及其各种属性。

为了实现在AutoCAD图形中直接提取道路，必须要求道路绘制在一个特定的图层上，且用多段线绘制，那么提取道路的过程就是在模型空间块表记录中搜寻出处于特定图层的多段线，然后调用多段线对象相应的方法来获取道路控制点数据。实现步骤如下:

第1步:道路ID的获取。首先获取当前数据库的对象，通过数据库对象得到块表对象，然后定义块表记录遍历器，遍历模型空间块表记录所有对象，获取处于道路中心线图层的所有实体ID。其主要实现代码如下:

第2步:获取道路控制点数据。为了建立道路关系所对应的距离矩阵，需要获取道路起点、终点、道路转折点以及道路交点。其主要实现过程如下:

对道路转折点的获取，ObjectARX并没有提供相应的方法来实现，只提供了用来获取顶点的方法，但顶点既包括转折点同时也包括我们所不需要的点。这样只能通过利用现有的方法来间接得到所需要的数据点。经过分析发现在道路转折点处，两个方向的直线斜率是不相等的，利用这个特性，我们通过排除法就能得到多段线上所有转折点的数据。通过以上两个过程，所有的道路关键点数据已经存储到AcGePoint3dArray类型的一维数组中，其中每元素对应着一条多段线上所有的控制点。

2.2 最短路径实现

两点间最短路径的确定是计算机科学与地理信息科学等领域研究的热点，到目前为止，前人已经发展了多种算法，比较经典的算法有Dijkstra算法、A*算法和Floyd算法。周文峰等根据上述算法提出了最短距离公交出行线路选择模型，并实现两个站点间最短距离确定。通过改进上述模型如图1所示，我们实现了在道路交通网中任意两控制点间最短距离的确定。

图1 改进的两点间最短距离确定模型

有了实现的基本思路后，这部分的主要工作就是在ARX丰富类库的基础上，结合VC++编程来完整地实现上述模型。实现步骤如下:

第1步:道路数据点格式化存储。

通过道路数据提取，我们获得了所有多段线的控制点，并将其按行存储到AcGePoint3dArray类型的一维数组中。但考虑到这样一种情况，即两条多段线的交点有可能处于多段线的起点、终点或转折点处，那么在前面提取到的数据点中就会重复提取，同时考虑到后面在建立直达距离矩阵时需将所有获取到的道路数据按各自到起点的距离进行排序，因此需要对提取的道路数据点进行格式化存储到AcGePoint3dArray数组中。部分实现代码如下:

第2步:建立每条道路的直达距离矩阵。

利用循环结构取出ptArray数组中的任意两点，通过ptTotal数组来判断是否是同一条多段线上相邻两点，如果是则调用相应多段线求距离方法求出它们间的距离，输出到直达距离矩阵中相应的位置，如果不相邻则在相应位置输出一个无穷大数。部分实现代码如下:

第3步:构造总的直达距离矩阵。

对所有多段线直达距离矩阵相应元素进行取小运算，得到总的直达距离矩阵totalDistanceMatrix[Max］[Max］(Max为控制点个数)。

第4步:建立任意两点间最短距离矩阵。

对总的直达距离矩阵使用Floyd算法，得到任意两点最短距离矩阵weight[Max］[Max］及任意两点最短距离路线上所经过的前一个控制点矩阵 path[Max］[Max］。

Floyd(totalDistanceMatrix，Max，weight，path);//调用 Floyd 算法给出道路控制点中的任意两点，结合 weight[Max］[Max］和 path[Max］[Max］，就可以确定两点间最短路径依次经过的控制点，也就确定了最短路径。

3 结语

本文利用ObjectARX本身具有的技术特点，开发了相应的ARX程序，实现了在AutoCAD图形中提取道路数据，建立道路交通网的数据模型。通过改进的最短距离选择模型，实现了任意两点间最短路径的确定，从而可以为物流方案的选择提供一个有价值的参考方案。但在实际中，物流方案的选择需考虑的因素很多，如交通限制等，因此本程序还有待于进一步完善。

[1]李国泰，王 祎，谢步瀛.图形区域操作的ARX关键技术[J］.东华大学学报(自然科学版)，2007，33(3):367-370.

[2]徐 斐.基于VC++和ObjectARX的选线系统的设计与开发[J］.兰州交通大学学报，2010，29(4):53-57.

[3]全思湘，方源敏，程永明.基于ObjectARX.net的面状符号自动绘制的实现方法[J］.测绘通报，2010(10):50-52.

[4]周文峰，李珍萍，刘洪伟，等.最优公交线路选择问题的数学 模型及算法[J］.运筹与管理，2008，17(5):80-84.