基于模块化A^*寻优算法的地铁货车快递联运系统

Subway truck express transport system based on improved modular A^* optimization algorithm

摘要

为缓解城市交通运输压力，进一步提高运输效率，本文根据复杂交通网络节点理论设计评价指标，结合层次分析法的多目标决策方法（AHP-RatioMOORA）对地铁站点重要性进行排序并计算出权重，并根据重要性对地铁物流配送枢纽进行选址。同时，为解决传统优化算法在复杂约束条件下存在收敛困难、全局搜索能力差的问题，通过对A^*算法进行结构化的改进，建立一种模块化的寻优算法，对地铁货车快递联运任务进行分析建模，并结合多种约束的改进目标函数对该任务进行实例分析。案例分析结果表明，本文所提出的方法相较于其他多种优化算法在地铁货车快递联运任务中有着显著提升，优化后最短物流运输距离平均缩小13.21%，物流订单完成时间平均缩短11.73%，算法运行时间平均缩短24.79%。

Abstract

In order to alleviate the pressure of urban transportation， in order to further improve the transportation efficiency. This paper designs evaluation indexes according to the theory of complex transportation network nodes， combines the multi-objective decision-making method of hierarchical analysis （AHP-RatioMOORA）， ranks the importance of subway stations and calculates the weights， and selects the location of subway logistics and distribution hubs according to the importance. In order to solve the traditional optimization algorithm in the complex constraints there are convergence difficulties， global search can be poor， this paper through the A* algorithm to improve the structure， the establishment of a modular optimization algorithm， the subway truck express intermodal task analysis modeling， combined with a variety of constraints of the improvement of the objective function of the task of the case study analysis. The results of the case study show that the method proposed in this paper has a significant improvement compared with other optimization algorithms in the subway truck express intermodal transport task， the shortest logistics transportation distance after optimization is reduced by 13.21% on average， the logistics order completion time is shortened by 11.73% on average， and the algorithm running time is shortened by 24.79% on average.

Graphical abstract

关键词

城市交通 / 地铁网络 / A^*算法 / RadioMOORA模型 / 遗传算法 / 多目标协同优化

Key words

urban transportation / subway network / A^* algorithm / RadioMOORA model / genetic algorithm / multi-objective collaborative optimization

0 引 言

随着城市现代化进程的推进，道路、地铁等基本运输设施日趋完善，生产和生活的物资需求量不断增长。同时，物流运输随着互联网经济的发展，也随之呈现出了蓬勃发展的态势，成为城市生产和生活的基本需求。

从2009年开始，随着“天猫双11”、“京东618”等大型电商促销活动的兴起，物流运输需求也随之猛增，我国电商物流行业在得到快速发展的同时，也面临着巨大的配送压力，各大电商平台通过提前布局、延长促销周期，试图分散订单高峰，减轻物流压力。即便如此，促销活动期间的快递量仍然是平时的数倍甚至数十倍，物流运输工作量的急剧增加，不仅容易造成城市的交通拥堵，还会导致快递服务质量下降，客户满意度及企业的服务形象都会受到严重影响。

近年来，为了缓解城市的货运压力，基于地铁的地下物流系统（Metro-Underground logistics system M-ULS）^［1］受到了国内外学者的广泛关注。Dampier等^［2］在国际会议上提出了利用地铁进行客货混运的理念；钱七虎^［3］借鉴国外优秀经验，提出了可通过地铁解放城市货运压力，建设地下物流系统格局；He等^［4］正式提出利用轨道交通建设完善新型城市物流配送系统，并设计了城市物流配送系统的具体框架，将信息管理中心、货运中心、轨道交通、配送人员巧妙合理相结合；Kikuta等^［5］提出了将传统地面货运车辆与地铁物流结合，相互配合共同运输的系统方案，并进行了试点检测；周芳汀等^［6］以最短配送时间为主要目的，在考虑列车时刻表和客户时间窗的同时，构建了基于随机变邻域搜索算法的地铁配送网络；聂闻聪等^［7］提出了一种“灌溉”概念的单向城市轨道配送模式，可以大幅度减少配送时间，同时还利用聚类及遗传算法对配送点的选址优化求解，构建了城市配送选址模型；舒达等^［8］采用双边匹配理论，构建了城市多级配送的选址-路径优化模型，能在最小化物流成本的同时，尽可能提高选址满意度。

所以，通过以地铁为主的城市轨道交通开展货运，并将其作为城市配送方案是极具意义的尝试。截止至今，已有许多城市通过轨道交通来开展城市货物运输的案例，例如，在东京有将废弃物品通过轨道的方式进行运输的实例^［9］；巴黎有使用列车将货物运输至中转站，然后再运输至商店的案例^［10］。

在开展道路与地铁联运运输的系统设计中，需要一套相应的地铁货车运输路径规划算法，目前在这一领域当中，主要使用经典路径规划算法，直接求解货物运输途径道路及地铁物流配送枢纽选址的最优方案。而为了完善的算法设计，即满足运行配送的效率、满意度等，可使用多目标优化算法将这些作为算法约束条件来进行求解，通过将地铁物流配送枢纽与取寄件点、配送点作为路径点，利用如粒子群算法（PSO）^［11］、遗传算法（GA）^［12］、模拟退火（SA）^［13］等算法求解快递地铁货车配送问题。然而在整体上，优化算法面对路径点及快递订单较多时，求解时间普遍偏长，从而影响系统整体的执行效率。因此，提升地铁货车快递运输配送最优路径求解的效率，是保障系统正常运行的关键所在。

为解决上述问题，本文通过对影响地铁货车运输系统配送因素进行分析，提出一种改进模块化寻优算法，适用于目前在地铁货车运输系统中使用的大部分优化算法。同时，针对地铁货车联运路径优化问题，引入受配送偏好、地铁线路设计、配送需求量、早晚高峰等影响，使得本文研究的地铁货车物流运输系统更加贴合实际情况。

1 地铁货车快递运输路径优化问题

在本节中，对地铁货车联运路径规划设计的模型场景进行详细介绍，同时说明本文中涉及假设的相关前提条件。地铁货车快递联运是目前较为热点的快递运输方式，本文针对地铁货车联运过程中的地铁物流配送枢纽选址及路径优化问题，做出了完善改进，提出一种可以全面提升快递运输效率的优化算法。

1.1　问题描述

采用地铁货车联合的方案，有助于城市轨道交通运力。本文研究的地铁货车联运任务以上海市地铁网络为基础，上海市地铁网络结构如图1所示，大城市的地铁网络覆盖面积大、地铁线路密集，城市的地铁网络物流系统存在充分的发展空间。本研究处理的地铁货车物流系统运行的基本流程可以分为若干步骤。首先，快递员到寄件人地址取货，送至邻近配送点，再由小货车将货物从配送点送至地铁物流配送枢纽，通过地铁网络将货物配送至合适的地铁物流配送枢纽，之后小货车将货物配送至配送点，最后由快递员送至收件人手中。

所以，在本文中涉及的配送系统由以下7个部分构成：

（1）配送点。各区域设置若干配送点，每次配送流程由配送点先派出快递员到下单的客户位置进行取货。

（2）地铁物流配送枢纽。配送点制定好配货批次后，由货车将货物运输至地铁物流配送枢纽进行挑拣分运。

（3）货车。用于行驶至派单客户位置取件以及配送货物至订单指定地点派送。

（4）寄件人p位置。客户在订单系统下单后确定快递员取货的位置。

（5）收件人q位置。客户在订单系统下单后确定快递员送货的位置。

（6）地铁线路。城市中存在用于运输的地铁网络。

（7）地铁站。作为地铁物流配送枢纽的候选站点，可改造为地铁物流配送枢纽。

本研究在进行数学模型建模时将这7个部分视为图结构的点或边，在2.5节中详细说明了具体的参数和决策变量设置。

1.2　问题假设

为保证求解结果的可靠性，对本问题的研究的模型做如下假设：①货物已提前在容器中装载，可以快速装卸。②货物不能直接通过不同的地铁线转运。③各个地铁物流配送枢纽的货物容纳量足够，不考虑货物在地铁物流配送枢纽滞留，列车进站后直接开始装卸配送。

下面对假设的目的进行说明：

（1）假设的主要目的是为了更加符合实际运输情况及提高地铁货车多级目标求解器的泛化能力，从而提升地铁货车联运的运输效率。

（2）在实际的地铁货车联运当中，各地铁路线转运的时间不同，因此在本研究涉及的地铁货车联运系统中不包含货物在不同地铁线之间转运的情况。

（3）本文的主要目的是为了提升地铁运行空载和空驶时利用率，进一步考虑地铁货物滞留的情况需要进行更为复杂的建模。

路径优化问题经典的求解方式是，利用优化模型设置相应的目标函数和约束条件对想要求解得到的参数结果进行限制。本文对建立的提高地铁货车快递运输效率的建立模型进行了介绍，同时对本文提出的用于评估地铁站点重要性的评价指标进行详细阐述，最后介绍了本研究如何通过在优化过程中混合A^*算法提升地铁货车快递联运任务的求解效率。

2 基于改进模块化A^*寻优算法的地铁货车快递联运优化模型

2.1　模块化A^*寻优算法

地铁货车快递联运问题复杂程度受到各级节点数量影响^［14］，通过传统算法直接进行求解的可接受的计算成本较高。一般形式的点对点路径寻优算法相关研究目前已经较为成熟并得到了十分广泛的应用，较为经典的寻径算法如A^*算法。但是，在处理地铁货车运输这样具有多个起始及终止目标点，且点与点之间存在前后的接续关系时，这一类点对点寻径算法通过一般的修改启发函数等方式是很难解决的。然而，这些复杂问题正是优化算法所擅长的领域，因此本文通过将两者进行结合用于解决地铁货车快递运输问题。

首先，对于利用优化算法求解最优路径的问题来说，一般都是基于旅行商问题的某种改进算法。本研究改进这一算法的关键点是，针对现实中地铁货车快递运输的点对点特性，将订单与订单之间的节点寻优过程由点对点路径寻优算法替代，优化算法用于决定订单与订单之间取件与派件的顺序。由于各地铁站点之间决策变量优化过程被路径寻优所替代，减少了决策变量的数量，从而提升了模型计算效率。在城市交通物流运输系统中定义的地铁站点很难视作一般点对点路径寻优算法中的节点，本研究通过在优化算法当中混合启发式算法A^*算法求解提升算法求解的效率。

综上，本文针对所研究问题设计了一种基于模块化A^*寻优算法，并使用该方法结合优化算法对模型进行求解，进而将其应用于本文研究中。

具体地，如图2所示，本文所提出的路径寻优方法主要包含两部分，基于A^*算法的全局成本优化器和基于遗传算法的多目标多级求解器。

首先，由A^*算法规划最优路径并根据如遗传算法的优化算法设置并判断是否满足约束条件，筛选后的路径由优化算法继续优化。得到的新策略继续由A^*算法判断是否为可达路径，直到满足输出条件。其中，全局成本优化器主要解决全局代价计算问题，多级求解器解决多目标寻优中城内地铁物流配送枢纽与寄取件订单地址以及订单完成顺序的调度问题。

如图3所示，在本文提出的成本优化器中，其中A^*算法主要用于求得地铁货车最短物流运输路径，同时在遗传算法中根据对多种惩罚代价约束进行求解。A^*算法是一种在图形平面上寻找从起始点到终点最短路径的启发式搜索算法。它结合了广度优先搜索和最佳优先搜索（Best-First Search）的特点，通过启发式函数评估节点的重要性。其中，遗传算法主要用于求得满足多目标寻优中多种约束条件限制下的可行解，并对多目标路径寻优方法进行优化得到最优解。地铁货车物流运输系统流程如下：

输入：路网信息；订单信息；相关参数设置

输出：各个运货批次的调度策略、运输成本

1. 标记地铁、车辆信息在地图中的位置，根据物流订单信息进行第一轮匹配。

2.2　参数说明和决策变量

表1为本文中解决地铁货车快递运输问题所使用的相关参数^［15-18］，并对每个参数的含义进行了说明。表2为本文地铁物流运输系统中求解快递运输问题的相关决策变量。

2.3　目标函数

在本文构建的地铁货车快递运输优化模型中，主要考虑运输成本、运输时间作为地铁货车快递运输系统中的主要因素，基于上述本文中问题描述，构建的地铁货车快递运输路径优化模型如下所示：

f_{\mathrm{1}}=\mathrm{m}\mathrm{i}\mathrm{n}\left(\eta \right)=C_{\mathrm{1}}\sum _{p\in I}\sum _{q\in L}{S}_{pq}^{\mathrm{1}}+C_{\mathrm{2}}\sum _{p\in I}\sum _{q\in L}{S}_{pq}^{\mathrm{2}}（1）

其中，S_{pq}^{\mathrm{2}}=\sum _{i\in A}{y}_{i_{\mathrm{1}}{i}_{\mathrm{2}}}{d}_{ij}；

S_{pq}^{\mathrm{1}}=\sum _{i\in A}\sum _{j\in B}\left(x_{vpj}{d}_{pj}+x_{vji}{d}_{ji}+x_{vij}{d}_{ij}+x_{vjq}{d}_{jq}\right)。

f_{\mathrm{2}}=\mathrm{m}\mathrm{i}\mathrm{n}\left(\rho \right)=\sum _{p\in I}{\phi }_{\mathrm{1}}{\iota }_p+\sum _{q\in L}{\phi }_{\mathrm{2}}{\iota }_q（2）

其中，{\iota }_p=\left\{\begin{array}{l}\mathrm{0},{\mathrm{E}}_{pi}\le T_p\le E_{pj}\\ \left(E_{pi}-T_p\right),T_p\le E_{pi}\\ \left(T_p-E_{pj}\right),T_p\ge E_{pi}\end{array}\right.

{\iota }_q=\left\{\begin{array}{l}\mathrm{0},{\mathrm{E}}_{qi}\le T_q\le E_{qj}\\ \left(E_{qi}-T_q\right),T_q\le E_{qi}\\ \left(T_q-E_{qj}\right),T_q\ge E_{qi}\end{array}\right.

其中，式（1）（2）为本文设计的地铁货车运输多级优化问题求解的目标函数，f_{\mathrm{1}}表示货车地铁运输总成本最小；f_{\mathrm{2}}表示未按照时间窗取货和送达的惩罚代价。

基于上述问题构建数学模型的约束条件设计如式（3）~（14）所示。

\sum _{v\in U}\sum _{p\in I}\sum _{j\in B}{x}_{vpj}=\mathrm{1}（3）

\sum _{v\in U}\sum _{i\in A}\sum _{j\in B}{x}_{vji}=\mathrm{1}（4）

\sum _{v\in U}\sum _{i\in A}\sum _{j\in B}{x}_{vij}=\mathrm{1}（5）

\sum _{v\in U}\sum _{q\in L}\sum _{j\in B}{x}_{vjq}=\mathrm{1}（6）

x_{vpj}\in \left\{\mathrm{0,1}\right\},\forall p\in I;\forall j\in B;v\in U（7）

x_{vji}\in \left\{\mathrm{0,1}\right\},\forall j\in B;\forall i\in A;v\in U（8）

x_{vij}\in \left\{\mathrm{0,1}\right\},\forall j\in B;\forall i\in A;v\in U（9）

x_{vjq}\in \left\{\mathrm{0,1}\right\},\forall j\in B;\forall q\in L;v\in U（10）

\sum _{j\in B}\sum _{p\in I}{x}_{vpj}{g}_{pj}\le G_v,\forall v\in G（11）

\sum _{j\in B}\sum _{i\in A}{x}_{vji}{g}_{ji}\le G_v,\forall v\in G（12）

\sum _{j\in B}\sum _{i\in A}{x}_{vij}{g}_{ij}\le G_v,\forall v\in G（13）

\sum _{q\in L}\sum _{i\in A}{x}_{viq}{g}_{iq}\le G_v,\forall v\in G（14）

其中，式（3）~（6）含义为每个订单货物必须被单独一辆车服务，客户的需求必须唯一不可被拆分；式（7）~（10）为决策变量0~1的约束；式（11）~（14）表示为货车最大载货量限制。

2.4　地铁网络中节点的重要性评估

2.4.1　路由优先度

确定地铁网络中的重要节点有助于定位地铁网络的枢纽，由于地铁网络是典型的无环路无向网络，因此可以利用复杂网络理论中的节点重要性指标评价各子网络中节点的重要性。本文提出并设置路由优先度来评估不同地铁站点在地铁网络中作为节点的重要性。

假设地铁网络中的地铁站点数量为A，将地铁站视为地铁网络的节点。Zhao等^［19］在研究中提出了评价地铁站点的度中心性指标，其在量化网络节点重要性方面具有较高的有效性。地铁站点的中心性越高说明该地铁站点在地铁网络中的可达性越高，且具有越多可达路线。

本文在货运距离的基础上加入紧密中心性指标、卡兹中心性指标、度中心性指标作为配送点对地铁站点的重要性指标。卡兹中心性不仅考虑了节点与其直接相邻节点连接，同时还通过递归的方式考虑节点与整个地铁网络中其他节点的连接，这种全局性考量能够更加准确地反映出目标地铁站点在地铁网络中的地位。在地铁网络中，紧密中心性则通过衡量节点与其他节点的距离反映其中心位置和重要性，紧密中心性不仅反映了节点在地铁网络中的位置，还间接衡量了节点信息传播的效率，在地铁网络中紧密中心性高的节点往往是交通枢纽，在整个地铁网络的流畅性和效率都具有重要影响。

紧密中心性：紧密中心性反映某一节点与其他节点之间的接近程度^［20］。如果一个节点离其他节点越近，则该节点传递信息时对其他节点的依赖就越小。一个节点到网络中各点的距离都很短，那么这个点就不会受制于其他点。在地铁网络中，地铁站点的标准紧密中心性是地铁站点与地铁网络中所有其他地铁站点和配送点之间最短，紧密中心性（A{Q}_i）计算公式为：

A{Q}_i=\frac{\mathrm{1}}{d_i}=\frac{n-\mathrm{1}}{\sum _{j\ne \mathrm{1}}{d}_{ij}}（15）

式中：d_i为该地铁站点到其它所有地铁站点或配送点的平均最短距离；d_{ij}为地铁站点i到配送点j的距离长度，紧密中心性A{Q}_i为d_i的倒数；n为地铁网络中地铁站点和配送点数量的总和，其公式：d_i=\frac{\mathrm{1}}{n-\mathrm{1}}\sum _{j\ne i}{d}_{ij}。

卡兹中心性：卡兹中心性度量的是通过一条路径可以连接的所有节点的数量^［21］，而远处节点的贡献会受到削减。卡兹中心性在地铁配送系统中表示为某一条地铁路线可以连接的所有的配送点，该地铁线远端连接的配送点贡献会逐渐削减。更高的卡兹中心性表示该地铁站点在路网中更具重要性，更加适合作为地铁物流配送枢纽。卡兹中心性（B{Q}_i）计算公式为：

B{Q}_i={\displaystyle \sum _{k=\mathrm{1}}^{\mathrm{\infty }}}{\displaystyle \sum _{i=\mathrm{1}}^B}{\displaystyle \sum _{j=\mathrm{1}}^A}{\alpha }^k{\left(A^k\right)}_{ji}（16）

式中：k为地铁站点节点i的k\mathrm{⁃}hop的邻节点；A^k为邻接矩阵；A为地铁网络中地铁站的数量；B为地铁网络中配送点的数量。

距离指标：即地铁站点与配送点最短距离的倒数。距离指标（C{Q}_i）计算公式如下：

C{Q}_i=\frac{\mathrm{1}}{d_{i,j}}（17）

式中：d_{i,j}为配送点j到地铁站点i的最短距离。

度中心性：在地铁网络中，地铁物流配送枢纽的度中心性表示为该地铁物流配送枢纽与除该地铁物流配送枢纽外地铁站点之间的路径连接数^［22］。D{Q}_i值越高，表示该地铁物流配送枢纽i与其他地铁站点的联系越紧密，也表明该地铁物流配送枢纽相较于D{Q}_i值越低的地铁物流配送枢纽拥有越强的交通运输能力。度中心性（D{Q}_i）计算公式如下：

D{Q}_i=\frac{K_i}{A-\mathrm{1}}（18）

式中：K_i为地铁网络节点的度。

2.4.2　地铁站点对配送点的重要性指标

距离指标：距离越长，货物的运输成本越高，选择离地铁物流配送枢纽越近的配送点，则货车运输成本越少。距离指标（A{W}_j）计算公式如下：

A{W}_j=\frac{\mathrm{1}}{d_{i,j}}（19）

式中：d_{i,j}为地铁物流配送枢纽i到配送点j的最短距离。

2.4.3　地铁站点与配送点的路由优先度计算

由于所有偏好指标度量和权重不同，为了方便计算，需要对指标进行归一化处理并加权求和。假设配送点对地铁站点的重要性指标权重矩阵为{\mathit{P}}_Q=\left[P_{\mathrm{1}}{P}_{\mathrm{2}}{P}_{\mathrm{3}}{P}_{\mathrm{4}}\right]，则地铁物流配送枢纽i对配送点j的路由优先度{\alpha }_{ij}和配送点j对地铁物流配送枢纽i的路由优先度{\beta }_{ji}的计算公式如下：

{\alpha }_{ij}=A{W}_j（20）

{\beta }_{ji}=\frac{{\displaystyle \sum _{Q=\mathrm{1}}^{\mathrm{4}}}{\mathit{P}}_Q\frac{l{Q}_i}{\sum _l\sum _{i\in V}l{Q}_i}}{\mathrm{4}},l\in \mathit{Z}=\left[W_A,W_B,W_C,W_D\right]（21）

式中：z为地铁网络中所有地铁站点的集合；W_A\mathrm{、}{W}_B\mathrm{、}{W}_C\mathrm{、}{W}_D为评价地铁网络节点的重要性的4个重要性指标的集合。

2.5　地铁站点重要性指标权重计算

虽然紧密中心性、卡兹中心性、度中心性和距离指标都可以被用来表示地铁网络中的地铁站点重要性，但这些指标都只单一反应了地铁站点的某一方面。为了更加全面地评估地铁站点的重要性，本文使用多目标决策方法（Multi objective optimization on the basis of ratio analysis，MOORA）^［23］。MOORA是一种多目标优化方法，常被用于系统工程中解决多个决策目标求解问题。通过构建备选对象的决策矩阵，按照一定的优先逻辑帮助决策者选出最合适的对象。本文使用RatioMOORA来结合这4个指标对其重要性进行排序，计算公式如下：

N{x}_{ij}=\frac{x_{ij}}{\sqrt[]{{\displaystyle \sum _{j=\mathrm{1}}^m}{x}_{ij}^{\mathrm{2}}}}（22）

在研究的地铁物流运输系统，x_{ij}为第j个重要性指标对i节点的响应。同时，由于上述的4个重要性指标都代表不同特征，有必要通过分配反映其重要性的权重使这些指标更好反映不同地铁站点在地铁网络中的特性。本文使用层次分析法（AHP）^［24］的三尺度方法对4个重要性指标进行两两比较。使用由本文上述提出的4个重要性指标及地铁站节点相关信息构建层次评价模型以及判断矩阵。通过计算判断矩阵最大特征值及对应的特征值确定各重要性指标权重，并进行一致性检验，最后将各层次权重向量合成得到满足一致性约束条件的权重。计算公式如下：

w_i=\frac{\mathrm{1}}{n}{\displaystyle \sum _{j=\mathrm{1}}^n}\frac{a_{ij}}{{\displaystyle \sum _{k=\mathrm{1}}^n}{a}_{kj}},i=\mathrm{1,2},\dots ,n（23）

{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\frac{\mathrm{1}}{n}{\displaystyle \sum _{i=\mathrm{1}}^n}\frac{(A{W}_i)}{W_i}（24）

（25）

3 实例分析

3.1　实例背景

截至2024年，上海地铁共有运营线路线20条线，由于地形或建设时间等因素影响，部分地铁线路不便被改造为地铁物流配送枢纽，本文采用除去浦江线、地铁磁悬浮和15号地铁线路外的17条上海地铁路线进行研究。地铁全天运营服务时间为5：30~00：00，在工作日（周一至周五）上海地铁交通首末班车时间分别为5：30、22：30。非高峰时间段为9：00~17：00、19：00~23：45，列车在非高峰时段的运行间隔平均为5 min，地铁平均行驶速度为60 km·h^-1，货车平均行驶速度为20km·h^-1，货车最大载货量为1 t，货物转运时间为5 min，客户服务时间为2 min。货车早到惩罚系数为5，货车晚到惩罚系数为10，每件货物按10 kg计算。

3.2　实例验证

3.2.1　上海市地铁网络路由优先度计算

在配送点计算对地铁站点的重要性指标计算中，以上海地铁网络中17条地铁路线作为地铁网络基础，总计447个地铁站点的路由优先度。使用RatioMOORA模型对地铁站点进行排序。l{x}_i(i=\mathrm{1,2},\dots ,\mathrm{447};l=A,B,C,D)表示第i个站点的第l个重要性指标，然后使用AHP方法的三尺度法确定重要性指标权重矩阵的权重PQ=\left[W_A,W_B,W_C,W_D\right]=\left[\mathrm{0.3,0.4,0.2,0.1}\right]，经过加权求和计算得出上海市17条地铁线共计447个地铁站点的路由优先度由高到低排序如表3所示，当中的路由优先度为归一化前数据。其中路由优先度最高的3个地铁站分制为曹杨路、金沙江路、静安寺庙。路由优先度最低的3个地铁站分别为金海湖、东方绿舟、奉贤新城。由表3可以看出，路由优先度最高的曹杨路地铁站连通的地铁的地铁路线最多，同时路由优先度最低的3个地铁站所连通的地铁路线仅有单一连通地铁路线。

上海市地铁网络各地铁站节点路由优先度分布如图4所示。由图可以看出，上海市地铁站节点路由优先度分布特征明显。

本文研究的上海市17条地铁路线路由优先度分布如图5所示。其中5、16、17号线的地铁站点与上海市中心地标的距离随着地铁站点序号增加而逐渐增加，同时路由优先度随即减小。由图可以看出，上海市各条地铁路线趋于中段的地铁节点路由优先度普遍高于分布于地铁路线两端的节点。由于5、16、17号线3条地铁线中，5、16号线仅有一个地铁站节点为中转站且只能连通额外一条路线，17号线无地铁物流配送枢纽，由图可以看出该3条地铁路线地铁站节点的路由优先度要普通低于其它地铁路线。

本文选取上海市地铁网络中路由优先度前10%的地铁站节点改造为地铁物流配送枢纽，如表5所示。

3.2.2　结合改进模块化A^*寻优算法多级求解计算结果

本文将从《上海经济和社会发展统计年鉴》中获得的居民社区定义为上海市内物流运输的需求位置，使用谷歌地图获取对应住宅社区的经纬度，在该范围内随机生成20个配送订单并对应生成时间窗，物流订单配送信息如表5所示。

结合案例数据并通过结合本文提出的改进模块化A^*寻优算法，对地铁货车物流运输方案进行计算。改进模块化A*寻优算法参数设置如表6所示，迭代过程如图6所示。

根据本文计算结果，对物流运输距离，订单完成时间，算法运行时间3个关键指标进行分析。为验证本文提出的模块化A^*算法的效果，本文使用7种不同的优化算法结合本文提出的模块化A^*算法进行实验验证。

（1）物流运输距离。在上海市地铁网络运输背景下，结合本文提出的模块化A^*寻优算法显著减少了货车地铁的物流运输距离。结合该算法前后各优化算法方案物流运输距离对比如表7所示。最短物流运输距离平均减少13.21%。

（2）订单完成时间。结合本文提出的改进模块化A^*寻优算法通过优化最优路径并依靠多级求解器优化订单顺序。在上海地铁网络复杂的交通网络情况下，显著减少了订单完成时间。结合模块化A*算法前后各算法方案订单完成时间对比如表8所示。订单完成时间平均减少11.73%。

（3）算法运行时间。模块化A^*寻优算法通过启发式搜索策略优先拓展路径代价更小的节点，显著减少了原优化算法的运行时间。结合模块化A^*算法前后各算法运行时间对比如表9所示。算法运行时间平均减少24.79%。

从最终结果来看（详见表7~9），结合本文提出的改进模块化A^*寻优算法后的优化算法在路径搜索、订单分配调度的全局任务优化上表现最佳。目前适用于地铁物流运输问题的优化算法经该算法优化后在物流运输距离、订单完成时间、算法运行时间3个关键指标效果均有显著提升，性能提升比率分别为13.21%、11.73%、24.79%。这表明在此次实验中，本文提出的改进模块化A*寻优算法具有更好的优化效果，且如图6所示，说明本文提出的算法同时具备良好的收敛性。由上述分析可以见得，本文提出的改进模块化A^*寻优算法在处理复杂地铁物流运输问题时更具优势。

4 结束语

为提高物流的及时性，降低企业的配送成本，本文研究的地铁货车快递联运路径寻优多级求解优化模型，针对地铁物流配送枢纽选址、物流配送路径及物流订单配送调度三方面做出优化，并对比分析各算法效果。首先，为减少模型规模提高运输效率及符合实际情况，本文从大量的地铁站点中选出候选地铁物流配送枢纽。同时，本文根据复杂交通网络节点理论选择设计评价指标，并根据多目标决策方法结合层次分析法对地铁站点的重要性进行评价，然后对地铁站点的重要性进行排序以及对地铁物流配送枢纽进行选址。其次，提出一种改进模块化A^*寻优算法适用于当前使用在地铁货车物流运输问题中的绝大部分优化算法。该算法融合启发式搜索策略和优化算法的特性，结合该算法的优化算法，收敛速度全局搜索能力显著提升。最后，本文使用改进模块化A*寻优算法结合多种算法进行对比分析。结果表明：目前多种使用于地铁物流运输系统的算法经过该算法优化后，物流运输距离、订单完成时间、算法运行时间三个关键指标效果均有显著提升。

参考文献

[1] Chen Z L, Chen J Y, Liu H, et al. Present status and development trends of underground space in Chinese cities: Evaluation and analysis[J]. Tunnelling and Underground Space Technology, 2018, 71: 253-270.

[2] Dampier A, Marinov M. A study of the feasibility and potential implementation of metro-based freight transportation in newcastle upon tyne[J]. Urban Rail Transit, 2015, 1(3): 164-182.

[3] 钱七虎. 建设特大城市地下快速路和地下物流系统:解决中国特大城市交通问题的新思路[J]. 科技导报,2004(4): 3-6.

[4] Qian Qi-hu. Construction of underground expressway and underground logistics system in megacities: a new approach to solving traffic problems in China's megacities[J]. Science & Technology Review, 2004(4):3-6.

[5] He K T, Shao J P, Liu Y B, et al. Conceptual design of rail transit based urban logistics delivery system[C]∥6th IEEE International Conference on Industrial Informatics, IEEE, 2008: 221-226.

[6] Kikuta J, Ito T, Tomiyama I, et al. New subway-integrated city logistics szystem[J]. Procedia-Social and BehavioralSciences, 2012, 39: 476-489.

[7] 周芳汀, 张锦, 周国华. 带时间窗的地铁配送网络路径优化问题[J]. 交通运输系统工程与信息, 2018, 18(5): 88-94.

[8] Zhou Fang-ding, Zhang Jin, Zhou Guo-hua. Subway-based distribution network routing optimization problem with time windows[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(5): 88-94.

[9] 聂闻聪, 楚龙娟, 向楠, 等. 城市轨道物流配送模式研究及节点选址优化[J]. 地下空间与工程学报, 2023, 19 (): 17-25.

[10] Nie Wen-chong, Chu Long-juan, Xiang Nan, et al. Researchon distribution model of urban rail logistics and optimization of node location[J]. Chinese Journal of Underground Space and Enginee, 2023, 19(Sup.1):17-25.

[11] 舒达, 梁承姬, 王钰, 等. 基于双边匹配的城市地铁多级配送选址-路径研究[J]. 计算机工程, 2025, 51(9): 1-12.

[12] Shu Da, Liang Cheng-ji, Wang Yu, et al. Research on Multi-stage distribution site-routing of urban Subway based on bilateral matching[J]. Computer engineering, 2025, 51(9): 1-12.

[13] Taniguchi E. City logistics for sustainable and liveable cities[J]. Green logistics and transportation: A sustainable supply chain perspective, 2015: 49-60.

[14] Diziain D, Taniguchi E, Dablanc L. Urban logistics by rail and waterways in France and Japan[J]. Procedia-Social and Behavioral Sciences, 2014, 125: 159-170.

[15] 余欣鹏, 余子扬, 崔歡鑫, 等. 基于优化算法的新能源汽车充电站选址研究[J]. 汽车测试报告, 2024(6): 71-73.

[16] Yu Xin-peng, Yu Zi-yang, Cui Huan-xin,et al. Research on charging station location for new energy vehicles based on optimization algorithm[J]. Auto Testing Report,2024(6):71-73.

[17] 丁昱杰, 张凯, 张龄允, 等. 基于遗传灰狼算法的员工通勤合乘路径优化[J]. 现代信息科技, 2023, 7 (2): 112-115.

[18] Ding Yu-jie, Zhang Kai, Zhang Ling-yun,et al.Employee commute carpooling route optimization based on genetic grey wolf algorithm[J]. Modern Information Technology, 2023, 7(2): 112-115.

[19] 潘寒川, 戚博洋, 胡华, 等. 考虑司机偏好的城市轨道交通混合乘务轮转模型[J]. 交通运输系统工程与信息, 2023, 23(5): 258-267.

[20] Pan Han-chuan, Qi Bo-yang, Hu Hua,et al. Preference-oriented task-type-mixed crew rostering optimization model for urban railway transit[J]. Journal of Transportation Systems Engineering and Information Technology,2023,23(5):258-267.

[21] 任睿, 胡万杰, 董建军, 等. 轴辐式城市地铁-货运系统网络布局优化[J]. 系统仿真学报, 2021, 33 (7): 1699-1712.

[22] Ren Rui, Hu Wan-jie, Dong Jian-jun, et al. Optimization of urban metro-based underground logistics system network with hub-and-spoke layout[J]. Journal of System Simulation, 2021, 33(7): 1699-1712.

[23] 程国柱, 吕岩峰, 冯天军. 地铁站周边常规公交换乘站点布局多目标优化模型[J/OL]. [2024-11-14].

[24] 刘康琳, 张泽宇, 蒋婧雯, 等.基于分布鲁棒优化的无人机配送设施选址分配问题[J/OL].吉林大学学报: 工学版[2024-11-14].

[25] 赵宏伟, 刘宇琦, 董立岩, 等. 智能交通混合动态路径优化算法[J]. 吉林大学学报: 工学版,2018, 48(4):1214-1223.

[26] Zhao Hong-wei, Liu Yu-qi, Dong Li-yan, et al. Dynamic route optimization algorithm based on hybrid in ITS[J]. Journal of Jilin University(Engineering and Technology Edition),2018,48(4):1214-1223.

[27] 王玉, 申铉京, 周昱洲, 等. 一种求解交通网络中最短路径问题的人工蜂群算法[J]. 吉林大学学报:理学版, 2021, 59(5): 1144-1150.

[28] Wang Yu, Shen Xuan-jing, Zhou Yu-zhou, et al. An artificial bee colony algorithm for solving the shortest path problem in traffic network[J]. Journal of Jilin University(Science Edition), 2021, 59(5): 1144-1150.

[29] Zhao L J, Li H Y, Li M C, et al. Location selection of intra-city distribution hubs in the metro-integrated logistics system[J]. Tunnelling and Underground Space Technology, 2018, 80: 246-256.

[30] Zhang J L, Yu L. Degree centrality, betweenness centrality, and closeness centrality in social network[C]∥2nd international conference on modelling, simulation and applied mathematics (MSAM2017). Atlantis press, 2017: 300-303.

[31] Zhang Y P, Bao Y Y, Zhao S, et al. Identifying node importance by combining betweenness centrality and katz centrality[C]∥International Conference on Cloud Computing and Big Data. IEEE, 2015: 354-357.

[32] Maharani W, Gozali A A. Degree centrality and eigenvector centrality in twitter[C]∥8th international conference on telecommunication systems services and applications, IEEE, 2014: 1-5.

[33] Brauers W K, Zavadskas E K. The MOORA method and its application to privatization in a transition economy[J]. Control and cybernetics, 2006, 35(2): 445-469.

[34] Ho W. Integrated analytic hierarchy process and its applications-A literature review[J]. European Journal of operational research, 2008, 186(1): 211-228.

[35] Pardalos P M, Mavridou T D. Simulated Annealing[M].Encyclopedia of Optimization. Cham: Springer International Publishing, 2024.

[36] Ye Y T, Guo J H, Yan L X. A metro freight plan for mixed passenger and freight transportation[J]. Journal of Advanced Transportation, 2022(1): 6602387.

基金资助

吉林省发改委基本建设资金项目(2022C043-2)