在动态和随机环境下进行的多目标、多属性车队规模决策:一种数据驱动的方法

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》:Multi-objective, multi-attribute fleet sizing in a dynamic and stochastic environment: A data-driven approach

【字体: 大 中 小 】 时间:2026年01月02日 来源:TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 8.8

编辑推荐:

  位置-路径问题与鲁棒优化在灾害救援中的应用研究,提出两阶段自适应鲁棒优化模型处理供应中断与需求波动不确定性,开发混合精确算法并通过数值与案例验证其有效性。

  
杨永健|李成龙|王杜娟|尹云强|程T.C.E.
西南财经大学管理科学与工程学院,中国成都,611731

摘要

本文将人道主义运营管理中的两个关键组成部分——设施选址问题和路线问题——整合为选址-路线问题。鉴于灾害具有极高的不确定性,本研究重点关注供应端的不确定性(如救援设施的中断概率)和接收端的不确定性(包括受影响区域的需求波动以及接收救援物资的截止日期)。为了制定一个能够减轻潜在中断的可靠选址方案,我们构建了一个两阶段自适应鲁棒优化模型。该模型需要确定在一组灾害情景下的选址、分配和路线计划。我们开发了一种结合了列生成与约束生成、整数Benders分解和分支定价算法的混合精确算法,并采用了先进的加速策略来改进求解过程。通过使用随机生成的数据集进行的全面数值研究评估了该算法的性能,证明了其优于CPLEX求解器和不使用列生成与约束生成的算法。

引言

近年来,自然灾害和人为灾害的发生频率显著增加,导致基础设施遭受严重破坏并造成大量人员伤亡。根据EM-DAT的数据,2000年至2024年间共发生了10,181起灾害,造成162.3万人死亡,约47亿人受到影响,经济损失达3.59万亿美元。鉴于这些灾难性的后果,制定高效有效的应急计划变得至关重要(Yin等人,2023a;Yang等人,2023b)。因此,人们对灾害运营管理的研究兴趣显著增加(Zobel等人,2016;Starr和Wassenhove,2014)。
设施选址问题(FLP)和车辆路线问题(VRP)是应急管理中的两个关键问题,合理制定选址计划和确定高效的运输路线可以显著提升应对能力。FLP侧重于战略层面的决策,以确定能够最小化物流成本的设施位置;而VRP则关注战术和运营层面的路线优化。最近的研究不再单独探讨这些问题,而是提倡采用一种称为选址-路线问题的综合方法(Nagy和Salhi,2007;Prodhon和Prins,2014)。
人道主义救援的一个关键特征是高度的不确定性,这严重影响了高效有效应急计划的制定。这些不确定性来源于多个方面,特别是供应端和接收端因素(Shen等人,2010)。供应端的不确定性包括可能导致重大财务损失的设施中断;例如,2000年飞利浦NM半导体工厂的火灾导致飞利浦直接收入损失4000万美元,爱立信移动业务间接损失23.4亿美元。同样,接收端的不确定性(如对救援物资需求的波动)也会严重阻碍救灾工作。一个显著的例子是2008年中国的汶川地震,由于对救援物资需求的突然激增,影响了超过4600万人。尽管现实世界中存在各种不确定性,但大多数研究往往一次只关注一种类型,限制了其在实际灾害情景中的适用性。
目前,一些学者采用了基于概率的模型来应对灾害环境中的不确定性(Qin等人,2013;Snyder和Daskin,2005;Snyder和Daskin,2006;Teimuory等人,2013;Xie等人,2015)。然而,由于历史数据不足或预测方法不可靠,获取准确的概率信息往往不切实际(An等人,2014;Snyder等人,2016)。因此,在不需要概率数据的情况下,鲁棒优化(RO)作为一种特别有效的管理不确定性的策略应运而生。这种方法通过预定义的集合来描述不确定性,从而产生在所有可能的干扰情景下仍然可行的解决方案。虽然单阶段(静态)RO方法被广泛使用,但它们可能导致过于保守和昂贵的决策。两阶段自适应RO允许在灾害发生后调整灾前决策,提供了一个更实用和灵活的框架,尽管计算复杂性有所增加(An和Zeng,2015;Zeng和Zhao,2013)。
基于上述观察,我们通过同时考虑供应端和接收端的不确定性来解决人道主义救援中的选址-路线问题(LRP)。为了处理这些不确定性,我们基于一组离散情景开发了两阶段自适应RO(TS-ARO)模型。在灾前阶段(也称为第一阶段),需要在缺乏关于未来不确定条件的精确信息的情况下确定救援设施的数量和位置。在灾后阶段(也称为第二阶段),一旦不确定性被揭示,模型会动态地将受影响区域分配给救援设施,确定资源分配,为同类型的无人机车队选择运输路线,并识别外包需求。为了解决该模型,我们引入了一种结合了多种先进加速策略的混合精确算法。我们研究的主要贡献如下:
  • •
    这是第一项在人道主义救援背景下研究LRP并考虑多种不确定性来源的研究。与以往的研究(例如Ahmadi-Javid和Seddighi,2013;Cheng等人,2018;Xie等人,2015;Zhang等人,2015)不同,我们的模型考虑了与设施中断概率、受影响区域的需求以及接收救援物资的截止日期相关的不确定性。我们使用离散情景集来模拟这些不确定性,并构建了一个TS-ARO模型以进行鲁棒决策。第一阶段涉及关于救援设施位置的战略决策,而第二阶段包括与资源分配和运输相关的战术和运营决策。我们的建模框架可以容纳额外的不确定性,并可以在第二阶段发生物理中断时扩展以包括新临时和永久设施的建立。
  • •
    我们提出了一种名为CCG-IBD-BP的精确算法,该算法结合了列生成与约束生成(CCG)、整数Benders分解(IBD)和分支定价(BP)算法。CCG算法将提出的模型分解为两个主要部分:一个放宽的主问题和一个对抗性分离子问题。前者仅包含有限数量的灾害情景,而后者旨在生成新的情景以挑战和改进当前解决方案。放宽的主问题使用集成BD和BP算法来解决,并通过几种先进的加速策略来加快求解过程。这种综合方法进一步将放宽的主问题分解为Benders主问题和几个Benders子问题,后者使用定制的BP算法来解决。
  • •
    基于随机生成的数据集进行的广泛数值研究证实了CCG-IBD-BP算法优于CPLEX求解器和不使用CCG的算法,并说明了关键模型参数对解决方案结构和性能指标的影响。此外,四川雅安市的案例研究进一步验证了TS-ARO模型的适用性,表明其在管理不确定性方面优于传统的确定性和随机优化模型。
  • 在引言之后,第2节介绍了相关工作的综述和该领域未解决的挑战。第3节介绍了正式的问题陈述并构建了TS-ARO模型。第4节详细描述了定制的CCG-BD-BP算法。第5节专门用于模型的实验评估和解决方案算法的评估。第6节通过一个实际案例研究提供了管理见解。最后,第7节总结了研究结果并展望了未来的研究方向。

    节选内容

    文献综述

    本节回顾了与本研究相关的两个关键领域的文献:(i)人道主义救援网络设计和(ii)不确定性下的选址-路线问题。

    问题描述和模型构建

    首先介绍了我们研究中使用的符号和假设,然后在本节中构建了TS-ARO模型。关键符号在表2中进行了总结。

    解决方法

    TS-ARO模型涉及大量的约束和变量,导致计算复杂性较高。然而,与许多具有广泛约束的MILP模型类似,只有少数依赖于情景的约束是活跃的。受到这一观察以及Liu等人(2023)和Agra等人(2018)研究的启发,我们提出了一种名为CCG-IBD-BP的精确算法,该算法结合了CCG、IBD和BP算法。

    数值研究

    数值研究旨在实现三个目标:(i)评估所提算法的整体有效性;(ii)评估加速策略的有效性;(iii)研究关键参数对解决方案配置的影响。我们使用Java实现了所提算法,并使用CPLEX 22.12对模型进行了线性优化。实验环境包括一台配备64位2.1 GHz处理器和16 GB RAM的PC。

    案例研究

    在本节中,我们使用一个实际案例来进一步验证我们的模型。为此,进行了以下测试:(i)突出RO在处理不确定性方面的优势;(ii)研究情景数量对解决方案结构和性能的影响。
    雅安位于中国四川省,是一个经常遭受地震影响的城市,近年来经历了多次不同强度的地震。因此,我们选择雅安作为案例研究。

    结论与未来研究

    本文提出了一种在人道主义救援背景下考虑两种关键不确定性来源的LRP模型:供应端和接收端。具体来说,它考虑了救援设施的中断概率、受影响区域的需求波动以及接收救援物资的截止日期的不确定性。为了解决这些不确定性,我们开发了一个TS-ARO模型,使用离散情景集来减轻灾害的负面影响。

    致谢

    本文部分得到了中国国家自然科学基金(项目编号72401234、72471158、72431008、72471197和W2511078)、教育部人文社会科学研究项目(项目编号24XJC630019)、四川省自然科学基金(项目编号2025NSFSC1978)以及四川省自然科学基金重点计划(项目编号2024NSFSC0025)的支持。

    CRediT作者贡献声明

    杨永健:撰写——原始草稿、软件、方法论、形式分析。李成龙:撰写——原始草稿、验证、方法论、概念化。王杜娟:撰写——审阅与编辑、验证、软件、方法论。尹云强:撰写——审阅与编辑、验证、方法论、概念化。程T.C.E.:撰写——审阅与编辑、验证。

    利益冲突声明

    我们声明与可能不恰当地影响我们工作的其他人或组织没有财务和个人关系,也没有任何形式的专业或其他个人利益涉及可能影响本文所述观点或手稿审查的任何产品、服务和/或公司。
    相关新闻
    生物通微信公众号
    微信
    新浪微博
    • 搜索
    • 国际
    • 国内
    • 人物
    • 产业
    • 热点
    • 科普

    热点排行

      今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

      版权所有 生物通

      Copyright© eBiotrade.com, All Rights Reserved

      联系信箱:

      粤ICP备09063491号