“*() %&’ “#$ !

SOLVING MULTI-OBJECTIVE LOCATION-ALLOCATION PROBLEMS
USING SIMULATED ANNEALING

Mohammad Taghi Taghavifard Arian Shahsavari
Allame Tabatabai University – Faculty of MSc. In Industrial Engineering
Management and Accountingsharian61@gmail.com dr.taghavifard@gmail.com

Abstract: In this paper, multi-objective set covering problems (MOSCP) as one of the location allocation models are being considered. Here, the objective is to minimize the cost of locating facilities and at the same time to maximize demand satisfaction in a defined structure so that each customer or zone is being covered by at least one facility. Since the problem falls into NP-hard category from the complexity point of view, it cannot be solved in a reasonable computational time period by an exact algorithm. For this reason, a Simulated Annealing (SA) algorithm is proposed to solve MOSCP. The algorithm is a meta-heuristic approach coupled with a neighborhood search technique.
The validity and quality of the proposed method is tested by solving benchmark problems and the results obtained were quite satisfactory.

1268732040128

Downloaded from ijiepm.iust.ac.ir at 14:23 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:23 IRST on Saturday November 4th 2017

! ” (SA) /- ,’+-. , #$ %& ‘ ()*+

, -& .+()* ‘&# $% ” ! :
;& & 481 9* :, + * 2 5 67+3* 41 2 “!1 +, #0 / -8 – ! *G1@ “D +F+ $+ & .+D A $+3* C ?@* $A B (; ) “4<
J5 GP J5 ” B J5 #!5 J5 :#F +A 5 H “- ! #0 $B 5 4DA NP-Hard $% & G* “!1 +G O4N . & ,+M 5 & # ! “K& H& & L* & … 5 C4 LP “SL JR 5 SL “Q N “4L & 4G , , “4& P “O4N ! # & MOSCP $B (43& SL & &+41 5 U@ +3& T ! ?3L) SM 5 4B ! 3&4 H* $B XW ! #0 % 5 %5 5 % “3<+ O4N ,, -@ .?1 4D A -V41
-& 8& %K& %Z ! “3<+ O4N Z ?1 #0 ! ZB U[B \4 .?1 – – #< YU4) $%
. % “& G1 $B *Z # ! 6 ?1 Z

.+()* ‘& # ]U +M $B G* “!1 +G :” # “$!

// :
// :
dr.taghavifard@gmail.com sharian61@gmail.com ()!* +$- .# /0 !” #!$ % & !% ‘ ,!”# $%
1.
Multi Objective Set Covering Problem (MOSCP)
2
Simulated Annealing (SA)
.
∀i = 1,…,n o “4< H* – : = i
∀j = 1,…, j o # H* – : = j
T j (# ) 2, $+3* 41 2 =C j
Ti (# ) ; “9* :, = Fi
?@* T j # $+3* ]1* Ti “4< -D) m = aij
(6[ +M ) V[ 5 (+D A
+M ) V[ 5 (+N& A T j 2, $+3* -D) m = x j
(6[
A $+3* C $A B ?@* Ti “4< -D) m = Si
(6[ +M ) V[ 5 (+D “- 5 4 aij Fi C j P 6@+9* & L* &
* & Si 5 x j ++H* / 5
. + * 9* +<+& 5 2 +,
. ‘& # C 1& .?1 C 5 V[ “2 & kA .+()* C “4< ” H* & T!K , p; ! W & 1? 8 $+3* C $A B U+15 & T “9* + * q, B 5 2 $A B & 1 ? 8 5 & 4 -D m #4< , O+, r D .D
% $s 9 4 -D n 4& 2+ 67+3* :

Min Z1 = ∑n CjXj (t)
j=1
m
Max Z2 = ∑ FiSi
i=1
Subject to:
∑n aijXj ≥ Si ; ∀i ∈{1,…,m}
j=1
∑n Xj ≤ p
j=1
Xj∈{ }0,1 ; ∀j∈{1,…,n}
Si ∈{ }0,1 ; ∀i ∈{1,…,m}

MOSCP
A={aij ∈{ }0,1 /i=1,…,m;j=1,…,n}aij Am×n

1268732040128

Downloaded from ijiepm.iust.ac.ir at 14:23 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:23 IRST on Saturday November 4th 2017

.
5 , “+D O+(* ” ! .+()* ‘& # a1 & , & 67+3* BW ^@G & _G* ` L 67+3* 41 +3& # GA $&A 5 +3& H* #0 5 (&) #L & L* & L 67+3* & 5 N & _G* & .D ++H* O+(* +H 5 67+3* L H* +<+& 5 1 +<+& (# ! / ? ) 2 +, W , %0 ! .[e5d] D “(4A -N& 9* + * $% -8 – ! *G1@ ” D +F+ $+ & $%
5 & # ! (X+A) ” – ! 30 $B & NP-Hard
.[g] & H +M $% (9 “! ) #, D , %0 ! K[ ” – 4 4<+& 4, 5 PG; ?3L HA5 “+
“W $% , & T!K R ?1 PV* B
. # H& * 5 #0 i2& H& & # 5&5 HA5 $% “!1 h+ +G kA l9 , & / j&* & U% $B # ! 2 kG1 * – “4 “!1 -& #0 H& ! H&* $B # ! N 6G & .D +H H& ! $% $B ?3L T!K # ! ?+H&* && 5 +H . & $B C+* &! & G1
?+V+, 2+ D . – + # ! D +F+ j&*
&! +H * 2+ “& – % SL
.[m] & $B C+*
$B & # $% ?3L !+ # ! +<+& # ! D +F+ j&* .[m] & +H O4N C & X&; (SL)
.
. _ , H & .?1 4D MOSCP . 4D 41+ +M 5 ” ; 6[ & 9* & #4< ! “G kA MOSCP 4D
L5 C “5 & $+3* 41 # # 2 , -D #
. 4D # 67+3* 5 YH* L5 #4< & 67+3* “1 ! 6 8 % ?5 @
$+3* ?@* # 2 * “4< 5
.+N& A

3.
Location and Allocation
4.
Facility Design
5.
Time complexity function
‘d D/H . 1 / 1 bB b\ . D6.
.5 50 )( )0. 3 3’ a)0.$ SA

MOSCP SA .
. 5 .# e %+. 0; bB @ 50 )( $ $/ L 3. D6. $ ! $ ‘ 7. .# bB SCP .5 bB @ , .0@ 5 D# + *0F B/ $ ! 5? f. / C G
.# i $ *0F + 0; ai .@ K,
.5 D# D 7. (h) *$# g @

h i i … h
h j T N
.

. / / 0` 56 0/ bB D# P O 1 ,S x L ‘ # 5 ‘ = j . ‘ A=[aij] = D. 0` = . . ‘ # D#
5 .5 D# D 3. N / D0. MOSCP .# 5/6 g c# / / 0` p 0/ bB = &'( ‘ # 52
.#
&% !” #$ . $ GH0F ‘ – Nd( Z B 3#4 ai (+%,) 7 3#4 5FB a j D+ K ! L ! ‘ # *( ,L C G / D# b\ . B bB 0` ? *; C G / *; C C 00` J;2 bB L I
a)0.$”a)0.$ .? J;2 *;
.# “K

1268732040128

Downloaded from ijiepm.iust.ac.ir at 14:23 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:23 IRST on Saturday November 4th 2017

‘# . *;2 B ‘ # b\ . ! T0 0/ 1 G ; .dW ( 4. 5( bB) 4 5( ,) *+ % &'( $ ! “#
..01 2 3#4 56 70 -+ .’ / ‘ *; <; ‘ !# ‘: *2 9& ‘ ( / aij =0 # #4 0= ‘ >= A# . @aij =1# ? ) 3#4 0=
D A / C 3#4 0= B
. @
n
,’ GH0F = E ( ∑Xj≤ p 5/6
j=1
/ JB G.$ 5/6 I ‘
.. 0B L GH0F <K. G)0F
P 9 ! 0C *2 O0C / M NH@ MOSCP R/ / *P &’ S? .# . Q /) D# “# Q 5( # ? $ MOSCP ‘
Q A .,L $ R/ ?0 H&
.[T],’ >=

[] .
‘ 5. 9 ,; 5 $/ (SA) ; 0;# 9! / 4/ .L @ 0 % =% ‘ N ‘ ; $)0 ,L .# DC D ; 9= 5 U. V% 04 D 3′ L 50=-/ D ; ,L .# D0. ? . 3′ L Y W / D# XL @? J0@ ;. .5 ? 9= 0 OB G 0X 0/ *( DZ/ 3’ 5 U. 50=-/ D / D# 4 D ‘ @ N + 3′ 0;# 3′ .0 \. ,0′ ( ,070 *P N + 3)) ,0’ * .0? a. D, ;F G00` A ‘ 5 G00` 3′ 1 L O0 DB $, .# b\ . ,0= 9 ( N Q D, ;F 0X *0J+ )0. 9 ( 3’ N + 2/ ‘ !
,0F * .5 SA $/ G2 c+. $ .
,’ * ,’ 4 ,
Rd4 NP-Hard D.@ * = 3) . 3) J’ ,0F ). / ,0F 0X bB .5 d4. b, B $ $/ DC , / 0/ *( .# e 5=/ \ . $/ ‘ .
# 5 5′( / 3’ Q / .2 00= :5 D# P *$# ‘ 5 %- ,0. O 0

α Ti =α(Ti−1 ) ;∀i =1,…,n (t)

‘ l ‘ # 3’ <- ; < ‘ ,S # ? f. i/vv i/t 0 m= / D $ D# P ) a. .[w] 1 L + G= =n / 5 D# O / / , α + 5 x,’ . ‘ # O 0 V% 3′
5l + , 56 L 00` $ VB6 .5 D# O . 9! MAXTEMPDECS

.
bB p0 / C0’ 00= OF 4 1 $
e D# B c+. = SA O 1 MOSCP (*() ). B ,0! 5FB 5l bB F,704 D .# O 1 * 6 bB a ‘ + b\ . (N’ D0. 9!) Ln + 00= Ln + ; .# D ()) D. , ; ‘ ? P / / + , O 1 G= = .[o/w] 5# @ /C + . B ;F , ‘ ; ,L O 1 *@ (O 0 = 5( *’ =) # D7. N Q f. , 56 ‘ # SA O 1 3’ <;
.5 D# DC / >= O 1 MAXSAMEMARKOV

$% # ! ” .
SA ‘( “( $$! # ! ” &
0 5 / 50C0′ D,,’ 00= C 1 $ bB e B / Rd4 D6. bB l *( J( ‘ 0,’ y .# Q + , x B *( :O 2 O 1 bB 1 a)0.$ / / p;! ‘ D# Z 9=
.# Z’ L N Q + ‘ 5 D# x’.’
;6 (Min 5( ;0′ Q) ΔZ = Z’−Z
:

4 A# 9( .#
1268732040128Downloaded from ijiepm.iust.ac.ir at 14:23 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:23 IRST on Saturday November 4th 2017

? G ;F ;0′ Q D? L # ΔZ ≤ 0D? .h bB / D# B bB )1B 1 bB 0 . / O0+ / V 0l O 0 0/ + 00= O 0 U. 50=-/ ‘ S bB 9;2 0 F 5FB m .# / 5m 0
– ( 4 5() O 0 4 U. 0 3’
.# O 0 ,) . N6. T0 9= D 5/ aFC B <0 .[o]. n% ,) 01.0 . N6. 9= 0/ 5/ R/ D# P B 0= G= = MOSCP N Q R +
=) NSAMP H& “(Non-Stable) 4. 5( . .# D 2 (0/ ;6 f, 0/ ..
N Q) Obj( j )K 0` . N6.
:# *( p! (

NSAMP
∑Obj( j)
1368552829901

NSAMP
1
)
)
(
(
1
2



=
NSAMP
Mean
j
Obj
NSAMP
j

1

NSAMP



قیمت: تومان


دیدگاهتان را بنویسید