校园自动售卖机的选址问题

余瑞丰

摘 要：探讨了校园自动售卖机的选址优化模型，并对模型进行分析并给出了求解算法，最后通过案例展示了其在现实中的应用。

关键词：选址优化模型；自动售卖机；成本最小化

当今，人们的生活因科技发展而愈加便捷，而这个社会也正以满足人们的物质文化需求为目标之一快速向前迈进。作为一名高中生，生活在已然成为自己第二个家的校园中，我深深地感受到同学们对一些物品的消费欲望日益增长，而小卖部早已不能满足同学们的需求。因此，自动售卖机的推广成了很好的选择，它既能满足同学们的消费需求，方便同学们的生活，也能为开展此项目的学生带来利润，可谓是双赢之举。但究竟在哪里设置自动售卖机，才能在最大限度地满足所有学生需求的前提下，获得可观的利润呢？这里，便介绍一种具有可操作性的校园自动售货机选址优化模型。

一、问题准备与分析

作为校园自动售卖机的运营商，自动售卖机选址的主要目标是既能方便学生购物，又使得收益最大，所以考虑利用优化模型来进行选址优化。应考虑以下两个方面的内容，一是成本因素，即自动售卖机的数量尽可能少，另一方面自动售卖机能覆盖尽量多的需求点。

二、模型建立与求解

根据对实际情况的分析，我做出以下假设：

1.问题假设

（1）对自动售卖机商品的需求量D与该地点的人流量N成正比，比例系数为k，即D=kN

且对于不同消费群体，比例系数k值不同，则ki（i=1，2）分别表示该学校的初中部和高中部。

（2）售卖机商品的数量与种类已选择好，不在本文考虑范

围内。

（3）每个自动售卖机的服务能力是有限的，其服务能力就为其可服务半径。

（4）记可放置自动售货机的区域的地点的集合为M={1，2，…m}，即排除客观条件不允许的区域，如操场、楼道间等。

2.决策变量

（1）设yi为0-1变量，表示是否在第i点设置自动售卖机。yi=1，表示在i点设置售卖机；yi=0，表示不在i点设置售卖机，i∈M；

（2）xij表示第i个售卖机在地点的需求量。

3.目标函数

（1）目标即总成本最小，即自动售卖机的总数量尽可能少，可表示为：minyi

（2）尽量满足学生的需求，即覆盖的服务面积尽可能大，则可表示为：maxxij

4.约束条件

（1）每一个自动售卖机设置点，其被分配的需要满足的需求总和不能超过其相应的服务能力，即xij≤Ciyi，i∈M

（2）对于一个需求点，其分配一个售卖机的需求量必须大于等于0，小于其总需求量D，即Dj≥xij≥0，i∈M，j∈N

5.模型建立

综上，可建立优化模型如下：

minyi

maxxij

s.t.xij≤Ciyi，i∈M

Dj≥xij≥0，i∈M，j∈N

yi∈{0，1}

三、求解算法

第一步：初始化。令所有的xj=0，yi=0，xi=xij=0（已分配的需求），并确定集合A（i）和集合B（j），其中A（i）-设施节点i可以覆盖的需求点j的集合，B（j）-可以覆盖需求节点j的设施节点i的集合；

第二步：选择下一个设施点。在M中选择yi=0，且A（i）的规模为最大的点i′为设施点，即A（i′）=max{A（i）}，令xi′=1，并在M集合中剔除节点i′，即M=M＼{i′}

第三步：确定节点i′的覆盖范围。将A（i′）中的元素按B（j）的規模从小到大的顺序指派给i′，直至i′的容量为Ci′=0或A（i）为空。其中对于j∈A（i′）且，xj≤Dj，将j支配给i′的方法为：若Dj-xj≤Ci′，则令xi′j=Dj-xj，Ci′=Ci′-（Dj-xj），xj=1，在A（i′）和N中剔除需求点j。若Dj-xj>Ci，则令xij=Ci，xj=xj+xij，Ci′=0

第四步：若N或M为空，停止；否则，更新集合A（i）和集合

B（j），转第二步。

执行完上述算法后，被选定的可放置自动售卖机的地点就为最终的选择地点。

四、数值模拟

以某学校为例，自动售卖机项目的同学们想要确定自动售卖机的放置位置，以为选出的5个需求量最大的地点服务，已知这6个需求点的位置如图，除第2个需求点外，其他地点都可作为自动售卖机的选择地，已知经调查，一般情况下，当一个学生距一个自动售卖机的距离不超过600米时，学生才会有购买的意愿，设置数量最少的自动售卖机以节约成本，同时又满足所有需求点的需求，应如何规划？

注：一般来讲，在校园中，一个自动售货机的服务能力应大于其服务半径所能覆盖的所有需求点的需求之和，而通常不会出现一个需求点的需求量被分配给不同售卖机的情况，而自动售卖机的服务能力是由其货物的数量与种类决定的，事先已根据需求量调整好，故这里不考虑需求量被分配给多个自动售卖机的情况。

根据求解算法：

第一步，初始化

确定一个设施点。因为A（5）={3，5，6}，A（5）=6为最大，故首先选取I′=5。由于无容量约束故依次指派5，6，3点归节点4服务。

第三步，更新。此时，N={1，2，4}，M={1，3，4，6}，更新集合A（i）和集合B（j）后如下表所示。

第四步，确定一个设施点。因为A（1）={2，1}，A（4）={2，4}，A（1）=A（4）=2为最大，故随机选取i′=1，并且1，2两点归节点1服务。

第五步，更新。此时，N={4}，M={3，4，6}，更新集合A（i）和集合B（j）后如下表所示。

第六步，确定一个设施点。因为A（4）={24}，A（4）=1为最大，故首先选取i′=4，并且4点归节点4服务。

第七步，更新。此时，N={}，M={3，6}，结束。

因此，计算结果为（5，1，4）。

由以上的分析可知，利用此选址优化模型与求解算法进行选址不失为一种好方法。这种方法以用最少数量的自动贩卖机来覆盖所有既定需求点为原则，在考虑了客观限制条件后，找到了较为方便的算法，使问题易于求解。而由于校园自动售卖机已逐渐在校园中流行起来，自动售卖机选址问题的优化模型也会愈来愈受到关注，同时也为学校自动售卖机设置提供了科学依据。

参考文献：

[1]李梦瑶，金海月，裴晓旭，等.大学校园自动贩卖机使用情况的调查报告：以延边大学为例[J].科教导刊（中旬刊），2014（9）.

[2]张晓楠，范厚明，李剑锋.B2C物流配送网络双目标模糊选址模型与算法[J].系统工程理论与实践，2015（5）.

[3]乔联宝.应急服务设施的排队最大覆盖选址模型与算法研究[D].南京大学，2013.

？誗编辑 李琴芳endprint