河北科技大學(xué)打印室選址優(yōu)化

1、目錄 TOC o 1-5 h z HYPERLINK l bookmark6 o Current Document 1研究的問題及意義21.1研究的問題21.2研究的意義2 HYPERLINK l bookmark12 o Current Document 科大校內(nèi)打印室選址設(shè)計(jì)3 HYPERLINK l bookmark15 o Current Document 2.1候選點(diǎn)的選擇3 HYPERLINK l bookmark18 o Current Document 2.2 方案的選擇及求解4 HYPERLINK l bookmark42 o Current Document 2.3優(yōu)化前后

2、的選址比較10 HYPERLINK l bookmark47 o Current Document 可行性分析114可行性分析125總結(jié)13 HYPERLINK l bookmark53 o Current Document 參考文獻(xiàn)141.研究的問題及意義1.1研究的問題2012年9月，理工學(xué)院師生整體搬遷全新校區(qū)。為了保證正常的教學(xué)秩序， 河北科技大學(xué)完成了理工生活區(qū)，南公教，學(xué)生三食堂的建設(shè)并投入使用，并且 各方面服務(wù)措施正在逐步完善。然而隨著學(xué)生容量的增加，同學(xué)們深刻體會(huì)到打 印復(fù)印越來越難。當(dāng)同學(xué)們需打印復(fù)印作業(yè)，資料時(shí)，往往需要絞盡腦汁，有的 甚至為了打印辛辛苦苦跑到西門或南門。針

3、對(duì)此問題，我們小組兩人于11月16 日分別在生活廣場(chǎng)，公共教學(xué)樓，南公教，理工生活區(qū)四大區(qū)域就“您認(rèn)為我校 打印室建設(shè)是否合理？”“不合理之處在哪？ ”“您希望打印室建在哪里更方便同 學(xué)？ ”進(jìn)行了隨機(jī)調(diào)查，結(jié)果顯示87%的同學(xué)認(rèn)為打印室分布不合理，具體問題 匯總?cè)缦拢?、公教D座與F座打印室距離較近，經(jīng)常出現(xiàn)供大于求，打印室機(jī)器閑置 的現(xiàn)象；2、理工生活區(qū)無打印室，致使學(xué)生復(fù)印文件極其不方便，通常走很遠(yuǎn)的路 或直接去校外打印，造成了很大的客源流失；3、由于浴池附近的學(xué)生比較密集，浴池附近的打印室經(jīng)常出現(xiàn)供小于求的 現(xiàn)狀，致使在打印文件的過程中，經(jīng)常出現(xiàn)排隊(duì)半個(gè)小時(shí)但還不能完成打印的現(xiàn) 象。1

4、.2研究的意義基于上述問題，我們對(duì)河北科技大學(xué)打印室選址進(jìn)行了優(yōu)化。合理的打印室 布局，不僅使學(xué)生們享受到快速的服務(wù)，避免其在打印過程中時(shí)間的浪費(fèi)，也為 學(xué)生們提供了一個(gè)高效愉悅的學(xué)習(xí)生活環(huán)境；并且合理的打印室布局，也避免了 學(xué)校打印室總客源的流失，提高打印室工作人員的工作效率，以及打印室機(jī)器的 利用率，進(jìn)一步提高整體收益。2 科大校內(nèi)打印室選址設(shè)計(jì)21候選點(diǎn)的選擇根據(jù)同學(xué)們上課和休息集中地，在已有的六個(gè)打印室基礎(chǔ)上，即：浴池、公 交樓D座、F座、建工樓、圖書館和材料樓，我們?cè)黾恿藘蓚€(gè)備選點(diǎn)，這兩個(gè)備 選點(diǎn)的選擇是經(jīng)過我們慎重考慮的，首先必須符合學(xué)校的規(guī)定，其次是根據(jù)同學(xué) 們需求的權(quán)重?？紤]到

5、打印室建在學(xué)校餐廳附近更加容易滿足需求，而且能夠成 功的降低前期的投入成本，所以最后選擇的兩個(gè)備選點(diǎn)為：名族餐廳和理工餐廳。 以便于同學(xué)們更方便的打印和復(fù)制文件。圖2.1候選點(diǎn)分布圖選址代號(hào)：1.浴池2.名族餐廳3.公教樓D座4.公教樓F座5.建工樓6.圖書館7.材料樓8.理工餐廳2.2方案的選擇及求解（一）方案的選擇為了盡可能的不增加成本所造成的影響，我們決定將這次課程設(shè)計(jì)的主要 方向確立為調(diào)節(jié)打印室的位置，而不是改變打印室的數(shù)量。我們?cè)黾雍蜻x點(diǎn)只是 為了通過一次次的篩選，最終決定留下最為合適的打印室地址，能夠最大程度的 滿足大學(xué)生們的打印需求。綜合考慮我們學(xué)過的物流選址模型：交叉中值法、集

6、 合覆蓋法、P一中值等。我們最終確立P一中值模型為最為恰當(dāng)?shù)姆椒?。（二）P一中值模型介紹P-中值模型是指在一個(gè)給定數(shù)量和位置的需求集合和一個(gè)候選設(shè)施位置的 集合下，分別為p個(gè)設(shè)施找到合適的位置并指派每個(gè)需求點(diǎn)到一個(gè)特定的設(shè)施， 使之達(dá)到在工廠和需求點(diǎn)之間的運(yùn)輸費(fèi)用最低。P-中值模型一般適用于在工廠或 者倉庫的選址問題，例如要求在它們和零售商或者顧客之間的費(fèi)用最少。P-中值模型也可以通過精確的數(shù)學(xué)語言進(jìn)行描述。再用數(shù)學(xué)語言進(jìn)行描述 時(shí)，需要準(zhǔn)確的表達(dá)問題的約束條件、目標(biāo)，還有合理的變量定義。一般P-中 值問題的目標(biāo)函數(shù)是:（式 1-1）（式 1-2）（式 1-3）（式 1-4）（式 1-5）（式

7、 1-6），n）；Min zz dcywN jM約束條件為：Zy. * Nz x = p jjwMy x ,i w N, j w Mx w 0,1, j w My r w 0,1, i w N, j w M式中：N-在研究對(duì)象中的n個(gè)客戶（需求點(diǎn)），N二（1,2,d 第i個(gè)客戶的需求量；M-在研究對(duì)象中的m個(gè)擬建設(shè)施的候選地點(diǎn)，M= （1,2，m）； c.-從地點(diǎn)i到j(luò)的單位運(yùn)輸費(fèi)用；P-可以建立的設(shè)施總數(shù)（pVm）；=0,其他情況假如客戶在iN,由設(shè)施jM來提供服務(wù)（0其他的情形式 （1-1）是P一中值模型的目標(biāo)函數(shù)約束條件式（1-2）保證每個(gè)客戶（需求點(diǎn)）只有一個(gè)設(shè)施來提供相應(yīng)的服務(wù)，約束

8、條件式（1-3）限制了總的設(shè)施數(shù)目為個(gè)，約束條件式（1-4）有效地保證沒有設(shè)施的地點(diǎn)不會(huì)有客戶對(duì)應(yīng)。從上面的兩種P-中值模型不同表達(dá)方式中，可以看出，求解一個(gè)P-中值模型需要解決兩方面的問題:選擇合適設(shè)施位置（數(shù)學(xué)表達(dá)中的x變量）。指派客戶到相應(yīng)的設(shè)施中去（表達(dá)式中的y變量）。一旦設(shè)施的位置確定之后，再確定每個(gè)客戶到不同的設(shè)施中，使費(fèi)用總和 Cij最小就十分的簡(jiǎn)單了。與覆蓋模型相似，求解一個(gè)P-中值模型的設(shè)施選址問題，主要有兩大類的 方法：精確計(jì)算法和啟發(fā)式計(jì)算法。由于P-中值模型是NP-hard問題，因此精確 計(jì)算法一般只能求解規(guī)模較小的P-中值問題，下面介紹一種求解P-中值模型的 啟發(fā)式算

9、法 貪婪取走啟發(fā)式算法（Greedy Dropping Heuristic Algorithm）。 這種算法的基本步驟如下：P-中值模型貪婪取走算法：第一步：令當(dāng)前選中設(shè)施點(diǎn)數(shù)k=m,即將所有m個(gè)候選位置都選中。第二步：將每個(gè)客戶指派給k個(gè)設(shè)施點(diǎn)中舉例最近的一個(gè)設(shè)施點(diǎn)。求出總運(yùn) 輸費(fèi)用Z。第三步：若k=p，輸出k個(gè)設(shè)施點(diǎn)及各客戶的指派結(jié)果，停止；否則，轉(zhuǎn)第 四步。第四步：從k個(gè)設(shè)施候選點(diǎn)中確定一個(gè)取走點(diǎn)，滿足：假如將它取走并將它 的客戶指派給其他的最近設(shè)施點(diǎn)后馬總費(fèi)用增加量最小。第五步：從候選點(diǎn)集合中刪去取走點(diǎn)，令k=k-1，轉(zhuǎn)第二步。（三）方案的求解表2.1需求與距離距離Cij候選點(diǎn)j需求

10、dj12345678宿舍樓1、225041226470宿舍樓316639534宿舍樓417233950051440宿舍樓516932065044宿舍樓618937734宿舍樓7、833217690宿舍樓93298356宿舍樓10、1133917139172公教A1712082772公教B7810930012公教C10615029024公教D47805044036432公教E1501044914082公教F6003095424經(jīng)管樓81366545229816藝術(shù)建工樓429245030外語樓46326720020文法樓42421517018講堂群522537206圖書館66306852信息樓5

11、5510152510電氣樓44319245814紡織樓53810167010機(jī)械樓5258068616材料樓635048414南公教5885046160宿舍樓12、1354757115070宿舍樓14、1555657817974宿舍樓1656158620532上表是我們利用百度地圖精確地測(cè)量出各需求地與候選點(diǎn)之間的距離，由于需要測(cè)量的距離實(shí)在太多，但是有些候選地實(shí)在是不適宜一些對(duì)應(yīng)的需求地去 往，例如：從宿舍樓6號(hào)樓去往圖書館打印的話實(shí)在太遠(yuǎn)了，我們就未將這些距 離標(biāo)出。另外關(guān)于需求的調(diào)查我們是通過在已有的6個(gè)打印室發(fā)放問卷，主要問 題是“您來打印之前是從哪棟宿舍樓或公教樓來的？ ”，從而確定

12、出各需求地的 日需求人數(shù)。當(dāng)然，我們的數(shù)據(jù)可能存在著一定的偶然性，但并不太影響我們的 結(jié)果。首先，肯定是設(shè)施點(diǎn)越多越好，這樣就可以盡可能的滿足更多的客戶。但 是，這樣的話隨之而來的我們不得不考慮到成本，設(shè)施點(diǎn)越多成本越高，并且如 果有一些設(shè)施點(diǎn)距離太近的話，就有可能造成不必要的成本浪費(fèi)。所以，我們決 定在不影響設(shè)施點(diǎn)數(shù)量的前提下進(jìn)行研究，下面就請(qǐng)欣賞我們利用P中值模型的 解題步驟。令k=8,在不刪除設(shè)施點(diǎn)的前提下，根據(jù)就近原則我們可以列出離各設(shè)施 最近的需求點(diǎn)，默認(rèn)為該需求點(diǎn)的同學(xué)去其對(duì)應(yīng)的設(shè)施點(diǎn)打印，然后根據(jù)總距離 D應(yīng)為各需求點(diǎn)到指定設(shè)施點(diǎn)的最距離與需求人數(shù)的乘積，最后總結(jié)為如下的表 格。

13、表2.2各設(shè)施點(diǎn)與需求點(diǎn)的對(duì)應(yīng)關(guān)系設(shè)施點(diǎn)j對(duì)應(yīng)的需求點(diǎn)i總距離D1宿舍樓 1、2、3、4、5、6438862宿舍樓 7、8、9、10、11328003公教樓A、B、C、D38224公教樓E、F10405經(jīng)管樓、藝術(shù)建工樓、外語樓、文法樓118286講堂群、圖書館、信息樓、電氣樓40167紡織樓、機(jī)械樓、材料樓、南公教樓52908宿舍樓 12、13、14、15、1630306合計(jì)132156從上表我們可以很明確的看出各設(shè)施點(diǎn)與其對(duì)應(yīng)的需求點(diǎn)的關(guān)系，并能從 理論上算出對(duì)應(yīng)需求點(diǎn)i到最短設(shè)施點(diǎn)j之間的總距離D。其次，我們選擇取走其中的一個(gè)候選點(diǎn)。要求滿足取走該點(diǎn)后，將各需求 點(diǎn)進(jìn)行重新的指派，使得各

14、需求點(diǎn)到設(shè)施點(diǎn)的距離增加最小。令k=k-1=7,以取走設(shè)施點(diǎn)1為例。在取走設(shè)施點(diǎn)1后我們發(fā)現(xiàn)其在表3.2 中對(duì)應(yīng)的宿舍樓16將會(huì)選擇設(shè)施點(diǎn)2,也就是說其增加的總距離只表現(xiàn)在 設(shè)施點(diǎn)2上，最后我們作出如下的表格。表2.3移走設(shè)施點(diǎn)1后增加的距離設(shè)施點(diǎn)j對(duì)應(yīng)的需求點(diǎn)i移走1后增加的距離2宿舍樓111388423公教樓A、B、C、D04005經(jīng)管樓、藝術(shù)建工樓、外語樓、文法樓06講堂群、圖書館、信息樓、電氣樓07紡織樓、機(jī)械樓、材料樓、南公教樓08宿舍樓 12、13、14、15、160增加的總距離38842同理，我們?cè)谝谱咂渌O(shè)施點(diǎn)的時(shí)候，對(duì)應(yīng)增加的距離會(huì)有所不同。具體 表現(xiàn)為：移走設(shè)施點(diǎn)2時(shí)，宿舍

15、樓711將會(huì)選擇設(shè)施點(diǎn)1，增加的距離為 39912m；移走設(shè)施點(diǎn)3時(shí)，公教樓A、B、C、D將會(huì)選擇設(shè)施點(diǎn)4，增加的距離 為3102m；移走設(shè)施點(diǎn)4時(shí)，公教樓E、F將會(huì)選擇設(shè)施點(diǎn)3,增加的距離為332m； 移走設(shè)施點(diǎn)5時(shí)，經(jīng)管樓、藝術(shù)建工樓、外語樓、文法樓將會(huì)選擇設(shè)施點(diǎn)4,增 加的距離為10310m；移走設(shè)施點(diǎn)6時(shí)，講堂群、圖書館、電氣樓將會(huì)選擇設(shè)施 點(diǎn)3,而信息樓將會(huì)選擇設(shè)施點(diǎn)7,增加的總距離為11894m；移走設(shè)施點(diǎn)7時(shí)， 紡織樓、機(jī)械樓將會(huì)選擇設(shè)施點(diǎn)6,材料樓、南公教樓則會(huì)選擇設(shè)施點(diǎn)8,其增 加的總距離為42926m；移走設(shè)施點(diǎn)8時(shí)，宿舍樓1216將會(huì)選擇設(shè)施點(diǎn)2, 其增加的距離為6108

16、0m。根據(jù)得出的數(shù)據(jù)結(jié)合移走設(shè)施點(diǎn)1增加的距離，我們將這些數(shù)據(jù)進(jìn)行整合 最終繪制成表格，見表2.4。表2.4移走各設(shè)施點(diǎn)后增加的距離移除的設(shè)施點(diǎn)增加的距離138842239912331024332510310611894742926861080從上表我們可以看出移走候選點(diǎn)4增加的距離最短為332m，移走設(shè)施點(diǎn)8 增加的距離最長(zhǎng)為61080m。采用貪婪取走法，最終決定取走候選點(diǎn)4,即公教樓 F座的打印室所造成的距離增加最短，則總距離D=132156+332=132488m。接下來，我們重復(fù)上一步的演算過程，同樣取出該點(diǎn)使得總距離增加最小， 然后令k=k-1=6。則可以得出：移走設(shè)施點(diǎn)1時(shí)，宿舍樓

17、16會(huì)選擇設(shè)施點(diǎn) 2,增加的距離為38842m；移走設(shè)施點(diǎn)2時(shí)，宿舍樓711將會(huì)選擇設(shè)施點(diǎn)1， 增加的距離為39912m；移走設(shè)施點(diǎn)3時(shí)，公教樓A、B、C、D、E座將會(huì)選擇設(shè) 施點(diǎn)6,而公教樓F座將會(huì)選擇設(shè)施點(diǎn)5,增加的距離為20452m；移走設(shè)施點(diǎn)5 時(shí)，經(jīng)管樓、藝術(shù)建工樓、外語樓、文法樓將會(huì)選擇設(shè)施點(diǎn)3,增加的距離為 11964m；移走設(shè)施點(diǎn)6時(shí)，講堂群、圖書館、電氣樓將會(huì)選擇設(shè)施點(diǎn)3,而信息 樓將會(huì)選擇設(shè)施點(diǎn)7,增加的總距離為11894m；移走設(shè)施點(diǎn)7時(shí)，紡織樓、機(jī)械 樓將會(huì)選擇設(shè)施點(diǎn)6,材料樓、南公教樓則會(huì)選擇設(shè)施點(diǎn)8,其增加的總距離為 42926m；移走設(shè)施點(diǎn)8時(shí)，宿舍樓1216將會(huì)

18、選擇設(shè)施點(diǎn)2,其增加的距離 為 61080m。根據(jù)我們演算過程中得結(jié)果，我們簡(jiǎn)略的將移走設(shè)施點(diǎn)與其對(duì)應(yīng)的增加的距離繪制成表格。具體見表2.5表2.5移除設(shè)施點(diǎn)與增加的距離之間的關(guān)系移除的設(shè)施點(diǎn)增加的距離138842239912320452511964611894742926861080從上表我們可以看出移走候選點(diǎn)6增加的距離最短為11894m,移走設(shè)施點(diǎn) 8增加的距離最長(zhǎng)為61080m。采用貪婪取走法，最終決定取走候選點(diǎn)5，即圖書 館的打印室所造成的距離增加最短，則總距離D=132156+332+11894=144382m。 此時(shí)k=k-1=6，由于k=p，計(jì)算結(jié)束。綜合以上計(jì)算過程，我們可以

19、看出，在同樣是選擇六個(gè)打印室的情況下， 我們利用P中值模型算出最為適宜的六個(gè)位置為：1、2、3、5、7、8,即為：浴 池、名族餐廳、公教樓D座、建工樓、材料樓和理工餐廳，總的距離為144382m。2.3優(yōu)化前后的選址比較我們知道在優(yōu)化前的打印室的位置分別為：1、3、4、5、6、7。而通過我們 的考查得到，為滿足每個(gè)需求點(diǎn)到相應(yīng)的設(shè)施點(diǎn)的距離最短，最后匯總成如下的 表格。表2.5優(yōu)化前的合理對(duì)應(yīng)關(guān)系設(shè)施點(diǎn)j對(duì)應(yīng)的需求點(diǎn)i1佰舍樓1113公教樓A、B、C、D4公教樓E、F5經(jīng)管樓、藝術(shù)建工樓、外語樓、文法樓6講堂群、圖書館、信息樓、電氣樓、宿舍樓12167紡織樓、機(jī)械樓、材料樓、南公教樓結(jié)合表2.

20、1和表2.5，通過計(jì)算得出總距離D1=需求*距離=237034m（1）根據(jù)我們之前選擇的P中值模型的計(jì)算，可以得出最終選擇的位置為：1、2、 3、5、7、8，即為：浴池、名族餐廳、公教樓0座、建工樓、材料樓和理工餐廳。 最后匯總成如下的表格。表2.6優(yōu)化后的合理對(duì)應(yīng)關(guān)系設(shè)施點(diǎn)j對(duì)應(yīng)的需求點(diǎn)i1佰舍樓162佰舍樓7113圖書館、講堂群、電氣樓、公教樓A、B、C、D5經(jīng)管樓、藝術(shù)建工樓、外語樓、文法樓7信息樓、紡織樓、機(jī)械樓、材料樓、南公教8宿舍樓1216結(jié)合表2.1和表3.6，通過計(jì)算得出總距離D廣需求*距離144382m（2）結(jié)合式（1）和（2）比較：D1D2=92652mo可能這個(gè)數(shù)據(jù)大家看

21、著比較的 抽象，我們舉幾個(gè)例子吧：（1）正常成年人的步速一般的是1.5m/s（即5.4km/h），那么92625則需要 一個(gè)正常成年人不停息地行走近17個(gè)小時(shí)；（2）河北科技大學(xué)新校區(qū)全新火車站距離為9300m，那么92652m則是其近 十倍。3.可行性分析此次課程設(shè)計(jì)我們主要對(duì)科大校內(nèi)的打印室選址進(jìn)行了整體優(yōu)化設(shè)計(jì)，通過 調(diào)查問卷的形式我們大體統(tǒng)計(jì)出每天的各宿舍樓和教學(xué)樓的需求人數(shù)。同時(shí)我們 根據(jù)學(xué)校的規(guī)定，在已有的打印室基礎(chǔ)上選定了兩個(gè)候選點(diǎn)。希望通過p中值模 型，設(shè)計(jì)出比較合理的打印室位置，從而比較優(yōu)化前后的數(shù)據(jù)。下面我們從需求 上、經(jīng)濟(jì)上和服務(wù)上的可行性進(jìn)行分析。從需求上分析可行性，打印室作為大學(xué)生學(xué)習(xí)過程中不可或缺的一部分。 不論是在學(xué)習(xí)過程中對(duì)于老師上課時(shí)講解的PPT，還是在臨近考試時(shí)同學(xué)們準(zhǔn)備 的復(fù)印資料方面考慮，我們都覺得打印室必須要建在最為合理的位置，以便于我 們更好的學(xué)習(xí)。從經(jīng)濟(jì)上分析可行性，我們最后決定建立的打印室數(shù)量為6,也就是說我 們并未改變打印室的數(shù)量，只是將打印室的位置進(jìn)行優(yōu)化調(diào)節(jié)。從這一方面考慮 的話，按照我們?cè)O(shè)計(jì)的方案執(zhí)行的話，所造成的是相當(dāng)之小。反而，我們從需求 上滿足更多的消費(fèi)者，所帶來的利潤(rùn)肯定是比較客觀的。從服務(wù)上分析可行性，按照原來的方案，理工區(qū)學(xué)生沒有打印室，生活區(qū) 打印室經(jīng)常供不應(yīng)求，而