基于Trans CAD的定位路线问题解决方案

江 伟

（江苏省交通技师学院车辆工程系 江苏 镇江 212006）

0 前言

Trans CAD拥有一套车辆路径和物流程序模块，能以表格和地图的形式输出Trans CAD软件系统计算出的最优选址、最优路径和车辆调度时刻表。Trans CAD的这些程序可以解决诸多复杂的物流问题。本文使用Trans CAD软件系统解决物流系统LRP，目的是为了说明采用先进的信息技术能更高效、直观地为现代物流规划提供最优解决方案。

1 定位路线问题

定位路线问题(Location Routing Problem，LRP)是物流规划中定位配给问题（LAP）和车辆路线（VRP）问题的集成，是物流系统优化的难题。LRP可描述为：给定一组符合实际情况的客户点集合和备选设施点集合，从这些备选设施点中选出一组新的设施位置集合作为规划设施点，同时还要确定出一套从各个设施到其服务客户点的运输路线，解决该问题的目的是使总费用最小。LRP通常作如下假定：（1）客户位置和客户需求量已知；（2）备选设施点位置已知；（3）货物由一个或多个设施供应；（4）每个客户只接收来自一个设施的一个车辆送来的货物。

2 基于Trans CAD的LRP方案优化

2.1 在Trans CAD中创建LRP地图

2.1.1 路网层及相关数据库的建立

将DXF格式的路网文件导入Trans CAD中，选取我们所需要的CAD图层，导入线地理文件。

为了防止输出矩阵时也很可能会出现空白矩阵单元，需对路网中的所有路段节点都和紧邻路段节点实现无间隔性连接的检验，断开的节点需用地图编辑工具来连接。

当路网层导入后，Trans CAD会自动生成与此图层相关的一些属性字段，再添加本文所需的属性字段SPEED和TIME，再为每条记录填充相应的字段值，这样就建立了路网层数据库。

2.1.2 设施点和客户点图层及数据库的创建

以城市道路网作为底图层，建立设施点层和客户点层。本文假定A市共有9个设施点，其中有1个已存在设施点和8个备选设施点，选址阶段需选出2个新建设施点。

（1）设施点图层及设施数据库的创建

新建地理文件Facility，添加到当前图层窗口，设置属性字段，再在图层中添加设施点。本文将设施点分为原有设施点和备选设施点两类，所以我们需要在地图图层中进行分类。在设施选择集中新建原有设施点Exsisting和备选设施点Candidate两个选择集，再到设施点数据窗分别点选两个选择集。

（2）客户点图层及客户数据库的创建

客户点图层的建立方法同设施点图层。本文假定有46个客户点分布在城市路网中，客户点层数据库需增加的属性字段有NAME，OPEN TIME， CLOSE TIME， FIXED SERVICE TIME， TIME PER UINT，DEMAND，NODE_ID。创建设施点层和客户点层后，需将所有设施点、客户点和路网节点连接起来，以实现设施点和客户点在路网上的通达性，查找出基于现实路网的最短路径。在Endpoints属性表中为设施点和客户点分别添加索引字段INDEX 01和INDEX 02，以便连接后自动生成节点ID和设施点ID、客户点ID的对应关系。

3 网络

创建网络文件并使之成为当前激活的网络。使用命令Networks/Paths>Multiple Paths创建的以时间为权值的最短路径阵。本文数据输入需要一个服务成本矩阵，所以需要在最小时间矩阵的基础上创建一个服务成本矩阵COST。本文在选址阶段的目标就是在保证设施到客户的平均服务成本最小的前提下确定待建设施点的位置。每个候选设施向客户提供物流服务都会产生相应的服务成本，本文构建服务成本公式[1]：C=F+P*t。式中，C—服务成本；F—固定投资成本；P—运营成本相关系数；T—车辆运营时间，单位：min。

本文给定固定投资成本为320/60，运营成本相关系数为80，因此服务成本公式为C=320/60+80*时间/60（以上数据仅供本文测试用），输出服务成本矩阵。服务成本矩阵用于查找基于路网层的设施点到客户点的最短路径，该矩阵中的索引为路网节点层的ID，这与原设施点ID和客户点ID不一致，因此必须使服务成本矩阵索引ID与设施点ID和客户点ID相一致。

3.1 基于Trans CAD的物流设施选址与配送路线解决方案

3.1.1 物流设施选址

本文进行物流设施选址所需要的材料包括：（1）A市的城市道路网图层；（2）包含所有备选设施点的点图层；（3）包含所有客户点的点图层；（4）客户点需求，表示客户点重要程度的权重量；（5）成本矩阵。每个设施都有与之相关的固定投资成本和运营成本。我们可以以此来建立物流服务的成本矩阵，行代表候选点列代表客户。

利用上述三个图层来输出作为选址程序基本输入的服务成本矩阵，它包括所有设施点和客户点，是通过计算候选点到客户点的运行时间来创建最短时间矩阵，然后利用时间矩阵求出成本矩阵。

在设施定位对话框进行相应设置，打开设施选择集对话框，就会看到Trans CAD自动生成了一个名为New Facilities的选择集，它包含两个点。设施数据窗中也会显示出选择集，最后Trans CAD生成一个设施选址结果图。

3.1.2 车辆路线安排

本文需要解决的是受车辆类型、容量及成本约束、带时间窗的车辆路线安排问题，需要事先准备好以下材料：（1）带有服务时间限制的设施数据库；（2）带有营业时间、车辆固定服务时间限制的客户数据库；（3）基于路网的包含所有设施点到客户间的距离和出行时间的路线矩阵文件；（4）各设施车辆信息数据库。[2]

本文在设施选址的基础上进行车辆路线安排。首先需要建立一个“规划后设施”的选择集以便后续程序调用，此选择集包括已经存在的1个设施和2个新设施。

在VRPTW对话框进行相应设置并输出路线矩阵，还可输出一个文本形式的车辆行程安排记录。点击演示路线命令，地图中就会增加路线图层并产生一个stops表格，显示设施点和客户点的对应关系。

3.2 结果分析

本文规划的三个设施中“F2”、“F8”为新规划设施，“F5”为原有设施。对比设施定位结果和车辆路线安排结果可知，在设施定位模型中由设施“F5”为客户“C10”提供配送服务，设施“F8”为客户“C43、C44”服务，而在车辆路线模型中客户“C10”是由设施“F2”服务的，客户“C43、C44”由设施“F5”服务。为了实现物流设施定位和配送路线的整体优化，本文要使用辆路线编辑工具箱对车辆路线安排方案进行调整，将客户点 “C10”添加到设施“F5”的配送路线Route 7中，再点击重新计算站点顺序按钮，系统将自动调整该路线时间顺序。另外，需为设施点“F8”和客户点“C43”、“C44”创建新路线。[3]

3.3 A市物流设施选址与配送路线解决方案

图1 A市物流系统LRP解决方案图

在本文案例的解决方案中，从8个备选设施点选出“F2”、“F8”两个规划设施，这两个设施和原有设施“F5”一起为46个客户提供物流配送服务。一共形成12条配送路线。其中设施“F2”派出3辆车，形成Route 9、Route 10、Route 11 共 3 条配送路线。 设施“F5”派出 5 辆车，形成 Route 4、Route 5、Route 6、Route 7、Route8 共 5 条配送路线。 设施“F8”派出 4 辆车，形成 Route 1、Route 2、Route 3、Route 12 共 4 条配送路线。

Trans CAD路线系统显示A市物流系统LRP解决方案（如图1所示），还能为每一辆车制定了详细的出行路径和出行时间表。

4 结论

本文对基于Trans CAD软件系统的物流系统LRP解决方案进行了研究，对如何运用Trans CAD中的物流模块解决物流系统LRP进行了阐述，解决了基于Trans CAD的物流系统LRP，最后对方案结果进行分析，并用路线编辑工具对物流配送方案进行调整，为非计算机专业的人员提供了一个解决LRP的平台。

［1］Caliper Corporation.Trans CAD 中文用户手册[M].America，2002：215-220.

［2］杨宁，尚新春，韦献兰，李海峰.利用Trans CAD软件包解决基于时间窗的车辆路径问题[J].交通与计算机，2007，1(25)：113-114.

［3］Caliper Corporation.Trans CAD 中文用户手册[S].America，2002：177-181.