校園自動售賣機的選址問題

余瑞豐

摘 要：探討了校園自動售賣機的選址優化模型，并對模型進行分析并給出了求解算法，最后通過案例展示了其在現實中的應用。

關鍵詞：選址優化模型；自動售賣機；成本最小化

當今，人們的生活因科技發展而愈加便捷，而這個社會也正以滿足人們的物質文化需求為目標之一快速向前邁進。作為一名高中生，生活在已然成為自己第二個家的校園中，我深深地感受到同學們對一些物品的消費欲望日益增長，而小賣部早已不能滿足同學們的需求。因此，自動售賣機的推廣成了很好的選擇，它既能滿足同學們的消費需求，方便同學們的生活，也能為開展此項目的學生帶來利潤，可謂是雙贏之舉。但究竟在哪里設置自動售賣機，才能在最大限度地滿足所有學生需求的前提下，獲得可觀的利潤呢？這里，便介紹一種具有可操作性的校園自動售貨機選址優化模型。

一、問題準備與分析

作為校園自動售賣機的運營商，自動售賣機選址的主要目標是既能方便學生購物，又使得收益最大，所以考慮利用優化模型來進行選址優化。應考慮以下兩個方面的內容，一是成本因素，即自動售賣機的數量盡可能少，另一方面自動售賣機能覆蓋盡量多的需求點。

二、模型建立與求解

根據對實際情況的分析，我做出以下假設：

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