“*() %&’ “#$ !

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.

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 – ! *[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

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 – ! *[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

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 [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 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



قیمت: تومان


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