Constantinescu

8/18/2019 Constantinescu

http://slidepdf.com/reader/full/constantinescu 1/20

Ann Oper Res (2013) 207:67–81DOI 10.1007/s10479-011-0888-1

Routing and scheduling in project shipping

Kjetil Fagerholt · Lars Magnus Hvattum ·Trond A.V. Johnsen · Jarl Eiri Korsvi

Pub!s"e# $n!ne: 19 %&' 2011 "e Au*"$r(s) 2011. "!s &r*!+e !s pub!s"e# ,!*" $pen &++ess &* pr!ner!n.+$

A!stract r&p s"!pp!n +$p&n!es &re +$!**e# *$ *r&nsp$r* & se* $ +$n*r&+*e# +&r$es &n#

*r' *$ #er!e &##!*!$n& reenue r$ +&rr'!n $p*!$n& sp$* +&r$es. ere ,e presen* & re& !e

s"!p r$u*!n &n# s+"e#u!n pr$be $r & s"!pp!n +$p&n' $per&*!n !n pr$5e+* s"!pp!n &

spe+!& seen* $ *r&p s"!pp!n. "!s seen* #!ers r$ $re *r&#!*!$n& *r&p seen*s

&s *"e +&r$es &re usu&' *r&nsp$r*e# $n & $ne-*!e b&s!s. e+&use $ *"e spe+!& n&*ure $ *"e+&r$es +$p!+&*!n reu!reen*s re&r#!n s*$,&e $nb$&r# *"e s"!ps &n# +&r$ +$up!n

us* be +$ns!#ere# ,"!e #e*er!n!n r$u*es &n# s+"e#ues $r *"e s"!ps !n *"e ee*. A

&*"e&*!+& $#e !s presen*e# &n# & *&bu se&r+" "eur!s*!+ !s pr$p$se# *$ s$e *"e pr$be.

$pu*&*!$n& resu*s s"$, *"&* *"e *&bu se&r+" "eur!s*!+ pr$!#es $p*!& $r ne&r-$p*!&

s$u*!$ns !n & re&s$n&be &$un* $ *!e &n# *"&* !* +&n !e s!n!!+&n* !pr$een*s *$

&nu& p&nn!n $r *"e s"!pp!n +$p&n'.

Ke"#ords %&r!*!e *r&nsp$r*&*!$n · &bu se&r+" · *$,&e · &r$ +$up!n

. &er"$* ( ) · ;.%. &**uDep&r*en* $ In#us*r!& <+$n$!+s &n# e+"n$$' =$r,e!&n >n!ers!*' $ +!en+e &n# e+"n$$' Are#?e*@ e 3 7491 r$n#"e! =$r,&'e-&!: 5e*!.&er"$*!$*.n*nu.n$

;.%. &**ue-&!: &rs.."&**u!$*.n*nu.n$

.A.B. C$"nsen · C.<. $rs! =$r,e!&n %&r!ne e+"n$$' Rese&r+" Ins*!*u*e (%ARI=<) PO 412 B&en*!n's* 740 r$n#"e!

=$r,&'

.A.B. C$"nsene-&!: *r$n#.5$"nsen&r!n*e.s!n*e.n$

C.<. $rs! Dep&r*en* $ %&r!ne e+"n$$' =$r,e!&n >n!ers!*' $ +!en+e &n# e+"n$$' 7491 r$n#"e! =$r,&'

e-&!: 5&r.$rs!&r!n*e.s!n*e.n$

mailto:[email protected]















68 Ann Oper Res (2013) 207:67–81

$ %ntroduction

%&r!*!e *r&nsp$r*&*!$n !s *"e &5$r &r*er' $ !n*ern&*!$n& *r&#e ,!*" &n es*!&*e# s"&re be-

*,een 6E &n# 8E (>=AD 2007). "!p r$u*!n &n# s+"e#u!n +$ns*!*u*es $ne $ *"e $s*

!p$r*&n* un+*!$ns !n &n' s"!pp!n +$p&n!es &n# pr$per r$u*!n &n# s+"e#u!n !s*"ere$re +ru+!& &s & $#es* !pr$een* !n ee* u*!!@&*!$n +&n resu* !n &re pr$!* !-

pr$een*s. De+!s!$n supp$r* *$$s b&se# $n $per&*!$ns rese&r+" &re be+$!n $re +$-$n

,!*"!n *"e s"!pp!n !n#us*r' bu* s"!pp!n +$p&n!es &re & "e*er$ene$us r$up &n# *"e se* $

res*r!+*!$ns *"&* &pp' *$ *"e $per&*!$ns #!er be*,een e&+" +$p&n'. en+e $#es &n#

s$u*!$n e*"$#s use# *$ pr$!#e #e+!s!$n supp$r* reu!re spe+!& &#&p*&*!$ns *$ &++$$#&*e

#!eren* seen*s $ *"e s"!pp!n !n#us*r'.

Fe s*u#' & spe+!& ers!$n $ *r&p s"!pp!n. A s"!pp!n +$p&n' $per&*!n !n *"e *r&p

&re* usu&' "&s & se* $ &n#&*$r' +$n*r&+* +&r$es !* !s +$!**e# *$ +&rr' &n# ,! *r' *$

!n+re&se !*s reenue b' *r&nsp$r*!n $p*!$n& sp$* +&r$es. "e &n#&*$r' +$n*r&+* +&r$es

+$e r$ $n-*er &reeen*s be*,een *"e s"!pp!n +$p&n' &n# *"e +&r$ $,ners. <&+"

+&r$ !n *"e !en p&nn!n per!$# us* be p!+e# up &* !*s p$r* $ $&#!n *r&nsp$r*e# &n# *"en

#e!ere# *$ !*s +$rresp$n#!n #!s+"&r!n p$r*. "ere &re *!e ,!n#$,s !en ,!*"!n ,"!+"

*"e $&#!n $ *"e +&r$es us* s*&r* &n# *"ere &' &s$ eG!s* *!e ,!n#$,s $r #!s+"&r!n.

"e s"!pp!n +$p&n' +$n*r$s & "e*er$ene$us ee* $ s"!ps *$ *r&nsp$r* *"e +&r$es. "ere

&re +$p&*!b!!*' +$ns*r&!n*s be*,een s"!ps &n# +&r$es s!n+e $r !ns*&n+e s$e s"!ps +&nn$*

en*er & $&#!n &n# #!s+"&r!n p$r*s #ue *$ #r&* !!*&*!$ns.

"e p&nners $ & *r&p s"!pp!n +$p&n' s$e $n & #&!' b&s!s & s"!p r$u*!n &n#

s+"e#u!n pr$be ,"!+" !s s!!&r *$ *"e multi-vehicle pickup and delivery problem with time

windows #es+r!be# b' Desr$s!ers e* &. (199). ?ener&' *"e s"!p +&p&+!*!es &n# *"e +&r$

u&n*!*!es &re su+" *"&* *"e s"!ps +&n +&rr' u*!pe +&r$es s!u*&ne$us'. "e +"&ene $r

*"e *r&p s"!pp!n +$p&n' !s *$ see+* sp$* +&r$es &n# +$ns*ru+* r$u*es &n# s+"e#ues !n

$r#er *$ &G!!@e pr$!*. ere *"e pr$!* !s #e!ne# &s *"e !n+$e $ & *r&nsp$r*e# +&r$es

!nus *"e &r!&be s&!!n +$s*s ,"!+" &!n' +$ns!s* $ ue &n# p$r* +$s*s.

In *"!s p&per ,e #es+r!be &n# s$e &n !p$r*&n* re& !e s"!p r$u*!n &n# s+"e#u!n

pr$be *"&* &r!ses !n & spe+!& seen* $ *r&p s"!pp!n #en$*e# &s project shipping . "!s

seen* !s &s$ n$,n &s "e&' #u*' &n# "e&' !*!n &n# #!ers r$ $re *r&#!*!$n& *r&p

seen*s su+" &s ,e* &n# #r' bu s"!pp!n &s *"e +&r$es &re $*en un!ue &n# usu&'

*r&nsp$r*e# $n & $ne-*!e b&s!s. u+" +&r$es +&n $r !ns*&n+e be p&r*s $ & pr$+ess &+!!*'re&+*$rs $r '&+"*s. In *"!s seen* *"ere &re reu!reen*s re&*e# *$ cargo coupling &n#

stowage $nb$&r# *"e s"!ps !n &##!*!$n *$ *"e &b$e *r&p s"!pp!n pr$be &spe+*s. "e

s*$,&e reu!reen*s &r!se be+&use $ *"e spe+!& +"&r&+*er!s*!+s $ *"e +&r$es. A pr$5e+*

s"!pp!n +$p&n' &' nee# &n en!neer!n un!* *$ +&+u&*e *"e e&s!b!!*' $ *r&nsp$r*!n *"e!r

+&r$es ,!*" respe+* *$ s"&pe s*&b!!*' ,e!"* $r *"e s"!psH "e&' !*!n +&p&+!*!es. &s!+&' &

+&r$ +&n be p&+e# $nb$&r# & !en s"!p !n *,$ ,&'s: $n *"e #e+ $r be$, #e+ !n *"e s"!pHs

+&r$ "$#. "e en!neer!n un!* &s$ +&+u&*es "$, u+" #e+ &re& $r $ue be$, #e+ &

+&r$ reu!res. $e*"er ,!*" *"e r$u*!n &n# s+"e#u!n #e+!s!$ns *"e p&nners us* *"ere$re

be &be *$ e&u&*e *"e e&s!b!!*' $ *r&nsp$r*!n *"e +&r$es ,"!+" !s &&!n &e+*e# b' ,"e*"er *"e +&r$ !s p&+e# $n $r be$, #e+. "!s sep&r&*es pr$5e+* s"!pp!n r$ *r&#!*!$n& *r&p

s"!pp!n ,"ere *"e s*$,&e pr$be !s usu&' "&n#e# &s &n $per&*!$n& *&s &n# n$* &s & p&r*

$ *"e r$u*!n &n# s+"e#u!n. A*"$u" +&r$ p&+een*

Ann Oper Res (2013) 207:67–81 69



Fig. $ Ius*r&*!$n $ & s& eG&pe pr$be

#e+!s!$ns &re *&en !n*$ &++$un* ,"en p&nn!n *"e en!neer!n un!* &' s*! be reu!re# *$

&e &##!*!$n& +&+u&*!$ns s$ &s *$ &e sure *"&* s"!p s*&b!!*' !s &!n*&!ne# &n# *"&* !*es pu* $n #e+ #$ n$* b$+ !*es pu* !n *"e +&r$ "$#.

"e spe+!& n&*ure $ *"e +&r$es &s$ e&#s *$ s$e $*"er reu!reen*s $r *"e r$u*!n &n#

s+"e#u!n #e+!s!$ns. $r !ns*&n+e *"e s"!pp!n +$p&n' +&n re+e!e & b$$!n *en#er ,"!+"

+$ns!s*s $ seer& +&r$es r$ #!eren* $r!!ns *$ be #e!ere# &* $ne pr$+ess &+!!*' *$e*"er.

"!s !es coupling constraints spe+!'!n *"&* s$e $ *"e +&r$es +&nn$* be e&u&*e#

!n#!!#u&' bu* r&*"er us* be e&u&*e# &s se*s. I* !s &s$ +$$n *$ !p$se & reu!reen*

*"&* & +&r$es !n & +$upe# se* &re ser!+e# b' *"e s&e s"!p ! ser!+e# &* &.

!ure 1 s"$,s & s& eG&pe pr$be r$ =$r*"ern <ur$pe ,!*" !e +&r$es &n# *,$

s"!ps ,!*" !n!*!& p$s!*!$ns &* se&. <&+" +&r$ reu!res & !en $ue be$, #e+ (!en !n+ub!+ e*ers) $r &re& $n *"e #e+ (!en !n su&re e*ers). $r s$e +&r$es *"e #e+!s!$n

re&r#!n ,"e*"er *$ s*$, $n $r be$, #e+ !s !Ge# (+&r$es 3 &n# !n *"e eG&pe !n !. 1).

In *"e eG&pe ,e see *"&* +&r$es 1 &n# 2 be$n *$ *"e s&e se*. I +&r$ 1



70 Ann Oper Res (2013) 207:67–81

!s *r&nsp$r*e# *"en +&r$ 2 us* &s$ be *r&nsp$r*e# &n# !+e ers&. "e s&e &pp!es *$ +&r$es 4

&n# .

In &##!*!$n *$ *"e &b$e en*!$ne# reu!reen*s s$e +&r$es &' "&e single ser-vice

customer requirements. "!s e&ns *"&* s$e +&r$es us* be *r&nsp$r*e# #!re+*' r$ !*s

$&#!n p$r* *$ !*s +$rresp$n#!n #!s+"&r!n p$r* ,!*" n$ $*"er +&r$es $nb$&r# *"e s"!p &* *"e

s&e *!e een *"$u" *"e +&r$ #$es n$* reu!re *"e u +&p&+!*' $ *"e s"!p.

%$s* rese&r+" s*u#!es $n s"!p r$u*!n &n# s+"e#u!n pr$bes +$ns!#er eG&+* e*"$#s. A

+$$n &$r!*" !s *$ ener&*e & se* $ e&s!be s!ne s"!p s+"e#ues &n# see+* &n $p*!-&

+$b!n&*!$n b' s$!n & se* p&r*!*!$n!n pr$be see $r !ns*&n+e (! &n# ;ee 1997 &us+"

e* &. 1998 &er"$* 2001 &n# rJn$ e* &. 2006). $r &rer pr$be !ns*&n+es *"e s$u*!$n

&ppr$&+" b&se# $n ener&*!$n $ e&s!be s!ne s"!p s+"e#ues &' reu!re *$$ u+"

+$pu*&*!$n& *!e *$ &e !* useu !n & pr&+*!+& p&nn!n s!*u&*!$n. "ere "&e &s$ been

s$e +$n*r!bu*!$ns $n $+& se&r+"-b&se# "eur!s*!+s $r s"!p r$u*!n &n# s+"e#u!n pr$bes.

rJn$ e* &. (2007) presen* & u*!-s*&r* $+& se&r+" "eur!s*!+ ,"!+" &pp!es *$ *r&p s"!p

r$u*!n &n# s+"e#u!n pr$bes ,"!e $rs! e* &. (2010) #ee$p & *&bu se&r+" "eur!s*!+ $r

& s!!&r pr$be. $,eer n$ne $ *"e &b$e +$n*r!bu*!$ns #e& ,!*" *"e spe+!&

+"&r&+*er!s*!+s &n# reu!reen*s *"&* &r!se !n pr$5e+* s"!pp!n.

eer& *'pes $ &r!*!e s*$,&e pr$bes "&e been #es+r!be# !n *"e !*er&*ure &n#

*"e!r +"&r&+*er!s*!+s #epen# $n *"e *'pe $ s"!p &n# +&r$. *eenen e* &. (2004) &n#

*&"b$+ &n# B$ss (2008) !e sure's $n s*$,&e $ +$n*&!ner s"!ps. A s*$,&e pr$b-

e &r!s!n !n bu s"!pp!n !s *re&*e# b' &**u e* &. (2009). R$R$ s"!ps +&rr' e"!+es

&n# r$!n eu!pen* &n# Ks*ebJ e* &. (2011&) s*u#' *"e pr$be $ $&#!n &n#

un$&#-!n su+" +&r$ $n & !Ge# r$u*e. "e s*$,&e pr$bes #es+r!be# !n *"ese

+$n*r!bu*!$ns &re & #!eren* r$ *"e $ne &r!s!n !n pr$5e+* s"!pp!n. $b!n&*!$ns $

s*$,&e &n# r$u*!n "&e &s$ been s*u#!e# be$re. &er"$* &n# "r!s*!&nsen ( 2000&

2000b) +$ns!#er *"e !n-*er&*e# pr$be $ r$u*!n &n# s*$,&e !n #r' bu s"!pp!n

,"!e Ks*ebJ e* &. (2011b) s*u#' *"e !n*er&*e# pr$be $r R$R$ s"!ps. "e !*er&*ure

$r +$b!n!n r$u*!n &n# p&+-!n !n $*"er *r&nsp$r* $#es !s r$,!n u!+' bu* &

re+en* sure' !s pr$!#e# b' I$r! &n# %&r*e$ (2010).

"e &!n +$n*r!bu*!$n $ *"!s p&per !s *"e #ee$pen* $ &n e!+!en* *&bu se&r+" &-

$r!*" $r s"!p r$u*!n &n# s+"e#u!n pr$bes !n pr$5e+* s"!pp!n. e+*!$n 2 !es &

&*"e&*!+& pr$be #es+r!p*!$n. "e pr$p$se# s$u*!$n e*"$# !s #es+r!be# !n e+*. 3.A +$pu*&*!$n& s*u#' !n+u#!n *es*s $n re& #&*& pr$!#e# b' & pr$5e+* s"!p-p!n

+$p&n' !s presen*e# !n e+*. 4 ,"!e ,e #r&, s$e +$n+u#!n re&rs !n e+*. .

& Model 'ormulation

Fe n$, presen* & $#e *"&* &s$ !es & #e*&!e# &n# pre+!se pr$be #e!n!*!$n. e+*!$n 2.1

!n*r$#u+es *"e n$*&*!$n *"&* !s use# !n *"e $#e ,"!e e+*s. 2.2 – 2.7 presen* &n# eGp&!n *"e$b5e+*!e un+*!$n &n# *"e &r!$us +$ns*r&!n*s.

Ann Oper Res (2013) 207:67–81 71

2.1 =$*&*!$n



Sets and indices

V "!ps !n *"e ee* !n#eGe# b' v

N v =$#es +$p&*!be ,!*" s"!p v !n#eGe# b' i j &n# k

N P ;$&#!n n$#es N P L M1 , 2 , . . . , nN ,"ere n !s *"e nuber $ +&r$es &&!&be

N D!s+"&r!n n$#es N L Mn 1 , n 2 , . . . , 2nN ,"ere n i !s *"e

+$rresp$n#!n #!s+"&r!n n$#e $r $&#!n n$#e i

N P v ;$&#!n n$#es +$p&*!be ,!*" s"!p v N P v ⊆ N P

N v D!s+"&r!n n$#es +$p&*!be ,!*" s"!p v N v ⊆ N

N ! ;$&#!n n$#es $r +$n*r&+*e# +&r$es N ! ⊆ N P

N " ;$&#!n n$#es $r $p*!$n& +&r$es N " ⊆ N P

N S ;$&#!n n$#es $r *"e +&r$es ,!*" s!ne ser!+e reu!reen* N S ⊆ N P

# $upe# $p*!$n& +&r$ se*s

N #m ;$&#!n n$#es !n +$upe# $p*!$n& +&r$ se* m ∈ #

$v Ar+s %i, j & +$p&*!be ,!*" s"!p v

Parametes

'i Reenue $r *r&nsp$r*!n +&r$ i ($&#!n &* n$#e i ∈ N P *r&nsp$r*!n &n#

#!s+"&r!n !* &* n$#e n i&

! ijv $s* $ s&!!n r$ n$#e i *$ j ,!*" s"!p v !n+u#!n p$r* &n# $&#!n +$s* &* n$#e i

Qi

A

u&re e*er $ #e+ &re& reu!re# $n *"e s"!p $r +&r$ i ! !* !s s*$,e# $n #e+

Qi

V

B$ue reu!re# $n *"e s"!p $r +&r$ i ! !* !s s*$,e# be$, #e+ De+

&re& +&p&+!*' $ s"!p v

Qv ACAP

B$ue reu!re# $n *"e s"!p $r +&r$ i ! !* !s s*$,e# be$, #e+ De+ &re&

+&p&+!*' $ s"!p v

Qv

VCAP

B$ue reu!re# $n *"e s"!p $r +&r$ i ! !* !s s*$,e# be$, #e+ De+

&re&

+&p&+!*' $ s"!p v

( ij v &!!n *!e be*,een n$#es i &n# j ,!*" s"!p v !n+u#!n ser!+e *!e &* n$#e i ) iv <&r!es* s*&r* $ ser!+e &* n$#e i $r s"!p v

*iv ;&*es* s*&r* $ ser!+e &* n$#e i $r s"!p v

Variables

+ijv !n&r' $, &r!&be eu& *$ 1 ! s"!p v s&!s #!re+*' be*,een n$#es i &n# j

&n# 0 $*"er,!se

t iv *&r* *!e $ ser!+e &* n$#e i $r s"!p v

qm !n&r' +$up!n &r!&be eu& *$ 1 ! se* N #m !s *r&nsp$r*e# &n# 0 $*"er,!se

i !n&r' s*$,&e &r!&be eu& *$ 1 ! +&r$ i !s s*$,e# $n #e+ &n# 0 ! !* !s s*$,e# be$, #e+

liv

A

Are& $ $&# $n #e+ (!n su&re e*ers) $ s"!p v ,"en e&!n n$#e i

liv

V

B$ue $ $&# (be$, #e+) $n s"!p v ,"en e&!n n$#e i

In &##!*!$n *$ *"e &b$e n$*&*!$n ,e &s$ #e!ne ov &n# d v ,"ere ov represen*s *"e !n!*!&



$pen p$s!*!$n $r s"!p v ,"!e dv represen* &n &r*!!+!& en# n$#e. "e #!s*&n+es &n# +$s*s

*$ d v r$ & $*"er n$#es *"&* &re +$nne+*e# *$ dv !n *"e ne*,$r &re se* *$ @er$.



72 Ann Oper Res (2013) 207:67–81

2.2 Ob5e+*!e un+*!$n

"e $b5e+*!e un+*!$n !s #e!ne# &s $$,s:

max∑v∈V

∑i∈ N O

∑ j∈ N v

R i x ijv−∑v∈V

∑(i , j)∈ Av

Cijv xijv (1)

Ob5e+*!e un+*!$n (1) &G!!@es *"e pr$!* b' *&!n *"e #!eren+e be*,een *"e reenue r$

*"e $p*!$n& sp$* +&r$es &n# *"e &r!&be s&!!n &n# p$r* +$s*s *"r$u" *"e p&nn!n per!$#.

!n+e *"e +$n*r&+*e# +&r$es us* be *r&nsp$r*e# *"e reenue r$ *"ese +&n be +$n-s!#ere#

!Ge#. "ere$re ,e #$ n$* !n+u#e *"e reenue r$ *"ese !n *"e $b5e+*!e un+*!$n.

2.3 "!p r$u*!n +$ns*r&!n*s

"e r$u*!n $ *"e s"!ps !s res*r!+*e# b' +$ns*r&!n*s (2)–(6):

∑v∈V

∑ j∈ Nv∨(ij)∈ Av

x xijv=i∈ N c

∑v∈V


x xijv ≤i∈ N 0

∑ j∈ Nx

x Oviv=1v∈V

¿

∑ j∈ Nv∨(ij)∈ Av x xijv− ∑ j∈ Nv∨(ij)∈ Av

x xijv=0v∈V , i∈ N v{


x idv v=1v∈V

∑ j∈ Nv

x ijv−∑ j∈ Nv

x j , n+i , v=0v∈V ,i∈ N pv

(2)

(3)

(4)

()

(6)

(7)

$ns*r&!n*s (2) ensure *"&* & +$n*r&+*e# +&r$es $r *"e !en p&nn!n per!$# &re *r&nsp$r*e#

,"!e +$ns*r&!n*s (3) s*&*e *"&* *"e $p*!$n& sp$* +&r$es +&n be ser!+e# &* $s* $n+e.

$ns*r&!n*s (4)–(6) &re *"e $, +$nser&*!$n +$ns*r&!n*s $r e&+" s"!p. $ns*r&!n*s (7)

ensure *"&* *"e s&e s"!p !s!*s b$*" $&#!n n$#e &n# *"e +$rresp$n#!n #!s+"&r!n n$#e.

2.4 "!p $&# +$ns*r&!n*s



"e $&# $nb$&r# *"e s"!ps !s res*r!+*e# b' +$ns*r&!n*s (8)–(16):

l $ovv

l $ovvL 0 v ∈ V (8)

l $iv $

i j / l $

jv (v ACAP + $

i &% 1-- +ijv& v ∈V, j∈ N Pv , %i,j&∈ $v (9)

l V iv v

j j / lV jv (v

VCAP + V i &% 0-- +ijv& v ∈V, j∈ N Pv , %i,j&∈ $v (10)

l $iv 1 $

i j / l $

j1n,v 1 v ACAP

&% 1-- +i,j1n,v& v ∈V, j∈ N Pv , %i,j&∈ $v (11)

l V iv 1v

j j / lV j1n,v 1 v

VCAP

&% 1-- +i,j1n,v& v ∈V, j∈ N Pv , %i,j&∈ $v (12)

$ns*r&!n*s (2) ensure *"&* & +$n*r&+*e# +&r$es $r *"e !en p&nn!n per!$# &re *r&ns-p$r*e#

,"!e +$ns*r&!n*s (3) s*&*e *"&* *"e $p*!$n& sp$* +&r$es +&n be ser!+e# &* $s* $n+e. $ns*r&!n*s

(4)–(6) &re *"e $, +$nser&*!$n +$ns*r&!n*s $r e&+" s"!p. $ns*r&!n*s ( 7) ensure *"&* *"e s&e s"!p

!s!*s b$*" $&#!n n$#e &n# *"e +$rresp$n#!n #!s+"&r!n n$#e.

2.4 "!p $&# +$ns*r&!n*s

"e $&# $nb$&r# *"e s"!ps !s res*r!+*e# b' +$ns*r&!n*s (8)–(16):

l o $

v v L l oV

v v L 0 v ∈ V (8)

l iv $

O . j $

j P l j $

v O %.v $!$P

O . j $

&% 1 Q +ij v & v ∈ V , j ∈ N P v , %i, j & ∈ $v (9)

l ivV O . j

V j P l j

V v O %.v

V !$P O . j

V &% 1 Q +ij v & v ∈ V , j ∈ N P v , %i, j & ∈ $v (10)

l iv $ Q . j

$ j P l j

$On,v O .v

$!$P % 1 Q +i,j On,v & v ∈ V , j ∈ N P v , %i, j & ∈ $v (11)

l ivV

Q . jV j P l j

V On,v O .v

V !$P % 1 Q +i,j On,v & v ∈ V , j ∈ N P v , %i, j & ∈ $v (12)

In constraints (8), we assume for simplicity that the ships have no load

onboard when the

ships are available in the planning period. Constraints () and (!")

calculate the dec# area

load and volume load below dec# onboard the ships in the loadingnodes, respectively, while constraints (!!) and (!$) do the same in the

discharging nodes. %ome cargoes can only be stowed on dec# or below

dec#, which can easily be ensured by &'ing the z i variables to either !

or ". Capacity constraints (both dec# area and volume under dec#) are

given by (!)(!*) for the loading and discharging nodes, respectively. It

is also common to have weight capacity constraints in ship routing and

scheduling problems. +owever, in this proect shipping routing and

scheduling problem this is not a practical restriction and it is therefore

not included in the formulation.

∑ .i $ +ij v Q &GM.v

$!$P , .i $ N% 1 Q i & P l iv

$ P.v $!$P +ij v v ∈ V , i ∈ N P v

j ∈ N v j ∈ N v (13)

0 P l n $

Oi,v P ∑ %.v $!$P

Q .i $

&+nOi,j v v ∈ V , i ∈ N P v (14)



j ∈ N v

∑ .iV +ij v Q &GM.v

V !$P , .i

v N i P l iv

V P ∑ .v

V !$P +ij v v ∈ V , i ∈ N P v (1)

j ∈ N v j ∈ N v

0 P l nV

Oi,v P ∑ %.vV !$P

Q .iV &+nOi,j v v ∈ V , i ∈ N P v (16)

j ∈ N v

Ann Oper Res (2013) 207:67–81 73

In +$ns*r&!n*s (8) ,e &ssue $r s!p!+!*' *"&* *"e s"!ps "&e n$ $&# $nb$&r# ,"en *"e s"!ps &re

&&!&be !n *"e p&nn!n per!$#. $ns*r&!n*s (9) &n# (10) +&+u&*e *"e #e+ &re& $&# &n# $ue

$&# be$, #e+ $nb$&r# *"e s"!ps !n *"e $&#!n n$#es respe+*!e' ,"!e +$ns*r&!n*s ( 11) &n# (12)

#$ *"e s&e !n *"e #!s+"&r!n n$#es. $e +&r$es +&n $n' be s*$,e# $n #e+ $r be$, #e+

,"!+" +&n e&s!' be ensure# b' !G!n *"e i &r!&bes *$ e!-*"er 1 $r 0. &p&+!*' +$ns*r&!n*s (b$*"

#e+ &re& &n# $ue un#er #e+) &re !en b' (13) – (16) $r *"e $&#!n &n# #!s+"&r!n n$#es

respe+*!e'. I* !s &s$ +$$n *$ "&e ,e!"* +&p&+!*' +$ns*r&!n*s !n s"!p r$u*!n &n# s+"e#u!n pr$bes. $,eer !n *"!s pr$5e+* s"!p-p!n r$u*!n &n# s+"e#u!n pr$be *"!s !s n$* & pr&+*!+&

res*r!+*!$n &n# !* !s *"ere$re n$* !n+u#e# !n *"e $ru&*!$n.

2. !e +$ns*r&!n*s

"e s+"e#u!n $ *"e s"!ps !s res*r!+*e# b' +$ns*r&!n*s (17)– (20):

t iv ( ij v t j v %l iv ( ijv &% 1 Q +ij v & v ∈ V , %i, j & ∈ $v , i L ov (17)

t ovv O ( ov j v P t j v O %t ov v O ( ij v &% 1 Q +ij v & v∈ V , %i, j & ∈ $v , i L ov (18)

) iv t iv *iv v ∈ V , i ∈ N v (19)

t iv ∑ ( ijv +ijv Qt nOi,v P 0

v∈ V, i ∈ = Pv (20)

j∈ N v

"e !n!n $ *"e r$u*es &n# s+"e#ues !s !en b' (17)–(18). e+&use $ *"e !neu&!*'

s"!ps &re &$,e# *$ ,&!* &* *"e n$#es be$re s*&r* $ ser!+e. !e ,!n#$, +$ns*r&!n*s &re!en b' +$ns*r&!n*s (19) ,"!e +$ns*r&!n*s (20) $r+e $&#!n n$#e i *$ be !s!*e# be$re

*"e +$rresp$n#!n #!s+"&r!n n$#e n i.

2.6 Pr$5e+* s"!pp!n +$ns*r&!n*s

"e reu!reen*s *"&* &re spe+!& $r pr$5e+* s"!pp!n (!n &##!*!$n *$ *"e s*$,&e +$ns*r&!n*s !n e+*.

2.4) &re !en b' +$ns*r&!n*s (21)–(2):

∑ ∑ ∑ +ijv L N #m qm m ∈ # (21) v∈V i∈ N #m j ∈ N v

+i,n1i,v ∑ +ijv v ∈ V , i ∈ N s

j∈ N v



∑ +ijv ∑ +kjv v ∈ V , N k ∈ #, i,k, ∈ N k

j ∈ N v j ∈ N v



74 Ann Oper Res (2013) 207:67–81

"e +$up!n $ +&r$es !s !en b' +$ns*r&!n*s (21). "e nuber $ n$#es !s!*e# ,!*"!n *"e se*

us* e!*"er be eu& *$ *"e +&r#!n&!*' $ *"e se* ! & n$#e !n *"e se* !s ser!+e# $r @er$ ! *"e +$upe#

se* !s n$* ser!+e# &* &. "ese +$ns*r&!n*s &re $n' ne+ess&r' $r $p*!$n& +&r$es s!n+e +$ns*r&!n*s

(2) &e sure *"&* & +$n*r&+*e# +&r$es &re *r&nsp$r*e#.

"e s!ne ser!+e reu!reen*s &re !en b' +$ns*r&!n*s (22) –(2). $ns*r&!n*s (22) en-sure *"&*

! & s"!p ser!+es & +&r$ !n *"e s!ne ser!+e se* !* us* s&! #!re+*' *$ *"&* +&r$Hs #!s+"&r!n

n$#e. =$*e *"&* *"!s +&n !p!+!*' &s$ be *&en !n*$ &++$un* b' $n' #e!n!n *"e +ij v &r!&bes $n

*"e &r+s $!n #!re+*' r$ i *$ n i ! i ∈ N S . $ns*r&!n*s (23) ensure *"&* & +&r$es ,!*"!n &

+$upe# +&r$ se* s"$u# be ser!+e# b' *"e s&e s"!p ! ser!+e# &* &. $ns*r&!n*s ( 22) &n# (23) &re

n$* su!+!en* *$ ensure s!ne ser!+e reu!reen*. Fe us* &s$ &## $&# +$ns*r&!n*s ( 24) &n# (2)

,"!+" u&r&n*ee *"&* *"e $&# $nb$&r# *"e s"!p &*er $&#!n & s!ne ser!+e +&r$ +&nn$* be &rer

*"&n *"e $&# $ *"e +&r$ !*se $r #e+ &re& &n# $ue un#er #e+ respe+*!e'. "!s ,! ensure*"&* *"e s"!p "&s n$ $*"er +&r$es $nb$&r# ,"!e *r&nsp$r*!n & +&r$ ,!*" & s!ne ser!+e +us*$er

reu!reen* ,"!+" !s n$* u&r&n*ee# b' +$ns*r&!n*s (22) &n# (23) $n'.

2.7 B&r!&be #$&!ns

"e &r!&be #$&!ns &re !en b' +$ns*r&!n*s (26) –(28):

+ij v ∈ M0 , 1N v ∈ V , %i, j & ∈ $v (26)

qm ∈ M0 , 1N m ∈ # (27)

i ∈ M0 , 1N i ∈ N P (28)

( Ta!u search algorithm

Fe pr$p$se & +$pu*&*!$n&' e!+!en* *&bu se&r+" &$r!*" $r s$!n *"e r$u*!n &n# s+"e#u!n

pr$be !n pr$5e+* s"!pp!n. I* uses *"e s&e s*ru+*ure &s *"e *&bu se&r+" &$-r!*" $ $rs! e* &.

(2010) bu* !n+$rp$r&*es seer& &##!*!$n& e&*ures spe+!!+ *$ $ur pr$be. *&r*!n r$ &n !n!*!&

s$u*!$n s0 *"e &$r!*" $es &* !*er&*!$n t r$ *"e +ur-ren* s$u*!$n st *$ *"e bes* s$u*!$n s S !n &

ne!"b$ur"$$# N %st & $ st . An !p$r*&n* e&*ure $ *"e &ppr$&+" !s *"e p$ss!b!!*' $ +$ns!#er!n

!ne&s!be s$u*!$ns #ur!n *"e se&r+". "!s re&G&*!$n e+"&n!s &+!!*&*es *"e eGp$r&*!$n $ *"e

s$u*!$n sp&+e &n# !s p&r*!+u&r' use-u $r *!"*' +$ns*r&!ne# !ns*&n+es ,"!+" !s *"e +&se $r &n'

s"!p r$u*!n &n# s+"e#u!n pr$bes. $ &$!# +'+!n s$u*!$ns p$ssess!n s$e &**r!bu*es $

re+en*' !s!*e# s$u-*!$ns &re #e+&re# *&bu $r & nuber $ !*er&*!$ns uness *"e' +$ns*!*u*e & ne,

!n+uben*. A +$n*!nu$us #!ers!!+&*!$n e+"&n!s re#u+es *"e !e!"$$# $ be+$!n *r&ppe# !n &

$+& $p*!u &n# per!$#!+ re$p*!!@&*!$n $ *"e +urren* $r *"e bes* n$,n s$u*!$n !s per-$re#.

"e &!n s*eps $ *"e *&bu se&r+" &re repe&*e# $r & prese* nuber 2 $ !*er&*!$ns. !!&r *&bu se&r+"

&$r!*"s &re pr$p$se# b' $r#e&u e* &. (2001) &n# $r#e&u &n# ;&-p$r*e (2003) $r *"e e"!+er$u*!n pr$be &n# *"e #!& & r!#e pr$be respe+*!e'. In *"e $$,!n subse+*!$ns ,e #es+r!be

*"e &!n eeen*s $ $ur *&bu se&r+" "eur!s*!+ !n #e*&!.

Ann Oper Res (2013) 207:67–81 7

3.1 Re&G&*!$n e+"&n!s



;e* S #en$*e *"e s$u*!$ns s&*!s'!n +$ns*r&!n*s (1) –(12) (17)–(18

) (20) &n# (26)– (28). $,eer ,e

&$, *"&* *"e s$u*!$ns !$&*e +$ns*r&!n*s (13)–(16) (19

) &n# (21)– (2) ,"!+" represen*s +&p&+!*'

+$ns*r&!n*s *!e ,!n#$,s +$ns*r&!n*s +$up!n +$ns*r&!n*s &n# s!ne ser!+e reu!reen*s

respe+*!e'. $r & s$u*!$n s ∈ S e* c%s& #en$*e *"e *$*& s&!-!n +$s* $r *"e ee* $ s"!ps. I seer&

$ *"e &&!&be +&r$es &re re5e+*e# !n s$u*!$n s ,e !n*r$#u+e & re5e+*!$n +$s* $r *"ese +&r$es. Fe

se* *"e re5e+*!$n +$s* $ &n $p*!$n& sp$* +&r$ i eu& *$ !*s $s* reenue 'i . $r & &n#&*$r' +$n*r&+*+&r$ ,e !p$se & &re re5e+*!$n +$s* *$ ensure *"&* *"e +&r$ ,! be sere#. F"eneer *"e

s"!pp!n +$p&n' +&n sub+$n*r&+* & +&r$ !.e. !* +&n "!re & sp$* s"!p *$ *r&nsp$r* *"e +&r$ *"e

re5e+*!$n +$s* +&n be se* *$ *"e +$s* $ "!r!n *"e sp$* s"!p. "e *$*& +$s* $r re5e+*e# +&r$es !n

s$u*!$n s !s !en b' c %s&. ;e* u%s& #en$*e *"e *$*& !$&*!$n $ +&p&+!*' +$ns*r&!n*s. "e !$&*!$ns

$ +&p&+!*' +$ns*r&!n*s &re +&+u&*e# $n & r$u*e b&s!s ,!*" respe+* *$ *"e s"!ps +&p&+!*!es ($r #e*&!s

see e+*. 3.8). "e *$*& !$&*!$n $ *!e ,!n#$, +$ns*r&!n*s !s #en$*e# b' w%s&

&n# !s eu& *$ ∑ 2n

%t i Q *i & ,"ere + L &GM0 , +N &n# n !s *"e nuber $ +&r$es (,e su up *$ 2n iL1

s!n+e e&+" +&r$ +$ns!s*s $ b$*" & $&#!n &n# & #!s+"&re n$#e). I* s"$u# be $bsere# *"&* ser!+e &* &

n$#e +&nn$* s*&r* be$re *"e be!nn!n $ *"e *!e ,!n#$,. $ "&n#e *"e +$up!n +$ns*r&!n*s ,e &ss!n &

pen&*' 3mv $r *r&nsp$r*!n & !en +&r$ se* m ,!*" s"!p v. Dur!n *"e se&r+" *"e pen&*!es 3mv &re &#5us*e#s$ *"&* +&r$es r$ m &re ser!+e# b' *"e s&e s"!p $s* $ *"e *!e. $r #e*&!s $n "$, *"e pen&*!es &re

&#5us*e# see e+*. 3.9. P$*en*!& $es &re e&u&*e# us!n *"e +$s* un+*!$n *$ be !n!!@e#:

f (s) - c(s) c (s) /u(s) 0 w(s) ∑

∑ ∑ ∑

1mv'iv

v∈V m∈ # i∈ Nk mj∈ Nv

,"ere *"e p&r&e*ers 4 5 &n# Tmv &re p$s!*!e &n# &re #'n&!+&' &#5us*e# #ur!n *"e se&r+".

3.2 =e!"b$ur"$$# s*ru+*ure

F!*" e&+" s$u*!$n s ∈ S !s &ss$+!&*e# &n &**r!bu*e se* $%s& L M%i, v& : i L 1 , . . . , n v L 1 , . .

. , mN ,"ere %i, v& e&ns *"&* +&r$ i !s &ss!ne# *$ s"!p v. "e re5e+*e# +&r$es !n s$u*!$n s &re

&ss!ne# *$ & #u' s"!p ($r & sp$* s"!p). "e ne!"b$ur"$$# N %s& $ & s$u*!$n +$ns!s*s $ &

s$u*!$ns *"&* +&n be $b*&!ne# b' re$!n &n &**r!bu*e %i, v& r$ $%s& &n# rep&+!n !* ,!*"

&n$*"er &**r!bu*e %i, v6 & ,"ere v U v6 . Re$!n &n &**r!bu*e %i, v& +$ns!s*s $ re$!n *"e

$&#!n &n# #!s+"&re n$#es $ +&r$ i r$ *"e r$u*e $ s"!p v. "!s r$u*e !s *"en re+$nne+*e#

b' !n!n *"e pre#e+ess$r &n# su++ess$r $ *"e #ee*e# n$#es. Inser*!n n$#es i &n# %n i& !n

*"e r$u*e $ s"!p v !s per$re# !n $r#er *$ !n!!@e *"e *$*& !n+re&se !n +$s* un+*!$n 7 %s& b'

us!n s!pe !nser*!$ns (!.e. *"e $r#er!n $ *"e n$#es &re&#' !n *"e r$u*e $ s"!p v re&!ns

un+"&ne#). F"en +&r$ i !s re$e# r$ *"e r$u*e $ s"!p vH !*s re!nser*!$n !n *"&* r$u*e !s

$rb!##en $r *"e neG* T !*er&*!$ns b' &ss!n!n & *&bu s*&*us *$ *"e &**r!bu*e %i, v&. "r$u" &n

&sp!r&*!$n +r!*er!$n *"e *&bu s*&*us $ &n &**r!bu*e +&n be re$e# ! *"e se&r+" re&+"es &

s$u*!$n $ s&er +$s* *"&n *"e bes* n$,n s$u*!$n "&!n *"e !en &**r!bu*e.

3.3 D!ers!!+&*!$n s*r&*e'

$ #!ers!' *"e se&r+" &n' s$u*!$n s ∈ N %s& su+" *"&* 7 % s )V 7 %s& !s pen&!@e# b'

& &+*$r pr$p$r*!$n& *$ *"e reuen+' $ &##!*!$n $ !*s #!s*!nu!s"!n &**r!bu*e &n# & s+&!n

&+*$r.

(29)



76 Ann Oper Res (2013) 207:67–81

Fe e* 8iv be *"e nuber $ *!es &**r!bu*e %i, v& "&s been &##e# *$ *"e s$u*!$n #ur!n *"e

se&r+" &n# t represen*s *"e +urren* !*er&*!$n nuber. I %i, v& !s *"e &**r!bu*e *"&* us* be &##e#

*$ *"e +urren* s$u*!$n s *$ $b*&!n *"e ne, n$n-!pr$!n s$u*!$n s S *"e pen&*'

p% s &9%c% s & c6 % s && √ nm ρ iv/t

!s &##e# *$ 7 % s ) ,"en e&u&*!n *"e +$s* $ s . "e s+&!n %c% s & c6% s &&

√ nm !n*r$-#u+es & +$rre+*!$n *"&* &#5us*s *"e pen&*' ,!*" respe+* *$ *$*& s$u*!$n +$s*

&n# !ns*&n+e s!@e &s e&sure# b' nuber $ p$ss!be &**r!bu*es. !n&' *"e p&r&e*er 9 !s use#

*$ +$n*r$ *"e !n*ens!*' $ *"e #!ers!!+&*!$n. "ese pen&*!es "&e *"e ee+* $ #r!!n *"e

se&r+" pr$+ess *$,&r#s ess eGp$re# re!$ns $ *"e s$u*!$n sp&+e ,"eneer & $+& $p

3.4 In!*!& s$u*!$n

$ +$ns*ru+* &n !n!*!& s$u*!$n s0 ,e !rs* s$r* *"e !s* $ un&ss!ne# +&r$es !n !n+re&s!n $r#er

$ *"e s*&r* $ *"e *!e ,!n#$, $r *"e $&#!n n$#e. <&+" +&r$ !s *"en seuen*!&' &ss!ne# *$

*"e s"!p !n!!@!n *"e &ue $ *"e +$s* un+*!$n &n# *"e &ss$+!&*e# n$#es i &n# %n i& &re

!nser*e# !n *"e bes* p$s!*!$n !n *"e p&r*!&' +$ns*ru+*e# r$u*e.

3. &bu se&r+" !*er&*!$ns

"e *&bu se&r+" &$r!*" s*&r*s r$ *"e !n!*!& s$u*!$n s0 &n# see+*s &* !*er&*!$n t *"e bes*

n$n-*&bu s$u*!$n s S ∈ N %st & ,!*" respe+* *$ *"e $b5e+*!e un+*!$n 7 %s& S p%s& S. In!*!&' 4 L

5 L 1 ,"!e & 3mv &re se* eu& *$ @er$. A*er e&+" !*er&*!$n *"e &ues $ *"e p&r&e*ers 4 &n#

5 &re $#!!e#. I *"e +urren* s$u*!$n !s e&s!be ,!*" respe+* *$ +&p&+!*' +$ns*r&!n*s *"e &ue

$ 4 !s #!!#e# b' 1 : ,"ere : V 0 *$ &e !* ess +$s*' *$ !s!* s$u*!$ns !$&*!n

+$ns*r&!n*s $ *"&* *'pe. I *"e +urren* s$u*!$n !s !ne&s!be re&r#!n +&p&+!*' +$ns*r&!n*s 4 !s

u*!p!e# b' 1. : &n# !* be+$es $re eGpens!e *$ !$&*e +$ns*r&!n*s $ *"&* *'pe. "e

s&e rue !s &s$ &pp!e# *$ *"e p&r&e*er 5 &ss$+!&*e# ,!*" !$&*!$n $ *!e ,!n#$,

+$ns*r&!n*s. "e p&r&e*ers 3mv &re +"&ne# #ur!n *"e se&r+" !n $r#er *$ $r+e *"e +$upe#

+&r$es *$ be *r&nsp$r*e# ,!*" *"e s&e s"!p (see #es+r!p*!$n !n e+*. 3.9). Inser*!$n &n#

#ee*!$n +$s*s &re n$* u' re+$pu*e# &* eer' !*er&*!$n. !n+e e&+" eG+"&ne !n$es $n'

*,$ r$u*es !nser*!$n &n# #ee*!$n +$s*s $r & re&!n!n r$u*es &re s*! &!# &*er *"e eG+"&ne

"&s been per$re#. "e &$r!*" !s repe&*e# $r 2 !*er&*!$ns. "e bes* e&s!be s$u*!$n s2

en+$un*ere# #ur!n *"e se&r+" !s !#en*!!e#.

3.6 Per!$#!+ r$u*e re$p*!!@&*!$n

<er' ; !*er&*!$ns !n*r&-r$u*e eG+"&nes &re per$re#. "e $&#!n &n# #!s+"&r!n n$#es $

& +&r$es &re seuen*!&' re$e# r$ *"e!r +urren* r$u*e &n# &re *"en re!nser*e# !n *"e r$u*e

$ *"e s&e s"!p !n $r#er *$ !n!!@e *"e &ue $ 7 %s&. $ pr$!#e s$e $r $ per!$#!+

!n*ens!!+&*!$n !n*r&-r$u*e eG+"&nes &re &s$ per$re# ,"eneer & ne, bes* s$u*!$n !s

!#en*!!e# #ur!n *"e se&r+".

3.7 =e!"b$ur"$$# re#u+*!$n



$ re#u+e *"e s!@e $ *"e ne!"b$ur"$$# +$ns!#ere# &* eer' !*er&*!$n *"e $$,!n rue !s use#

,"en e&u&*!n *"e !p&+* $ !nser*!n *"e *,$ n$#es i &n# %n i& $ +&r$ i !n*$ *"e r$u*e $

s"!p v. !rs* !nser* *"e $&#!n n$#e i $ *"e +&r$ !n *"e bes* p$s!*!$n !n *"e r$u*e.

77 Ann Oper Res (2013) 207:67–81

"en !G!n *"e $&#!n n$#e !n !*s bes* p$s!*!$n & subseuen* !nser*!$ns $ *"e #!s+"&re

n$#e %n i& &re e&u&*e#. "!s rue "&s & s!n!!+&n* ee+* $n *"e +$pu*&*!$n& *!e &s !*

re#u+es *"e *!e $r e&u&*!n *"e !nser*!$n $ +&r$ i !n *"e r$u*e $ s"!p v r$ " %n2 & *$ "

%n&. "e bes* !nser*!$n $ & !en $&#!n n$#e *"e $ne *"&* !n!!@e *"e &ue $ 7 %s& !s

#epen#en* $n *"e &ues $ 4 &n# 5 be+&use *"ese p&r&e*ers &re $#!!e# &*er e&+" !*er&*!$n

$ *"e se&r+". As & resu* *"e bes* !nser*!$n p$s!*!$n $ *"e n$#e +&n +"&ne r$ $ne !*er&*!$n

*$ *"e neG* een ! *"e r$u*e !s un+"&ne#. In $r#er *$ re#u+e +$pu*&*!$n *!e ,e #$ n$*

re+$pu*e *"e !nser*!$n +$s*s !n un+"&ne# r$u*es een ! *"ere &' +$n+e!&b' eG!s* be**er

!nser*!$ns !en *"e ne, &ues $ 4 &n# 5 . A +$pe*e re+$pu*!n $ *"e !nser*!$n +$s*s !s$n' per$re# eer' < !*er&*!$ns.

3.8 *$,&e subpr$be

F"en +$ns!#er!n & !Ge# r$u*e *"&* !s ,"ere & *"e r$u*!n &r!&bes +ij v & *"e s+"e#u-!n

&r!&bes t iv &n# & *"e +&r$ +$up!n &r!&bes qm &re !Ge# *"e s*$,&e pr$be *"&* re&!ns

!s *$ #e+!#e $r e&+" n$#e !s!*e# ,"e*"er *"e +&r$ !s *$ be p&+e# &b$e $r be-$, #e+. "e

$b5e+*!e !s *$ !n!!@e *"e *$*& !$&*!$n $ *"e +&p&+!*' +$ns*r&!n*s ,!*" sep&r&*e ,e!"*s $r

&re& !$&*!$ns $ue !$&*!$ns &n# s!ne ser!+e !$&*!$ns. "!s pr$be ,"ere $n' *"e i

&r!&bes &re ree (*$e*"er ,!*" *"e &uG!!&r' l iv $ &n# l ivV &r!-&bes) !s s*! =P-"&r# &s +&n be

s"$,n *"r$u" & re#u+*!$n r$ *"e partition problem (PP) ,"!+" !s n$,n *$ be =P-+$pe*e

(?&r' &n# C$"nsen 1979): In PP ,e &re !en & se* = L Mb1 , . . . , bn N $ n nubers &n# us*

#e*er!ne ,"e*"er *"ere eG!s*s & p&r*!-

*!$n $ = !n*$ *,$ subse*s =1 &n# =2 su+" *"&*∑

j∈B 1

bj L

∑ j∈B 2

bj . r$ &n !ns*&n+e

$ PP ,e +&n ener&*e &n !ns*&n+e $ *"e s*$,&e pr$be ,"ere & s!ne s"!p !s!*s n $&#!n

n$#es !n su++ess!$n (&n# *"ere&*er *"e +$rresp$n#!n n #!s+"&r!n n$#es) ,"ere

Qv

ACAP=Q v

VCAP∑ j∈ B

bj2 &n# Q j

A

L Q j

V

L b j . e&r' & e&s!be s$u*!$n *$

*"e PP

eG!s*s $n' ! & s*$,&e s$u*!$n eG!s*s ,!*" n$ !$&*!$n $ e!*"er +$ns*r&!n*s $ern!n *"e &re&

&b$e #e+ $r +$ns*r&!n*s $ern!n *"e $ue be$, #e+. en+e *"e s*$,&e pr$b-e !s

=P-"&r# een *"$u" !* &' be ess +$peG *"&n $*"er s*$,&e pr$bes $++urr!n !n

&r!*!e *r&nsp$r*&*!$n su+" &s !n Ar!e e* &. (1998) De&#$ e* &. (2009) &n# &**u e* &.

(2009).

"e $$,!n &$r!*" !s use# *$ !n# s*$,&e #e+!s!$ns *"&* !n!!@e *"e *$*& !$&-*!$n$ +&p&+!*' +$ns*r&!n*s: A !Ge# r$u*e $ & s"!p ($r r$u*e seen* s*&r*!n &n# en#!n ,!*" *"e

s"!p be!n ep*') !s +$ns!#ere# n$#e b' n$#e &n# $r e&+" n$#e ,e +re&*e &bes ,!*" *"ree

&ues n&e' *"e +urren* $&# &b$e #e+ *"e +urren* $&# be$, #e+ &n# *"e su $

+&p&+!*' !$&*!$ns !n+urre# s$ &r. $r $&#!n n$#es *"e &bes &re +re&*e# b' eG-*en#!n e&+"

&be r$ *"e pre!$us n$#e b' e!*"er $&#!n &b$e $r be$, #e+ &n# $r #!s+"&r!n n$#es

*"e &bes &re +re&*e# b' &#5us*!n *"e +urren* $&# b&se# $n *"e +$rre-sp$n#!n $&#!n n$#e



&be. $r &n eG&+* &$r!*" ,e &' $n' &pp' #$!n&n+e rues $r n$#es ,"ere *"e s"!p !s

ep*' bu* $r & "eur!s*!+ &$r!*" ,e &s$ +$ns!#er #$!n&n+e $r n$n-ep*' s"!ps: ! & &be

"&s "!"er $r eu& &ues $r & *"e +urren* $&#s &n# *"e su $ !$&*!$ns s$ &r !* !s

re$e# &n# n$* +$ns!#ere# &&!n. F"en re&+"!n *"e !n& n$#e $ *"e r$u*e ($r seen*) *"e

&be ,!*" *"e

$,es* su $ +&p&+!*' !$&*!$ns !s use# &s & s*&r*!n p$!n* &n# *"e s*$,&e #e+!s!$ns &re $un#

b' b&+*r&+!n *"r$u" *"e &bes.

78 Ann Oper Res (2013) 207:67–81

3.9 $up!n +$ns*r&!n*

"e *er ∑v∈V ∑ m∈ #∑i∈ = #m ∑ j∈ Nv 3mv +ij v !n *"e $e e&u&*!$n un+*!$n (29) !s use# *$ $r+e *"e

+$upe# +&r$es *$ be *r&nsp$r*e# ,!*" *"e s&e s"!p. In *"e !n!*!& s$u*!$n *"ere

Ta!le & Resu*s $ runn!n Wpress us!n & *!e !!* $ *,$ "$urs

=$. ;P-re&G&*!$n es* b$un# es* ?&p e+$n#s *$ e+$n#s e+$n#s *$

s$u*!$n e&s!be *$ bes* $p*!&!*'

1 26638 473276 473276 0.0E 0.1 0.7 7.1

2 761491 91463 91463 0.0E 3.1 170.3 78.

3 761881 7190892 7190892 0.0E 1.3 98.0 13.74 4066972 313310 313310 0.0E 1.9 2.2 129.1

497428 3826624 3826624 0.0E 3.6 2.8 127.9

6 499879 4177192 4177192 0.0E 0.3 26.1 630.1

7 1081782 10128483 8682041 16.7E 60.9 131.8 =A

8 1094603 1028363 999807 3.0E 72.2 680.1 =A

9 9912482 9438833 9047644 4.3E 4.8 6364.9 =A

10 1239219 11808827 =A =A =A =A =A

11 1118321 144731 11178887 29.E 1732.8 7107.0 =A

12 21104308 20448860 =A =A =A =A =A13 2671969 26287692 =A =A =A =A =A

14 4239432 41764364 =A =A =A =A =A

Ta!le ( Resu*s $ runn!n *"e *&bu se&r+" *en *!es us!n e!*"er 1000 $r 10000 !*er&*!$ns

=$. 1000 !*er&*!$ns 10000 !*er&*!$ns

es* Aer&e Aer&e es* Aer&e Aer&e bes*/

s$u*!$n s$u*!$n *!e (s) s$u*!$n s$u*!$n *!e !n WPR<

se+$n#s

1 473276 473276 7.0 473276 473276 69.1 1.0000

2 91463 91463 9. 91463 91463 94.0 1.0000

3 7190892 7190892 9.2 7190892 7190892 93.6 1.0000

4 3120913 3120913 11.1 3120913 3120913 112.0 0.9960

3826624 3826624 11.0 3826624 3826624 108.0 1.0000

6 4177192 4177192 10.7 4177192 4177192 103.3 1.0000



7 8683460 8683460 14.4 8683460 8683460 139.0 1.0002

8 9960280 9960280 1.2 9960280 9960280 14.9 1.0000

9 9048296 9048296 17.3 9048296 9048296 162.8 1.0001

10 8741703 8688618 18.6 8741703 8741703 18.0 =A

11 11467091 11393601 22.2 11467091 11467091 220.8 1.028

12 16961882 16664222 27. 16972808 1691413 272.0 =A

13 218711 21428294 71.3 21871DD1 2181947 697.4 =A14 3686798 36633223 11.4 369647D2 36934720 196.9 =A

79 Ann Oper Res (2013) 207:67–81

!n&' resu*s us!n *"e *&bu se&r+" &re rep$r*e# !n &be 3. "e *&bu se&r+" "&s been

run $r 1000 &n# 10000 !*er&*!$ns ,!*" *en #!eren* r&n#$ see#s $r e&+" !ns*&n+e.

&be 3 s"$,s b$*" *"e bes* s$u*!$n &n# *"e &er&e s$u*!$n $un# $er *"e *en #!eren*

r&n#$ see#s &s ,e &s *"e &er&e *!e !n se+$n#s *&en. "ese *es*s ,ere eGe+u*e# $n &

+$pu*er ,!*" &n In*e $re2 Du$ 2.20 ?@ P>.

$p&r!n Wpress &n# *"e *&bu se&r+" ,e see *"&* Wpress pr$es *"e $p*!& s$u*!$n

$n s!G !ns*&n+es &n# *"&* *"e *&bu se&r+" !s &be *$ !n# *"e s&e s$u*!$n $n !e $ *"ese

!ns*&n+es. $r !ns*&n+e nuber $ur *"e *&bu se&r+" !n#s & s$u*!$n *"&* !s $n' s!"*'

,$rse. "e *&bu se&r+" !s er' r$bus* &n# !n#s *"e s&e s$u*!$n s*&r*!n r$ & *en

r&n#$ see#s &*er ess *"&n 1000 !*er&*!$ns. $r $ur &##!*!$n& !ns*&n+es Wpress !s &be *$

!n# & e&s!be s$u*!$n ,!*"$u* pr$!n $p*!&!*' bu* $r & $ *"ese $ur !ns*&n+es *"e

*&bu se&r+" $n &er&e pr$#u+es be**er s$u*!$ns &*er 5us* 1000 !*er&*!$ns. $r *"ere&!n!n $ur !ns*&n+es Wpress #$es n$* !n# e&s!be s$u*!$ns &n# *"e &ps be*,een *"e

bes* upper b$un#s b' Wpress &n# *"e s$u*!$ns $un# b' *"e *&bu se&r+" &re u!*e &re

(be*,een 13 &n# 3E). $,eer *"e !n!*!& &ps pr$#u+e# r$ Wpress &re u!*e &re $n

& *"e !ns*&n+es "en+e !* !s p$ss!be *"&* *"e !n& &ps be*,een *"e *&bu se&r+" s$u*!$ns

&n# *"e upper b$un#s $ Wpress &re $s*' #ue *$ "&!n p$$r upper b$un#s.

I* s"$u# be n$*e# *"&* us!n 10000 !*er&*!$ns !e n$* u+" +$p&re# *$ us!n $n'

1000 !*er&*!$ns. "ere$re !* sees *"&* 1000 !*er&*!$ns &re su!+!en* $r &n' pr&+*!+& &p-

p!+&*!$n. "!s &s$ !es & runn!n *!e ess *"&n 3 !nu*es $r s$!n *"e b!es*!ns*&n+es.

) *onclusion

In *"!s p&per ,e "&e !n*r$#u+e# &n# s$e# & re& r$u*!n &n# s+"e#u!n pr$be *"&* &r!ses !n

*"e pr$5e+* s"!pp!n seen* & spe+!& seen* !n *r&p s"!pp!n. "!s seen* #!ers r$

$re *r&#!*!$n& *r&p seen*s &s *"e +&r$es &re usu&' *r&nsp$r*e# $n & $ne-*!e b&s!s.

"e +"&r&+*er!s*!+s $ *"e +&r$es reu!re s*$,&e p&nn!n *$ be !n*er&*e# ,!*" *"e s+"e#u!n

&n# r$u*!n #e+!s!$ns. Fe presen*e# & &*"e&*!+& $#e &n# sues*e# & *&bu se&r+""eur!s*!+ *$ s$e *"e pr$be. A +$pu*&*!$n& s*u#' ,&s per$re# $n 14 *es* !n-s*&n+es

b&se# $n #&*& r$ & s"!pp!n +$p&n'. "e resu*s s"$, *"&* *"e pr$p$se# *&bu se&r+"

"eur!s*!+ pr$!#es $p*!& $r ne&r-$p*!& s$u*!$ns *$ *"e s&es* !ns*&n+es ,"!+" Wpress +&n

s$e. $r e#!u-s!@e# !ns*&n+es Wpress +&n !n# e&s!be s$u*!$ns bu* +&nn$* pr$e

$p*!&!*' &n# $r *"ese !ns*&n+es *"e *&bu se&r+" "eur!s*!+ !n#s be**er s$u*!$ns. $r *"e

&res* !ns*&n+es Wpress +&nn$* een !n# e&s!be s$u*!$ns. $,eer +$p&r!s$ns ,!*"



s$u*!$ns pr$#u+e# &nu&' b' p&nners !n *"e s"!pp!n +$p&n' !n#!+&*e *"&* *"e s$u*!$ns

"&e "!" u&!*' &n# !e s!n!!+&n* !pr$een*s. An$*"er $$# +"&r&+*er!s*!+ ,!*" *"e *&bu

se&r+" !s *"&* !* sees *$ be er' r$bus* &n# pr$#u+e s$u*!$ns $ er' s!!&r u&-!*' een ,!*"

#!eren* r&n#$ see#s. I* &s$ sees *"&* $r &n' pr&+*!+& &pp!+&*!$n 1000 !*er&*!$ns (!!n &

runn!n *!e $ ess *"&n 3 !nu*es een $r *"e &res* !ns*&n+e) &re su-!+!en*. A ers!$n $

*"e *&bu se&r+" "eur!s*!+ #es+r!be# !n *"!s p&per "&s been !n*er&*e# &s & s$er !n & pr$*$*'pe

#e+!s!$n supp$r* s's*e use# b' seer& s"!pp!n +$p&n!es (&er"$* 2004).



80 Ann Oper Res (2013) 207:67–81

Acno#ledgements "!s rese&r+" ,&s +&rr!e# $u* ,!*" !n&n+!& supp$r* r$ *"e

D<I%A; pr$5e+* sup-p$r*e# b' *"e Rese&r+" $un+! $ =$r,&'. Fe &re &s$ r&*eu *$

*"e s"!pp!n +$p&n' *"&* pr$!#e# re& #&*& $r *"e *es* +&ses use# !n *"e +$pu*&*!$n&s*u#'. "&ns &re #ue *$ *,$ reerees $r *"e!r &u&be +$en*s.

+pen Access "!s &r*!+e !s #!s*r!bu*e# un#er *"e *ers $ *"e re&*!e $$ns

A**r!bu*!$n =$n+$er-+!& ;!+ense ,"!+" per!*s &n' n$n+$er+!& use #!s*r!bu*!$n

&n# repr$#u+*!$n !n &n' e#!u pr$!#e# *"e $r!!n& &u*"$r(s) &n# s$ur+e &re +re#!*e#.

Re'erences

Ar!e %. Penn %. "p!rer =. X F!**eb$$n . (1998). *$,&e p&nn!n $r +$n*&!ner s"!ps *$ re#u+e *"e nuber $ s"!*s. $nnals o7 "peration 'esearch >? –71.

&us+" D. O. r$,n ?. ?. X R$nen D. (1998). +"e#u!n s"$r*-*er &r!ne *r&nsp$r*

$ bu pr$#u+*s.

@aritime Policy and @anagement AB 33–348.

rJn$ ?. "r!s*!&nsen %. &er"$* . X ='reen . (2007). A u*!-s*&r* $+&

se&r+" "eur!s*!+ $r s"!p s+"e#u!nYA +$pu*&*!$n& s*u#'. !omputers C

"perations 'esearch DE 900–917.

rJn$ ?. "r!s*!&nsen %. &er"$* . X ='reen . (2006). "!p r$u*!n &n#

s+"e#u!n ,!*" eG!be +&r$ s!@es. Fournal o7 the "peration 'esearch Society BG

1167–1177.

$r#e&u C.-. X ;&p$r*e ?. (2003). A *&bu se&r+" "eur!s*!+ $r *"e s*&*!+ u*!-e"!+e

#!&-&-r!#e pr$be.

(ransportation 'esearch. Part =H @ethodological D> 79–94.

$r#e&u C.-. ;&p$r*e ?. X %er+!er A. (2001). A un!!e# *&bu se&r+" "eur!s*!+ $r

e"!+e r$u*!n pr$bes ,!*" *!e ,!n#$,s. (he Fournal o7 the "perational

'esearch Society BA 928–936.

De&#$ R. Censen %. X +"u*e . (2009). ?ener&*!n $p*!& s*$,&e p&ns $r +$n*&!ner esse b&'s. In (he proceedings o7 the 0Bth international con7erence on

principles and practice o7 constraint pro-gramming %!P-IJ& *N!S Series $. B>DA

(pp. 6–20). er!n: pr!ner.

Desr$s!ers C. Du&s Z. $$$n %. %. X $u!s . (199). !e +$ns*r&!ne# r$u*!n

&n# s+"e#u!n. In %. O. & . ;. %&n&n*! . ;. %$n& X ?. ;. =e"&user

(<#s.) Kandbooks in operations research and management scienceH network routing

(pp. 3–139). As*er#&: =$r*"-$&n#.



Ann Oper Res (2013) 207:67–81 81

&er"$* . (2001). "!p s+"e#u!n ,!*" s$* *!e ,!n#$,sY&n $p*!!@&*!$n b&se#

&ppr$&+". )uropean Fournal o7 "perational 'esearch 0D0 9–71.

&er"$* . (2004). A +$pu*er-b&se# #e+!s!$n supp$r* s's*e $r esse ee*

s+"e#u!nYeGper!en+e &n# u*ure rese&r+". ecision Support Systems D> 3–47.

&er"$* . X "r!s*!&nsen %. (2000&). A +$b!ne# s"!p s+"e#u!n &n# &$+&*!$n

pr$be. (he Fournal o7 the "perational 'esearch Society B0 834–842.

&er"$* . X "r!s*!&nsen %. (2000b). A *r&e!n s&es&n pr$be ,!*" &$+&*!$n

*!e ,!n#$, &n# pre+e#en+e +$ns*r&!n*sY&n &pp!+&*!$n *$ s"!p s+"e#u!n.

Lnternational (ransactions in "perations 'esearch > 231–244.

?&r' %. R. X C$"nsen D. . (1979). !omputers and intractabilityH a guide to the theoryo7 NP-completeness. &n r&n+!s+$: ree&n.

&**u ;. %. &er"$* . X Aren*&n$ B. A. (2009). &n &$+&*!$n pr$bes !n

&r!*!e bu s"!p-p!n. !omputers C "perations 'esearch D? 301–3060.

I$r! %. X %&r*e$ . (2010). R$u*!n pr$bes ,!*" $&#!n +$ns*r&!n*s. ("P 0G 4–

27.

! .-. X ;ee .-. (1997). An $p*!!s&*!$n-b&se# #e+!s!$n supp$r* s's*e $r s"!p

s+"e#u!n. !om-puters C Lndustrial )ngineering DD 689–692.

$rs! C. <. &er"$* . X ;&p$r*e ?. (2010). A *&bu se&r+" "eur!s*!+ $r s"!p r$u*!n

&n# s+"e#u!n.(he Fournal o7 the "perational 'esearch Society ?0 94–603.

*&"b$+ R. X B$ss . (2008). Oper&*!$ns rese&r+" &* +$n*&!ner *er!n&s: & !*er&*ure

up#&*e. "'-Spektrum DI 1–2.

*eenen D. B$ss . X *&"b$+ R. (2004). $n*&!ner *er!n& $per&*!$n &n#

$per&*!$ns rese&r+"Y & +&ss!!+&*!$n &n# !*er&*ure re!e,. "'-Spektrum A? 3–49.

>=AD (2007). Re!e, $ &r!*!e *r&nsp$r* 2007. >n!*e# =&*!$ns =e, Z$r &n#

?ene&.

Ks*ebJ . O. &**u ;. %. X &er"$* . (2011&). Op*!!@&*!$n $ s*$,&e

p&nn!n $r R$R$ s"!ps.!omputers C "perations 'esearch DG 142–1434.

Ks*ebJ . O. &**u ;. %. X &er"$* . (2011b). R$u*!n &n# s+"e#u!n $

R$R$ s"!ps ,!*" s*$,&e +$ns*r&!n*s. $r*"+$!n !n (ransportation 'esearch Part

! .

Date post:	07-Jul-2018
Category:	Documents
Upload:	dana-daniela
View:	212 times
Download:	0 times

Constantinescu

Documents