校園自動(dòng)售賣機(jī)的選址問題

余瑞豐

摘 要：探討了校園自動(dòng)售賣機(jī)的選址優(yōu)化模型，并對(duì)模型進(jìn)行分析并給出了求解算法，最后通過案例展示了其在現(xiàn)實(shí)中的應(yīng)用。

關(guān)鍵詞：選址優(yōu)化模型；自動(dòng)售賣機(jī)；成本最小化

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

一、問題準(zhǔn)備與分析

作為校園自動(dòng)售賣機(jī)的運(yùn)營(yíng)商，自動(dòng)售賣機(jī)選址的主要目標(biāo)是既能方便學(xué)生購物，又使得收益最大，所以考慮利用優(yōu)化模型來進(jìn)行選址優(yōu)化。應(yīng)考慮以下兩個(gè)方面的內(nèi)容，一是成本因素，即自動(dòng)售賣機(jī)的數(shù)量盡可能少，另一方面自動(dòng)售賣機(jī)能覆蓋盡量多的需求點(diǎn)。

二、模型建立與求解

根據(jù)對(duì)實(shí)際情況的分析，我做出以下假設(shè)：

1.問題假設(shè)

（1）對(duì)自動(dòng)售賣機(jī)商品的需求量D與該地點(diǎn)的人流量N成正比，比例系數(shù)為k，即D=kN

且對(duì)于不同消費(fèi)群體，比例系數(shù)k值不同，則ki（i=1，2）分別表示該學(xué)校的初中部和高中部。

（2）售賣機(jī)商品的數(shù)量與種類已選擇好，不在本文考慮范

圍內(nèi)。

（3）每個(gè)自動(dòng)售賣機(jī)的服務(wù)能力是有限的，其服務(wù)能力就為其可服務(wù)半徑。

（4）記可放置自動(dòng)售貨機(jī)的區(qū)域的地點(diǎn)的集合為M={1，2，…m}，即排除客觀條件不允許的區(qū)域，如操場(chǎng)、樓道間等。

2.決策變量

（1）設(shè)yi為0-1變量，表示是否在第i點(diǎn)設(shè)置自動(dòng)售賣機(jī)。yi=1，表示在i點(diǎn)設(shè)置售賣機(jī)；yi=0，表示不在i點(diǎn)設(shè)置售賣機(jī)，i∈M；

（2）xij表示第i個(gè)售賣機(jī)在地點(diǎn)的需求量。

3.目標(biāo)函數(shù)

（1）目標(biāo)即總成本最小，即自動(dòng)售賣機(jī)的總數(shù)量盡可能少，可表示為：minyi

（2）盡量滿足學(xué)生的需求，即覆蓋的服務(wù)面積盡可能大，則可表示為：maxxij

4.約束條件

（1）每一個(gè)自動(dòng)售賣機(jī)設(shè)置點(diǎn)，其被分配的需要滿足的需求總和不能超過其相應(yīng)的服務(wù)能力，即xij≤Ciyi，i∈M

（2）對(duì)于一個(gè)需求點(diǎn)，其分配一個(gè)售賣機(jī)的需求量必須大于等于0，小于其總需求量D，即Dj≥xij≥0，i∈M，j∈N

5.模型建立

綜上，可建立優(yōu)化模型如下：

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）-設(shè)施節(jié)點(diǎn)i可以覆蓋的需求點(diǎn)j的集合，B（j）-可以覆蓋需求節(jié)點(diǎn)j的設(shè)施節(jié)點(diǎn)i的集合；

第二步：選擇下一個(gè)設(shè)施點(diǎn)。在M中選擇yi=0，且A（i）的規(guī)模為最大的點(diǎn)i′為設(shè)施點(diǎn)，即A（i′）=max{A（i）}，令xi′=1，并在M集合中剔除節(jié)點(diǎn)i′，即M=M＼{i′}

第三步：確定節(jié)點(diǎn)i′的覆蓋范圍。將A（i′）中的元素按B（j）的規(guī)模從小到大的順序指派給i′，直至i′的容量為Ci′=0或A（i）為空。其中對(duì)于j∈A（i′）且，xj≤Dj，將j支配給i′的方法為：若Dj-xj≤Ci′，則令xi′j=Dj-xj，Ci′=Ci′-（Dj-xj），xj=1，在A（i′）和N中剔除需求點(diǎn)j。若Dj-xj>Ci，則令xij=Ci，xj=xj+xij，Ci′=0

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

B（j），轉(zhuǎn)第二步。

執(zhí)行完上述算法后，被選定的可放置自動(dòng)售賣機(jī)的地點(diǎn)就為最終的選擇地點(diǎn)。

四、數(shù)值模擬

以某學(xué)校為例，自動(dòng)售賣機(jī)項(xiàng)目的同學(xué)們想要確定自動(dòng)售賣機(jī)的放置位置，以為選出的5個(gè)需求量最大的地點(diǎn)服務(wù)，已知這6個(gè)需求點(diǎn)的位置如圖，除第2個(gè)需求點(diǎn)外，其他地點(diǎn)都可作為自動(dòng)售賣機(jī)的選擇地，已知經(jīng)調(diào)查，一般情況下，當(dāng)一個(gè)學(xué)生距一個(gè)自動(dòng)售賣機(jī)的距離不超過600米時(shí)，學(xué)生才會(huì)有購買的意愿，設(shè)置數(shù)量最少的自動(dòng)售賣機(jī)以節(jié)約成本，同時(shí)又滿足所有需求點(diǎn)的需求，應(yīng)如何規(guī)劃？

注：一般來講，在校園中，一個(gè)自動(dòng)售貨機(jī)的服務(wù)能力應(yīng)大于其服務(wù)半徑所能覆蓋的所有需求點(diǎn)的需求之和，而通常不會(huì)出現(xiàn)一個(gè)需求點(diǎn)的需求量被分配給不同售賣機(jī)的情況，而自動(dòng)售賣機(jī)的服務(wù)能力是由其貨物的數(shù)量與種類決定的，事先已根據(jù)需求量調(diào)整好，故這里不考慮需求量被分配給多個(gè)自動(dòng)售賣機(jī)的情況。

根據(jù)求解算法：

第一步，初始化

確定一個(gè)設(shè)施點(diǎn)。因?yàn)锳（5）={3，5，6}，A（5）=6為最大，故首先選取I′=5。由于無容量約束故依次指派5，6，3點(diǎn)歸節(jié)點(diǎn)4服務(wù)。

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

第四步，確定一個(gè)設(shè)施點(diǎn)。因?yàn)锳（1）={2，1}，A（4）={2，4}，A（1）=A（4）=2為最大，故隨機(jī)選取i′=1，并且1，2兩點(diǎn)歸節(jié)點(diǎn)1服務(wù)。

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

第六步，確定一個(gè)設(shè)施點(diǎn)。因?yàn)锳（4）={24}，A（4）=1為最大，故首先選取i′=4，并且4點(diǎn)歸節(jié)點(diǎn)4服務(wù)。

第七步，更新。此時(shí)，N={}，M={3，6}，結(jié)束。

因此，計(jì)算結(jié)果為（5，1，4）。

由以上的分析可知，利用此選址優(yōu)化模型與求解算法進(jìn)行選址不失為一種好方法。這種方法以用最少數(shù)量的自動(dòng)販賣機(jī)來覆蓋所有既定需求點(diǎn)為原則，在考慮了客觀限制條件后，找到了較為方便的算法，使問題易于求解。而由于校園自動(dòng)售賣機(jī)已逐漸在校園中流行起來，自動(dòng)售賣機(jī)選址問題的優(yōu)化模型也會(huì)愈來愈受到關(guān)注，同時(shí)也為學(xué)校自動(dòng)售賣機(jī)設(shè)置提供了科學(xué)依據(jù)。

參考文獻(xiàn)：

[1]李夢(mèng)瑤，金海月，裴曉旭，等.大學(xué)校園自動(dòng)販賣機(jī)使用情況的調(diào)查報(bào)告：以延邊大學(xué)為例[J].科教導(dǎo)刊（中旬刊），2014（9）.

[2]張曉楠，范厚明，李劍鋒.B2C物流配送網(wǎng)絡(luò)雙目標(biāo)模糊選址模型與算法[J].系統(tǒng)工程理論與實(shí)踐，2015（5）.

[3]喬聯(lián)寶.應(yīng)急服務(wù)設(shè)施的排隊(duì)最大覆蓋選址模型與算法研究[D].南京大學(xué)，2013.

？誗編輯 李琴芳endprint