“*() %&’ “#$ !

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.

! ” (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

.
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

‘# . *;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 p02 / 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( .#
? 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 15/ 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! (

0?.. 01.0 = Mean

(j)
NSAMP −1

NSAMP
1368552-99223

∑(Obj( j)− Mean) 0? .. . N6.= j= (T)
NSAMP −1

: 5 G ; 0/ 9

T0 = Sqrt(Sum/( NSAMP−1)) (s)

f. E 0/ 0 G/C R/ ,S +
G 0/ O 1 R/ / .5
0/ + NSAMP DC / P
.’ ;6 >J \ 9 T D ; 0;# O 1 R/ 9( .? P NSAMP DC 0/ 0 .. = / Q0 O N Q / + 9/ 5( .L 5 0/ D# ? . N6. F.L . N6. N Q + a’ a/ 5(
0/ )0 + / L 01.0 D1.L / L 5
.# 0/ N Q a’ a 5(
5/ R/ DC / # ? f. )
.# ;6

. MOSCP *( 5FB D# (! O 1 OF z)B $ O 1 4 5FB ‘ # O 1 >2 A# 4 D# d4 %@ l bB 4
*’ 0= .# (+J() O 1 *@ $ ‘ V% G00` G= = 5 ; O 1
, 56 ‘ ( $ *’ =) 5 D# aH
.5 D# DC L O 1 MAXTEMPDECS

SA .
SA .
: !”
:0,’ >= 4
(Ln ) N’ D0. 9! •
(α) ; <- + •
(0` / F /6)(N ) = /( M )% = •
/ C 3#4 • ( $ *’ =) V% 00` G= = &'( •
(MAXTEMPDECS)
Gm( =) ;F 9K( a G= = &'( •
( MAXSAMEMARKOV) (O 0 9= 00= 5FB O 0 4. A# K .. = •
(NSAMP)0/ 2 ‘ (Q /) ω= •
= ω1 =ω2 / D# {/# ω2 =/ω1 =0 ‘) 0?
(/ 304 0/ / /

:#
.# ;0’ N Q ω2 =1 / ω1 =0 • ,0F bB ‘ 0e2 B ) [v/|]E(x)=∑D ωi fi(x)
i=1
l bB l bB ;0’ Q ([hi]#
:$ ‘ 0,’ 5 / / , N •
= &'() 0? 2 3, 9;2 *2 f. .(# p

: +J O 0 B bB , 9;2 *2 0/ bB •
.0,’ ;6 ;0′ N Q + .0,’

1 bB / # Nd( ,0F bB x B
.? J( L ,0F bB , ‘ 1 bB ;F a ,= # ΔZ > 0 D? .j h/i0 K Exp(−ΔZ / t ) + 5(
K L ?/ 0? 2 + ( Random(0,1)) / D# B bB )1B 1 bB D1.L ? ) G 0X / . J;2 B bB ,0F bB
1 bB D / / #. d4 1 bB .#

SA . l *( J( ‘ 0,’ y N Q + , x B *( :O 2 O 1 1 a)0.$ / / p;! ‘ 5 D# Z2 /Z1 9= N Q + ‘ 5 D# x’ .’ bB
/ (,) Q) ΔZ1 = Z1’−Z1 .# J( Z2′ / Z1′ L
9( .# ;6 (-+ .’ Q) ΔZ2 = Z2’−Z2
:

4 A#
;F Q / D? L # ΔZ2 ≥ 0 / ΔZ1 ≤0 D? .h B bB )1B 1 bB 0 . / ? G # Nd( l bB x B bB / D# l bB *( 1 1 bB /
1 1 bB AJ G / # +
.# Nd( bB L ($/) bB ;F a 1 / ;F N Q $ D? .j
,= (

? G
/ B bB / D? L N Q / 3) 3′ L )1B 1 bB / D AJ 0X 1 bB bB / ? 2 l bB / / D# l bB l bB 1 1
1 1 bB AJ G / # +
.# Nd( bB L ($ /) bB 01. G ;F N Q / D? .T
Exp(−ΔZ1 / t ) + N Q / D1.L (ΔZ2<0/ΔZ1>0)
K ! t G ( B Exp(ΔZ2 / t ) /
? / 0? 2 + ( Random(0,1)) / C 0 1 *( D? L K ? ) . Q / = J( / D# )1B B B bB , bB G 0X / # 1 L DC
1 bB D / / #. d4 1 .#
:%/
+J( @ ( (MAXSAMEMARKOV) D? •
.0? G 3′ / D#  @ J@
@ ( (MAXTECPDECS) >2 0= D? •
0 4 O 1 5 D# $ f. = O 1 . ,@f. ;0′ Q l bB J( + /

:$ 5 D0. 0/ω + ω2 ‘ . ω2 + •
./ / a? / 0 3) (/ / 0 3) $ ω1D? L # 0/ω ω2 ? •
./ / a? @ O 1 D? L .# 0/ω ω2 / ω1D? •
.

0$ SA .+

:!”
:0,’ >= 4
(Ln) N’ D0. 9! •
(α) ; <- + •
(0` / F /6) (N) = /( M )%= •
/ C 3#4 • ( $ *’ =) V% 00` G= = &'( •
(MAXTEMPDECS) = ) ;F 9K( a G= = &'( •
( MAXSAMEMARKOV) (O 0 9= Gm( (NSAMP) O 0 4. A# K .. = •
T0 ;6 T j h 9 5

:# 0 *0$7 / / , N • .(# p = &'()

:$ / +J O 0 B bB , 9;2 *2 0/ bB • .0,’ ;6 N Q +

:
0? $ ) 0,’ () B .’ *( •
.(K 1 a)0.$

: %&
0? $ ) 0,’ (1) B .’ *( •
.(K 1 a)0.$ 0@ 5 9;2 *2 B bB L ‘ 0,’ 9 ,’ •
.(# p = &'() / / O,4 a? 9;2 *2 D# 0 bB ? • .? FS a? D / G 0X

:'() # d4 B .’ bB L ‘ 0. }\7 •
.(B .’ bB Rd4 a)0.$ 0? $ ) ~0@ bB U. V% NH @ ;6 1 G ;
Q ΔZ = Z’−Z ,= ” x’ D# 0 bB / x 0/
.0,’ / ;6 ;0′

:* ,= 0? G O 0 U. V% ;F D? • bB .# x = x’ 9 ( [ΔZ = Z’−Z ≤ 0 ]
bB x’ 1 bB / D# Nd( x 0/
.0? 2 l
L (;0′ N Q ;F a) [ΔZ = Z’−Z > 0 ]D? •
/ C 0 K Exp(−ΔZ / t )9 ( D? L “. K ? ) ? / # + bB / .# (= $ bB x’ ) x = x’ D? .0? . 2 l bB

:*+
l bB e 1 B bB
5? 2 AJ 56 B ‘ .0P. + .0,’ N( bB

:,- N’ D0. 9! B O,4 a FS F? •
.0. $

:! .2 p;! : 3′ ( Q ) .2 •

Ti =αTi−1;α<1 ;∀i =1,…, Maxtempdecs (w)

.0. 3′ a2 α( 3′) ; <- +

:,
bB 704 0 ‘ . O C a FS a? •
.0,’ $ g ” t€j a? ” p% 7. *(
:
+J( @ ( (MAXSAMEMARKOV) D? •
.0? G 3′ / D#  @ J@
# *( (MAXTECPDECS) >2 A# / 0= D? •
l bB J( + .0 4 O 1 . ,@

! ! .
>= G 0= / D# 0 bB
.[|]#

&'( “#$% . ‘ J l bB D# 0 l bB J
9 DC 5 D# 2 R/ A
, F.L *2( / ;6 d 2( x,P ) = min∑D [ fi ( x )− y] 2
i=1
;6 4 .L 5 l bB %+. L J
, J bB a *2( J ? 2 bB 0=

d F P( , ) =Mean d x P[ ( , )] (*) .5 <, # ). C / $S’ +S +

-#/ 01( .,
‘ # 0 bB 0= 1 $ 😕 >= G

780665-33912

1618865-33912

{x P x x F≺ ∧ ≺ }
ν(P F,) = −1 (v)
{x P x≺ }

5 O 1 A D# 0 bB = ‘ G = *’ ‘ \ / ,#. J l bB )B ‘
S + .# SA O 1 D# 0 bB .5 F # ). / ? )

.
4 $J 1.1S / 0l f,
Ti×Ti / (M=N=10) hi×hi = MOSCP Q
=) %ji 5;. (M=N=50) ti×ti / (M=N=30) D# (5 %ji /( 3#4 B 0@ 5 9;2 *2 B bB L ‘ # 9 ,’ •
.(# p = &'() 0X / / FS a? 9;2 *2 D# 0 bB ? • .? a? G

: %& B .’ bB Rd4 a)0.$ 0? $ •
# d4 B .’ bB L ‘ 0,’ 0? O0K FB U. V% NH @ ;6 1 G ; ~0@
/ ΔZ = Z’−Z ,= x’ D# 0 bB / x 0/ .0,’ / ;6 N Q

:
;F D? •
x = x’ 9 ( 0? G O 0 U. V%
x’ 1 bB / D# Nd( x 0/ bB .#
.0? 2 l bB $ ? ,= 5# B/ AJ 0X bB / D? •
/ [ΔZ2 = Z2’−Z2 < 0 / ΔZ1 = Z1’−Z1 ≤ 0 ] : A#
/ 2 [ΔZ2 = Z2’−Z2 ≥ 0 / ΔZ1 = Z1’−Z1 > 0 ]
/ / D# x = x’ 9 ( / # d4 bB
..0? 2 l bB
;F a) [ΔZ2 = Z2’−Z2 < 0 /ΔZ1 = Z1’−Z1 > 0 ] D? • Exp(ΔZ2 / t ) / Exp(−ΔZ1 / t ) 9 ( D1.L (bB / / ? / # + / C 0 K $ bB x’ ) x = x’ D? L . K ? )
2 l bB bB / .# (= .0? . bB e 1 B bB :s€j a?
5? 2 AJ 56 B ‘ .0P. + l .



قیمت: تومان


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