Sol ing Mul i acili y Huff Loca ion Models on
Ne wo ks Using Va iable Neighbo hood Sea ch
and Mul i-S a Local Sea ch Me aheu is ics
Sanja Roksandi´ca,1Emilio Ca izosa b,2D agan U oˇse i´ca,3
Nenad Mladeno i´cc,4
aMa hema ical Ins i u e, Se bian Academy o Sciences and A s, Belg ade, Se bia
bFacul y o Ma hema ics, Uni e si y o Se ille, Se ille, Spain
cDepa men o Ma hema ics, SISCM, B unel Uni e si y, London, UK
Abs ac
We conside mul i acili y Huff loca ion p oblems on ne wo ks. The mixed in ege
nonlinea op imiza ion p oblem is sol ed using Va iable Neighbo hood Sea ch and
Mul i-S a Local Sea ch me aheu is ics. Compu a ional expe ience is epo ed.
Keywo ds: ne wo k, acili y loca ion, Huff model, a iable neighbo hood sea ch,
mul i-s a local sea ch, global op imiza ion.
1 In oduc ion
Loca ion op imiza ion p oblems on a ne wo k in a compe i i e en i onmen
ha e been ex ensi ely s udied in OR. The p oblem was fi s p esen ed by
1Email: [email p o ec ed]
2Email: [email p o ec ed]
3Email: [email p o ec ed]
4Email: nenad.mladeno ic@b unel.ac.uk
A ailable online a www.sciencedi ec .com
Elec onic No es in Disc e e Ma hema ics 39 (2012) 121–128
1571-0653/$ – see on ma e © 2012 Else ie B.V. All igh s ese ed.
www.else ie .com/loca e/endm
doi:10.1016/j.endm.2012.10.017
Hakimi [2]. He o mula ed he compe i i e p oblem unde he assump ion
ha consume s de e minis ically choose he nea es s o e. In he eal wo ld,
howe e , his assump ion is no always accep able, because consume s do no
always choose he nea es s o e. Ra he , consume s p obabilis ically choose
among se e al s o es. This p obabilis ic choice beha io is modeled by Huff,
known as he Huff model. Huff o mula ed a model o cap u ing ma ke sha e
assuming ha he p obabili y ha a consume pa onizes a shopping cen e is
p opo ional o he a ac i eness o he cen e and in e sely p opo ional o
a powe o he dis ance o i . Al hough he o iginal Huff model was based on
an assump ion ha a ma ke a ea is ep esen ed by a con inuous plane wi h
Euclidean dis ance, he model was ex ended o he ne wo k Huff model by
Okabe and Ki amu a [6] which was defined on a ne wo k wi h he sho es -
pa h dis ance. Ghosh and McLaffe y [1] conside ed hei p oblem unde he
same assump ion o disc e e demand (nodal demand). Okunuki and Okabe
[7] conside ed link based demand wi h sligh ly changed objec i e unc ion.
In his pape we apply he ne wo k Huff model o a compe i i e loca ion
p oblem op imizing new acili y loca ions on a ne wo k. We apply Va iable
Neighbo hood Sea ch and Mul i-S a Local Sea ch me aheu is ics o sol e
his p oblem assuming ha new acili ies can be loca ed a any poin on he
ne wo k and demand gene a ed in he nodes.
1.1 P oblem defini ion
We assume ha cus ome s a e loca ed in he e ices o a ne wo k N=(V,E),
V={ 1,...,
n},n∈N,E⊆V2. The cus ome s aise demand. We also
assume ha he e a e m acili ies al eady loca ed on he ne wo k. The acili ies
p o ide se ice and hence sa is y he aised demand. They a e loca ed a
poin s y1,...,y
mon ne wo k N. The demand w( i)=wiassocia ed wi h he
e ex i,i∈{1,...,n}, has he ollowing p ope ies:
w( i)≥0and 
i∈V
w( i)=1.
The demand wmay a y om e ex o e ex. Fo ins ance, i can be dis-
ibu ed uni o mly o each e ex.
Ou goal is o loca e pnew acili ies x1,...,x
pon he ne wo k which will
espond o he cus ome s’ demand so ha he cap u ed demand is maximal.
To s a e he abo e loca ion op imiza ion p oblem mo e explici ly, le us
o mula e he ne wo k Huff model on N.Fi s ly, le us in oduce acili y a -
ac i eness, a p ope y o each acili y in he sys em. Facili y a ac i eness
S. Roksandi´c e al. / Elec onic No es in Disc e e Ma hema ics 39 (2012) 121–128122
o a specific acili y may be measu ed by he floo a ea, by he numbe o se -
ices/i ems ha specific acili y offe s o in any o he p edefined way. The e-
o e, le us deno e wi h ay1,...,a
ymand ax1,...,a
xp he a ac i eness o he
exis ing and new acili ies, espec i ely. In o de o uni y he no a ions and
simpli y o mulas, le us deno e wi h a j he a ac i eness o
• he exis ing acili y when ≡y,j∈{1,...,m}and
• he new acili y when ≡x,j∈{1,...,p}
loca ed a poin j.Le d( i,
j) be he dis ance om he cus ome loca ed in
e ex i o he acili y a jon ne wo k N. Le us now in oduce dis ance
de e ence unc ion F(d( i,
j)) o he cus ome in i om he acili y a j.
The dis ance de e ence unc ion is a mono onically dec easing unc ion wi h
espec o d( i,
j). In his o iginal model, Huff specified he dis ance de e ence
unc ion Fas a powe unc ion, i.e.
F(d( i,
j)) = d( i,
j)−λ,λ>0.
E en ually, le P( i,
j) be he p obabili y o cus ome in ichoosing acili y
a jamong he m+ppossible acili ies. In hese e ms, he ne wo k Huff
model is as ollows
P( i,
j)= a jd( i,
j)−λ
 ka kd( i,
k)−λ.
Using he ne wo k Huff model, we p oceed wi h o mula ing a p oblem o
ob aining he demand D( j) cap u ed by acili y a j.Le D( i,
j)be he
demand in icap u ed by acili y a j. Since he Huff model gi es us he
choice p obabili y o cus ome in ichoosing he acili y a j,D( i,
j)is
ob ained om mul iplying he p obabili y P( i,
j)byw( i), i.e.
D( i,
j)=P( i,
j)w( i)= a jd( i,
j)−λ
 ka kd( i,
k)−λw( i).(1)
To ob ain he demand D( j) cap u ed by acili y a jwe need o sum he
equa ion (1) o e all e ices i∈V, i.e.
D( j)=
i∈V
D( i,
j)=
i∈V
a jd( i,
j)−λ
 ka kd( i,
k)−λw( i).
Wi h mexis ing acili ies loca ed a poin s y1,...,y
mo ne wo k Nwe a e
supposed o loca e pnew acili ies a poin s x1,...,x
pin o de o compe e
S. Roksandi´c e al. / Elec onic No es in Disc e e Ma hema ics 39 (2012) 121–128 123
hem and cap u e maximal demand. The o al demand cap u ed only by new
acili ies is gi en by o mula
p

j=1
D(xj)=
p

j=1

i∈V
axjd( i,x
j)−λ
 ka kd( i,
k)−λw( i),
whe e ∈{y,z};j∈{1,...,m}i =y, and j∈{1,...,p}i =z. Since
i has o be maximal, p oblem we ha e o sol e is
max
x1,...,xp∈N
p

j=1

i∈V
axjd( i,x
j)−λ
 ka kd( i,
k)−λw( i).
2 Va iable Neighbo hood Sea ch and he applica ion o
Huff loca ion p oblem
2.1 Va iable Neighbo hood Sea ch concep
Va iable Neighbo hood Sea ch (VNS) ([3],[5]) is a well known me aheu is ic
me hod. I is designed o sol ing a ious combina o ial op imiza ion p ob-
lems. I uses local sea ch p ocedu e as one o i s basic ools. Mo eo e ,
i in ol es sys ema ic change o neighbo hoods in he sea ch. Unlike me a-
heu is ics based on local sea ch me hods, VNS does no ollow a ajec o y,
bu explo es inc easingly dis an neighbo hoods o he cu en incumben so-
lu ion. Then, a local sea ch ou ine is applied epea edly o find local op ima
s a ing om hese neighbo ing solu ions. The sea ch is e-cen e ed a ound
a new solu ion i and only i an imp o emen has been made wi h espec o
global bes solu ion.
The e o e, o cons uc diffe en neighbo hood s uc u es and o pe o m a
sys ema ic sea ch, we need o ha e a way o finding he dis ance be ween any
wo solu ions, i.e., one needs o supply he solu ion space wi h some me ic
(o quasi-me ic) and hen induce neighbo hoods om i . In he ollowing
sec ions we answe his p oblem-specific ques ion o ou pa icula p oblem.
The basic idea o VNS me aheu is ic is o use mo e han one neighbo hood
s uc u e and o p oceed o a sys ema ic change o hem wi hin a local sea ch.
The algo i hm emains in he same solu ion un il ano he solu ion be e han
he incumben is ound and hen jumps he e. Neighbo hoods a e usually
anked in such a way ha in ensifica ion o he sea ch a ound he cu en
solu ion is ollowed na u ally by di e sifica ion. The le el o in ensifica ion o
di e sifica ion can be con olled by a ew easy o se pa ame e s. We may iew
S. Roksandi´c e al. / Elec onic No es in Disc e e Ma hema ics 39 (2012) 121–128124
he VNS as a ”shaking” p ocess, whe e a mo emen o a neighbo hood u -
he om he cu en solu ion co esponds o a ha de shake. Unlike andom
es a , he VNS allows a con olled inc ease in he le el o he shake.
2.2 The applica ion o he Huff ne wo k model
In o de o implemen VNS o he specific a ian o he Huff loca ion p ob-
lem, we need o define solu ion ep esen a ion as well as neighbo hood s uc-
u es and local sea ch s a egy. A pa icula solu ion consis s o he loca ion
se o he new acili ies on he gi en ne wo k. The loca ion o each acili y is
uniquely de e mined by he edge, i.e. by he pai o e ices, and he posi ion
on he edge. The posi ion on he edge is gi en by 1-dimension coo dina e
belonging o he [0,1] in e al wi h espec o one o he e ices o he edge.
The e o e, he loca ion o he pa icula acili y is gi en by he o de ed pai
(x, (u, )), whe e he fi s en y e e s o he posi ion on he edge gi en by he
second en y o he pai . The posi ion xis calcula ed wi h espec o he fi s
e ex o he pai ela ed o he edge. As he pa icula solu ion consis s o p
acili y loca ions, i will be p esen ed as a lis [(x1,(u1,
1)),...,(xp,(up,
p))]
o po de ed pai s whe e he i h pai co esponds o he i h acili y loca ion.
Le us now define a neighbo hood s uc u e in he solu ion space we in-
oduced. I s=[(x1,(u1,
1)),...,(xp,(up,
p))] is a solu ion, we may chose
a andom one o he p acili ies and mo e i o one o he adjacen edges.
Then we pe o m local sea ch on he new edge by some o he well known
echniques (line sea ch, Fibonacci sea ch, e c.) in o de o each he loca ion
which influences he objec i e unc ion he mos . We call his ope a ion he
ank 1s epping. I we epea his ope a ion k imes, k<=p,wecalli he
ank ks epping. We say ha a solu ion sis a he s ep-dis ance k om he
solu ion si scan be ans o med in o sby applying he ank ks epping.
In o de o imp o e he implemen a ion pe o mances, we ha e in oduced
ano he ype o neighbo hood s uc u es. I s=[(x1,(u1,
1)),...,(xp,(up,
p))]
is a solu ion, we may chose a andom wo o he pnew acili ies o he solu ion
and swap hei loca ions. We call his ope a ion he ank 1swapping.I we
epea his ope a ion k imes, k<p/2,wecalli he ank kswapping.We
say ha a solu ion sis a he swap-dis ance k om he solu ion si scan
be ans o med in o sby applying he ank kswapping. The bes esul s a e
ob ained combining hese wo ypes o neighbo hood s uc u es.
To comple e he VNS implemen a ion, we ha e o define local sea ch s a -
egy. A fi s imp o emen local sea ch s a egy is pe o med: s a ing om a
solu ion swe mo e a new acili y o each o he adjacen edges un il he fi s
S. Roksandi´c e al. / Elec onic No es in Disc e e Ma hema ics 39 (2012) 121–128 125

imp o emen o he objec i e unc ion alue is ound. A e epea ing his o
each o he pnew acili ies, he bes o he ob ained ploca ions is kep .
Le us deno e by Nk,k=1,...,k
max a fini e sequence o p e-selec ed neigh-
bo hood s uc u es, and by Nk(x) he se o easible solu ions co esponding
o neighbo hood s uc u e Nka he poin x,whe exis an ini ial solu ion. Le
us no e ha mos local sea ch me aheu is ics use one neighbo hood s uc u e,
i.e. kmax = 1. The algo i hm p esen ed he e demons a es he applica ion o
he basic VNS heu is ic o he mul i acili y Huff loca ion model on a ne wo k.
Algo i hm 1 VNS algo i hm o Huff loca ion model.
1. Find an ini ial solu ion
2. Choose a s opping c i e ion
3. epea
4. k=1
5. while (k<=kmax)
6. (Shaking) Choose a andom ei he s epping o
swapping neighbo hood ype wi h equal p obabili y.
Gene a e andomly a poin x om Nk(x)
7. (Local sea ch) Apply fi s imp o emen local sea ch me hod
wi h xas he ini ial solu ion;
he ob ained local minimum deno e by x
8. (Mo e o no ) i x is be e han he incumben
9. mo e o x (x=x)
10. k=1
11. else k=k+1
12. un il he s opping c i e ion is me
Usually, he ini ial solu ion is de e mined by some cons uc i e heu is-
ic and hen imp o ed by local sea ch be o e he beginning o ac ual VNS
p ocedu e. In his case he ini ial solu ion is gene a ed andomly and hen
imp o ed by Fibonacci local sea ch me hod. The s opping c i e ion may be
e.g. he p ede e mined maximal allowed CPU ime, he maximal numbe o
all i e a ions o he i e a ions be ween wo imp o emen s. He e he s opping
c i e ion is maximal allowed CPU ime. O en successi e neighbo hoods Nk
a e nes ed, bu i is no necessa y o be always he case. Le us no e ha he
poin xis gene a ed a andom in o de o a oid cycling which migh occu i
any de e minis ic ule was used. Basic VNS is a simple me aheu is ic and i s
only pa ame e is kmax he p eselec ed numbe o neighbo hoods. Al hough,
o each pa icula p oblem he solu ion ep esen a ion, numbe and o de o
neighbo hoods, and s opping condi ion should be defined in a way o ensu e
S. Roksandi´c e al. / Elec onic No es in Disc e e Ma hema ics 39 (2012) 121–128126
Table 1
Compu a ional esul s
Ins ance VNS MSLS
No. n q p bes a g s .de bes . ime bes bes . ime
1lin105. sp 105 13 850.00 50.00 0.00 3077.89 20.77 102.06
2p 124. sp 124 15 10 49.71 49.65 0.07 3844.65 22.55 2599.89
3p 136. sp 136 17 11 41.50 41.22 0.30 4205.92 23.41 3572.44
4k oA150. sp 150 18 12 41.67 41.39 0.22 4783.25 19.68 2157.19
5k oB200. sp 200 25 16 47.64 47.28 0.21 14687.06 17.96 8959.79
efficien execu ion o he sea ch.
3 Compu a ional esul s
The VNS algo i hm o he specific Huff loca ion model is implemen ed in C
p og amming language on Linux pla o m. Tes ins ances ha e been un on
he compu e wi h he i686 In el Co e 2 Duo CPU E6750 a 2.66GHz and
8GB RAM.
Since he e does no exis s he se o benchma k p oblems o he Huff lo-
ca ion model, we ha e chosen small p oblems om he TSPLIB lib a y whe e
ne wo k dimension a ies om 100 o 200. The numbe qo exis ing acili ies
is se o n/8 and he numbe o new ones o 2/3q. The loca ions o exis ing
acili ies a e c ea ed in he ollowing way. Fi s ly, hey ha e been chosen an-
domly. Then he VNS me hod was applied wi h 10% o o al unning ime
planned o he VNS algo i hm execu ion o he pa icula es ins ance. In
he end, andomly chosen pou o qexis ing acili y loca ions we e swi ched
wi h he new acili y loca ions ob ained by he VNS algo i hm. The a ac-
i eness o each acili y has been chosen andomly. Ou expe ience shows ha
he bes esul s a e ob ained i he p obabili y o choosing ei he s epping o
swapping shaking s a egy is se o 0.5. kmax should be se o p/2. Maximal
unning ime depends on he size o he pa icula es ins ance and i a ies
om1 o5hou s.
The esul s ob ained by VNS a e compa ed wi h he esul s ob ained by
he Mul i-S a Local Sea ch me aheu is ic (MSLS). I is an i e a i e app oach
whe e a single i e a ion consis s o gene a ing a andom solu ion and pe o m-
ing a local sea ch s a egy wi h he andom solu ion as a s a ing poin . In
case he e was he imp o emen o he objec i e unc ion alue, he incum-
S. Roksandi´c e al. / Elec onic No es in Disc e e Ma hema ics 39 (2012) 121–128 127
ben is upda ed. We applied fi s imp o emen local sea ch s a egy. Ini ial
solu ion was gene a ed andomly. The algo i hm is implemen ed in C p o-
g amming language on Linux pla o m. The ob ained esul s a e p esen ed in
he Table 1. Bo h o he algo i hms we e gi en he same o al execu ion ime,
al hough, only ime when he bes solu ion was eached is epo ed. Solu ions
(ei he bes o a e age) a e exp essed as he pe cen age o he o al demand.
4Conclusion
We may conclude ha VNS beha es be e han MSLS in all es ed examples
in he sense o he objec i e unc ion alue, al hough o he same unning
pe iod MSLS eaches i s bes solu ion in less ime.
Re e ences
[1] Ghosh, A., McLaffe y, S., and C. S. C aig, Mul i acili y e ail ne wo ks,in
Facili y Loca ions, (D ezne , Z., ed). (1995), 301-330.
[2] Hakimi, S. L., On loca ing new acili ies in a compe i i e en i onmen ,Eu opean
Jou nal o Ope a ional Resea ch. 12, (1983), 29–35.
[3] Hansen, P., and N. Mladeno i´c, Va iable neighbo hood sea ch me hods,
Encyclopedia o Op imiza ion, 2nd Ed., Sp inge . pa (22), (2009), 3975–3989.
[4] Huff, D. L., A P obabilis ic Analysis o Shopping Cen e T ade A eas,Land
Economics. 39, (1963), 81–90.
[5] Mladeno i´c, N., and P. Hansen, Va iable neighbo hood sea ch: p inciples and
applica ions, Eu opean Jou nal o Ope a ional Resea ch. 130, (1997), 449–467.
[6] Okabe, A., and M. Ki amu a, A compu a ional me hod o ma ke a ea analysis
on a ne wo k, Geog aphical Analysis. 28, (1996), 330-349.
[7] Okunuki, K.-I., and A. Okabe, Sol ing he Huff-Based Compe i i e Loca ion
Model on a Ne wo k wi h Link-Based Demand, Annals o Ope a ions Resea ch.
111, (2002), 239-252.
S. Roksandi´c e al. / Elec onic No es in Disc e e Ma hema ics 39 (2012) 121–128128