“*() %&’ “#$ !

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 [email protected] [email protected]

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 – ! *[email protected] “D +F+ $+ & .+D A $+3* C [email protected]* $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 [email protected] +3& T ! ?3L) SM 5 4B ! 3&4 H* $B XW ! #0 % 5 %5 5 % “3<+ O4N ,, [email protected] .?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 :” # “$!

// :
// :
[email protected] [email protected] ()!* +$- .# /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
[email protected]* 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 [email protected]* Ti “4< -D) m = Si
(6[ +M ) V[ 5 (+D “- 5 4 aij Fi C j P [email protected]+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 – ! *[email protected] ” 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* [email protected]* # 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 @ , [email protected] 5 D# + *0F B/ $ ! 5? f. / C G
.# i $ *0F + 0; ai [email protected] 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 [email protected] 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 @? [email protected] ;. .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 [email protected] * = 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#  @ [email protected]
@ ( (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.$ [email protected] 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? $ ) [email protected] 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#  @ [email protected]
# *( (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 [email protected] 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 ; [email protected]
/ Δ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 .



قیمت: تومان


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