第1章引言
1.1设施选址问题简介
设施选址问题的起源可以追溯到17世纪法国数学家费马（Fermat）提出的一个几何问题：在欧几里得平面上，哪个点到三个给定点的距离之和*小？该问题对选址科学的发展产生了深远影响，并且至今仍有许多学者致力于相关问题研究（Benko and Coroian，2018;Gorner and Kanzow，2016）.在20世纪初，朗哈特（Launhardt）和韦伯（Weber）在3-节点Weber问题的研究中*次提出了规范的（normative）设施选址模型（Fearon，2006;Launhardt，1900）.该模型的目标是为一个炼钢设施选择*优的地址，使得钢铁供应链的总运输成本*小.随后几十年中，选址科学不断发展，并成功地应用于多种实际问题.直到20世纪60年代，米勒(Miehle）和库珀（Cooper）将Weber问题拓展到多个设施选址的情况，这标志着现代选址科学的产生（Cooper，1963;Miehle，1958）.特别是，Cooper提出了中位工厂（设施）选址问题（p~medianfacilitylocationproblem），即在多个设施备选地址中选择v个地址，以使设施到需求点之间的运输成本*小.这一问题是现代选址科学的核心问题，也是当前研究的热点（Brimberg and Drezner，2013;Drezner and Salhi，2017;Croci et al.，2023）.
设施选址问题根据选址决策的性质可以分为连续、网络或离散三类.此外，也可根据设施选址问题的目标、约束条件或设施的类型进行分类，如中位设施选址问题、中心(p~center）设施选址问题、工厂设施选址问题、枢纽设施选址问题、多层级设施选址问题以及多阶段设施选址问题等（Laporte et al，2019）.本书主要讨论两种具有离散选址决策的设施选址问题，即工厂丨设施）选址问题（facility location problem）和枢纽设施选址问题（hub location problem）.
工厂设施选址问题是选址科学的一类重要问题.在这一问题中，决策者需要在有限的备选地址中找到*优的建厂地址，以充分满足客户的需求.工厂设施选址包含两个关键决策：设施选址决策和商品运输决策.设施选址决策确定了工厂设施应该建在何处，而运输决策决定如何从工厂将商品运送至客户，以满足其需求.该问题的目标是确定*优的工厂建设和商品运输决策，以*小化建厂和运输成本（Ferndndez and L and ete，2019）.
工厂设施选址模型的应用范围极为广泛，它在供应链管理、分布式系统、人
道主义救援、应急系统、路径规划、货物运输以及资源回收管理等实际问题中发挥着至关重要的作用.Melo等（2009）详细总结了工厂设施选址模型在供应链管理问题中的应用.Klose和Drexl(2005）探讨了工厂设施选址模型在分布式系统设计中的应用.Balcik和Beamon(2008）的研究是将人道主义救援与设施选址模型相结合的一个重要成果.Erkut等（2008）运用设施选址模型解决了希腊城市废物管理问题.其他相关应用研究可参考（Daskin et al.，2002;Jia et al.，2007）以及Nagy和Salhi(2007）.此外，工厂设施选址模型还被应用于机器调度、集群分析及组合拍卖等领域（Drezner and Hamacher，2004;Escudero et al.，2009;Klose and Drexl，2005;Singh，2008）.
枢纽设施选址问题是交通运输、电信通信和计算机系统网络设计的核心问题.该问题通过设计枢纽-辐射型网络（hub- and -spokenetwork）来实现在始发地与目的地之间高效运输资源.在枢纽选址问题中，始发地相同但目的地不同的商品或货物在抵达枢纽后进行分拣，然后与其他目的地相同的商品一同运输.这有助于降低运输成本，并通过货物集中运输实现规模经济效益.枢纽设施选址问题的决策主要包括枢纽设施选址和商品运输（或网络设计）决策，其目标为*小化建设枢纽和运输成本（Campbell and O’Kelly，2012;Contreras and O’Kelly，2019）.
枢纽设施选址模型在交通运输领域应用十分广泛，包括快递包裹运输、航空货运和客运、卡车运输和快速运输系统（Campbell and O’Kelly，2012;Farahani et al.，2013）.对于这些问题，枢纽设施选址模型中的商品或货物是指由各种交通运输工具在公路、铁路、水路和空中航线运输的商品，如快递包裹、乘客、邮件和货物等.枢纽设施通常为商品分拣中心或运输终端（O’Kelly and Bryan，1998;Contreras and O’Kelly，2019）.Bryan和O’Kelly(1999）总结了枢纽设施选址模型在航空运输中的应用.Kuby和Gray(1993）研究了FederalExpress公司如何基于枢纽设施选址模型设计其快递运输网络.Limbourg和Jourquin(2009）研究了枢纽设施选址模型在欧洲公路和铁路货物运输中的应用.更多相关研究可以参考（Campbell et al.，2005;Gelareh and Pisinger，2011;Qetiner et al.，2010;Gelareh and Nickel，2008）.
此外，枢纽设施选址模型在电信领域的应用主要体现在各种分布式数据网络设计问题中，模型涉及的对象是通过各种物理链路（光纤或同轴电缆）或空中链路(卫星或微波链路）所传输的电子数据.枢纽设施是各种交换机、多路复用器和路由器等硬件.同样地，在电信领域，枢纽设施选址模型通过降低数据传输成本来实现规模经济效应（Klincewicz，1998）.关于枢纽设施选址模型在电信领域的其他应用，读者可以参考（Alumur and Kara，2008;Carello et al.，2004;Kim and O’Kelly，2009;Yaman and Carello，2005）.
1.2设施选址问题与不确定性
自20世纪60年代以来，选址科学受到了越来越多学者和业界专家的关注，已成为一个热点研究领域.作为该领域的一类核心问题，设施选址问题的目标为确定一个或多个设施的“*佳”位置以便为一组需求点提供服务.其中，“*佳”的含义取决于所研究问题的性质，即所考虑的约束条件和优化目标.随着选址科学与其他应用科学的交互发展，设施选址已被广泛地应用于供应链管理、交通运输、通信网络、应急管理以及城市固体垃圾管理等众多实际应用领域中（DSrnnez et al_，2021;Farahani et al.，2019;Gollowitzer and Ljubic，2011;Melo et al.，2009;Saldanha da Gama，2022）.
设施选址问题中的“设施”具有广泛的含义，在生产与运营环境下，一般指物流中心、仓库、分销中心、工厂和废物处理厂等设施，这些设施具有固定成本高和运行寿命长的特点.所以，设施选址决策成本高昂且一般很难被改变，而且对运营有长期影响.在设施运营期间，其运营环境可能会发生很大的变化.比如，成本、需求、运输时间以及设施选址模型的其他参数可能会具有高度的不确定性.因此，决策环境的不确定性是设施选址问题中的一个重要挑战（Snyder，2006）.这使得不确定环境下的设施选址模型成为选址科学和不确定优化领域的研究热点.在设施选址问题中，环境的不确定性通常可以根据其来源被分为三类：供给方或服务方的不确定性、需求方的不确定性，以及供给方与需求方之间的不确定性（Shen et al.，2011）.供给方的不确定性包括不确定的供给能力或产能、交货时间和设施状态（Cui et al.，2010;Yu et al.，2017;Afify et al.，2019）.需求方的不确定性主要是指需求的不确定性（Atamtiirk and Zhang，2007;Baron et al.，2011;Giilpmar et al.，2013）.两者之间的不确定性包括不确定的运输成本、运输时间和运输路径状态（Gao and Qin，2016;Miskovic et al.，2017;Nikoofal and Sadjadi，2010）.
进一步，根据参数的不确定性特征，我们又可以将不确定性分为三类情况：不确定参数概率分布已知、不确定参数概率分布未知，以及不确定参数概率分布部分可知.不确定参数概率分布已知的情况是指不确定参数可由已知的概率分布刻画.这种情况下的设施选址问题属于随机优化问题，这类问题的决策目标一般是优化目标函数的期望值（Louveaux，1993）.不确定参数概率分布未知的情况是指不确定环境中参数的概率分布信息不可获得，这时可用不确定集对其进行刻画.这种情况下的设施选址问题是一个鲁棒优化问题，这类问题一般优化不确定集中的极值（worst-case value）目标(Bertsimas and Sim，2004）.介于上述两种不确定性环境之间的情况为不确定参数概率分布部分可知也就是分布不确定性(ambiguity），即不确定参数的概率分布属于一个分布不确定集中，决策者优化极值概率分布(worst-case probability distribution或extreme probability distribution）下的期望目标值(Delage and Ye，2010）.这种情况下的设施选址问题是一个分布鲁棒优化问题（Saif and Delage，2021）.
1.2.1随机设施选址问题
在随机设施选址模型中，决策者通常假设不确定参数的概率分布是已知的，并将模型的目标定为*小化设施选址系统的期望成本，或*大化期望利润（Snyder，2006）.Cooper(1974）研究了需求点位置不确定下的随机Weber模型.Mirchan-dani等（1985）*次提出了运输路径距离不确定下的随机设施选址模型，并以*小化其期望成本为目标.Louveaux(1986）研究了具有不确定需求、生产成本和价格的随机>中位容量限制型设施选址问题.Liste§和Dekker(2005）构建了需求不确定下反向物流网络设施选址问题的随机规划模型.Sim等（2009）研究了运输时间不确定且服从正态分布下的枢纽设施选址问题，其目标是*小化期望运输时间.Yang(2009）在不确定需求服从一个已知离散概率分布的假设下，提出了一个两阶段随机规划航空运输枢纽设施选址模型.Contreras等（2011）在商品需求和运输成本都存在不确定性的情况下，研究了容量充足型设施选址问题，并构建了两阶段随机规划模型.Alumur等（2012）对容量充足型设施选址问题进行了研究，并提出了两个随机规划模型，来分别处理设施建设成本和需求不确定性的情况.Sun等（2012）以及Srivastava和Nema(2012）在假设垃圾产生率、单位成本和收益等参数均服从均匀分布的前提下，分别研究了单目标和多目标随机能源回收设施选址和容量规划问题.
上述研究大多以选址系统的期望成本或收益为目标，还有一些研究在期望目标值的基础上，同时考虑了系统的风险规避水平，构建了均值-方差设施选址模型.例如，Jucker和Carlson(1976）在销售价格具有不确定性的情况下，研究了随机均值-方差容量充足型设施选址模型.Hodder和Jucker(1985）将上述模型推广到考虑不确定参数相关的情况.Verier和Dincer(1992）总结了与随机设施选址和产能扩张问题相关的研究，重点关注均值-方差模型在全球制造问题中的应用.Wagner等（2009）将金融中的“在险价值”的概念引入需求不确定下设施选址问题的
展开
