|
超市选址模型
. v$ e k8 @4 o9 O
" {) V/ B5 T7 b! {) G! D; Y, H小组成员：高才萱：经济与工商管理学院国际经济与贸易专业
4 f4 X7 _9 k: R, F" Z) o, ?6 P 彭爱军：经济与工商管理学院国际经济与贸易专业 . x0 x# Q% H' i* R
吴 质：经济与工商管理学院电子商务专业
2 C3 @ C9 |/ `: }2 Q0 p1 Q
- s3 C' K! y# _) f$ ?. p
! }3 j7 l! `* ?7 B }9 c
+ R9 q5 c [2 q' c 9 Z W: ?6 l- _, Q, ~' G
摘要 正确选址对于超市的成功运营至关重要，是运营决策中需要解决的首要问题。作为一个最优化问题，选址问题的制约条件用分析的方法不易处理，用穷举的方法又因为潜在的选址点有无穷多个也不易实现。本文引入图论将难以用分析的方法处理的制约条件加以简化处理，通过适当的假设规避大规模的潜在选址点，将复杂的问题简单化。针对不同的假设，给出四种不同的超市选址模型，利用计算机编程给出令人满意的解。
$ j% t2 a% U" A4 O8 D7 _ 9 \: U& B: j2 u: X' U; {
关键词 选址、最短路径、无向图、重心
5 |0 J% T \0 V
1 R4 R" ^* T! Y4 W
; v* P/ H( A; d+ a6 L4 P0 x5 r$ G
4 H1 O1 l: S3 s 0 j( U% k; C3 d! ^* J4 _+ q
: F7 Q4 ^2 K% R
- T& `0 V% B7 b7 y3 s
6 U3 `$ J7 Z( o
, F( M4 o0 w3 C 2 i- K/ A, P* R3 q7 d* |
8 s! `' I) ]& p. D3 ^5 x1 a
o' a- Z; a1 g t+ R( V& Y# @0 v
- q' O( l: v; w3 P# f: a0 z- r. P 8 T. {/ c5 F; n: i# P$ V& Q
+ \; r8 p! V; S7 K4 T( } 4 v' ^5 K* z3 s- z
2 T0 l& }* }2 ?
2 q5 F" k4 V2 b( K- i' X众所周知，选址是关系到零售门店成功关键的关键因素之一。曾经有句名言叫做“连锁超市成功的关键有3个条件，那就是选址，选址，还是选址！” 由此可见，选址在连锁商业的日常经营中的地位是多么的举足轻重。因为选址是门店的重要工作，所以选址工作受到每个超市管理者的关注和重视。 % f: P, V' o% P% S3 R5 l
好又多公司计划在四川省南充市城区修建一到两个大型超市，为了更好的实现最大化的收益，该集团委托本小组协助他们实现超市的最佳选址。好又多公司希望我们的选址位置需要满足以下两点： 2 F0 t# C" T B% Y
1.给顾客提供充足的便利，便利程度主要指顾客到达超市的路途长短以及要尽可能的选在交通比较发达的干道旁。 % \+ D$ ]0 }- n) ^& y- U
2.顾客在按照便利原则（路径最短原则）选择超市时到达所选超市的客流量要尽量的大，因为到达超市的客流量直接影响到超市的赢利。
( k+ g* O1 U/ J1 \二．资料数据说明 + N z6 ]/ P; h& V6 D2 o
为完成此项选址工作我们找来了市区地图（见附图1），直接在图上进行选址是不现实的，所以我们根据好又多集团的要求1，仅保留了市区主干道，并且以干道交叉点为顶点，以干道长度（由南充市市政工程处提供）为边，把市区交通图简化为图1， 同时要计算到达超市的客流量还需要知道南充市的人口分布情况，该资料由南充市公安局户籍科提供。
( ]9 T0 W. T/ U$ L. Q) T7 d- s8 Q - A) R* ~$ y5 @0 a
三、基本假设与符号说明
6 l6 T9 c( U. @+ F% p3.1、基本假设
' a1 s# x3 i8 n/ c. [1 z1 s（1） 准备新建的超市可以容纳所有到来的顾客，可以满足所有人的需求；
q" Y0 f F3 v" D（2） 超市选择的最佳地址只受路径长短的影响，与其他因素无关； # k$ D3 J: t( b `4 [* R" Y5 N
（3） 各个区居民平均分布于各区； * r8 M. @# b. P3 W# f
（4） 居民出行方式都选择公交汽车，而公交汽车站点设立在各个主干道的交叉处；居民在主干道交接点处换乘汽车的时间忽略不计； & {' p: N1 J$ H2 ~ X
（5）所建立的任意两个超市没有任何区别，其选址也只受总路径长度的影响，与其他任何因素无关，人们只选择距离自己位置最近的超市进行购物消费； 8 m& f7 s0 m3 S& ^9 h# H9 w$ a
( W8 C1 m& s. T! g# w6 ]" X
3.2、符号说明
: E* @ W, x9 x（1） 为南充市各个区人口数；
0 b; p t$ S) ~3 k' w# Z+ ]' k: @（2） 为坐标系中各个乡镇中心点的坐标；
1 D: R% L1 T& `（3） 为第i点位置的标示; 5 f2 ^. X! g7 p* f3 W9 n; R/ H
（4） 为顶点 、 点之间的最短路径长度； - ]4 h- q6 D: ?* N
（5） 为通过顶点 到达超市的人口数； 6 o5 z" u' H2 \: t. O" {
（6） 为分布在街道 两旁的人口数； & ?. M2 d3 z! o* A
（7） 为各区域所有顶点按照最短路径到达 点的路径之和. , d1 A; E) j5 O }4 C8 e5 Z$ G
（8） 为各区域所有顶点按照最短路径到达 或 点的路径之和； ( B7 { U7 [9 v; d4 ]" U2 r3 B# i
（9） 为各区域所有顶点按照最短路径到达 点的人口数；
( B5 X. E4 b7 t v4 X6 M3 H7 Z
0 i) o/ J0 B* h% A a四、模型的建立和求解
7 B: Q- Y L4 w# S- Z
# l' v7 r) x( N* w实际上该问题是图论中的选址问题：给出一个无向赋权图 ，其中顶点集V代表所有的可能选址处，也就是所有的干道交叉点，E是每一条干道， 为权重，其中， 为赋权图中的标识长度， 为各干道两旁居住的人口数。我们需要作的任务是，找到一顶点子集 ，（其中k是商家拟建的超市个数，具体由商家决定）使得在此点集中每个点建立超市使目标值最优。 : d) }9 B ?4 o0 h! k
. F) P6 Z- F H
4.1 模型一 9 H& ]! f4 i* [. e3 x$ j
' [# R4 \& Y+ T6 `* r7 z( o
为了模型（一）的简单方便易操作，所以我们暂先不考虑道路、建筑物等其他因素的影响，任何两点之间可以直线行走。另外暂考虑人口在各个区域内均匀分布，所以我们可以在城区各个区中分别找出几何中心位置集中代表该区人口的居住地点，进行建模。 , W# H+ D3 b- |( f
以过一区几何中心（1）为x轴，过三区几何中心（3）为y轴，建立二维直角坐标系。
, g& M/ ~' n# M A1 }7 i1 s图中各区的几何中心坐标：
9 l6 X6 q$ g& {, j& ?& V8 d- w# a% \! A——（1，0）、 ——（1.43，1.06）、
7 Q6 I: p W+ `5 y2 n——（0，1.631）、 ——（1.83，1.83）、 & O% h/ c, ?+ _4 u( s
——（0.77，2.8）、 ——（0.57，3.2）、 , V* i# x+ S8 Y( A4 ~0 W/ k
——（2.28，3.25）、 ——（3.03，4.7）。 ) o" y( l4 x5 j/ o6 G. R
各区所居住人口数：
! c( K" d. |" I) q- h% O+ H7 o' c=2.18 、 =3.4379 、 =3.5561 、 =6.24808
1 c, G5 w; s: ]=4.4873 、 =3.4252 、 =7.7711 、 =4.4282
8 g) E/ U3 j3 I F
3 @ N9 b! M' D$ n2 B2 o
6 g8 w" E9 l% s1 q+ F
- C A" z; v7 k9 V/ g* h2 u4 K3 l （6） （7） * G3 _9 m( P1 ?; L# C
（5）
' B$ U2 v7 K8 J
! @4 \! b( b5 z& Y; \$ c6 M （3） （4） 8 ?3 X, B- W7 ~3 K% i
( J% u0 L0 Q2 X7 `& b3 m' G9 \0 _
（2）
$ {! i& Q: z* _
2 [5 r1 i$ R8 |% {1 ? （1）
6 e( x# P7 e5 I P/ `' z' \
0 X. o" G% j2 b6 p! v! C / G/ j9 K: m# M" G i, [4 s6 B
4.1.1模型建立
& b: s4 E" g8 s. t9 V& X目标函数为：
5 P8 y+ k. J2 X; K
, J& v) d) g. C5 G# t
约束函数： 4 T. Q" P" j) i$ Q, H
4.1.2 模型的求解 7 l. }. L% m f
根据数学分析中关于多元函数最值的知识，最值只可能在边界和极值点处达到，而本问题的最优解显然不应在边界取到，另一方面我们可以看到函数的驻点是唯一的，而实际问题的最优解又是必然存在的，所以我们下面求得的驻点一定是最优值对应的最优值点： 0 q+ t6 W& l4 s, h2 H+ x! O
- `8 y( ]4 v7 J7 h4 ?; }
& G6 r! |2 `1 E( S1 U) |4 a解得 2 \6 P' ], y2 |5 b, z
代入得：（x，y）={1.5499，2.5461 } ! Q7 M2 d Q) }6 i/ Y* j5 {
从实际情况上看我们这个点是{1.5499，2.5461}，对应与地图上五星花园和仪凤街之间，而这一段恰恰是南充市最繁华的商业街区，可见我们的结果和现在的实际情况非常吻合。 $ B, y0 F. h' j- r
从上面的公式和数学分析的关于重心坐标的计算的知识我们看出，在平面上选址实际上就是找出所谓的“重心”位置，那么当平面上各个点人口分布不均匀的时候，这个时候上面的公式将不适用，而且通过数学推导也很难得到一个通用的公式，但是我们可以根据物理学的知识采用的“悬挂法”来求重心位置。具体方法如下： ' B; b! E4 H5 r
首先，根据实际的南充市地图作一个均匀的、轻质的摸板，然后根据人口分布的情况，在各个居民点放置对应成比例的砝码，最后通过悬挂法找到我们的实物模型的重心，再对应于实际地点，这就是我们需要找到的选址点。 % y. L( o! O0 F8 J8 }' ?* N
9 w+ F; n& w) }1 W
模型的优点：思路比较简单、计算比较方便，有个计算器即可，推广之后的模型也不需要复杂的计算和计算机编程。 ; x5 ?, U8 a# C; O0 A
模型的缺点：首先地图上的任何两点之间不可能都能以直线的路径行走；而且如果得到的“最优解”不在要求的干道交叉点，虽然我们可以把离该“最优解”最近的路口作为一个近似解，但可信度并不十分理想。
! G: L4 g& i1 A/ Q2 P# Q- H8 v ' n' j2 i% k0 U
为此我们建立模型二
# }; _% m2 H G# x4.2 模型二
* V( x3 h* C' {& e3 K0 F" _7 U2 S 注意到问题本身兼有离散和连续的特征：可行点的选取是有限个的，只能选在干道的交叉处，这是离散的特征；人口均匀的分布在各个区，这又是连续的特征，所以这是一个既有离散又有连续的混合模型。这方面的研究比较少，解决起来难度比较大。所以我们需要对问题加以一定的简化。
5 r( t: n* ?9 M& C首先我们考虑到“人口均匀的分布在各区内”这个条件直接处理起来比较麻烦，但是由于每个人选择乘公交车到达超市那么他们首先需要到达干道，然后按照到最近的路口乘公交车，那么我们可以把从顶点 乘公交车的人口 作为 的一个权值，这样我们就把一个混合的规划问题转化成一个离散的规划问题。 & Z0 i x/ b: W$ z
的计算：由于我们只有南充各个区的人口情况，所以我们只能假设南充各个区的人口均匀分布在干道两旁，另外一方面每一个人按照最近路径选择乘车点，所以我们可以认为每条街道的人口数又平均分配在该干道的两个顶点。所以
% y; D1 X& H, [% q& V $ h; d/ i! z3 w- u* `/ z; D+ b
其中 为第j区的人口数。
1 F. a, C! x" |! v4 T% F' D; g6 @由此问题简化为：给出一个无向赋权图 。我们需要作的任务是，找到一顶点集 ，（其中k是商家拟建的超市个数，具体由商家决定）使得在此点集中每个点建立超市使目标值最优。 8 }2 t9 D* V% W; a" C0 M
下面的模型取
, B+ M/ v: m/ q$ M, S! C4.2.1 模型的建立
, r$ L3 n- C6 B. w2 l: ]2 u' R 选择下标 ，使得
4 P8 ], O6 }# d+ o0 O; u0 o" {=minLP
A f5 I+ T- k t6 c7 d: i其中 ，
4 W9 r* I/ y2 h/ g) c' |3 S3 Y； " H) N$ b1 X) J: C. T+ S5 z+ V
为顶点 、 点之间的最短路径长度；
) q$ G: w* e3 R: F8 H- ] 为通过顶点 到达超市的人口数。
7 S9 h3 B+ B! H* M% m" S' I t1 p4.2.2 模型求解
5 ^$ H/ X5 b. v& L @
) e& k4 T- f* ?; U, o! \6 Q3 f 求解这个模型关键在于两个矩阵 L和P的求法，具体算法如下： + [2 o; N; n7 x9 t% r
（1）任意两点之间的最短通路构成的矩阵L ; u8 T8 M2 P+ \% b4 r2 }: ^
首先，将赋权图中的长标志为矩阵L= ，如下： 4 D& x& w- v- \% m
) q6 ?! @' k1 |9 ]: P- z
其次，令 =[ ]出发，依次构造出N个矩阵 ， ，…， 。其中第k个矩阵 =[ ]的元素 表示从 到 而中间点仅属于 到 的k个点的所有通路中的最短通路长。
. ~7 z: q: P8 }, `8 ]4 A. b# T 已知 =[ ]，第k个矩阵 =[ ]定义如下：
& ^0 P8 C4 J1 }5 [+ S: }) C $ T. m- P7 p: L
运算过程从k=1开始，让i、j分别取遍从1到N的所有值，然后k增加1，反复进行，直到k=N时终止。这时 =[ ]的元素 就是从 到 的最短通路长。
! Q' v( ?6 o, ~
7 {: \& a' S1 d& |4 E2 k算法流程图如下：
' f7 g* z4 l. W+ { [ s
& A$ e! t4 [, V& f$ I' x
5 L2 T7 Z2 v2 g* g3 i
2 h( x# Q) r. f1 b: @* r4 r7 W! x5 J
8 T" Q' v j; j$ u$ Q- t
8 \/ K5 ]; D: `+ i
- s. {; u# O+ N) Z$ [9 Y（2）各个端点所拥有的人口数构成的列矩阵P
, q% K5 w. c2 U# b! O4 T 由公式
* Q+ }! |% A( q& M2 N ^我们可以得到矩阵
- [8 H: l) `. V* ?2 q
$ ^+ J9 o" P+ q T5 |; N求所有人到 点最短路径之和的算法流程图 4 A: K% X( Y/ t8 n5 Z% _2 O" g- Q2 I
" e% }1 Z' ?/ y( D/ c0 p
9 E# n. `$ I* V1 l i+ C3 a
; U6 [: [; O* e0 q; K
3 g1 S& J2 M( Z. d: {
5 i1 b( d8 g# `# Y4 T e# e
) Y: h) i3 B# [
2 ^: ], X) D" ^3 [7 w* o3 X
. c' k, }6 [9 U) R4 U$ p7 y$ Y
" q2 @, K" E5 D! l' p S1 k
- P: T6 C5 O9 C
1 O2 ^" V; {' R3 ~+ t2 @+ T% o
. x' n' `, n' _4 W; |6 a' ?
是
/ @+ y r; F4 h9 k非
4 M4 B$ Q8 t. Y; C$ D0 _8 U 是 # [. Q8 Z# d$ a5 D8 x
非 / s1 X/ q- f" [. X+ Q8 V7 d
结束
. L7 D& z7 Y2 Z: @9 X! v' ~ w + [4 P, ]5 W$ B& Q' f" d
0 f5 ]$ k3 F1 Q/ @（3）运用计算机,
+ g6 D5 P+ k) P得到
6 [4 P# ?: l; n3 B4 U; ]* y h* f< < <……。 % v0 |2 \8 P, i7 G0 \* t! O' m) M
其中40是所有点中的最优解。
9 l$ y9 f) o6 V+ Q5 q 我们选择40点，实际上在我们选择的最优点就分布着四川万福来集团的南充总店，即使是次优点41、43点也已经有成百集团的超市建立，说明我们的结果和实际情况比较吻合。
, e' ]9 f# R3 p0 p' Y `模型的优点：模型中考虑了道路问题，取消了各个区域人口集中于一点的假设，将人口平均分布于各个区内无穷多个点转化为分布在有限的几个乘车点上。 4 w. W8 E7 `% c. z( Q4 H
模型的缺点：一个城市内不可能只开一家超市，存在一个公司开多家超市和多个公司开一家超市的问题。
* z. M* _; D$ ^ . e' ~0 W# F! l7 ?
现在我们考虑 的情形。模型三给出了一个集团公司作出决策开两家超市的情况；模型四考虑已经有若干家超市存在的前提下，新进超市应当如何选址。 7 D# r; f9 h6 v. M
, |/ g/ `& B8 \3 g+ I
4.3 模型三
7 L' Q$ F: ?) R1 c4 p5 R/ U4 J 假定两个超市分别选定在 ， 点， 据假设（11），则 点处的人只选择 ， 中较近的超市进行消费，则顶点 的人到达超市所需要走的道路总长度为 。 : ^1 [) x$ `( d2 ], ^
所以选址 ， ，总的路径长度为
2 N# w7 t, d! Y1 g
a) U' }. m9 G9 }# S4 a4.3.1模型建立
4 A9 v+ D) {0 I+ {$ ?: ~选择下标 使得 $ n; I9 x6 `' }/ N
* f: Z6 @& A) p9 y; L9 }( d
4.3.2、模型的求解 , E0 v/ T8 X2 m7 V6 i8 q- @7 @" I
为了简化计算，首先我们考虑到两个超市不可能建立在同一个点上，否则的话，可以将他们合并成一个超市，其次由于对称性，显然有 。由此我们只需计算矩阵 的上三角部分。
3 h8 J( I: \6 c3 D& M9 S: {( x求解 算法流程图 $ F* T, C& c! J
+ ~, H- I9 }. j
! G' _ M. d+ Y+ |
+ w: j/ o% z. p9 x$ t+ v: i, ^# \
% e7 a8 [' R' t! k, Q
( S; H c1 z6 y2 Y
4 A7 ?$ { m! S$ o5 D, \8 p' Q
n% _4 E1 E/ ~! q% p+ n: I! C
: z7 [' c' X/ d" W! P% U
" [4 z( L- n% J- D; y: F- A
8 x& w, V0 r- t
, v9 X D2 H0 B( ^6 }
8 _' M" {' |1 }
' Q; G2 G/ q3 d5 g! W }' T) g# @1 ?
5 N4 J" }' W; n1 U
# f$ Y4 F2 n- G" |3 y 是 . W+ b5 \1 q/ G+ O) h
非 7 E" j" d5 [! {1 r5 U: x
是
7 S7 `& d* I3 N, X; i8 }+ L非 . ^' Y, w$ j g: h4 D) _% }! T; m
是
! u# }. T, P) y# w非
2 V, t, v/ q; V结束
# e" T2 T# l4 Q! k
. W0 y: K- c3 I. k1 @通过计算机运算得出如下几个可以选择的结果：
" f: u2 ^& V- o: Q. q, h（21 ，58）>（20 ，58 ）>（20 ，38 ）>（20 ，29 ）>……
% J, V3 D {* ]. [" x" m; `- _7 r$ Q其中（21 ，58 ）是所有点中的最优解，“>”表示优先级数前者大于后者。 1 E: l0 b) `- K9 L4 K5 J* o% F
由此，我们认为其中 （21 ，58 ）更具有合理性。 8 Q: o9 a# J: S2 o3 Y
模型的优点：此模型考虑了建立多个超市情况，对于超市选址问题的解决。
& I+ _; J( w8 ?" F$ M9 e% i模型的缺点：一个城市中的任何经济行为不可能没有竞争，而此模型中建立两个超市必然要有竞争，我们忽略竞争问题，是此模型的一大缺点。
' q) ~# J7 g3 h/ E
, ?) l- O( c% Y实际生活中，在南充市城区市场领域进行经济行为的时候，市区内已经拥有一个或多个成熟经营的规模超市，在 、 、 点已经存在这样的超市。面对这样实际背景，我们给出模型四。
! t! h7 \' }& i& @$ O. p
, l0 y, j$ F0 N- b; |4.4模型四 ( G8 w* _1 d2 z1 M% P
根据好又多公司的要求我们在 、 、 点已经存在超市的情况下寻找建立“一个”超市的最优点，实际上使用我们下面的方法结合模型三，只需要对我们的模型稍加改动，我们就可以得到同时建立多个超市的最优点。 2 `8 k2 l! F: j. N
据假设（5），任何两个超市之间没有影响，也就是说在居民的眼里不存在区别。假定超市建立在 点：根据假设（5），对于 点的人们来说，他们只会
6 W+ O, |' N) i, U: m) h到 决定的超市消费。则 点的居民到超市购物所走的路程为 。
% E5 y% F1 Z: X$ {, N6 ^4.4.1 模型的建立
5 e- ?! s o3 j- ]4 c+ h 选择下标 ，使得
* w/ x8 o# H9 a h" c7 J. f
( g+ ^! x6 e; D# D- ^. l: y! U
4.4.2、模型的求解 7 v5 R& m2 [+ }" d: {5 ?0 | ~
求解 的算法流程图 % _( x) N3 t4 l- L$ @' T/ e- r, k# b% b
$ p" R/ [/ r$ ^! a
+ Q' v! l% M" G* S
& `7 p. w& M2 D0 V% ~. Y
: ]) ~: M: b% z/ O9 N
2 N7 ?: z( V& k4 @0 D8 Z, O
# `! w, k: ?, c& k6 M7 l7 X, j: h
- c1 o2 O. X& B `9 e， ，
+ l) R" K$ C$ l3 p2 b2 N6 s 6 a/ z* k( c. ?
/ u- G: Q s! D7 Z2 C( Q
% K' \. G+ U. a; |" \
+ d! m$ _- `! {
, X" t# q, b- Z' Q
4 `, V* }) `) u, T' H! i: N- g! f9 |
; H" S# ~) m5 \/ D
7 k3 S* o$ P) a/ S- H, O$ w4 S1 h4 E
是 ~# j# D2 @+ v/ L6 m
非
4 R S" Y& x' @" N2 z. |+ d 是
* `9 x5 N ^ r7 W! y! z非 0 `* ~8 d/ R0 C$ l2 S3 c0 H
结束
5 w3 x/ W4 x% `
1 V+ N/ }! F: g& N7 _: u
. g i- h- y6 A) J9 V* q通过计算机运算得出如下几个可以选择的结果： 1 X0 C, W& F' `7 ^ O$ f5 }
' l; `: g9 \' j* l- `通过分析，最终我们选定41 # ^3 Y0 g1 @9 s; A( ?
模型的优点：在这个模型中我们引入了竞争，更加符合实际。 $ z" z N/ u3 m. d) t; h
模型的缺点：由于对超市的选址不仅仅依赖与路径长短，还和交通、选址地点周围人口的经济状况等有关，由于缺乏相关的数据，我们在这个模型中都没有涉及，相信如果有了相关的数据我们可以做的更好。
+ s3 d) ^, F' ^- h% {, P0 b五、进一步展望
$ `8 ?6 y$ o* B& x; O. P1 K; u g" h9 N我们所得的结果与实际情况很符合，在相对最优的最优点与次优点上均有大型连锁超市抢驻。其实如果数据齐全的话，模型假设中的1、2、3三条假设可以去掉，使得模型更加符合实际，从而更具有合理性与可操作性。 . ^$ n* o* Y/ A5 A; ]
更进一步，如果时间允许的话，我们可以编制个一个决策软件：只要输入各条道路长，各个区的人口数，该城市中已有的超市分布情况等其他客观数据，软件可以给决策者提供一个超市选址的较优地址。 | 
IP卡
狗仔卡
发表于 2005-9-18 10:32
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
