Yang, Lu; Yang, Zhouwang
A icle
An ad anced Successi e De i a i e Sho es Pa h
algo i hm o conca e cos ne wo k low p oblems
Ope a ions Resea ch Pe spec i es
P o ided in Coope a ion wi h:
Else ie
Sugges ed Ci a ion: Yang, Lu; Yang, Zhouwang (2025) : An ad anced Successi e De i a i e Sho es
Pa h algo i hm o conca e cos ne wo k low p oblems, Ope a ions Resea ch Pe spec i es, ISSN
2214-7160, Else ie , Ams e dam, Vol. 14, pp. 1-13,
h ps://doi.o g/10.1016/j.o p.2025.100331
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/325808
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h p://c ea i ecommons.o g/licenses/by-nc-nd/4.0/
Con en s lis s a ailable a ScienceDi ec
Ope a ions Resea ch Pe spec i es
jou nal homepage: www.else ie .com/loca e/o p
An ad anced Successi e De i a i e Sho es Pa h algo i hm o conca e cos
ne wo k low p oblems✩
Lu Yang , Zhouwang Yang∗
Uni e si y o Science and Technology o China, He ei, PR China
ARTICLE INFO
Da ase link: h ps://gi hub.com/lu izyang/Da
a-and-Code- o -CCNFP
Keywo ds:
Ne wo k low
Non-con ex p oblem
App oxima ion algo i hm
Regional i s -o de in o ma ion
In e al educ ion
ABSTRACT
As p oduc ion scales up, anspo a ion ne wo ks inc easingly in ol e nonlinea cos s, leading o he conca e
cos ne wo k low p oblem (CCNFP), which is no ably challenging due o i s nonlinea i y. Exis ing nonlinea
p og amming me hods add essing he CCNFP o en su e om low e iciency and high compu a ional cos ,
limi ing hei p ac ical applica ion. To o e come hese limi a ions, his pape p oposes he Successi e De i a-
i e Sho es Pa h (SDSP) algo i hm, an e icien app oach ha combines a sequen ial linea app oxima ion
amewo k wi h egional i s -o de in o ma ion o he objec i e unc ion. By in eg a ing egional i s -o de
in o ma ion and employing an in e al educ ion mechanism, he SDSP algo i hm e ec i ely a oids p ema u e
con e gence o subop imal solu ions, he eby achie ing highe -quali y solu ions. Nume ical expe imen s,
including pa ame e selec ion, alida ion, and compa a i e analysis, demons a e ha he SDSP algo i hm
ou pe o ms exis ing me hods in e ms o bo h solu ion quali y and con e gence speed. This esea ch o e s a
obus and e icien solu ion o he CCNFP, wi h po en ial applica ions in a ious ields, including logis ics
and supply chain ne wo ks, whe e conca e cos ne wo k low issues a e common.
1. In oduc ion
As socie al demands e ol e and p oduc ion p ocesses g ow in
complexi y, he need o op imizing esou ce alloca ion o maximize
economic e iciency has become inc easingly c i ical. The minimum-
cos low p oblem [1], a ounda ional model in op imiza ion and
esou ce alloca ion, has seen b oad applica ions ac oss di e se p ac ical
ields [2–4]. Howe e , endogenous ac o s in eal-wo ld applica ions
o en in oduce nonlinea cos s uc u es, such as economies o scale [5]
and isk- ela ed cos s [6], making hese p oblems challenging o
adi ional minimum-cos low algo i hms [7–10] o add ess e ec i ely.
Consequen ly, conca e cos ne wo k low p oblems ha e eme ged as a
cen al ocus wi hin he op imiza ion esea ch communi y [11–13].
The Conca e Cos Ne wo k Flow P oblem (CCNFP) is a specialized
a ian o he minimum-cos low p oblem1cha ac e ized by conca e
objec i e unc ions. Sol ing he CCNFP aims o iden i y easible lows
in a ne wo k ha minimize he o e all objec i e alue. The inclu-
sion o conca e objec i es enhances he CCNFP’s modeling lexibili y,
making i applicable o a wide ange o scena ios in anspo a ion
[14–16] and wa ehousing [17,18]. Fo ins ance, he mos eliable pa h
✩Funding: The wo k is suppo ed by he NSF o China (Nos. 92270205, 12301659, 12171453), he Na ional Key R&D P og am o China (Nos.
2022YFA1005201, 2022YFA1005202, 2022YFA1005203), and he Majo P ojec o Science and Technology Inno a ion Tackling Plan o Anhui P o ince (No.
202423e09050003).
∗Co esponding au ho .
E-mail add esses: [email p o ec ed] (L. Yang), [email p o ec ed] (Z. Yang).
1In his a icle, he e m ‘‘minimum-cos low p oblem’’ e e s speci ically o i s o m wi h linea objec i e unc ions.
p oblem [19] is essen ial o de e mining op imal a el ou es and
depa u e imes, wi h eliabili y quan i ied by he s anda d de ia ion
o a el ime—a nonlinea componen in he objec i e unc ion. In
wa ehousing, he join loca ion-in en o y p oblem [6] add esses de-
mand luc ua ion isks by minimizing he s anda d de ia ion o p oduc
demand o educe eliabili y cos s. While conca e cos s p o ide iche
modeling capabili ies, hey also in oduce signi ican compu a ional
challenges, especially gi en he inc easing complexi y and scale o
ne wo k opologies. The CCNFP is known o be NP-ha d [18], wi h
complexi y s emming om he ac ha minimizing a conca e cos
o e a con ex easible egion does no gua an ee inding a global
op imum [20]. This NP-ha d na u e p esen s challenges in de eloping
e icien algo i hms, pa icula ly when a emp ing o ind op imal o
nea -op imal solu ions wi hin a easonable ime ame. Consequen ly,
esea ch in o high-quali y, e icien algo i hms o sol ing he CCNFP is
essen ial o bo h heo e ical ad ancemen s and p ac ical applica ions.
Exis ing esea ch has ye o de elop di ec algo i hms speci ically
o sol ing he CCNFP. Cu en app oaches o en simpli y he ne wo k
s uc u e o ea i as a gene al nonlinea p og amming p oblem. The
h ps://doi.o g/10.1016/j.o p.2025.100331
Recei ed 23 No embe 2024; Recei ed in e ised o m 19 Janua y 2025; Accep ed 11 Feb ua y 2025
Ope a ions Resea ch Pe spec i es 14 (2025) 100331
A ailable online 19 Feb ua y 2025
2214-7160/© 2025 The Au ho s. Published by Else ie L d. This is an open access a icle unde he CC BY-NC-ND license ( h p://c ea i ecommons.o g/licenses/by-
nc-nd/4.0/ ).
L. Yang and Z. Yang
Nomencla u e
𝛼Lowe bound o sampling in e al
𝛽Uppe bound o sampling in e al
𝑤A e age de i a i e alue
𝜅Unbalanced s a e o node
𝜋Po en ial unc ion
𝑥Flow on edge
Ac onyms
CCNFP Conca e cos ne wo k low p oblem
AugLag Augmen ed Lag ange unc ion algo i hm
Penal y Penal y unc ion algo i hm
SDSP Successi e de i a i e sho es pa h
SGSP Successi e g adien sho es pa h
SLSQP Sequen ial leas squa e p og amming
SSP Successi e sho es pa h
ARE A e age ela i e e o
MRE Maximum ela i e e o
Pa ame e s
𝐺G aph/ne wo k s uc u e
𝐺Residual g aph
𝑉 , 𝑆 , 𝐷Node se
𝐸 ,
𝐸Edge se
𝑣, 𝑙 , 𝑘Node
𝑒Edge
𝑢Fini e capaci y on edge
𝑟Residual capaci y on
𝐺
𝑏Supply on node
𝑐Cos unc ion on edge
𝑃Pa h
𝑎In e al educ ion coe icien
𝑀Maximum i e a ion coun
𝑛𝑠Numbe o sampling poin s
conca e cos anspo a ion p oblem, o ins ance, is a special case o
he CCNFP o mula ed on a bipa i e g aph [11]. Addi ionally, some
s udies ha e ocused on a ian s o he CCNFP wi h single-sou ce, un-
capaci a ed edges [20,21]. Howe e , hese simpli ied g aph s uc u es
o e look he complexi ies inhe en in eal-wo ld ne wo ks, limi ing
he p ac ical applicabili y o such algo i hms. Fo example, bipa i e
g aphs assume a s uc u e consis ing solely o sou ces and sinks, an
assump ion ha a ely holds in ealis ic se ings. E en wi h hese
simpli ica ions, solu ions o such cases ypically ely on me aheu is ic
me hods [21–24], which o en equi e subs an ial ime o ind subop i-
mal solu ions wi hou gua an ees o con e gence, e en o mode a ely
sized p oblems. Fu he mo e, since he CCNFP is inhe en ly a nonlinea
p og amming p oblem, es ablished nonlinea p og amming algo i hms,
such as augmen ed Lag angian me hods and sequen ial leas squa es
p og amming [12,25], can be applied. Howe e , hese me hods ace
challenges due o he lack o heo e ical gua an ees o inding exac
solu ions and hei ypically p olonged sol ing imes, making hem less
sui able o la ge-scale o ime-sensi i e applica ions.
In his pape , we p opose a no el sequen ial educ ion algo i hm,
he Successi e De i a i e Sho es Pa h (SDSP) algo i hm, which com-
bines he Successi e Sho es Pa h (SSP) algo i hm [10] wi h i s -o de
in o ma ion o conca e objec i e unc ions. While SSP is an exac algo-
i hm o sol ing minimum-cos low p oblems, i canno be di ec ly
applied o he CCNFP. To add ess his, we app oxima e he conca e
cos unc ion in he CCNFP by u ilizing egional i s -o de in o ma-
ion, he eby enabling an app oxima e solu ion o he p oblem. This
app oach allows us o es ablish a sequen ial p ocess ha gene a es a
se ies o minimum-cos low subp oblems, each s ep inc emen ally op i-
mizing he CCNFP solu ion. Addi ionally, by p og essi ely educing he
in e al size o calcula ing i s -o de in o ma ion, he SDSP algo i hm
ensu es con e gence and mi iga es he isk o p ema u e con e gence
o subop imal solu ions. Theo e ical analysis and alida ion expe i-
men s con i m ha he sequen ial educ ion p ocess e ec i ely di ec s
he algo i hm owa d highe -quali y solu ions. Compa isons wi h o he
algo i hms demons a e he supe io solu ion quali y and con e gence
a e achie ed by he SDSP algo i hm.
The emainde o his pape is o ganized as ollows. Sec ion 2
o mally de ines he conca e cos ne wo k low p oblem (CCNFP). Sec-
ion 3p esen s he p oposed algo i hm in de ail, ollowed by Sec ion 4,
which desc ibes and discusses he simula ion esul s. Finally, Sec ion 5
concludes he pape wi h a summa y o he indings and implica ions.
2. Fo mula ion o p oblems
The Conca e Cos Ne wo k Flow P oblem (CCNFP) is a nonlinea
p og amming p oblem o mula ed on a g aph s uc u e wi h a conca e
objec i e unc ion and subjec o linea cons ain s.
Le 𝐺(𝑉 , 𝐸)be a di ec ed g aph wi h a se o 𝑛nodes 𝑉= {𝑣𝑖}𝑛
𝑖=1
and a se o 𝑚di ec ed edges 𝐸. Each node 𝑣𝑖has an associa ed supply
𝑏𝑖, which is used o pa i ion he node se 𝑉in o he h ee subse s:
he sou ce node se 𝑆= {𝑣𝑖∈𝑉∣𝑏𝑖>0}, he in e media e node se
𝑉𝑖𝑛 = {𝑣𝑖∈𝑉∣𝑏𝑖= 0}, and he sink node se 𝐷= {𝑣𝑖∈𝑉∣𝑏𝑖<0}.
Each edge 𝑒𝑖𝑗 ep esen s a di ec ed connec ion om node 𝑣𝑖 o node
𝑣𝑗.𝑥𝑖𝑗 is a non-nega i e eal numbe ha deno es he amoun o low
h ough he edge 𝑒𝑖𝑗 , ypically subjec o a ini e capaci y 𝑢𝑖𝑗 . In he
CCNFP, each edge 𝑒𝑖𝑗 has an associa ed conca e cos unc ion 𝑐𝑖𝑗 (𝑥𝑖𝑗 ),
which depends on he low 𝑥𝑖𝑗 .
Simila o he minimum-cos low p oblem, he Conca e Cos Ne -
wo k Flow P oblem (CCNFP) also en o ces ha he sum o he ne low
and supply a each node equals ze o, ensu ing low conse a ion ac oss
he ne wo k. This cons ain can be w i en as
∑
𝑗∈𝑉−
𝑖
𝑥𝑗 𝑖−∑
𝑗∈𝑉+
𝑖
𝑥𝑖𝑗 +𝑏𝑖= 0,∀𝑖∈𝑉(1)
whe e 𝑉−
𝑖= {𝑗∈𝑉∶𝑒𝑗 𝑖∈𝐸}and 𝑉+
𝑖= {𝑗∈𝑉∶𝑒𝑖𝑗 ∈𝐸}.
Addi ionally, he low alue on each edge is cons ained wi hin he
ange om ze o o i s capaci y, i.e., 0⩽𝑥𝑖𝑗 ⩽𝑢𝑖𝑗 . A solu ion ha
sa is ies bo h o hese cons ain s is a easible solu ion o he CCNFP.
Thus, he conca e cos ne wo k low p oblem can be o mula ed as
min
𝑥𝐶(𝑥) =∑
𝑒𝑖𝑗 ∈𝐸
𝑐𝑖𝑗 (𝑥𝑖𝑗 )
s. . ∑
𝑗∈𝑉−
𝑖
𝑥𝑗 𝑖−∑
𝑗∈𝑉+
𝑖
𝑥𝑖𝑗 =𝑏𝑖,∀𝑖∈𝑉
0⩽𝑥𝑖𝑗 ⩽𝑢𝑖𝑗 ,∀𝑒𝑖𝑗 ∈𝐸
(2)
The o mula ion o CCNFP is a gene alized de ini ion o he ne wo k
low p oblems when Model (2) does no es ic i s objec i e unc ion
ype. The minimum-cos low p oblem a ises as a special case when he
objec i e unc ion simpli ies o a linea unc ion passing h ough he
o igin. In cases whe e he linea objec i e exhibi s jump discon inui ies
a he o igin, he p oblem ans o ms in o a ixed-cha ge ne wo k low
p oblem [26]. The cons ain s a e iden ical, es ablishing an equi alence
in he easible domains be ween he CCNFP and he minimum-cos low
p oblem on he same g aph s uc u e. This o ms he basis o con-
s uc ing a sequence o minimum-cos low p oblems o app oxima e
he CCNFP.
The concep s ou lined in he de ini ion o CCNFP ha e di ec co -
espondences wi h eal-wo ld scena ios. In logis ics and anspo a ion,
he s o age poin s o goods co espond o he sou ce nodes in he g aph,
he demand poin s o goods co espond o he sink nodes, and he
Ope a ions Resea ch Pe spec i es 14 (2025) 100331
2
L. Yang and Z. Yang
ansi poin s co espond o he in e media e nodes. The anspo a ion
ou es na u ally es ablish connec ions be ween hese nodes. Goods
anspo a ion in ol es mo ing goods om s o age poin s o demand
poin s, o en cha ac e ized by mul i-sou cing and mul i- ie anspo a-
ion asks. Addi ionally, la ge-scale o long- e m anspo a ion asks,
due o dec easing ma ginal cos s [27], esul in objec i e unc ions
exhibi ing conca e cha ac e is ics. The e o e, CCNFP is pa icula ly
well-sui ed o applica ion in such scena ios.
3. Sequen ial educ ion algo i hm
In his sec ion, we de ail he SDSP algo i hm, co e ing he oun-
da ional p inciples o he SSP algo i hm and he sequen ial educ ion
mechanism ha dis inguishes SDSP.
3.1. Successi e sho es pa h
The SSP algo i hm inds he op imal solu ion o he minimum-
cos low p oblem by i e a i ely sea ching o he sho es pa h ha
balances supply and demand nodes be ween sou ce and sink nodes in
he esidual g aph. The esidual g aph
𝐺(𝑉 ,
𝐸)is cons uc ed based
on 𝐺(𝑉 , 𝐸)by adding he e e se edges co esponding o each o iginal
edge in 𝐸. The se o e e se edges is deno ed as 𝐸′= {𝑒′
𝑗 𝑖∶𝑒𝑖𝑗 ∈𝐸},
whe e he edges 𝑒′
𝑗 𝑖and 𝑒𝑗 𝑖a e no he same. The e o e, he edge se
𝐸can be ep esen ed as
𝐸=𝐸∪𝐸′. Du ing he sol ing p ocess, lows
on e e se edges {𝑥𝑒}𝑒∈𝐸′ ep esen he algo i hm’s abili y o back ack
p e iously alloca ed lows. The uni cos o he e e se edge is he
opposi e numbe o he uni cos o he o iginal edge, and he capaci y
o he e e se edge is he alloca ed low on he o iginal edge. Thus, he
esidual capaci y in
𝐺(𝑉 ,
𝐸)can be w i en as
{𝑟𝑒=𝑢𝑒−𝑥𝑒, 𝑒∈𝐸
𝑟𝑒′=𝑥𝑒, 𝑒′∈𝐸′(3)
whe e he esidual capaci y o e e se edges 𝑒′is he alloca ed low 𝑥𝑒
on he o iginal edge. SSP iden i ies he sho es pa h be ween a pai
o sou ce and sink nodes wi hin he cu en esidual g aph, assigns he
maximum easible low in each i e a ion, and epea s he abo e ope a-
ion un il all nodes sa is y he conse a ion condi ion. The unbalanced
s a e 𝜅(𝑖), which cha ac e izes he change o node supply in i e a ions,
is de ined as
𝜅(𝑖) =𝑏(𝑖) +∑
𝑒∈𝐸−
𝑖
𝑥𝑒−∑
𝑒∈𝐸+
𝑖
𝑥𝑒, o all 𝑖∈𝑉(4)
whe e 𝐸−
𝑖= {𝑒𝑗 𝑖∈𝐸∶𝑣𝑗∈𝑉} ∪ {𝑒′
𝑗 𝑖∈𝐸′∶𝑣𝑗∈𝑉}, 𝐸+
𝑖= {𝑒𝑖𝑗 ∈𝐸∶
𝑣𝑗∈𝑉} ∪ {𝑒′𝑖𝑗 ∈𝐸′∶𝑣𝑗∈𝑉}. SSP in oduces he po en ial unc ion 𝜋(⋅)
o elimina e he impac o nega i e cos s in sol ing SSP and es ablishes
a ans o ma ion om he edge cos 𝑐𝑒 o he equi alen cos 𝑐𝜋
𝑒as
𝑐𝜋
𝑒𝑖𝑗 =𝑐𝑒𝑖𝑗 −𝜋(𝑖) +𝜋(𝑗)(5)
whe e 𝑐𝑒𝑖𝑗 is he uni cos o edge 𝑒𝑖𝑗 ∈
𝐸.
In he SSP algo i hm, he ini ial condi ions a e se as 𝑥𝑒= 0,∀𝑒∈
𝐸
and 𝜋(𝑖) = 0,∀𝑣𝑖∈𝑉. Each node’s imbalance 𝜅(𝑖)is ini ialized o 𝑏(𝑖)
o all 𝑣𝑖∈𝑉, o ming he unbalanced node se s 𝑆=𝑣𝑖∶𝜅(𝑖)>0
and 𝐷=𝑣𝑖∶𝜅(𝑖)<0. SSP hen selec s a sou ce 𝑘 om se 𝑆and a
sink 𝑙 om se 𝐷, iden i ies all sho es pa hs om 𝑘 o o he nodes
𝑣𝑗∈𝑉, and calcula es he pa h cos 𝑃𝑘𝑗 as 𝑑(𝑗) =∑𝑒∈𝑃𝑘𝑗 𝑐𝑒. Each node’s
po en ial unc ion 𝜋(𝑖)is upda ed based on he alue 𝑑(𝑖)as
𝜋(𝑖) =𝜋(𝑖) −𝑑(𝑖),∀𝑣𝑖∈𝑉(6)
Using he maximum easible low 𝛿on he sho es pa h 𝑃𝑘𝑙, he low
alues o all edges on 𝑃𝑘𝑙 a e upda ed by
𝑥𝑒={𝑥𝑒+𝛿 𝑒∈𝑃𝑘𝑙
𝑥𝑒𝑒∈
𝐸∖𝑃𝑘𝑙
(7)
whe e 𝛿= min[𝜅(𝑘),−𝜅(𝑙),min{𝑟𝑒∶𝑒∈𝑃𝑘𝑙}]. The esidual capaci y
𝑟𝑒, sou ce se 𝑆, sink se 𝐷, and equi alen cos s 𝑐𝜋
𝑒a e hen upda ed
acco dingly. Th oughou he sol ing p ocess, he posi i e alue o 𝛿
ensu es ha SSP e mina es a e a ini e numbe o s eps, achie ing a
balanced s a e o all nodes. A he end, SSP yields he op imal solu ion
o he minimum-cos low p oblem. The ull SSP p ocess is ou lined in
Algo i hm 1.
Algo i hm 1Successi e Sho es Pa h Algo i hm
Inpu : Residual g aph
𝐺(𝑉 ,
𝐸), ec o 𝐛
Ou pu : Op imal solu ion 𝐱∗
1: Ini ializa ion: 𝑥𝑒= 0,∀𝑒∈
𝐸;𝜋(𝑖) = 0, 𝜅(𝑖) =𝑏(𝑖),∀𝑣𝑖∈𝑉.
2: 𝑆= {𝑣𝑖∶𝜅(𝑖)>0},𝐷= {𝑣𝑖∶𝜅(𝑖)<0}
3: while 𝑆≠∅do
4: Selec nodes 𝑘∈𝑆and 𝑙∈𝐷
5: Calcula e 𝑑(𝑗) = min
𝑃𝑘𝑗 {∑
𝑒∈𝑃𝑘𝑗
𝑐𝑒∶𝑃𝑘𝑗 ⊂
𝐸},∀𝑣𝑗∈𝑉
6: Upda e 𝜋(𝑖) =𝜋(𝑖) −𝑑(𝑖),∀𝑣𝑖∈𝑉
7: Compu e 𝛿= min[𝜅(𝑘),−𝜅(𝑙),min{𝑟𝑒∶𝑒∈𝑃𝑘𝑙 }]
8: Upda e lows: 𝑥𝑒=𝑥𝑒+𝛿 ,∀𝑒∈𝑃𝑘𝑙
9: Upda e 𝑟𝑒:𝑟𝑒={𝑟𝑒−𝛿∀𝑒∈𝑃𝑘𝑙
𝑟𝑒+𝛿∀𝑒∈𝑃′
𝑘𝑙
⊳ 𝑃′
𝑙 𝑘is he e e se pa h
o 𝑃𝑘𝑙.
10: Upda e 𝜅(𝑘) =𝜅(𝑘) −𝛿,𝜅(𝑙) =𝜅(𝑙) −𝛿
11: i 𝜅(𝑘) = 0 hen
12: Remo e node 𝑘 om 𝑆
13: end i
14: i 𝜅(𝑙) = 0 hen
15: Remo e node 𝑙 om 𝐷
16: end i
17: Upda e 𝑐𝜋
𝑒:𝑐𝜋
𝑒𝑖𝑗 =𝑐𝑒𝑖𝑗 −𝜋(𝑖) +𝜋(𝑗),∀𝑒𝑖𝑗 ∈
𝐸
18: end while
19: e u n 𝐱∗= {𝑥𝑒−𝑥𝑒′}𝑒∈𝐸
3.2. Successi e de i a i e sho es pa h
The SSP algo i hm is unsui able o sol ing CCNFP because he low
alloca ion in each i e a ion dis up s he o de o edge cos s, leading o
inconsis encies in he sho es pa hs be o e and a e alloca ion. Rec-
ognizing hese limi a ions o SSP o CCNFP, his subsec ion desc ibes
he SDSP algo i hm, which app oxima es he solu ion o CCNFP by
i e a i ely sol ing a se ies o minimum-cos low models.
SDSP cons uc s an app oxima e minimum-cos low model o CC-
NFP in each i e a ion, using he i s -o de in o ma ion o he conca e
objec i e unc ion o c ea e a linea app oxima ion cos . P oposi ion 1
p o ides heo e ical suppo , showing ha he op imal solu ion o he
app oxima e model is consis en ly supe io in objec i e alue o he
p e ious easible solu ion when he i s -o de in o ma ion is se o he
g adien s a he p e ious solu ion. Howe e , he linea app oxima ion
based on he g adien s leads he algo i hm o con e ge o a subop imal
solu ion, wi h he objec i e alue highly dependen on he ini ial
easible solu ion chosen. To add ess his, SDSP cons uc s egional
i s -o de in o ma ion by a e aging de i a i e alues o sample poin s
wi hin a gi en in e al and g adually educes he sampling in e al o
app oach he g adien , allowing SDSP o con e ge o an app oxima e
solu ion close o he op imal solu ion o he o iginal p oblem.
P oposi ion 1. Gi en a easible solu ion 𝑥0o he o iginal p oblem (2),
he app oxima e cos is gene a ed by he g adien s o he o iginal objec i e
unc ion a 𝑥0. The g adien s a e deno ed as ∇𝐶(𝑥0) = (… , 𝑐′
𝑒(𝑥0
𝑒),… ).
The objec i e o he app oxima e minimum-cos low model is
𝐶(𝑥) =
∑𝑒∈𝐸𝑐′
𝑒(𝑥0
𝑒)⋅𝑥𝑒. Then, he op imal solu ion o he app oxima e model 𝑥1
sa is ies ha
𝐶(𝑥1)⩽𝐶(𝑥0)
In o he wo ds, solu ion 𝑥1imp o es upon 𝑥0in objec i e alue when 𝑥1≠
𝑥0.
Ope a ions Resea ch Pe spec i es 14 (2025) 100331
3
L. Yang and Z. Yang
P oo . Since he easible domains o CCNFP and he minimum-cos
low p oblem a e he same, 𝑥1is he easible solu ion o CCNFP. By
he i s -o de condi ion o he conca e unc ion, he o iginal objec i e
𝐶(𝑥)sa is ies ha
𝐶(𝑦)⩽𝐶(𝑥) + ∇𝐶(𝑥)𝑇(𝑦−𝑥)
Thus, he di e ence be ween objec i es a solu ions 𝑥1and 𝑥0sa is ies
𝐶(𝑥1) −𝐶(𝑥0)⩽∇𝐶(𝑥0)𝑇(𝑥1−𝑥0)
=
𝐶(𝑥1) −
𝐶(𝑥0)
⩽0
Equali y holds i and only i 𝑥0is he op imal solu ion o he app oxi-
ma e model, ha is, 𝑥1=𝑥0.□
In he g aph 𝐺(𝑉 , 𝐸), le [𝛼𝑒, 𝛽𝑒] ep esen he sampling in e al o
edge 𝑒, and le 𝑛𝑠deno e he numbe o sampling poin s. The ollow-
ing o mula yields he a e age de i a i e alue 𝑤𝑒unde equidis an
sampling:
𝑤𝑒=1
𝑛𝑠
𝑛𝑠
∑
𝑖=1
𝑐′
𝑒(𝛼𝑒+ (𝑖− 1) ⋅𝛥𝑒),whe e 𝛥𝑒=𝛽𝑒−𝛼𝑒
𝑛𝑠− 1(8)
Conside ing 𝑤𝑒as he uni cos on edge 𝑒, he cons uc ed app oxi-
ma ion model can be sol ed using SSP. In each i e a ion o SDSP, he
algo i hm sol es he app oxima e model o ob ain a easible solu ion
𝑥(𝑘)
𝑒and hen upda es he lowe and uppe bounds o he sampling
in e als o he nex i e a ion. The upda es o he in e al’s bounds
a e as ollows:
𝛼(𝑘+1)
𝑒= max {𝑥(𝑘)
𝑒−1
2⋅𝑎⋅(𝛽(𝑘)
𝑒−𝛼(𝑘)
𝑒),0},
𝛽(𝑘+1)
𝑒= min {𝑥(𝑘)
𝑒+1
2⋅𝑎⋅(𝛽(𝑘)
𝑒−𝛼(𝑘)
𝑒), 𝑢𝑒},
(9)
whe e 𝑎∈ (0,1) is he in e al educ ion coe icien , con olling he
ex en o educ ion in each i e a ion. The algo i hm i e a i ely pe o ms
his p ocess un il he op imal solu ion o he app oxima e model e-
mains unchanged om he p e ious i e a ion. The de ails o SDSP a e
p esen ed in Algo i hm 2.
Algo i hm 2Successi e De i a i e Sho es Pa h
Inpu : G aph 𝐺(𝑉 , 𝐸); Objec i e and de i a i e unc ions 𝑐𝑒(𝑥𝑒), 𝑐′
𝑒(𝑥𝑒);
Numbe o sampling poin s 𝑛𝑠
Ou pu : Flows {𝑥𝑒}𝑒∈𝐸
1: Ini ialize {𝑤(1)
𝑒}𝑒∈𝐸and le [𝛼(1)
𝑒, 𝛽(1)
𝑒] = [0, 𝑢𝑒]
2: o 𝑘= 1 o 𝑀do
3: 𝑥(𝑘)
𝑒= SSP(𝐺,{𝑤(𝑘)
𝑒})
4: i |𝑐𝑒(𝑥(𝑘)
𝑒) −𝑐𝑒(𝑥(𝑘−1)
𝑒)|< 𝜖 ,∀𝑒∈𝐸 hen
5: b eak
6: end i
7: 𝛼(𝑘+1)
𝑒= max {𝑥(𝑘)
𝑒−𝑎⋅(𝛽(𝑘)
𝑒−𝛼(𝑘)
𝑒),0}
8: 𝛽(𝑘+1)
𝑒= min {𝑥(𝑘)
𝑒+𝑎⋅(𝛽(𝑘)
𝑒−𝛼(𝑘)
𝑒), 𝑢𝑒}
9: 𝛥(𝑘+1)
𝑒=𝛽(𝑘+1)
𝑒−𝛼(𝑘+1)
𝑒
𝑛𝑠−1
10: 𝑤(𝑘+1)
𝑒=1
𝑛𝑠∑𝑛𝑠
𝑖=1 𝑐′
𝑒(𝛼(𝑘+1)
𝑒+ (𝑖− 1) ⋅𝛥(𝑘+1)
𝑒)
11: end o
12: e u n {𝑥∗
𝑒}𝑒∈𝐸
In SDSP, he ini ial alues o egional i s -o de in o ma ion 𝑤𝑒and
he pa ame e s 𝑛𝑠, 𝑎canno be di ec ly de e mined h ough heo e ical
analysis, no can hey be au oma ically op imized by he algo i hm. To
add ess his, we design a se ies o nume ical expe imen s o e alua e
he impac o a ious ini ializa ions and pa ame e se ings on he
algo i hm’s pe o mance. These expe imen s se e as a e e ence o se-
lec ing ini ial alues o egional i s -o de in o ma ion and pa ame e
se ings, acili a ing he p ac ical applica ion o SDSP.
3.3. Time and space complexi y analysis
This sec ion analyzes he ime and space complexi y o he SSP and
SDSP. The analysis o he SSP algo i hm is based on he conclusions
in he book Ne wo k Flows. The analysis o he SDSP is de i ed and
analyzed based on he p oposed algo i hm in his pape .
3.3.1. Time complexi y analysis
In he SSP, each i e a ion sol es a sho es pa h p oblem wi h
nonnega i e weigh s and s ic ly dec eases he unbalanced s a e o
some node. Consequen ly, i 𝑛is he numbe o nodes in G aph, 𝑚
is he numbe o edges in G aph, and 𝑈is an uppe bound on he
la ges supply o any node, he SSP e mina es in a mos 𝑛𝑈 i e -
a ions. Le 𝑆(𝑛, 𝑚, 𝐶)deno e he ime aken o sol e a sho es pa h
p oblem wi h nonnega i e weigh s, he ime complexi y o he SSP
is 𝑂(𝑛𝑈 𝑆(𝑛, 𝑚, 𝑛𝐶)). In his pape , we apply Dijks a’s algo i hm o
sol e he sho es pa h p oblem, using a special da a s uc u e, he
heap, o accele a e he Dijks a’s algo i hm. Lemma 1p o ides he ime
complexi y o Dijks a’s algo i hm wi h bina y heap implemen a ion.
Lemma 1. A bina y heap da a s uc u e equi es 𝑂(log 𝑛) ime o pe o m
inse , dec ease-key, and dele e-min, and i equi es 𝑂(1) ime o he
o he heap ope a ions. Consequen ly, he bina y heap e sion o Dijks a’s
algo i hm uns in 𝑂(𝑚log 𝑛) ime.
P oo . The de ails o his lemma a e p o ided in Sec ion 4.7 o he
book Ne wo k Flows.□
Lemma 1s a es ha 𝑆(𝑛, 𝑚, 𝐶) =𝑂(𝑚log 𝑛), he e o e es ablishing
he ime complexi y o he SSP algo i hm as p esen ed in Theo em 1.
Theo em 1. When he ime complexi y aken o sol e a sho es pa h
p oblem wi h nonnega i e weigh s is 𝑂(𝑚log 𝑛), he ime complexi y o he
SSP algo i hm is 𝑂(𝑛𝑚𝑈 log 𝑛).
In he SDSP algo i hm, P oposi ion 1p o es ha he algo i hm’s
mechanism ensu es he descen o he objec i e unc ion, bu he heo-
e ical p ope y o ini e-s ep con e gence emains unclea . To add ess
his, a maximum i e a ion coun 𝑀is in oduced o gua an ee he
e mina ion o he SDSP algo i hm. Building on he ime complexi y
o he SSP algo i hm, Co olla y 1p o ides he ime complexi y o he
SDSP algo i hm.
Co olla y 1. Le 𝑀be he maximum i e a ion coun o he SDSP
algo i hm, he ime complexi y is 𝑂(𝑀 𝑛𝑚𝑈 log 𝑛).
Al hough he ini e-s ep con e gence o he in e al educ ion mech-
anism in he SDSP algo i hm lacks heo e ical p oo , nume ical expe -
imen s show ha he algo i hm e ec i ely achie es ini e-s ep con e -
gence in p ac ice, equi ing only a ew i e a ions.
3.3.2. Space complexi y analysis
In he analysis o space complexi y, i is necessa y o conside
he s o age o he g aph s uc u e as well as he s o age o a iables
in ol ed in he solu ion p ocess o he ela ed algo i hms. To de e mine
he space complexi y o he SDSP algo i hm, we i s calcula e he space
complexi ies o he Dijks a and SSP algo i hms as a ounda ion.
In Dijks a’s algo i hm, he space complexi y includes g aph s o age,
p io i y queue, dis ance a ay, isi ed a ay, and auxilia y s uc u es.
The SSP algo i hm compu es he sho es pa h p oblem by in oking
Dijks a’s algo i hm. Al hough he wo s -case i e a ion coun o he
SSP algo i hm is 𝑉×𝑈, since he space occupied by he a iables in
Dijks a’s algo i hm can be eleased a e each in oca ion. The e o e,
he SSP algo i hm does no inc ease he space complexi y o de . Simi-
la ly, when he SDSP algo i hm i e a es o e he SSP algo i hm, i s o es
only he nume ical esul s om he p e ious i e a ion. As a esul , he
o e all space complexi y emains unchanged in e ms o o de , wi h a
sligh inc ease in he cons an ac o coe icien . Table 1p o ides he
de ailed space complexi y calcula ions o he h ee algo i hms.
Ope a ions Resea ch Pe spec i es 14 (2025) 100331
4
L. Yang and Z. Yang
Table 1
Space complexi y o a iables in di e en algo i hms.
Va iable Dijks a SSP SDSP
G aph s o age 𝑂(𝑉+𝐸)𝑂(𝑉+𝐸)𝑂(𝑉+𝐸)
P io i y queue (Bina y heap) 𝑂(𝑉)
Dis ance & Visi ed a ay 𝑂(𝑉)
Residual g aph 𝑂(𝑉+𝐸)
𝑆 , 𝐷 , 𝜋 , 𝑑 , 𝜅 𝑂(𝑉)
Flows 𝑥 𝑂(𝐸)𝑂(𝐸)
𝛼 , 𝛽 , 𝛥, 𝜔 𝑂(𝐸)
Auxilia y s uc u es 𝑂(1) 𝑂(1) 𝑂(1)
To al 𝑂(𝑉+𝐸)𝑂(𝑉+𝐸)𝑂(𝑉+𝐸)
4. Nume ical expe imen s
This sec ion demons a es he e ec i eness and ad an ages o SDSP
in sol ing CCNFP h ough a se ies o nume ical expe imen s. Sec-
ion 4.1 in oduces he p oblem ins ances and hei cons uc ion me h-
ods. Sec ion 4.2 p esen s expe imen s ha iden i y he mos e ec i e
ini ializa ion me hod o egional i s -o de in o ma ion and op imal
pa ame e se ings. Sec ion 4.3 examines he impac o he sequen-
ial p ocess and in e al educ ion mechanisms in SDSP. Finally, Sec-
ion 4.4 compa es he pe o mance o SDSP wi h ha o nonlinea p o-
g amming algo i hms and a sequen ial linea app oxima ion algo i hm,
highligh ing i s supe io i y.
The algo i hms used in he nume ical expe imen s a e compiled
and execu ed in a C++17 en i onmen , excep o he Sequen ial Leas
Squa es P og amming, which is implemen ed in Fo an and in oked
h ough a Py hon in e ace. All p og am codes p esen ed in his pape
a e execu ed on he same desk op compu e , equipped wi h an In el
Co e i7-11700 2.50 GHz p ocesso and 32 GB o RAM.
4.1. Ins uc ion o ins ances
Since he ela ed wo k does no p o ide a ailable ins ances, we
cons uc he g aph s uc u e o CCNFP based on he ins ance scales
ou lined in he li e a u e. Addi ionally, we apply a ious ca ego ies o
conca e unc ions as he objec i e o CCNFP.
The ins ance scale ypically e e s o he numbe o nodes and edges
in he g aph s uc u e. In his pape , we cons uc se en g oups o
ins ances wi h di e en scales: (10, 40), (20, 100), (40, 300), (60, 400),
(100, 1000), (150, 2500), and (250, 7500).2We andomly gene a e a
speci ied numbe o nodes wi hin a wo-dimensional ec angula egion
using a uni o m dis ibu ion. The connec ions be ween hese nodes
a e de e mined by compa ing hei Euclidean dis ance o a h eshold.
A lexible h eshold con ols he numbe o connec ed node pai s,
ensu ing ha he numbe o edges ma ches he speci ied scale o he
g aph. Nex , we andomly selec 10%, 20%, and 40% o he nodes o
se e as he sou ce and sink nodes in each ins ance, espec i ely. The
node supply o each sou ce ollows he uni o m dis ibu ions U(3,30),
while he node supply o each sink ollows U(−30,−3). Addi ionally,
we cons uc ed ins ances wi h a ious sampling dis ibu ions o assess
hei impac s he algo i hm’s pe o mance. Adjus men s a e applied o
ensu e he o al supply equals ze o. Excluding sou ce and sink nodes,
all o he nodes a e designa ed as in e media e nodes wi h a supply
o ze o. We assume ha he cos unc ion o each edge is a conca e
unc ion passing he poin (0,0). These cos unc ions a e di ided in o
h ee ca ego ies: Loga i hmic, Powe , and Sigmoid, and a e de ined as
ollows:
𝐶𝐿𝑜𝑔(𝑥) = log𝜃(𝑥+ 1), 𝐶𝑃 𝑜𝑤(𝑥) = (𝑥+ 1) 1
𝜃− 1,
𝐶𝑆 𝑖𝑔 (𝑥) =1
1 +𝜃−𝑥−1
2
(10)
2The i s numbe ep esen s he numbe o nodes, while he second
ep esen s he numbe o edges.
Table 2
In o ma ion abou ins ances.
Ins ance cha ac e is ics Pa ame e alues
Node numbe 10, 20, 40, 60, 100, 150, 250
Edge numbe 40, 100, 300, 400, 1000, 2500, 7500
Sou ce node adio 10%, 20%, 40%
Sink node adio 10%, 20%, 40%
Samp. Dis . o Sou ce U(3,30),U(1,5) o U(26,30)
Samp. Dis . o Sink U(−30,−3),U(−30,−26) o U(−5,−1)
Objec i e unc ion 𝐶𝐿𝑜𝑔 (𝑥), 𝐶𝑃 𝑜𝑤(𝑥), 𝐶𝑆 𝑖𝑔 (𝑥), 𝐶𝑀 𝑖𝑥(𝑥)
Table 3
The o mula o ini ializing 𝑤𝑒a speci ic poin s.
Fo mula 𝑥𝑒= 0𝑥𝑒=𝑢𝑒∕2 𝑥𝑒=𝑢𝑒
De i a i e alue 𝑐′
𝑒(0) 𝑐′
𝑒(𝑢𝑒∕2) 𝑐′
𝑒(𝑢𝑒)
In e pola ion slope – 2
𝑢𝑒
𝑐𝑒(𝑢𝑒∕2) 1
𝑢𝑒
𝑐𝑒(𝑢𝑒)
whe e 𝜃∼U(2,12). Addi ionally, we de ine a mixed-cos unc ion ha
combines he h ee conca e unc ions. By pa i ioning he edge se 𝐸
in o h ee disjoin subse s 𝐸1, 𝐸2, 𝐸3, we de ine he mixed objec i e
unc ion as ollows:
𝐶𝑀 𝑖𝑥(𝑥) =⎧
⎪
⎪
⎨
⎪
⎪
⎩
log𝜃(𝑥+ 1) o 𝑒∈𝐸1
(𝑥+ 1) 1
𝜃− 1 o 𝑒∈𝐸2
1
1+𝜃−𝑥−1
2 o 𝑒∈𝐸3
(11)
The all in o ma ion o gene a ing ins ances a e lis ed in Table 2,
whe e Samp. Dis . s ands o he sampling dis ibu ion.
4.2. Ini ializa ion and pa ame e selec ion
In his subsec ion, we p o ide guidance on ini ializa ion me hods,
he numbe o sampling poin s, and he in e al educ ion coe icien s
based on nume ical expe imen s.
The ini ializa ion o egional i s -o de in o ma ion signi ican ly
a ec s he solu ion. Nume ical expe imen s help iden i y he mos sui -
able ini ializa ion me hod by compa ing he algo i hm’s pe o mance
ac oss di e en s a egies. These s a egies can be ca ego ized in o
wo g oups. One g oup compu es he egional i s -o de in o ma ion
using he upda e o mula o 𝑤(𝑘)
𝑒o e he ini ial sampling in e al
[0, 𝑢𝑒], deno ed as
𝑐′
𝑒. The o he g oup uses he de i a i e alues o
linea in e pola ion slopes a speci ic poin s as he egional i s -o de
in o ma ion. In he expe imen s, we calcula e he de i a i e alue and
he linea in e pola ion slope a he poin s 𝑥𝑒= 0, 𝑥𝑒=𝑢𝑒∕2,and 𝑥𝑒=
𝑢𝑒, as summa ized in Table 3.
Table 4p esen s he objec i e alues ob ained by SDSP unde six
di e en ini ializa ion me hods o he cons uc ed ins ances. In he
expe imen , 30 sampling poin s a e used, and he in e al educ ion
coe icien is se o 0.5. The Min column displays he minimum objec-
i e alue o each ins ance. The ela i e e o be ween he objec i e
alues o di e en ini ializa ions and he minimal alue is hen cal-
cula ed o di ec compa ison. Two indica o s a e used o compa e he
esul s o di e en me hods: ARE and MRE. ARE s ands o A e age
Rela i e E o , which se es as an o e all me ic o e alua ing algo-
i hm pe o mance. MRE s ands o Maximum Rela i e E o , which is
used o assess he algo i hm’s pe o mance in he wo s -case scena io.
Bo h ARE and MRE a e p o ided in he able. The esul s indica e
ha SDSP pe o ms bes wi h he ollowing ini ializa ion me hods:
𝑤𝑒=2
𝑢𝑒
𝑐𝑒(𝑢𝑒
2),𝑐𝑒(𝑢𝑒)
𝑢𝑒
,and
𝑐′
𝑒. Fo hese h ee ini ializa ions, he ARE
emains consis en ly below 2.5%. In con as , he ARE o he o he
me hods exceeds 10%. Howe e , he di e ence be ween hese h ee
ini ializa ion me hods is insu icien o de e mine a clea winne . Nex ,
we combine he esul s om Table 4wi h expe imen s on he numbe
o samples and he in e al educ ion coe icien o iden i y he op imal
ini ializa ion me hod, sampling numbe , and coe icien .
Ope a ions Resea ch Pe spec i es 14 (2025) 100331
5
L. Yang and Z. Yang
Table 4
The objec i e alues o SDSP unde six ypes o ini ializa ion.
Objec i e Scale Objec i e alues (𝑛𝑠= 30, 𝑎= 0.5) Min
𝑐′
𝑒(0) 𝑐′
𝑒(𝑢𝑒
2)2
𝑢𝑒
𝑐𝑒(𝑢𝑒
2)𝑐′
𝑒(𝑢𝑒)𝑐𝑒(𝑢𝑒)
𝑢𝑒
𝑐′
𝑒(𝑥𝑒)
𝐶𝐿𝑜𝑔 (𝑥)
(20, 100) 16.110 15.966 15.928 15.966 15.966 15.928 15.928
(60, 400) 14.535 14.316 14.339 14.764 14.339 14.339 14.316
(150, 2500) 48.754 49.478 51.536 49.497 49.617 49.617 48.754
(250, 7500) 119.695 107.613 108.444 107.960 107.814 106.965 106.965
𝐶𝑃 𝑜𝑤 (𝑥)
(20, 100) 4.582 4.617 4.617 4.617 4.617 4.617 4.582
(60, 400) 1.040 1.083 1.050 1.110 1.083 1.029 1.029
(150, 2500) 13.362 14.107 13.791 13.620 13.838 13.529 13.362
(250, 7500) 33.160 32.196 31.351 31.898 30.995 31.351 30.995
𝐶𝑆 𝑖𝑔 (𝑥)
(20, 100) 6.495 6.753 5.749 6.753 5.749 6.249 5.749
(60, 400) 14.990 18.499 14.467 17.980 14.467 14.467 14.467
(150, 2500) 28.140 32.946 21.737 32.187 21.737 23.618 21.737
(250, 7500) 50.981 80.461 36.201 80.050 36.201 35.444 35.444
𝐶𝑀 𝑖𝑥(𝑥)
(20, 100) 7.694 7.584 6.793 7.133 7.021 6.793 6.793
(60, 400) 7.946 12.666 8.037 12.666 7.917 8.725 7.917
(150, 2500) 28.148 37.207 18.596 38.605 18.799 19.149 18.596
(250, 7500) 55.973 96.011 39.558 96.758 39.787 38.972 38.972
ARE (%) 13.82 34.99 1.22 34.74 1.33 2.23
MRE (%) 51.37 146.36 5.71 148.28 5.25 10.21
Fig. 1. The end o a e age ela i e e o co esponds o he numbe o sampling poin s. The in e al educ ion coe icien is se o 0.5.
Two expe imen s a e designed o compa e he pe o mance o SDSP
wi h a ying sampling numbe s and in e al educ ion coe icien s
unde h ee selec ed ini ializa ion me hods. Fig. 1illus a es he end
o he ela i e e o in objec i e alues as a unc ion o he sampling
numbe , while Fig. 2shows he end o ela i e e o wi h espec o
he in e al educ ion coe icien . The esul s demons a e ha he lin-
ea in e pola ion slope ini ializa ion me hods ou pe o m he de i a i e
mean me hod. Howe e , no signi ican di e ence is obse ed be ween
he wo linea in e pola ion slope me hods. Based on hese indings,
we adop 𝑐𝑒(𝑢𝑒)
𝑢𝑒
as he ini ial egional i s -o de in o ma ion, se he
numbe o sampling poin s o one, and choose an in e al educ ion
coe icien o 0.65.
These wo igu es show mo e in o ma ion abou he e ec o he
egional i s -o de in o ma ion and he in e al educ ion mechanism.
In Fig. 1, ewe sampling poin s implies ha he a e aged de i a i e
compu ed wi hin he in e al e ec i ely app oxima es he g adien a
a poin close o he uppe pa o he egion. As he numbe o sampling
poin s inc eases, he a e aged de i a i e shi s o e lec he g adien o
a poin close o he in e al’s midpoin . When he ini ializa ion me hod
uses he linea in e pola ion slope, ewe sampling poin s demons a e a
dis inc ad an age. F om an op imiza ion pe spec i e, his phenomenon
a ises because he g adien o a conca e unc ion in he uppe egion o
he in e al is inhe en ly s eepe han a he midpoin . This s eepness
esul s in a lowe e ec i e cos o he e e se edge in he esidual
g aph du ing he algo i hm’s i e a ions, inc easing he likelihood o i s
selec ion in subsequen i e a ions. This mechanism in oduces na u al
e e sibili y o he low assignmen s, allowing he algo i hm o explo e
he solu ion space mo e e ec i ely and a oid p ema u e con e gence.
As a esul , he algo i hm can o e come he limi a ions o he successi e
sho es pa h algo i hm, which s uggles wi h conca e cos s uc u es,
ul ima ely achie ing highe -quali y solu ions and be e objec i e al-
ues. This beha io highligh s he p ac ical u ili y o le e aging egional
i s -o de in o ma ion in he SDSP amewo k.
In Fig. 2, he a e age ela i e e o exhibi s a dis inc ‘‘U-shaped’’
ela ionship wi h he in e al educ ion coe icien . When he coe i-
cien app oaches ze o, he algo i hm elies only on he g adien alue
a he solu ion om he p e ious i e a ion o app oxima e he conca e
cos unc ion. Con e sely, when he coe icien app oaches one, he al-
go i hm uses a ixed-leng h in e al o sampling o cons uc he linea
objec i e. The expe imen al esul s show ha bo h ex eme app oaches
a e subop imal o sol ing he p oblem. An i e a i e amewo k based
solely on single-poin g adien alues o en con e ges o subop imal
solu ions due o he challenge o e isi ing p e iously assigned low
alues. Con e sely, using ixed-leng h in e al sampling h oughou he
Ope a ions Resea ch Pe spec i es 14 (2025) 100331
6
L. Yang and Z. Yang
Fig. 2. The end o a e age ela i e e o co esponds o he in e al educ ion coe icien . The numbe o sampling poin s is se o 30.
Table 5
Valida ion on sequen ial p ocess and egional i s -o de in o ma ion.
Objec i e Scale Objec i e alues
LPo LPu SGSP SDSP(𝑎= 1) SDSP
𝐶𝐿𝑜𝑔 (𝑥)
(20, 100) 16.248 15.966 15.966 15.844 15.760
(60, 400) 14.689 15.233 15.233 14.556 14.222
(150, 2500) 53.033 55.037 55.037 45.689 44.772
(250, 7500) 89.473 80.368 78.816 75.795 71.763
𝐶𝑃 𝑜𝑤 (𝑥)
(20, 100) 4.820 4.617 4.617 4.617 4.617
(60, 400) 1.069 1.116 1.116 1.015 1.006
(150, 2500) 13.734 14.053 13.891 13.198 12.830
(250, 7500) 23.483 21.327 20.553 20.444 19.793
𝐶𝑆 𝑖𝑔 (𝑥)
(20, 100) 6.495 5.749 5.749 5.749 5.749
(60, 400) 15.999 14.500 14.000 14.500 12.956
(150, 2500) 34.614 22.834 22.834 22.834 19.244
(250, 7500) 57.630 38.026 38.206 38.026 37.525
𝐶𝑀 𝑖𝑥(𝑥)
(20, 100) 8.914 7.442 7.442 7.076 7.021
(60, 400) 9.033 8.578 7.912 7.728 7.604
(150, 2500) 29.050 22.317 20.887 19.900 17.788
(250, 7500) 33.166 30.333 26.717 27.913 25.166
ARE (%) 24.79 10.52 7.90 4.67 –
p ocess isks assigning e e se low o edges ha should ecei e low,
hinde ing he algo i hm’s abili y o con e ge o high-quali y solu ions.
The in e al educ ion mechanism e ec i ely na iga es he ade-o s
be ween hese opposing ac o s, enabling he algo i hm o ind a Pa e o-
op imal balance. This mechanism is analogous o s ep-size adjus men
in op imiza ion algo i hms: la ge s ep sizes help escape local minima,
while educ ions ensu e con e gence o a local minimum in a mo e
p omising neighbo hood.
4.3. E ec i eness
This sec ion aims o alida e he e ec i eness o SDSP by showcas-
ing he imp o ed pe o mance achie ed h ough bo h he sequen ial
p ocess and he inco po a ion o egional i s -o de in o ma ion.
In compa ison, we cons uc wo minimum-cos low models o
app oxima e he CCNFP in a single s ep. The linea uni cos on edges is
de ined as 𝑐𝑒(𝑥) =𝑐′
𝑒(0)⋅𝑥o 𝑐𝑒(𝑥) =𝑐𝑒(𝑢𝑒)
𝑢𝑒
⋅𝑥, wi h hese wo app oxima e
models deno ed as LPo and LPu espec i ely. Addi ionally, we simpli y
he SDSP by upda ing 𝑤(𝑘+1)
𝑒based solely on he g adien s a poin 𝑥(𝑘)
𝑒,
ha is, 𝑤(𝑘+1)
𝑒=𝑐′
𝑒(𝑥(𝑘)
𝑒)which is deno ed as SGSP. In he expe imen s,
we ensu e ha he ini ializa ion and pa ame e se ings o SGSP a e
consis en wi h hose o SDSP.
Table 5p esen s he objec i e alues o hese ou app oaches ac oss
16 ins ances. The objec i e alues ob ained by SDSP a e consis en ly
minimal compa ed o he o he s o all ins ances. We calcula e he
a e age ela i e e o be ween SDSP’s objec i e alues and hose o
he o he me hods. The esul s show ha he objec i e alues achie ed
by SGSP a e always less han o equal o hose ob ained by LPu,
con i ming he descen p ope y ou lined in P oposi ion 1. Howe e ,
when upda ing 𝑤(𝑘+1)
𝑒using g adien s, he sequen ial p ocess only
esul s in a modes 2.62% dec ease in he objec i e alue. In oducing
egional i s -o de in o ma ion in o he sequen ial p ocess leads o a
subs an ial imp o emen , wi h he a e age ela i e e o be ween SGSP
and SDSP eaching 7.9%. The descending end in ARE om LPu o
SDSP highligh s he c ucial ole ha he sequen ial p ocess and he
in eg a ion o egional i s -o de in o ma ion play in op imizing he
objec i e alues o CCNFP. Also, he esul s o SDSP wi h he pa ame e
𝑎= 1ha e been lis ed in he able o compa ison. The SDSP algo i hm
wi hou in e al educ ion explo es a wide solu ion space han SGSP,
esul ing in a gene ally supe io solu ion. Howe e , he algo i hm s ill
shows a 4.67% po en ial o imp o emen when he in e al educ ion
mechanism is inco po a ed.
Fig. 3shows he dec ease in he objec i e unc ion ac oss ou
cases wi h dis inc a ge unc ions, compa ing he pe o mance o
h ee i e a i e s a egies. Bo h SDSP(𝑎= 0.65) and SGSP show a
Ope a ions Resea ch Pe spec i es 14 (2025) 100331
7
L. Yang and Z. Yang
Fig. 3. The dec easing p ocess o SGSP and SDSP.
s eady dec ease in he objec i e alue o e i e a ions, bu SGSP o en
con e ges p ema u ely o subop imal local minima. Con e sely, SDSP
wi hou in e al educ ion (when 𝑎= 1) achie es be e esul s han
SGSP in se e al cases, bu i lacks gua an eed mono onic dec ease and
quickly s agna es a e a ew i e a ions. The p oposed in e al educ ion
mechanism in SDSP e ec i ely in eg a es he ad an ages o he o he
wo s a egies, enabling i o iden i y highe -quali y solu ions. Fu he -
mo e, e en wi hou a p ede ined maximum i e a ion limi , he in e al
educ ion mechanism exhibi s ini e-s ep con e gence in nume ical
expe imen s, eliably mee ing he s opping c i e ia wi hin a limi ed
numbe o i e a ions. These indings highligh how SDSP balances ex-
plo a ion and exploi a ion, leading o obus and e icien op imiza ion
pe o mance.
4.4. Compa ison
To e alua e he pe o mance o SDSP, we conduc ed compa ison ex-
pe imen s wi h exis ing algo i hms o sol ing he conca e cos ne wo k
low p oblem on di e en g aph s uc u e ins ances.
We compa e SDSP wi h wo ca ego ies o algo i hms. The i s
ca ego y includes h ee nonlinea p og amming algo i hms:
•Sequen ial Leas Squa e P og amming (SLSQP) [28]
•Augmen ed Lag ange Func ion algo i hm (AugLag) [29–33]
•Penal y Func ion algo i hm (Penal y) [29,30,34,35]
SLSQP is a g adien -based op imiza ion me hod ha sol es cons ained
nonlinea op imiza ion p oblems by i e a i ely app oxima ing he ob-
jec i e unc ion and cons ain s wi h quad a ic models, e icien ly han-
dling bo h equali y and inequali y cons ain s. The AugLag algo i hm
combines Lag angian elaxa ion o cons ain s wi h an augmen ed
penal y e m, imp o ing con e gence and s abili y in sol ing con-
s ained op imiza ion p oblems. The Penal y me hod inco po a es a
penal y e m in o he objec i e unc ion o penalize cons ain io-
la ions, sol ing he p oblem as an uncons ained op imiza ion while
p og essi ely igh ening he penal y. The second ca ego y includes
he sequen ial linea app oxima e algo i hm, Dynamic Slope Scaling
P ocedu e (DSSP) [36], which is also applicable o CCNFP. All base-
line algo i hm pa ame e se ings a e a ailable in he sha ed Gi Hub
eposi o y, ensu ing consis ency by using he same se o pa ame e s
o all expe imen al cases. Fi s , we conduc expe imen s on ins ances
wi h g aph s uc u es ha include se en di e en scales and h ee
sou ce node a ios, esul ing in a o al o 84 ins ances. The sou ce node
supply ollows a sampling dis ibu ion o U(3,30). Nex , we explo e
he pe o mance o i e algo i hms on ins ances wi h di e en supply
sampling dis ibu ions.
Tables 6and 7p esen he a e age and maximum ela i e e o s
be ween he objec i e alues ob ained by he i e algo i hms and he
minimum ac oss 84 ins ances. The minimum o each ins ance is he
smalles objec i e alue among he i e algo i hms. The de ails o
he esul s o all ins ances a e lis ed in Appendix.Table 6shows
he pe o mance di e ences o he algo i hms ac oss ins ances wi h
a ying scales. Table 7shows he pe o mance o he algo i hms unde
di e en sou ce node a ios. In Table 6, we obse e ha he a e age
ela i e e o o he p oposed algo i hm dec eases as he ins ance scale
inc eases: he la ge he scale, he smalle he ela i e e o . This
sugges s ha as he p oblem scale inc eases, he SDSP algo i hm can
ind he op imal solu ion in mos cases. In con as , bo h he SLSQP
and DSSP algo i hms show an inc ease in a e age ela i e e o as he
p oblem scale g ows, while he a e age ela i e e o o he AugLag
algo i hm emains a ound 10%. This u he highligh s he signi ican
ad an age o he SDSP algo i hm in sol ing la ge-scale conca e cos
ne wo k low p oblems. Wi h an a e age ela i e e o o 0.71% and a
maximum ela i e e o o 8.69%, he SDSP algo i hm demons a es
bo h e ec i eness and s abili y in sol ing his p oblem. E en in he
wo s -case scena io, he algo i hm’s ela i e e o emains wi hin 10%,
a le el una ainable by he o he compa ed algo i hms.
In Table 7, he pe o mance o all i e algo i hms gene ally shows
ha he a e age ela i e e o dec eases as he a io o sou ce nodes
Ope a ions Resea ch Pe spec i es 14 (2025) 100331
8
