论文部分内容阅读
摘要：截流问题研究的对象为路径上行走的消费者，其研究的问题为如何选址使设施截得网络上最大的流量。大部分截流的文献假设设施容量无限制，只要在消费者行走路径上有一个设施即可截得路径上的全部流量。本文的截流问题，考虑了设施的容量限制，并可以通过一定的技术改进容量，也考虑了路径上流量有一定的截取比例，建立了具有容量和预算限制的截流设施选址和设计模型。
关键词：截流 设施选址 容量 设计
0 引言
选址问题为策略管理决策问题，选址的好坏直接影响着企业的利润和消费者满意度等一系列重要问题。从Hodgson（1981）[1]一篇文章起，在过去的近三十年时间里，大量设施选址的文献关注的不是产生流或吸引流而是截得的流量，在提前计划路径上的发点到终点的流量，被路径上的设施自愿或强加的截得。换言之，流量的目的不是为了获得服务，但如果在他们提前计划的路径上存在一个设施，则他们会自愿的或者不可避免的中断下来获取服务，然后继续前行到达目的地。因此此类问题称作截流的设施选址问题。Gendreau（2000）[2]描述预防和惩罚截流问题的公式和特征，给出了监测站选址模型，目标是总的危险减少最大化。Uno（2008）[3]本文考虑一个新的选址问题，防御性选址问题（DLP）。在DLP中，决策者选址设施为了阻止他的对手到达一个重要的位置称为中心；例如：“一个国家的一个政府部门选择自我防御设施，为了阻止入侵者到达国家的首都”。本文的决策者和对手称为防御者和入侵者，假设决策者考虑防御设施的选址，背景是网络的。DLP被看为0-1规划问题，可以找到斯坦尔伯格解。进一步把DLP拓展为一个多目标DLP，如：防御者需要同时保护两个或者多个中心。Boccia（2009）[4]总结了FIFLP的五个基本重要知识点：①O-D（origin-destination）路径和相关流的知识；②连线失败或者偏离原计划路径；③单一或多形式截流；④是否运用抽样操作的流量监控；⑤在网络结点还是弧上选址。Jong-Geun Kim（2012，2013）[5][6]研究了燃料补充设施的截流选址问题，与一般截流问题不同的是，文中需要补充燃料的车辆是否被设施服务，取决于网络上的车辆，是否在行走的路径上的站点或附近的站点停车补充燃料。
现有的截流选址问题，基本假设设施容量是无限制的，只要在行走路径上有设施开放，则流量全部截得。通过对实际问题的研究发现，设施不可能无限制的提供服务，设施对不同路径上的流量截得存在比例问题。本文的截流选址模型考虑了上述问题。
2 模型与算法
2.1 问题描述
店面布局、服务窗口数量、工作人员的操作熟练程度等都会影响设施的服务容量，服务容量与基础设施有关，同时也可以通过布局、规划设计或培训等技术手段改进和扩充容量。不同的方法对设施容量改进的效果不同，同时耗费的成本也不同。本文研究的截流问题，考虑了在网络上开放设施时，有基础的可接纳服务的容量，通过一定的技术手段可以扩充设施的服务容量，这种设施容量的改进有上限，无论采用多先进的技术和方法，不可能使设施容量无限制增加，因此本文设置了改进的上限，采用不同的方法扩充容量，其消耗的成本不同。本文将成本分为两部分，一部分为开放设施的固定成本，一部分为扩充设施容量所消耗的变动成本。建立了基于容量限制和预算限制的截流选址和设施服务容量设计模型。
2.2 模型建立
符号说明：
yik：采用第k种技术改进i点的设施带来的容量影响
fp：路径p上的流量
αi：i点的建立设施的基础容量
zi=1 i点开放一个设施0 其他
xip：i点的设施对路径p上的需求截取的比例
Ci=ziαi（1+yik）
v（yik）：非减的可变成本，
wi：固定成本。
B：建立设施的成本限制
maxfpxip （1）
ST.
fpxip≤Ci （2）
v（yik）+wizi≤B （3）
yik≤ziy （4）
xip≤1 （5）
xip≤zi （6）
zi∈{0，1} （7）
xip∈{0，1} （8）
yik∈[0，y]（9）
目标函数（1）为截得流量最大化，约束条件（2）为i点设施容量限制约束，约束条件（3）为预算限制约束，约束条件（4）为采用第k种技术改进i点的设施带来的容量扩充不会超过技术上限，约束条件（5）保证路径p上的每点设施截得的总需求比例不会超过1，约束条件（6）保证只有在i开放设施，才能截得路径上的流量。约束条件（7）、（8）、（9）为变量取值范围约束。
2.3 模型求解
所建立的模型为混合整数规划模型，可以通过分支定界法求解模型。Lingo软件是一款非常好的求解模型软件，本文模型，如果给定参数的具体数值，可以通过lingo软件，运用分支定界法求出最优解。
3 结语
本文研究的截流问题，即考虑了设施的容量，也考虑了容量扩张问题，在容量扩张中有技术瓶颈和预算限制等问题，在这些因素的前提下，建立了具有容量和预算限制的截流选址模型。所建立的模型为基本截流问题的扩展模型，由于基本截流模型为NP-hard问题，故所建立的模型为NP-hard问题，对于小规模问题，可以运用分支定界求的问题的最优解，但如果问题规模较大，则求最优解不太现实，需设置启发式算法求解模型的满意解，今后将研究求解模型的启发式算法。
参考文献：
[1]Hodgson M J.The location of public facilities intermediate to the journey to work[J].European Journal of Operational Research.1981，6（2）：199-204.
[2]Gendreau M，Laporte G，Parent I.Heuristics for the location of inspection station on a network. Naval Research Logistics，2000，47（4）：287-303.
[3]Uno T，Katagiri H.Single- and multi-objective defensive location problems on a network. European Journal of Operational Research，2008，188（1）：76-84.
[4]Boccia M，Sforza A，Sterle C.Flow Intercepting Facility Location： Problems， Models and Heuristics. Journal of Mathematical Modelling and Algorithms，2009，8：35-79.
[5]Jong-Geun Kim，Michael Kuby.The deviation-flow refueling location model for optimizing a network of refueling stations[J].international journal of hydrogen energy，2012，37：5406-5420.
[6]Jong-Geun Kim，MichaelKuby.A network transformation heuristic approach for the deviation flow refueling location model[J].Computers & Operations Research，2013，40：1122-
1131.
基金项目：国家自然科学基金（70871044，70971045）。
作者简介：
张曦（1980-）女，河北南宫人，讲师，博士，主要研究方向为选址和网络优化。
关键词：截流 设施选址 容量 设计
0 引言
选址问题为策略管理决策问题，选址的好坏直接影响着企业的利润和消费者满意度等一系列重要问题。从Hodgson（1981）[1]一篇文章起，在过去的近三十年时间里，大量设施选址的文献关注的不是产生流或吸引流而是截得的流量，在提前计划路径上的发点到终点的流量，被路径上的设施自愿或强加的截得。换言之，流量的目的不是为了获得服务，但如果在他们提前计划的路径上存在一个设施，则他们会自愿的或者不可避免的中断下来获取服务，然后继续前行到达目的地。因此此类问题称作截流的设施选址问题。Gendreau（2000）[2]描述预防和惩罚截流问题的公式和特征，给出了监测站选址模型，目标是总的危险减少最大化。Uno（2008）[3]本文考虑一个新的选址问题，防御性选址问题（DLP）。在DLP中，决策者选址设施为了阻止他的对手到达一个重要的位置称为中心；例如：“一个国家的一个政府部门选择自我防御设施，为了阻止入侵者到达国家的首都”。本文的决策者和对手称为防御者和入侵者，假设决策者考虑防御设施的选址，背景是网络的。DLP被看为0-1规划问题，可以找到斯坦尔伯格解。进一步把DLP拓展为一个多目标DLP，如：防御者需要同时保护两个或者多个中心。Boccia（2009）[4]总结了FIFLP的五个基本重要知识点：①O-D（origin-destination）路径和相关流的知识；②连线失败或者偏离原计划路径；③单一或多形式截流；④是否运用抽样操作的流量监控；⑤在网络结点还是弧上选址。Jong-Geun Kim（2012，2013）[5][6]研究了燃料补充设施的截流选址问题，与一般截流问题不同的是，文中需要补充燃料的车辆是否被设施服务，取决于网络上的车辆，是否在行走的路径上的站点或附近的站点停车补充燃料。
现有的截流选址问题，基本假设设施容量是无限制的，只要在行走路径上有设施开放，则流量全部截得。通过对实际问题的研究发现，设施不可能无限制的提供服务，设施对不同路径上的流量截得存在比例问题。本文的截流选址模型考虑了上述问题。
2 模型与算法
2.1 问题描述
店面布局、服务窗口数量、工作人员的操作熟练程度等都会影响设施的服务容量，服务容量与基础设施有关，同时也可以通过布局、规划设计或培训等技术手段改进和扩充容量。不同的方法对设施容量改进的效果不同，同时耗费的成本也不同。本文研究的截流问题，考虑了在网络上开放设施时，有基础的可接纳服务的容量，通过一定的技术手段可以扩充设施的服务容量，这种设施容量的改进有上限，无论采用多先进的技术和方法，不可能使设施容量无限制增加，因此本文设置了改进的上限，采用不同的方法扩充容量，其消耗的成本不同。本文将成本分为两部分，一部分为开放设施的固定成本，一部分为扩充设施容量所消耗的变动成本。建立了基于容量限制和预算限制的截流选址和设施服务容量设计模型。
2.2 模型建立
符号说明：
yik：采用第k种技术改进i点的设施带来的容量影响
fp：路径p上的流量
αi：i点的建立设施的基础容量
zi=1 i点开放一个设施0 其他
xip：i点的设施对路径p上的需求截取的比例
Ci=ziαi（1+yik）
v（yik）：非减的可变成本，
wi：固定成本。
B：建立设施的成本限制
maxfpxip （1）
ST.
fpxip≤Ci （2）
v（yik）+wizi≤B （3）
yik≤ziy （4）
xip≤1 （5）
xip≤zi （6）
zi∈{0，1} （7）
xip∈{0，1} （8）
yik∈[0，y]（9）
目标函数（1）为截得流量最大化，约束条件（2）为i点设施容量限制约束，约束条件（3）为预算限制约束，约束条件（4）为采用第k种技术改进i点的设施带来的容量扩充不会超过技术上限，约束条件（5）保证路径p上的每点设施截得的总需求比例不会超过1，约束条件（6）保证只有在i开放设施，才能截得路径上的流量。约束条件（7）、（8）、（9）为变量取值范围约束。
2.3 模型求解
所建立的模型为混合整数规划模型，可以通过分支定界法求解模型。Lingo软件是一款非常好的求解模型软件，本文模型，如果给定参数的具体数值，可以通过lingo软件，运用分支定界法求出最优解。
3 结语
本文研究的截流问题，即考虑了设施的容量，也考虑了容量扩张问题，在容量扩张中有技术瓶颈和预算限制等问题，在这些因素的前提下，建立了具有容量和预算限制的截流选址模型。所建立的模型为基本截流问题的扩展模型，由于基本截流模型为NP-hard问题，故所建立的模型为NP-hard问题，对于小规模问题，可以运用分支定界求的问题的最优解，但如果问题规模较大，则求最优解不太现实，需设置启发式算法求解模型的满意解，今后将研究求解模型的启发式算法。
参考文献：
[1]Hodgson M J.The location of public facilities intermediate to the journey to work[J].European Journal of Operational Research.1981，6（2）：199-204.
[2]Gendreau M，Laporte G，Parent I.Heuristics for the location of inspection station on a network. Naval Research Logistics，2000，47（4）：287-303.
[3]Uno T，Katagiri H.Single- and multi-objective defensive location problems on a network. European Journal of Operational Research，2008，188（1）：76-84.
[4]Boccia M，Sforza A，Sterle C.Flow Intercepting Facility Location： Problems， Models and Heuristics. Journal of Mathematical Modelling and Algorithms，2009，8：35-79.
[5]Jong-Geun Kim，Michael Kuby.The deviation-flow refueling location model for optimizing a network of refueling stations[J].international journal of hydrogen energy，2012，37：5406-5420.
[6]Jong-Geun Kim，MichaelKuby.A network transformation heuristic approach for the deviation flow refueling location model[J].Computers & Operations Research，2013，40：1122-
1131.
基金项目：国家自然科学基金（70871044，70971045）。
作者简介：
张曦（1980-）女，河北南宫人，讲师，博士，主要研究方向为选址和网络优化。