Processing math: 100%
高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

探索快递物流网的离散数学模型

张明军 张玉婧 杨见青 姚兵

张明军, 张玉婧, 杨见青, 姚兵. 探索快递物流网的离散数学模型[J]. 电子与信息学报, 2025, 47(3): 769-779. doi: 10.11999/JEIT240767
引用本文: 张明军, 张玉婧, 杨见青, 姚兵. 探索快递物流网的离散数学模型[J]. 电子与信息学报, 2025, 47(3): 769-779. doi: 10.11999/JEIT240767
Jin Wen-guang, Wang Jin-ming. Study on Chaotic Signal Processing with Symbol Dynamics[J]. Journal of Electronics & Information Technology, 2006, 28(10): 1774-1777.
Citation: ZHANG Mingjun, ZHANG Yujing, YANG Jianqing, YAO Bing. Exploring The Discrete Mathematical Models of Express Logistics Networks[J]. Journal of Electronics & Information Technology, 2025, 47(3): 769-779. doi: 10.11999/JEIT240767

探索快递物流网的离散数学模型

doi: 10.11999/JEIT240767
基金项目: 国家自然科学基金(61363060, 61662066),兰州财经大学科研资助项目(Lzufe2022B-002),甘肃省自然科学基金(23JRRA1785, 25JRRA232)
详细信息
    作者简介:

    张明军:男,教授,研究方向为图论及其应用,物联网和供应链,网络信息安全等

    张玉婧:女,硕士生,研究方向为物联网和供应链

    杨见青:女,硕士生,研究方向为物联网和供应链

    姚兵:男,教授,研究方向为拓扑编码及其应用,图格和图群,网络信息安全

    通讯作者:

    张玉婧 zyjdm@qq.com

  • 中图分类号: TN911.7; O157.6

Exploring The Discrete Mathematical Models of Express Logistics Networks

Funds: The National Natural Science Foundation of China (61363060, 61662066), Lanzhou University of Finance and Economics Research Funding Programme (Lzufe2022B-002), The Natural Science Foundation of Gansu Province (23JRRA1785, 25JRRA232)
  • 摘要: 针对快递物流网络,该文研究:(1) 构建全新的快递物流网的离散数学模型 (又称拓扑模型);(2) 根据理论基础从图论学科的角度对快递物流网络拓扑模型进行定性分析,通过数学模型法结合参数统计、优化算法等数学手段对模型进行定量分析。对拓扑模型中的边赋予路长权重,并为快递物流网拓扑模型设计了新的优化算法(集散算法、控制集算法、预先指定子图算法);(3) 以兰州市城关区主城区作为快递物流网拓扑模型的应用实例,实施了相应的优化算法。同时针对模型计算面临的复杂度等困难提出了解决办法,为进一步完善、优化快递物流网络提供了一定参考。
  • 图  1  一个具有权重的区域道路图G

    图  2  解释第k个集散过程及其算法模块

    图  3  兰州市城关区道路图(摘自高德地图)

    图  4  基于图G的两个最小权重森林

    图  5  基于图G的最小权重支撑树

    1  无约束快递集散 CD-算法

     输入:集装C(k)={Ak,1,Ak,2,,Ak,n(k)},其中Ak,j是货物,且有Ak,jAk,t, jt
     输出:分散D(k+1)
     在一般的快递物流网中,不会为一个货物进行 式(1)的无约束快递集散,而是进行下面的多个快递货物的集装和分散:
     步骤1 集装C(k)被分散,形成分散D(k)
      (1) 分散集装C(k)的货物,其中有货物EDk={Aki,1,Aki,2,,Aki,a(ki)}被发送到客户手中;
      (2) 又有新的货物NBk={Bk,1,Bk,2,,Bk,m(k)}补充进来。
     步骤2 形成集装C(k+1):将集合(C(k)EDk)NBk中的货物组装成小集装模块Ck+1,1,Ck+1,2,,Ck+1,n(k+1),其中
     n(k+1)n(k)a(ki)+m(k),使得集装C(k+1)由这n(k+1)个集装模块构成。
     步骤3 由集装C(k+1)返回分散D(k+1)
    下载: 导出CSV

    2  最小权重路控制集算法

     输入:权重路拓扑模型 Gweight(t)
     输出:权重路拓扑模型 Gweight(t) 的一个最小权重路控制集
     步骤1 选择节点 u1V(Gweight(t)) 以及与节点 u1 相邻的节点 w1Nei(u1),使得路 P(u1,w1) 的权重之和为最小。得到节点集
     合: U1{u1}, W1{w1}, V1=V(Gweight(t))(U1W1)
     步骤2 选择节点 ukVk 以及与节点 uk 相邻的节点 wkNei(uk),使得路 P(uk,wk) 的权重之和是最小的,且 wkUk1。得到
     节点集合:UkUk1{uk}, WkWk1{wk}, Vk=V(Gweight(t))(UkWk)。转到步骤3。
     步骤3 如果有节点 xVk 使得路 P(x,y) (yNei(x)) 的权重之和达到最小值,但是 yWk,则令 WkWk1{x},以及
     UkUk1{y}, Vk=V(Gweight(t))(UkWk)。转到步骤4。
     步骤4 如果有 |Vk|2,转到步骤2。否则,转到步骤5。
     步骤5 如果 Vk={z},且有节点zNei(z),使得路 P(z,z) 的权重之和达到最小。当节点 zUk,则令 Wk+1Wk{z},
     Uk+1Uk;当节点 zWk,则令 Uk+1Uk{z}, Wk+1Wk, Vk+1=V(Gweight(t))(Uk+1Wk+1)=。转到步骤6。
     步骤6 返回权重路拓扑模型 Gweight(t) 的最小权重路控制集 Wk+1
    下载: 导出CSV

    3  最小权重路 m-控制集算法 (m≥2)

     输入:在最小权重路控制集算法2中,最小权重路控制集 Wk+1 导出权重路拓扑图H1=G[Wk+1],它是权重路拓扑模型 Gweight(t) 的一
     个子图
     输出:权重路拓扑图 Hm 的最小权重路 m-控制集算法 (m≥2)
     步骤1 对图H1=G[Wk+1]运用最小权重路控制集算法,得到权重路拓扑图H1的一个最小权重路控制集S1,它是权重路拓扑模型
     Gweight(t)的一个最小权重路 2-控制集,使得权重路拓扑模型Gweight(t)的任何一个节点a满足:aS1,或者有节点bS1,使得路
     P(a,b)的权重之和达到最小值,且有边集|E(P(a,b))|2
     步骤2 节点集S1导出权重路拓扑图H2=G[S1]。实施最小权重路控制集算法2,得到权重路拓扑图H1的一个最小权重路控制集S2,它
     是权重路拓扑模型Gweight(t)的一个最小权重路 3-控制集。
     步骤(m1) 节点集Sm2 导出权重路拓扑图Hm1=G[Sm2]。实施最小权重路控制集算法2后,得到权重路拓扑图Hm的一个最
     小权重路控制集Sm1,它是权重路拓扑模型Gweight(t)的一个最小权重路m-控制集。
    下载: 导出CSV

    4  预先指定子图控制算法

     输入:连通边赋权图G(t),指定连通图G(t)的一个真子图H(t)
     输出:连通图G(t)的一个子图L(t),使得H(t)L(t),每个节点uV(L(t))到真子图H(t)的距离最小
     步骤1 选择最大的节点子集合V1V=V(G(t))V(H(t)),使对每一个节点 xV1,有节点yV(H(t))x 相邻,并且边
     xyE=E(G)E(H(t)) 的权重最小,V1叫做 1-层节点集。做:E1E(H(t)), E2(E1E(V1,V(H(t))),其中边集合
     E(V1,V(H(t)))中的边xy权重最小,且满足xV1yV(H(t))
     步骤2 选择最大的节点子集合V2VV1,使对每一个节点xV2,有节点yVV1x相邻,并且边xyEE(V1,V(H(t)))
     权重最小,V2叫做 2-层节点集。做:E3E2E(V2,V1),其中边集合E(V2,V1)中的边xy权重最小,且满足xV1yV2
     步骤3 如果k-层节点集Vk=Vk1i=1Vi,转到步骤2,否则转到步骤4。
     步骤4 如果k-层节点集Vk=Vk1i=1Vi=,做:V(L(t))V(G(t)), E(L(t))E2E(V2,V1)E(V3,V2)E(Vk1,Vk2)
     到步骤5
     步骤5 返回连通图G(t)的子图L(t),每个节点 uV(L(t))到真子图H(t)的距离最小。
    下载: 导出CSV

    表  1  相关算法比较和评估

    算法 核心思想 性能比较及适用范围
    最小权重路
    控制集算法
    通过贪心选择和迭代构建的方式,逐步逼近最优解,即在满足控制集条件下使权重之和最小。 计算过程较为直观,其时间、空间复杂度与图的规模和迭代次数有关,可能在大规模复杂网络中效率较低。适用于规模较小或结构简单、连通性较强的网络。
    最小权重路
    m-控制集
    (m≥2)算法
    通过基于子图的迭代操作,利用算法2作为基础步骤,逐步构建出权重路拓扑模型的最小权重m-控制集。这种方法通过分解问题为多个子问题来解决寻找特定阶数最小权重控制集的复杂问题。 在计算上比最小权重路控制集算法更复杂,但通过多次迭代和基于子图的操作,其求解精度相对算法 2会更高。适用于多层网络的层次化资源管理等,特别是当问题的求解依赖于前一阶控制集的结果,并且需要不断细化和扩展控制集以满足更复杂的条件时。
    预先指定子图
    控制算法
    算法通过层次选择节点集逐步找到最优路径。通过最大化节点集和最小化边权重来保证每个节点都与指定的真子图保持最小距离。 在优化子图和控制集的过程中,能更好地处理特定拓扑结构,计算复杂度也是较高的。适合处理较为特殊的拓扑结构,如环型、树型网等,尤其适合实际应用中先给定子图的情况。
    下载: 导出CSV
  • [1] 王咏仪. 考虑拥堵的轴辐式快递网络的布局优化与资源均衡研究[J]. 上海管理科学, 2024, 46(1): 72–76,95. doi: 10.3969/j.issn.1005-9679.2024.01.014.

    WANG Yongyi. Layout optimization and resource balancing when considering congestion on the Hub-and-Spoke express network[J]. Shanghai Management Science, 2024, 46(1): 72–76,95. doi: 10.3969/j.issn.1005-9679.2024.01.014.
    [2] 常兰, 刘湃. 碳交易视角下绿色快递多式联运网络优化[J]. 重庆电力高等专科学校学报, 2023, 28(6): 37–43. doi: 10.3969/j.issn.1008-8032.2023.06.008.

    CHANG Lan and LIU Pai. A study on the network optimization of the multimodal transportation of green delivery from the perspective of carbon trading[J]. Journal of Chongqing Electric Power College, 2023, 28(6): 37–43. doi: 10.3969/j.issn.1008-8032.2023.06.008.
    [3] 吴旗韬, 李苑庭, 吴海玲, 等. 基于关键节点积极效应模型的快递物流网络点集挖掘[J]. 复杂系统与复杂性科学, 2024, 21(4): 28–33. doi: 10.13306/j.1672-3813.2024.04.005.

    WU Qitao, LI Yuanting, WU Hailing, et al. Nodes-set mining of express logistics network based on the key player problem-positive model[J]. Complex Systems and Complexity Science, 2024, 21(4): 28–33. doi: 10.13306/j.1672-3813.2024.04.005.
    [4] 李悦, 秦威. 基于混合轴辐式网络的快递运输路径再设计[J]. 工业工程, 2023, 26(6): 93–100. doi: 10.3969/j.issn.1007-7375.2023.06.010.

    LI Yue and QIN Wei. Re-design of express transportation route based on hybrid Hub-and-Spoke network[J]. Industrial Engineering Journal, 2023, 26(6): 93–100. doi: 10.3969/j.issn.1007-7375.2023.06.010.
    [5] 张建军, 王嘉铭, 王天浩, 等. 低碳情景下的复合轴辐式快递网络规划[J]. 同济大学学报(自然科学版), 2023, 51(2): 288–294. doi: 10.11908/j.issn.0253-374x.21403.

    ZHANG Jianjun, WANG Jiaming, WANG Tianhao, et al. Multi-layered multi-service-leveled hybrid hub-spoke network design in low-carbon scenarios[J]. Journal of Tongji University (Natural Science), 2023, 51(2): 288–294. doi: 10.11908/j.issn.0253-374x.21403.
    [6] 杨从平, 郑世珏, 党永杰, 等. 基于连接成本的快递网络拥塞控制[J]. 中国管理科学, 2017, 25(4): 143–151. doi: 10.16381/j.cnki.issn1003-207x.2017.04.017.

    YANG Congping, ZHENG Shijue, DANG Yongjie, et al. Congestion control of express delivery network based on connection cost[J]. Chinese Journal of Management Science, 2017, 25(4): 143–151. doi: 10.16381/j.cnki.issn1003-207x.2017.04.017.
    [7] 杨从平, 郑世珏, 党永杰, 等. 基于配送时效和连接成本的快递网络优化[J]. 系统工程理论与实践, 2016, 36(8): 1983–1992. doi: 10.12011/1000-6788(2016)08-1983-10.

    YANG Congping, ZHENG Shijue, DANG Yongjie, et al. Optimization of express delivery network based on delivery timeliness and connection cost[J]. Systems Engineering-Theory & Practice, 2016, 36(8): 1983–1992. doi: 10.12011/1000-6788(2016)08-1983-10.
    [8] 赵晋, 张建军, 严蔡华. 允许直达的混合轴辐式快递网络规划模型与算法研究[J]. 中国管理科学, 2016, 24(11): 58–65. doi: 10.16381/j.cnki.issn1003-207x.2016.11.007.

    ZHAO Jin, ZHANG Jianjun, and YAN Caihua. Research on hybrid hub-spoke express network decision with Point-to-point direct shipment[J]. Chinese Journal of Management Science, 2016, 24(11): 58–65. doi: 10.16381/j.cnki.issn1003-207x.2016.11.007.
    [9] 郑长江, 胡欢, 杜牧青. 考虑枢纽失效的多式联运快递网络结构设计[J]. 吉林大学学报(工学版), 2023, 53(8): 2304–2311. doi: 10.13229/j.cnki.jdxbgxb.20211128.

    ZHENG Changjiang, HU Huan, and DU Muqing. Design of multimodal express delivery network structure considering hub failure[J]. Journal of Jilin University (Engineering and Technology Edition), 2023, 53(8): 2304–2311. doi: 10.13229/j.cnki.jdxbgxb.20211128.
    [10] 李苑君, 吴旗韬, 吴康敏, 等. “流空间”视角的电子商务快递物流网络结构研究——以珠三角城市群为例[J]. 地域研究与开发, 2021, 40(2): 20–26. doi: 10.3969/j.issn.1003-2363.2021.02.004.

    LI Yuanjun, WU Qitao, WU Kangmin, et al. Structure of E-commerce express logistics network from the perspective of flow space: Take the Pearl River Delta urban agglomeration as example[J]. Areal Research and Development, 2021, 40(2): 20–26. doi: 10.3969/j.issn.1003-2363.2021.02.004.
    [11] 牟能冶, 康秋萍, 贾程方. 突发事件影响下的城市快递网络脆弱性评估[J]. 中国安全科学学报, 2020, 30(12): 125–132. doi: 10.16265/j.cnki.issn1003-3033.2020.12.018.

    MU Nengye, KANG Qiuping, and JIA Chengfang. Vulnerability assessment of urban express networks under influence of emergencies[J]. China Safety Science Journal, 2020, 30(12): 125–132. doi: 10.16265/j.cnki.issn1003-3033.2020.12.018.
    [12] 牟能冶, 康秋萍. 基于节点重要度网络结构熵的城市快递网络抗毁性测度[J]. 综合运输, 2020, 42(3): 108–113.

    MU Nengye and KANG Qiuping. Invulnerability measurement of urban express network based on node importance network structure entropy[J]. China Transportation Review, 2020, 42(3): 108–113.
    [13] 谢逢洁, 崔文田. 加权快递网络鲁棒性分析及优化[J]. 系统工程理论与实践, 2016, 36(9): 2391–2399. doi: 10.12011/1000-6788(2016)09-2391-09.

    XIE Fengjie and CUI Wentian. Analyzing and optimizing the robustness of weighted express networks[J]. Systems Engineering-Theory & Practice, 2016, 36(9): 2391–2399. doi: 10.12011/1000-6788(2016)09-2391-09.
    [14] Bondy A and Murty U S R. Graph Theory[M]. London, UK: Springer, 2008.
    [15] Gallian J A. A dynamic survey of graph labeling[J]. Electronic Journal of Combinatorics, 2022, 6(25): 4–623.
    [16] 卜月华, 王维凡, 吕新忠. 图论及其应用[M]. 2版. 南京: 东南大学出版社, 2015.

    BU Yuehua, WANG Weifan, and LV Xinzhong. Graph Theory With Applications[M]. Nanjing: Southeast University Press, 2015.
    [17] YAO Bing and WANG Hongyu. Recent colorings and labelings in topological coding[J]. arXiv: 2106.15254, 2021. doi: 10.48550/arXiv.2106.15254.
    [18] 兰州市统计局. 《兰州统计年鉴》2023年[EB/OL]. https://tjj.lanzhou.gov.cn/art/2024/1/31/art_4866_1315620.html, 2024.

    Lanzhou Municipal Bureau of Statistics. Lanzhou Statistical Yearbook 2023[EB/OL]. https://tjj.lanzhou.gov.cn/art/2024/1/31/art_4866_1315620.html, 2024.
    [19] 甘肃地方史志网. 《兰州市城关区年鉴2024》[EB/OL]. 兰州市城关区年鉴. http: //www. gsdfszw. org. cn/gsxnj/lzs_297/lzscgqnj123/202410/P020241024621772314554. pdf, 2024. Gansu Local History Network. Yearbook of Chengguan District, Lanzhou City 2024[EB/OL]. 兰州市城关区年鉴. http://www.gsdfszw.org.cn/gsxnj/lzs_297/lzscgqnj123/202410/P020241024621772314554.pdf, 2024.
    [20] 王晓敏, 苏静, 姚兵. 基于格思想的图结构相似问题的算法[J]. 计算机科学, 2021, 48(S1): 543–551. doi: 10.11896/jsjkx.201100167.

    WANG Xiaomin, SU Jing, and YAO Bing. Algorithms based on lattice thought for graph structure similarity[J]. Computer Science, 2021, 48(S1): 543–551. doi: 10.11896/jsjkx.201100167.
  • 加载中
图(5) / 表(5)
计量
  • 文章访问数:  174
  • HTML全文浏览量:  101
  • PDF下载量:  33
  • 被引次数: 0
出版历程
  • 收稿日期:  2024-09-09
  • 修回日期:  2025-02-19
  • 网络出版日期:  2025-03-05
  • 刊出日期:  2025-03-01

目录

    /

    返回文章
    返回