APP下载

线状需求下两阶段设施选址问题

2020-10-20王紫萌周建勤

上海海事大学学报 2020年3期
关键词:分配算法

王紫萌 周建勤

摘要:鉴于大型交通线路建设项目的物资需求随时间变化(在初期阶段需求较低;在后续阶段项目全面展开,需求显著上升),本文采用线积分对沿线连续分布的线状物资需求进行刻画,构建两阶段设施选址模型,第一阶段进行部分设施的选址,第二阶段对剩余设施选址,以实现系统总成本最低的目标。针对模型特点,设计基于Voronoi图的两阶段交替定位-分配(alternative location-allocation,ALA)算法进行求解,并进行实例分析,比较两阶段模型与传统模型的异同。研究表明,将两阶段设施选址模型应用于交通线路建设项目多物流节点选址,能节约运营成本,并缓解初期资金压力。

关键词:设施选址; 线状需求; 交替定位-分配(ALA)算法; Voronoi图

中图分类号:  U492.1+44

文献标志码:A

Two-stage facility location problems with linear demands

WANG Zimeng, ZHOU Jianqin

(School of Economics and Management, Beijing Jiaotong University, Beijing 100044, China)

Abstract:

The material demand of a large-scale traffic line construction project changes with time: the demand is lower in the initial stage; the project is fully carried out in the subsequent stage, and the demand is significantly increased.In view of this, the line integral is adopted to describe the linear material demands with the continuous distribution along the line, and a two-stage facility location model is constructed, where some facilities are located in the first stage, and the others are located in the second stage so as to minimize the total cost. According to the characteristics of the model, a two-stage alternative location-allocation (ALA) algorithm based on Voronoi diagram is designed to solve the model. An example analysis is carried out to compare the similarities and differences between the two-stage model and the traditional model. The research shows that the application of the two-stage facility location-allocation model to the multi-logistics node location of the traffic line construction project can save the operation cost and relieve the initial financial pressure.

Key words:

facility location; linear demand; alternative location-allocation (ALA) algorithm; Voronoi diagram

0 引 言

大型交通線路覆盖距离较长,建设过程中涉及海量的物资供给,同时产生巨大的物流费用。物流节点选址对于大型交通线路建设项目影响重大。因此,在实际建设中需要进行科学合理的物流节点选址,控制物流成本,保障物资供应。

在交通线路建设项目中,物资需求在空间上沿拟建交通线路分布。拟选址的物流节点需要为整条路段提供服务。需求以一定的密度连续分布在一条曲线上的设施选址问题被定义为线状需求设施选址问题,它不同于经典的离散需求设施选址问题。GDEN等[1]研究了铁路建设工程沿线的物流节点选址问题,计明军等[2]研究了线状需求下长江航道危险品应急中心选址优化问题,但他们都将连续线状需求离散成若干个点状需求,这与实际连续线状需求存在差异[3]。ALEXANDRIS等[4]证明了需求刻画方式会对选址结果产生影响。连续线状需求可以采用线积分进行刻画。BERMAN等[5]和GASTNER[6]用密度函数描述连续线状需求。

在交通线路建设项目中,物资需求的时间分布特点也会对物流节点选址产生影响。在项目建设初期阶段,需要完成“三通一平”工作,物资需求量和物流工作量较小;进入项目建设中期阶段,随着大规模土建类施工展开,物资需求量和物流量显著增加:拟建交通线路上的物资需求密度在两个阶段内差异明显。针对需求动态变化的设施选址问题:陈鑫等[7]考虑了需求动态变化下的情形;BRANCOLINI等[8]提出了根据当前阶段需求进行多阶段选址的策略;SUZUKI等[9]对设施多阶段选址的几种策略进行了对比分析,认为分阶段选址节省的设施运作成本可能足以弥补增加的运输成本。针对需求两阶段变化的情况,一些学者研究了两阶段设施选址模型的实际应用,这里的两阶段设施选址指先进行部分设施的选址,随后进行其余设施的选址。代文强[10]设计了两阶段设施选址优化模型,针对离散需求,使用近似优化算法进行了求解。姜秀山等[11]研究了铁路应急服务设施的两阶段选址问题。魏明等[12]针对公交站场选址布局问题,也设计了两阶段模型与算法。然而,这些两阶段选址文献多集中在离散需求领域,未见针对连续需求的研究。

为此,本文引入线密度函数,用线积分对连续线状需求进行刻画,以此取代经典需求离散化处理方式。考虑需求两阶段变化的实际情况,本文建立两阶段设施选址模型。在初期阶段需求密度较低时进行部分设施的选址,在后续阶段需求密度上升时对其余的设施进行选址。线状需求下的两阶段设施选址模型可为实际的交通线路建设项目中的设施选址决策提供支持。

1 问题描述与建模

1.1 问题描述

在交通线路建设项目中,物资需求沿拟建线路连续分布。物流节点可以位于交通线路所在二维平面内的任意一点,物流节点的选址分两个阶段展开。在项目建设初期阶段,物资需求量较低,需要按照当时的物资需求密度建设一定数量的物流节点。随着项目建设的推进,物资需求量显著增大,需要在已有物流节点的基础上增加一定数量的物流节点,并由全部物流节点共同为项目建设提供服务,以满足需求并有效降低成本。

为此,本文提出以下假设:(1)各个物流节点的功能无差异;(2)物流节点具有足够大的服务能力,无容量限制;(3)物资需求密度在两个阶段内都是确定的;(4)采用欧氏距离度量距离;(5)从各个物流节点到需求线路的运输费率相同。

首先定义参数和变量:k表示阶段,k=1,2;P为物流节点集合,P={1,2,…,p};Q为第一阶段待选址的物流节点集合,Q={1,2,…,q};μk为单个设施在第k阶段的运营费率;g为运输费率;L为物资需求线路;Lj为由物流节点j服务的物资需求线路子区段;X为物资需求线路上的点,X=(x,y);ρk(X)为第k阶段X处的需求密度;Xj为物流节点j的坐标,Xj=(xj,yj);T为整条拟建线路上所有需求点的集合,t∈T;Tj为Lj内所有需求点的集合。

物资需求线路L的参数方程表示为

x=u(t), y=v(t), t∈T

(1)

由物流节点j提供服务的物资需求线路子区段Lj的参数方程表示为

x=u(t), y=v(t), t∈Tj

(2)

1.2 模型构建

交通线路建设项目的物流总成本主要包括物流节点的总运营成本、从供应商到物流节点的上游运输成本和从物流节点运输到交通线路的末端运输成本。由于从供应商到物流节点的距离很远,物流节点位置对上游运输成本影响较小,所以从供应商到物流节点的上游运输成本不予考虑。

物流节点j的运输成本可以表示为

其中X-Xj表示从物流节点j到物资需求线路上的点X的距离。结合式(2)~(4)可以得到

对第一阶段的q个物流节点进行选址,选址模型如下:

式(6)为目标函数,表示第一阶段末端运输总成本最低;式(7)刻画了需求分配的靠近性原则,即任一物流节点服务的需求线路子区段都是距离该节点最近的;式(8)表示整条物资需求线路都有物流节点提供服务。

第二阶段共有p个物流节点提供服务,其中q个物流节点的坐标已经在第一阶段确定,需要对p-q个新增物流节点进行选址。第二阶段物流节点选址模型如下:

式(9)为目标函数,表示第二阶段末端运输总成本最低;式(10)和(11)的意义分别与式(7)和(8)类似。

总运营成本与设施数量和运营费率成正比,建设期内总运营成本可以表示为

物流总成本为第一阶段末端运输成本、第二阶段末端运输成本和总运营成本之和,可以表示为

2 求解算法

2.1 单设施选址算法

单设施选址算法是多设施选址算法的基础。为求解连续线状需求下物流节点的运输成本(式(4)),根据定积分的定义,在Tj=[tj,tj]区间内插入n-1个分点,tj=t0

当λ→0,即n→∞时,需求线路等同于无穷多个需求点的集合,可将式(14)写成如下形式:

利用式(19),通过迭代即可最终求得需求线路子区段Lj内物流节点j的最优位置(xj,yj)。

单设施选址算法步骤如下:

步驟1 输入Lj{x=u(t),y=v(t)}、Tj、g、ρk(X)、δ(迭代终止容差值)、n。

步骤2 初始化:m=0,随机生成初始坐标(x(m)j,y(m)j),根据式(17)计算初始运输成本Z(m)j。

步骤3 迭代:将(x(m)j,y(m)j)代入式(19)右侧,计算并更新坐标(x(m+1)j,y(m+1)j)。

步骤4 计算运输成本:将(x(m+1)j,y(m+1)j)代入式(17),计算运输成本Z(m+1)j。

步骤5 收敛判定:若满足Z(m+1)j-Z(m)j≤δ,则Xj=(x(m+1)j,y(m+1)j);否则,令m←m+1,返回步骤3。

步骤6 输出Xj。

式(17)中,物资需求线路等同于无穷多个需求点的集合,这相当于将连续需求线路离散为充分多个需求点,将连续线状需求下的设施选址问题转化为离散需求下的设施选址问题进行求解。WESOLOWSKY等[13]证明了离散需求下迭代选址算法的收敛性,因此连续线状需求单设施选址算法也是收敛的。

2.2 第一阶段模型求解算法

解决多设施选址分配问题有很多经典算法,其中最为广泛使用的是COOPER[14]提出的交替定位-分配(alternative location-allocation,ALA)算法。该算法具有收敛速度快、精度高的特点,关键思路在于给定设施初始坐标,划分需求,将多设施选址问题转化成单设施选址问题进行求解,得到新的设施位置后再进行分配和迭代,直到满足容差值,最终得到多设施选址分配问题的最优解。

二维平面内需求的划分多采用Voronoi图的方法。Voronoi图是计算几何领域对平面区域进行分割的经典方法之一。

定义1 设Xj(j∈P)为二维平面内p个设施的坐标,则由给出平面内需求的划分,划分后的图形被称为以物流节点j为生成元的Voronoi图。图1中各多边形被称为以物流节点为生成元的Voronoi多边形,Voronoi多边形的交点称为节点。

性质1 Voronoi图各多边形区域内任意一点到该多边形区域内生成元的距离不大于到任意其他多边形内的生成元的距离。

性质2 Voronoi图的每个多边形区域内只存在一个生成元。

本文将Voronoi图与经典的ALA算法相结合,设计了改进算法。使用Voronoi图划分需求线路,将多设施选址问题转化为若干单设施选址问题。再使用单设施选址算法求解。随后,进行交替选址和需求划分迭代,对两阶段模型多设施选址问题进行求解。第一阶段模型算法步骤如下:

步骤1 输入L{x=u(t),y=v(t)}、T、q、g、ρ1(X)、δ、n。

步骤2 初始化:m=0,随机生成q个坐标为X(m)j(j∈Q)的点,作为初始坐标。

步骤3 需求划分:根据式(7)对需求线路L进行划分,确定各需求线路子区段L(m)j(j∈Q)。

步骤4 计算运输成本:

步骤4.1 计算需求线路子区段运输成本:根据式(17),分别计算L(m)j内运输成本Z(m)j(j∈Q)。

步骤4.2 计算总需求线路运输成本:根据式(6),计算总运输成本C(m)1。

步骤5 再选址:在需求线路子区段内,使用单设施选址算法求解各物流节点新坐标X(m+1)j(j∈Q)。

步骤6 再次划分需求:与步骤3类似,将X(m+1)j(j∈Q)代入,确定L(m+1)j(j∈Q)。

步骤7 再次计算运输成本:与步骤4类似,计算得到C(m+1)1。

步骤8 收敛判定:若满足C(m+1)1-C(m)1≤δ,则Xj=X(m+1)j(j∈Q);否则,返回步骤5,令m←m+1。

步骤9 输出Xj(j∈Q)。

2.3 第二阶段模型求解算法

第二阶段需求密度上升,需要加入其他物流节点提供服务。在第一阶段已确定q个物流节点位置,在第二阶段再加入p-q个物流节点,使第二阶段在满足需求的条件下总运输成本最低。第二阶段模型求解算法步骤如下:

步骤1 输入L{x=u(t),y=v(t)}、T、p、q、g、ρ2(X)、δ、n。

步骤2 初始化:m=0,随机生成p-q个坐标为X(m)j(j∈P\\Q)的点,作为初始坐标。

步骤3 需求划分:根据式(10)对需求线路L进行划分,确定各需求线路子区段L(m)j(j∈P)。

步骤4 计算运输成本:

步骤4.1 计算需求线路子区段运输成本:根据式(17),分别计算L(m)j内运输成本Z(m)j(j∈P)。

步骤4.2 计算总需求线路运输成本:根据式(9),计算总运输成本C(m)2。

步骤5 部分节点再选址:

步骤5.1 在Lj(j∈P\\Q)内使用单设施选址算法求解物流节点j的新坐标X(m+1)j(j∈P\\Q)。

步骤5.2 X(m+1)j=X(m)j(j∈Q)。

步骤6 再次划分需求:与步骤3类似,将X(m+1)j(j∈P)代入,确定L(m+1)j(j∈P)。

步骤7 再次计算运输成本:与步骤4类似,计算得到C(m+1)2。

步骤8 收敛判定:若满足C(m+1)2-C(m)2≤δ,则停止计算;否则,返回步骤5,m←m+1。

步骤9 输出Xj(j∈P)。

3 算例分析

3.1 算例设计

江苏南沿江城际铁路于2018年10月开工,建设工期4年。线路自南京南站引出,向东经过句容市、金坛区、武进区、江阴市、张家港市和常熟市,终至沪通铁路太仓站。线路全长270.2 km,具体走向如图2所示。

本文算例基于江苏南沿江城际铁路建设的实际背景,探究物流节点的选址问题。首先收集沿线重要站点经纬度坐标,转化为平面坐标系坐标。将线路拟合成若干首尾相连的折线段表示。由于整条线路均位于江苏省南部,地形地貌与交通运输情况无显著区别,故设定全线的运输费率均为1元/(t·km)。在该建设项目开始前,进行施工组织调查,根据《铁路工程施工组织设计规范》和《铁路大型临时工程计算方法及设计技术研究》的规定,结合项目实际情况,编写组织设计方案,制定沿线各子区段在各阶段内级配碎石的用料计划,可简化为表1中的数据。在建设过程中拟建8個物流节点,为建设项目沿线提供级配碎石等物料。建设期第一年为第一阶段,进行5个物流节点选址;第二年至第四年为第二阶段,进行3个物流节点选址。

3.2 结果分析

首先确定沿线8个关键城市的经纬度坐标,使用高斯-克吕格投影转化为平面直角坐标,对拟建线路进行拟合。随后根据两阶段选址模型和算法,使用MATLAB编写程序进行求解,可以获得第一阶段和第二阶段物流节点最优位置以及需求的划分。两阶段物流节点在平面直角坐标系中的选址分配见图3,其经纬度坐标见表2。

对于第一阶段进行5个物流节点选址,第二阶段进行3个物流节点选址的两阶段选址模型,可以求解出其第一阶段运输成本C1(5,3)、第二阶段运输成本C2(5,3)分别为1 185.987 8万元和5 875.038 6万元。

为将两阶段选址模型与传统的一次性选址模型进行比较,针对第一阶段即对全部的8个物流节点进行一次性选址的传统选址模型,同样进行运输成本的计算,得到C1(8,0)和C2(8,0)分别为572.305 1万元和5 723.051 0万元。比较可知,两阶段选址模型的运输成本略高于一次性选址模型的运输成本。

两阶段选址模型的物流总成本为

C(5,3)=C1(5,3)+C2(5,3)+C3(5,3)

传统的一次性选址模型的物流总成本为

C(8,0)=C1(8,0)+C2(8,0)+C3(8,0)

如果两阶段选址模型优于传统的一次性选址模型,则两阶段选址模型的物流总成本应当小于等于传统的一次性选址模型的物流总成本,即

C(5,3)≤C(8,0)

整理得到

μ1≥C1(5,3)+C2(5,3)-C1(8,0)-C2(8,0)3

计算可得:当μ1≥255.223 4万元/a时,两阶段选址模型的物流总成本低于一次性选址模型的物流总成本,选择两阶段选址模型比一次性选址模型更加有利;反之,即当μ1<255.223 4万元/a时,选择一次性选址模型更能节约成本。

μ1是单个物流节点第一阶段的运营费率,第一阶段的运营费率与第一阶段物流节点运营的时间和单个物流节点单位时间内运营成本正相关。当该工程项目第一阶段建设期较长,物流节点单位时间内运营成本较高,且运输费率较低时,与传统的一次性选址模型相比,选择两阶段选址模型,能够节约物流总成本,为工程建设带来经济效益。相反地,如果第一阶段建设期较短,物流节点单位时间内运营成本较低,且运输费率较高时,则应考虑选择传统的一次性选址模型。

总之,两阶段选址模型与传统的一次性选址模型相比,增加了一定的运输成本,但节约了物流节点的运营成本,同时降低了项目建设初期资金筹措的压力。在工程建设项目中,应根据实际的相关参数进行计算与比较,选择最优的选址策略。

4 结 论

针对大型交通线路建设项目中的物流节点选址问题,考虑交通线路需求连续线状分布且需求随时间两阶段变化的特点,采用线密度函数刻画需求,构建了线状需求下两阶段选址模型。分析连续线状需求与经典离散需求的异同,设计了基于Voronoi图的改进交替定位-分配(ALA)算法。以江苏南沿江城际铁路物流节点建设项目为例进行实证研究,证明了模型和算法的有效性。两阶段选址模型与传统的一次性选址模型相比,增加了少量的运输成本,但节约了运营成本,缓解了项目建设初期资金筹措的压力,具有现实意义。本文提出的模型为交通线路建設项目中物流节点选址的实际问题提供了解决思路。进一步的研究可以考虑在有物流节点容量限制的情况下的物流节点两阶段选址问题。另外,需求不确定的两阶段设施选址问题也值得研究。

参考文献:

[1]GDEN H,SRAL H. Locating mobile facilities in railway construction management[J]. Omega, 2014, 45: 71-79. DOI: 10.1016/j.omega.2014.01.001.

[2]计明军, 宋婷婷, 宋佳, 等. 线状需求下的长江航道危险品应急中心选址优化[J].运筹与管理, 2016, 25(5): 68-74.DOI: 10.12005/orms.2016.0163.

[3]WESOLOWSKY G O, LOVE R F. Location of facilities with rectangular distances among point and area destination[J].Naval Research Logistics Quarterly, 1971, 18: 83-90.DOI: 10.1002/nav.3800180107.

[4]ALEXANDRIS G, GIANNIKOS I. A new model for maximal coverage exploiting GIS capabilities[J]. European Journal of Operational Research,2010, 202(2): 328-338. DOI: 10.1016/j.ejor.2009.05.037.

[5]BERMAN O, KRASS D, MENEZES M. Location and reliability problems on a line: impact of objectives and correlated failures on optimal location patterns[J]. Omega, 2013, 41: 766-779.DOI: 10.1016/j.omega.2012.09.002.

[6]GASTNER M T. Scaling and entropy in p-median facility location along a line[J].Physical Review E, 2011, 3(16): 1-7. DOI: 10.1103/PhysRevE.84.036112.

[7]陈鑫, 汪传旭, 石刘红.模糊随机需求下应急救援中心排队选址模型及算法[J].上海海事大学学报, 2011, 32(1): 74-79. DOI: 10.3969/j.issn.1672-9498.2011.01.016.

[8]BRANCOLINI A, BUTTAZZO G, SANTAMBROGIO F, et al. Long-term planning versus short-term planning in the asymptotical location problem[J]. Control, Optimisation and Calculus of Variations, 2009, 15(3): 509-524. DOI: 10.1051/cocv:2008034.

[9]SUZUKI T, ASAMI Y, OKABE A. Sequential location-allocation of public facilities in one- and two-dimensional space: comparison of several policies[J]. Mathematical Programming, 1991, 52: 125-146. DOI: 10.1007/BF01582883.

[10]代文强.两阶段选址优化问题研究[J].运筹与管理, 2007, 16(6): 47-50. DOI: CNKI:SUN:YCGL.0.2007-06-009.

[11]姜秀山, 张赣, 匡敏. 铁路应急服务设施双阶段组合选址模型研究[J]. 交通运输系统工程与信息, 2015, 15(3): 152-159. DOI: 10.3969/j.issn.1009-6744.2015.03.024.

[12]魏明, 陈学武, 孙博. 公交站场选址布局优化模型和算法[J]. 交通运输系统工程與信息, 2015, 15(4): 113-117. DOI: 10.3969/j.issn.1009-6744.2015.04.017.

[13]WESOLOWSKY G O, TRUSCOTT W O. The multiperiod location-allocation problem with relocation of facilities[J]. Management Science, 1975,22(1): 57-65. DOI: 10.2307/2629789.

[14]COOPER L. Location-allocation problems[J]. Operations Research, 1963, 11: 331-343. DOI: 10.1287/opre.11.3.331.

(编辑 赵勉)

收稿日期: 2019-09-09

修回日期: 2020-02-24

基金项目: 国家自然科学基金(71372013)

作者简介:

王紫萌(1996—),女,辽宁辽阳人,硕士研究生,研究方向为物流管理与工程,(E-mail)1679605902@qq.com;

周建勤(1975—),男,湖北黄冈人,教授,博导,博士,研究方向为物流管理与工程,(E-mail)jqzhou@bjtu.edu.cn

猜你喜欢

分配算法
国际主流轧差算法介绍:以CHIPS的BRA算法为例
跟踪导练(6)
Travellng thg World Full—time for Rree
Crying Foul
遗产的分配
学习算法的“三种境界”
算法框图的补全
算法初步知识盘点
阅读理解Ⅳ
我会好好地分配时间