考虑服务惩罚的配送中心选址的双层规划模型*

庆艳华+左小德

摘要： 从系统的角度考虑在配送中心选址决策过程中，处于物流企业上层和下层之间的有机联系，深入的分析了两者所追求的目标、面临的约束以及相互影响，并在此基础上构建了上层以总成本最小为目标，下层以无法及时响应所带来的服务惩罚最小为目标的双层规划模型。根据模型的特点，利用免疫遗传算法求解在不同配送中心方案数目下，上下层模型的最优解，并最终确定双层规划的解。以某电网公司的电力物资配送网络的实际数据和配送中心选址问题为算例验证了模型和算法的有效性和实用性。

关键词：服务惩罚；双层规划；免疫遗传算法

中图分类号：F25214

文献标志码：A

文章编号：1009-055X（2014）03-0056-07

一、引言

配送中心是物流网络的节点，它的设立是整个物流网系统中最关键的因素。配送中心的位置、规模等问题直接影响整个物流网络的成本及运作。过去由于缺乏系统性的思考等因素，许多企业设立了过多的配送中心或周转仓库，尽管较多的配送中心可以有效满足配送的需求，但是同时也意味着巨大的资源浪费。许多企业都面临这样的问题，即如何从全局的角度出发，对现有的配送网络进行优化，在现有仓库中选择设置区域配送中心，构建更高效的物流网络，本文要解决的即是这类问题。

选址问题的研究始于1909年韦伯的选址的文章的发表，较多以费用最小化为目标，确定实施的具体选址［1-3］。其中，重心法选址仅考虑运输成本而未考虑配送中心的固定成本，比较容易操作，但是只对单一配送中心选址比较有效，而且重心法使用的是平面距离，因此求解结果与实际会有差异；CLUSTER法则是首先对客户点进行组合，然后根据组合的几何重心安排配送中心，直到费用不再降低得到优化方案；鲍姆尔一沃尔夫法则在运输费用、配送费用的基础上加入了存储费用，使用迭代法以总费用最小为目标进行选址，虽然操作简单，但是有时会得到配送中心个数较多的方案；而CFLP法则是在面临配送中心能力限制时的选址方法，该方法在初始方案的基础上不断的优化，最终找到一个总费用（固定费用，运输费用）最小的配送中心选址方案，计算过程繁琐。这些方法均是单层规划方法，将企业看作一个整体，认为企业各个层级的目标都是一致的，都是追求满足约束条件下总费用最小的。而实际上企业处于不同层级（如战略层和运作层）的决策者面临的约束和追求的目标经常是不一致的，企业选址的过程也是一个上下级之间博弈的过程。本文所采取的双层规划模型即反映了企业决策过程中的这种博弈，在寻求配送中心选址方案的同时兼顾了企业层级间的利益协调。双层规划模型中不仅追求费用最小，也加入新的服务约束，以及下层追求服务惩罚最小的目标，使用实际的运输距离以及运输时间，而不是平面距离，也更加符合实际情况。

配送中心的选址一直都是以单层规划研究为主，直到Taniguchi（1999）［4］在研究公共物流运输站点的建立问题时，将双层规划应用到了物流领域。我国学者也开展了这方面的研究，文献［5, 6］就构建了上层为配送中心成本最小，下层为顾客费用最小的双层规划模型。文献［7］则将政府看作上层决策者，对环境污染进行控制，而企业则为下层，目标是总成本最小。而这些文献都是建立企业与外部相关者，如客户，政府等的双层模型，研究外部对企业选址模型的影响，而实际上企业在决策时，内部不同层级之间的目标也是不一致的，甚至是相互矛盾的。分析可以发现在决策过程中企业内部的确存在目标不同的决策者，简单来说企业的上层和下层目标就是很不同的。处于组织不同层次的任何决策部门都不可避免的与它的上层或下层产生相互的影响，如果使用单层规划方法来开展物流配送中心选址的工作，就割裂了上下层之间的这种联系。而建立企业与外部相关者双层规划模型时也掩盖了这种关系。本文从企业系统角度出发，找出位于企业决策上下层之间的相互联系，从而构建相应的双层规划模型。

双层规划问题求解是很复杂的，因为它是一个NP-hard问题。Ben-Ayed和Blair（1988）［8］指出即使是很简单的双层线性规划问题也是NP-hard，不存在多项式求解算法。在求解双层规划问题的方法中，常见的是利用Karush-Kuhn-Tucker条件或者值函数将双层规划转换为单层规划，再利用现有的单层规划的求解算法（分支定界法、罚函数法、割平面法等）进行求解，且可以求解的问题规模较小［5-7］。而有些能够很好的反映实际问题的模型，如非线性的，问题规模较大的，目前还没有可行的求解方法，因此很多研究借助智能算法求解。文献［9］就提出了一种求解一般双层规划问题的层次粒子群算法，将一般双层规划问题转化为两个变形粒子群算法的交互迭代来求解上下两层规划问题。文献［10］则针对无容量限制的双层规划选址模型提出了粒子群优化算法、模拟退火算法及结合变邻域搜索算法三种智能算法，通过一个2000客户和2000候选点的算例验证了三种算法的有效性。根据模型特征，对模型进行转换后，通过免疫遗传算法求解，并以某电网企业的电力物资配送网络的实际数据为算例，对模型和算法进行验证，并给出了配送中心的选址方案及相应的配送方案。

二、模型构建

对于配送中心的选址问题，位于企业的不同层级具有不同的目标。处于上层的是决策者，其目标是追求成本最低，因此可能追求尽可能少的配送中心数目，或者配送中心和配送路径总成本最小等；而处于下层的下属部门，他们则不关心配送中心的固定成本等因素，而是追求尽可能高的服务水平，尽可能低的需求满足成本，或因服务水平低而带来的惩罚最小等。一旦上层给定了某一方案，下层就会选择对下层最有利的行动，而这又会反过来影响上层的决策，这个过程一直反复，直到达到双方都满意的状态。本文就在此基础上建立了分别以具有不同目标的企业上下层为模型和上下层的双层优化模型。

模型假设配送中心的选址是在现有配送网络基础上开展的，即候选配送中心均是给定的，配送中心的固定费用为从候选仓库改建成区域配送中心所需的改建费用。

（一） 配送中心选址的上层规划模型

上层规划反映的是位于企业上层的决策部门的规划目标，即在满足配送需求点情况下，实现成本最小（包括固定的改造成本，以及变动成本）。本文构建的上层规划模型以经典的无容量限制的配送中心选址模型为基础，引入以服务惩罚成本最小为目标的下层规划，进而构建从系统最优角度考虑配送中心选址的双层规划模型。其中，上层规划模型(U)如下所示，

(U)Objective:

minF(x,y)x=∑J j=1xjfj+∑J j=1∑I i=1yijdijcij（1）

st ∑J j=1xj≥1（2）

xj=1,表示在j点建设配送中心；

0，否则 （3）

yij=

1,第j个配送中心为第i个需求点提供服务；

0，否则 （4）

其中J表示候选配送中心的数目；

I表示需求点的数目；

fj表示第j个配送中心的改建成本；

dij表示从需求点i到配送中心j的路程，

dij满足三角不等式性质：(1)dij≥0,(2)dij=dji,(3)dij≤dik+dkj;

cij表示从需求点i到配送中心j的单位运输成本。

在上述上层规划模型中，式（1）为上层规划的目标函数，表示设立配送中心的总成本最小，成本包括配送中心改造成本和运输成本两部分；式（2）表示至少有一个配送中心；式（3）、（4）表示yij,xj为

0-1变量。

（二） 配送中心选址的下层规划模型

在上层规划给定配送中心的选址方案后，下层规划主要考虑的是在给定方案下，如何在配送中心之间分配需求点才能使得因服务时间超时而造成的惩罚最小。这里假设，下层的主要目标是及时响应客户的服务请求，而如果服务超时，则会受到来自于上层的惩罚，因此作为下层来说，一旦给定了配送中心的方案，就要确定每个需求点对应哪个配送中心，才能在时效范围内取得物资满足客户需求，从而降低惩罚成本。因此以服务惩罚成本最小为目标，满足下层规划的约束，得到如下的配送中心选址的下层规划模型：

(L) Objective:minf(x,y)y=∑I i=1∑J j=1β(tij)yij（5）

st∑J j=1yij=1,i=1,2,…,I（6）

yij≤xj,i=1,2,…,I,j=1,2,…,J（7）

yij,xj∈0,1,i=1,2,…,I,j=1,2,…,J（8）

β(tij)=0,tij

a*tij-Li Ui-Li,tij∈［Li,Ui］,a为常数

M,tij>Ui,M为足够大正数? （9）

其中tij表示从配送中心j到需求点i所需要的时间，不同的时间反应了不同的服务

水平；

Li为需求点i最高服务水平的最长等待时间，即当配送时间小于Li，需求点的服务水平令人满意，不需要面临惩罚；

Ui为需求点i最差服务水平的最短等待时间，即一旦tij超过Ui，将面临M的惩罚，M为足够大整数也就是表示不允许出现这样的情况；

a表示惩罚系数， tij在Li和Ui之间时，会根据服务水平的高低受到不同程度的惩罚，需要说明的是，位于不同地理区域的需求点，对于时间的要求是不同的，因此Li和Ui是不同的。

在上述下层规划模型中，式（5）是下层规划的目标函数，表示需求点的总惩罚成本最低；式（6）～（9）为下层规划的约束条件，式（6）表示一个需求点只能由一个配送中心提供配送，式（7）、（8）表示yij,xj为0-1变量；式（9）为需求点所面临的惩罚函数［11］。

三、算法设计

双层规划问题是一个NP-hard问题［8］，即使是最简单的线性规划问题也很难求解。常用的精确算法和启发式算法都对双层规划问题有较高的要求，因此其应用就受到限制。而现代启发式算法（模拟退火、粒子群算法、遗传算法等）则因为对双层规划问题的要求条件不高而体现了其解决复杂双层规划问题的优势。

免疫遗传算法是将免疫理论和基本遗传算法的优点结合起来的一个交叉的优化算法［12］100-115。在保留遗传算法的全局寻优的搜索特性的基础上，又引入免疫算法的多样性产生和维持机制来保持群体的多样性，从而避免了遗传算法“早熟”的问题。

分析上述双层规划模型，看到配送中心的方案xj会由作为最终决策者的上层给出，然后下层会根据给定的方案，寻求对自己最优的需求分配方案yij。而下层的分配方案又会反馈给上层，从而上层对自己的方案进行调整，从而给出新的最优的方案，这个过程会一直反复，直到上下层均得到了比较满意的方案才会停止。根据这些特点，模型的求解转换成为求解在不同配送中心数目情况下，下层的分配方案，及相应上层的成本问题，然后找到不同配送中心数目情况下能够达到系统最优的方案。

（一） 解的编码方案

下层规划的一个解向量采用实数编码，解向量XL=(y1,y2,…,yJ)表示，配送中心方案。例如：某染色体编码方案X=3620，对应的方案的含义是确定第3、6和20个候选仓库为区域配送中心，其中染色体长度表示配送中心的数目。若该方案能够满足下层规划的约束条件，则X为一个可行解。

（二） 抗体的期望繁殖率

本文中下层规划的求解中，抗体的期望繁殖率［12］由抗体和抗原之间的亲和力和抗体浓度共同决定：

P=αA ∑A+(1－α)C ∑C

其中A表示抗体和抗原之间的亲和力，为目标函数的倒数；

C表示抗体浓度，即群体中相似抗体所占的比例。

（三） 免疫操作及操作终止

免疫操作包括选择，交叉和变异三种。本文选择轮盘赌的选择法，在当前群体中根据期望繁殖率找出优良的个体作为父代进一步繁殖，同时采用精英保留的方法，把表现最好的抗体放入记忆库，从而防止在免疫操作过程中最优解遗失。而交叉则是以一定的概率根据单点交叉算子对一对父代抗体中基因段交换而产生新的抗体；变异则是随机选择群体中的抗体，以变异概率改变其基因座上的基因值，从而为新个体的产生提供了机会。

当操作完成种群给定的迭代次数，或者连续若干代种群的平均适应度值没有变化时，操作终止。

四、算例

本文以某省电网企业物流网络的实际数据为算例。该企业现有的物流配送网络中由一级仓库为二级仓库提供电力物资供应，二级仓库又为基层的工作班组提供物资供应。在常规状态下，配送层级较多，管理复杂；当面临电力紧急抢修时，又容易出现配送混乱，延误配送时间，且一、二级仓库过多，运营成本高。因此该企业计划对现有的物流网络进行改造，将一二级仓库作为候选仓库，进行区域中心仓的选址，打造区域中心仓加班组的两层级配送网络。

该企业共有21个一级和二级仓库和146个班组，需要区域配送中心满足常规的物资补给和应急物资供应。候选仓库到各个班组的路程和时间数据如下所示：

表1候选仓库与班组之间的路程表（单位：公里）

候选仓库

班组 候选仓库1 候选

仓库2 候选

仓库3 候选

仓库4 候选

仓库5 … 候选

仓库20 候选

仓库21

班组1 1890011700126001980015600… 2320012900

班组2 115001840088302370021500… 1910026200

班组3 1390010600164001380013900… 1290014600

班组4 244006600180001460010500… 180006710

班组5 141001690077002490020800… 2830018100

班组6 23400122002970047608280… 309014900

… … … … … … … … …

班组145 160002580096602550029600… 2090027000

班组146 2020012900138001610016100… 1510016800

表2候选仓库与班组之间的时间表（单位：小时）

候选仓库

班组 候选仓库1 候选

仓库2 候选

仓库3 候选

仓库4 候选

仓库5 … 候选

仓库20 候选

仓库21

班组1 280172190302225… 308237

班组2 282418198525478… 432497

班组3 333245345367313… 292355

班组4 355105265238162… 245168

班组5 218240130375297… 380308

班组6 323183412113142… 055227

… … … … … … … … …

班组145 313460227575513… 482525

班组146 363302277422368… 348410

对于电力抢修来说，位于不同地点的班组，响应时限的要求是不同的，如经济发达地区和人口密集区域电力中断的损失比较大，对于抢修时限要求也很高；而相对不发达地区，抢修时限的要求相对较低；对于经济落后、偏远、人口稀少地区来说，电力中断损失比较小，同时由于交通状况较差，对抢修时效的要求最低。不同地区所面临的服务惩罚的时限如表3所示：

根据模型中惩罚函数及表2、表3中的数据，可以得到每个班组选择不同仓库时所面临的服务惩罚系数，部分数据如表4所示：

表3班组的服务时限表（单位：小时）

不受惩罚的

最长时间Li 受最大惩罚的

最短时间Ui

位于城区的班组 12

位于郊区的班组 2 4

位于偏远地区的班组 3 6

表4班组的服务惩罚系数表

候选仓库

班组 候选仓库1 候选仓库2 候选仓库3 候选仓库4 候选仓库5 … 候选仓库20 候选仓库21

班组1 100000072090100000100000… 100000100000

班组2 100000100000098100000100000… 100000100000

班组3 100000100000100000100000100000… 100000100000

班组4 100000005100000100000062… 100000068

班组5 100000100000030100000100000… 100000100000

班组6 100000083100000013042… 000100000

… … … … … … … … …

班组145 004053000092071… 061075

班组146 021001000041023… 016037

表5双层规划的求解结果

区域配送中心数目 方案 上层目标函数值 下层目标函数值

2个 方案1：仓库1和17 2177712 70150

方案2：仓库11和20 2060026 60162

3个

方案3：仓库1、6和15 2679393 10135

3个

方案4：仓库3、16和17 2497776 20101

方案5：仓库10、11和20 2455622 10164

4个 方案6：仓库1、16、17和19 2886025 85400

方案7：仓库3、16、17和18 2952621 81100

方案8：仓库3、6、17和18 3093082 84900

方案9：仓库2、3、16和18 3124313 90400

方案10：仓库3、16、17和20 3172587 86200

方案11：仓库3、10、17和18 2952321 85300

5个 方案12：仓库1、16、17、19和203353413 57500

6个 方案13：仓库3、7、8、10、16和18 4003362 28400

7个 方案14：仓库3、7、8、10、16、18和20 4496780 18100

不同的仓库改造成为区域中心仓库的成本是不同，一级仓库改建的成本较高，为4000万，二级仓库改建的成本相对较低，为3000万，但是在计算过程中，改建成本远远高于配送成本和服务惩罚成本，因此对改建成本进行处理，按照50年使用期分摊到每个月，在模型中使用月平均改建成本。由配送中心向位于不同区域的班组进行配送时，配送成本分别为5元/每公里车次（位于城区的班组），8元/每公里车次（位于郊区的班组），10元/每公里车次（位于偏远地区的班组）。为了计算方便，惩罚系数设为1。

本文采用Matlab2012a编写求解双层规划的免疫遗传程序，相关参数设置如下：最大迭代次数为1000，种群规模为50，记忆库容量为10，交叉概率为06，变异概率为03，多样性评价参数为095。对不同配送中心数目的情况下运行20次，计算各自的上下层目标值，其中1个配送中心的情况下，下层目标函数值很大，即有较多的班组由于无法满足响应时限而面临很高度惩罚惩罚，因此不考虑其作为最佳方案。在给定配送中心数目的情况下，首先求解下层规划，得到班组的服务分配方案，再对上层规划求解，得到的结果如表5所示：

从表5中我们可以看到，当配送中心数目小于3时，总是有班组无法满足时限约束。而当配送中心数目增加到4时，下层的目标函数有了大幅度的下降，所有的班组都可以有效满足服务的响应时限不必承担过高的服务惩罚成本。但当配送中心的数目继续增加时，服务惩罚成本下降的幅度却比较小，且改建成本更多。综合考虑上下层的目标，4个配送中心是最佳的选择，其中方案7，即将仓库3、仓库16、仓库17和仓库18改建为区域中心仓，为最佳方案（不同的决策者由于对上下层目标的重视程度不同，可能选定的最佳方案会不同）。方案7的区域配送中心与班组之间的电力物资供应方案如下表6所示：

表6区域配送中心与班组之间的电力物资供应方案

配送中心数目 仓库序号 仓库对应的班组序号

4个 仓库3 2、5、7、16、17、18、29、43、65、66、67、68、74、76、77、78、79、80、96、99、100、101、102、103、104、105、106、107、114、116、128、134、135、136、140、141、142、143、144、145、146

仓库16 3、13、14、15、49、69、70、71、72、73、75、82、83、86、119、120、121、122

仓库17 1、4、6、10、19、20、21、22、23、24、25、26、27、28、30、31、32、33、34、35、36、37、38、39、40、41、42、44、45、46、47、48、50、51、52、53、54、55、56、57、58、59、60、61、62、63、64、81、87、88、89、90、91、92、93、94、108、109、110、111、112、113、115、117、118、123、124、125、126、127、129、130、131、132、133、137、138、139

仓库18 8、9、11、12、84、85、95、97、98

五、结论

本文从区域配送中心的选址的实际问题出发，充分考虑了在决策过程中处于企业上层和下层双方的利益，深入分析了两者之间的有机联系，建立了上层目标为成本最小和下层目标为服务惩罚最小的双层规划模型，从而更符合实际情况。本文在模型基础上提出了求解较大规模问题的免疫遗传算法，并通过某电网企业的电力物资配送网络的实际数据和面临的选址问题为算例，对双层规划模型进行了求解，验证了该模型及免疫遗传算法是可行有效的，为实际的配送中心选址提供决策的依据，避免了盲目决策。算例研究结果显示，在服务响应时效的约束下，随着配送中心数目的增加，各个班组的响应能力增强，响应时间缩短，同时由于未能及时响应而造成的惩罚成本减小，但当数目增加到一定程度，这种成本的减小就不明显了，相反因配送中心数目增多而带来的成本就快速增加，且配送中心的利用效率降低。因此必须设置一定数目的配送中心保证能够满足响应时效的要求，同时配送中心的利用效率不会过低，并承担由此带来的上层成本（包括固定改建成本和配送成本）的增加。

在构建该双层规划模型的时候，考虑的约束条件较少，主要是响应时效的约束，而在实际的选址决策中，所需要考虑到约束条件是比较多的，如配送中心的容量约束，班组的需求量等，因此需要进一步对该模型进行扩展和完善，从而提高其实际应用性。

参考文献：

［1］Owen S·H, Daskin M·S Strategic facility location: A review ［J］.European Journal of Operational Research，1998，3: 423-447

［2］ReVelle C·S, Eiselt H·A Location analysis: A synthesis and survey［J］. European Journal of Operational Research，2005，165: 1-19

［3］Snyder L·V Facility location under uncertainty: A review［J］. IIE Transactions， 2006，38: 547-564

［4］Taniguchi E, Noritake M, Yamada T，et al Optimal size and location planning of public logistics terminals［J］. Transportation Research Part E: Logistics and Transportation Review，1999，35: 207-222

［5］孙会君, 高自友 考虑路线安排的物流配送中心选址双层规划模型及求解算法［J］. 中国公路学报， 2003 (02): 116-120

［6］Sun H, Gao Z, Wu J A bi-level programming model and solution algorithm for the location of logistics distribution centers［J］. Applied mathematical modelling， 2005，32: 610-616

［7］胡长英, 刘国山 基于环境角度的双层选址优化模型［J］. 中国管理科学，2007(15): 59-62

［8］Ben-Ayed O, Boyce D·E, Blair C·E A general bilevel linear programming formulation of the network design problem［J］. Transportation Research Part B: Methodological，1988，22: 311-318

［9］李相勇, 田澎 双层规划问题的粒子群算法研究［J］. 管理科学学报， 2008 (5): 41-52

［10］Maric＇ M, Stanimirovic＇ Z, Milenkovic＇ N Metaheuristic methods for solving the Bilevel Uncapacitated Facility Location Problem with Clients Preferences［J］. Electronic Notes in Discrete Mathematics， 2012，39：43-50

［11］马云峰, 杨超, 张敏,等 基于时间满意的最大覆盖选址问题［J］. 中国管理科学，2006 (02): 45-51

［12］史峰, 王辉, 郁磊，等 MATLAB 智能算法 30+ 案倒分析［M］. 北京：北京航空航天大学出版社，2010

Bilevel Model for the Distribution Center Location Problem

with Service Punishment

QING Yanhua, ZUO Xiaode

(School of management, Jinan University, Guangzhou 510632, Guangdong, China)

Abstract: From the perspective of system, the paper analyzes the relationship between the upper and lower of logistics enterprises in the decisionmaking process of distribution center location, and carries out indepth analysis of the objectives, constraints and interaction between these two levels. On the basis of above analysis, the paper builds a bilevel programming model. The objective of the upper model is to minimize the total cost (including reconstruction costs and distribution costs), and the objective of the lower model is to minimize the service punishment cost caused by the failed service response. According to the models characteristics, the above issue is equivalently to solve the optimal solutions for the upper and lower under the different numbers of distribution centers, and ultimately determines the solution of bilevel programming model. Due to the fact that bilevel programming problem is a NP hard problem, the paper uses the immune genetic algorithm to solve this problem. Finally，the practicality and effectiveness of the proposed model and the algorithm are verified by an example of a power grid company with actual data.

Keywords: service punishment; bilevel programming; immune genetic algorithm

（责任编辑：邓泽辉）

在构建该双层规划模型的时候，考虑的约束条件较少，主要是响应时效的约束，而在实际的选址决策中，所需要考虑到约束条件是比较多的，如配送中心的容量约束，班组的需求量等，因此需要进一步对该模型进行扩展和完善，从而提高其实际应用性。

参考文献：

［1］Owen S·H, Daskin M·S Strategic facility location: A review ［J］.European Journal of Operational Research，1998，3: 423-447

［2］ReVelle C·S, Eiselt H·A Location analysis: A synthesis and survey［J］. European Journal of Operational Research，2005，165: 1-19

［3］Snyder L·V Facility location under uncertainty: A review［J］. IIE Transactions， 2006，38: 547-564

［4］Taniguchi E, Noritake M, Yamada T，et al Optimal size and location planning of public logistics terminals［J］. Transportation Research Part E: Logistics and Transportation Review，1999，35: 207-222

［5］孙会君, 高自友 考虑路线安排的物流配送中心选址双层规划模型及求解算法［J］. 中国公路学报， 2003 (02): 116-120

［6］Sun H, Gao Z, Wu J A bi-level programming model and solution algorithm for the location of logistics distribution centers［J］. Applied mathematical modelling， 2005，32: 610-616

［7］胡长英, 刘国山 基于环境角度的双层选址优化模型［J］. 中国管理科学，2007(15): 59-62

［8］Ben-Ayed O, Boyce D·E, Blair C·E A general bilevel linear programming formulation of the network design problem［J］. Transportation Research Part B: Methodological，1988，22: 311-318

［9］李相勇, 田澎 双层规划问题的粒子群算法研究［J］. 管理科学学报， 2008 (5): 41-52

［10］Maric＇ M, Stanimirovic＇ Z, Milenkovic＇ N Metaheuristic methods for solving the Bilevel Uncapacitated Facility Location Problem with Clients Preferences［J］. Electronic Notes in Discrete Mathematics， 2012，39：43-50

［11］马云峰, 杨超, 张敏,等 基于时间满意的最大覆盖选址问题［J］. 中国管理科学，2006 (02): 45-51

［12］史峰, 王辉, 郁磊，等 MATLAB 智能算法 30+ 案倒分析［M］. 北京：北京航空航天大学出版社，2010

Bilevel Model for the Distribution Center Location Problem

with Service Punishment

QING Yanhua, ZUO Xiaode

(School of management, Jinan University, Guangzhou 510632, Guangdong, China)

Abstract: From the perspective of system, the paper analyzes the relationship between the upper and lower of logistics enterprises in the decisionmaking process of distribution center location, and carries out indepth analysis of the objectives, constraints and interaction between these two levels. On the basis of above analysis, the paper builds a bilevel programming model. The objective of the upper model is to minimize the total cost (including reconstruction costs and distribution costs), and the objective of the lower model is to minimize the service punishment cost caused by the failed service response. According to the models characteristics, the above issue is equivalently to solve the optimal solutions for the upper and lower under the different numbers of distribution centers, and ultimately determines the solution of bilevel programming model. Due to the fact that bilevel programming problem is a NP hard problem, the paper uses the immune genetic algorithm to solve this problem. Finally，the practicality and effectiveness of the proposed model and the algorithm are verified by an example of a power grid company with actual data.

Keywords: service punishment; bilevel programming; immune genetic algorithm

（责任编辑：邓泽辉）

在构建该双层规划模型的时候，考虑的约束条件较少，主要是响应时效的约束，而在实际的选址决策中，所需要考虑到约束条件是比较多的，如配送中心的容量约束，班组的需求量等，因此需要进一步对该模型进行扩展和完善，从而提高其实际应用性。

参考文献：

［1］Owen S·H, Daskin M·S Strategic facility location: A review ［J］.European Journal of Operational Research，1998，3: 423-447

［2］ReVelle C·S, Eiselt H·A Location analysis: A synthesis and survey［J］. European Journal of Operational Research，2005，165: 1-19

［3］Snyder L·V Facility location under uncertainty: A review［J］. IIE Transactions， 2006，38: 547-564

［4］Taniguchi E, Noritake M, Yamada T，et al Optimal size and location planning of public logistics terminals［J］. Transportation Research Part E: Logistics and Transportation Review，1999，35: 207-222

［5］孙会君, 高自友 考虑路线安排的物流配送中心选址双层规划模型及求解算法［J］. 中国公路学报， 2003 (02): 116-120

［6］Sun H, Gao Z, Wu J A bi-level programming model and solution algorithm for the location of logistics distribution centers［J］. Applied mathematical modelling， 2005，32: 610-616

［7］胡长英, 刘国山 基于环境角度的双层选址优化模型［J］. 中国管理科学，2007(15): 59-62

［8］Ben-Ayed O, Boyce D·E, Blair C·E A general bilevel linear programming formulation of the network design problem［J］. Transportation Research Part B: Methodological，1988，22: 311-318

［9］李相勇, 田澎 双层规划问题的粒子群算法研究［J］. 管理科学学报， 2008 (5): 41-52

［10］Maric＇ M, Stanimirovic＇ Z, Milenkovic＇ N Metaheuristic methods for solving the Bilevel Uncapacitated Facility Location Problem with Clients Preferences［J］. Electronic Notes in Discrete Mathematics， 2012，39：43-50

［11］马云峰, 杨超, 张敏,等 基于时间满意的最大覆盖选址问题［J］. 中国管理科学，2006 (02): 45-51

［12］史峰, 王辉, 郁磊，等 MATLAB 智能算法 30+ 案倒分析［M］. 北京：北京航空航天大学出版社，2010

Bilevel Model for the Distribution Center Location Problem

with Service Punishment

QING Yanhua, ZUO Xiaode

(School of management, Jinan University, Guangzhou 510632, Guangdong, China)

Abstract: From the perspective of system, the paper analyzes the relationship between the upper and lower of logistics enterprises in the decisionmaking process of distribution center location, and carries out indepth analysis of the objectives, constraints and interaction between these two levels. On the basis of above analysis, the paper builds a bilevel programming model. The objective of the upper model is to minimize the total cost (including reconstruction costs and distribution costs), and the objective of the lower model is to minimize the service punishment cost caused by the failed service response. According to the models characteristics, the above issue is equivalently to solve the optimal solutions for the upper and lower under the different numbers of distribution centers, and ultimately determines the solution of bilevel programming model. Due to the fact that bilevel programming problem is a NP hard problem, the paper uses the immune genetic algorithm to solve this problem. Finally，the practicality and effectiveness of the proposed model and the algorithm are verified by an example of a power grid company with actual data.

Keywords: service punishment; bilevel programming; immune genetic algorithm

（责任编辑：邓泽辉）