493
1 INTRODUCTION
Thedynamicdevelopmentofglobaltechnologyinall
industries, including automation is associated with
theuseofhighqualityenvironment‐friendlytechnical
goods.Nowadays,manufacturingprocessesundergo
continuousdevelopment,andthisalsoappliestothe
wide use of liquefied natural gas (LNG), the most
commonenergycarrier.
LNG
is created from gaseous state through the
process of liquefaction. The process brings many
advantages,namelyreductionoffuelvolumeby600
times makes transport of LNG over long distances
viableandcost‐effective.Onequarterof globalLNG
tradereferstoitsliquefiedstate[5].
LNG in fact is
pure methane (CH4) with small
additives of heavier hydrocarbons which makes it
nearly 100% clean fuel. The fuel, commonly called
ʺbluefuelʺisveryclean,safe,andfreeofmoistureand
otherundesiredcomponents.
Due to its ecological characteristics and a wide
range of applications, LNG is present in the various
stages
of the logistics chain. In order to meet the
requirements of the Directive 2012/33/EU of the
European Parliament and of the Council, amending
Directive1999/32/ECconcerningthesulfurcontentin
marine fuels, and to improve the safety of human
health and protect the environment, LNG has been
usedasanalternative
totraditionalmarinefuels[20].
In Polish and foreign literature, the methods of
bunkering ships in technical terms and legal
Multicriteria Optimization Method of LNG Distribution
E.Chłopińska&M.Gucma
M
aritimeUniversityofSzczecin,Szczecin,Poland
ABSTRACT:LiquefiedNaturalGas(LNG)isconsideredasarealisticsubstationofmarinefuelin21century.
Solution of building new engines or converting diesels into gas fueled propulsion meets the stringent
international emission regulations. For HFO (heavy fuel oil) or MDO (marine diesel oil)
propelled vessels,
operationofbunkeringisrelativelywideknownandsimple.Itsduetothefactthatfuelitselfdoesn’trequire
highstandardsofhandling.WhereforLNGasafuelitsverydemandingprocess–itevaporatesandrequires
either consuming by bunker vessel or reliquefication. Distribution of such
bunker is becoming
multidimensionalproblemwithtimeandspaceconstrains.Theobjectiveofthearticleistoreviewthemethods
of optimization using genetic algorithms for a model of LNG distribution. In particular, there will be
considered methods of solving problems with many boundry criteria whose objective functions are
contradictory. Methods
used for solving the majority of problems are can prevent the simultaneous
optimizationoftheexaminedobjectives,e.g.theminimisationofcostsordistancecovered,orthemaximisation
ofprofitsorefficiencyetc.Herethestandardgeneticalgorithmsaresuitableforsolvingmulti‐criteriaproblems
byusingfunctionsproducinga
diversityofresultsdependingontheadoptedapproach.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 14
Number 2
June 2020
DOI:10.12716/1001.14.02.30
494
regulationshavebeenwidelydescribed.Marineunits
usedforLNGtransport,LNGbunkerandLNGports
are described in detail. The low profitability of the
creation of the LNG bunkering network and LNG
distributionarerarelydiscussed.
Currentlytherehavebeennoworkonthepossible
use of the LNG
terminal in Swinoujscie port as a
bunkerport.Therewereconductedteststodetermine
therealdemandforLNGasbunkerfuelintheBaltic
Sea.TheworkproposedauniversalLNGdistribution
model.
2 MODEL
Themodeloflocationofroutesandwarehouseswill
be an original optimization model
based on the
mechanism of natural evolution. The model will be
built on a simple evolutionary algorithm, thanks to
which it is possible to quickly and efficiently search
forthebestpossibleallocations.
Analyzed such input data as geographical
coordinatesofrealports,technicalparametersofLNG
bunkers,LNGdistributioncosts,
typesofLNGunits,
LNG demand will allow for the best distribution of
LNGwarehousesalongthePolishBalticSeacoastline
and determine the distribution range of a given
warehouse(Figure1).
Figure1.Modelexamples
Theoptimalroutelocationmethodisdesignedto
match LNG units to LNGbunker units that provide
the total required LNG quantity and which are
respectively assigned to optimally placed individual
LNGwarehouses.
Twoapproachesofmulti‐criteriaoptimizationare
distinguished:
1 Combining all objective functions into one
complex function. In
this case, the difficulty
consists in an appropriate, precise and accurate
choice of the weights or utility functions (even
minorvariationsintheweightsmayyieldvarious
solutions). Therefore, a set of solutions is often
used when multiple objectives are taken into
account [18]. Defining one objective function is
possible
byusing:
thetheoryofutility,
themethodofweightedsum.
2 ThedeterminationofoptimalParetosub‐setorset.
TheoptimalsolutionforaParetosetisreferredto
as a set of non‐dominated solutions. This is a
solution x’∈ D where there is no
solution x ∈ D,
that enables the improvement of the value of at
least one objective function, while the other
defined objective functions do not get degraded.
Themethodsusedinclude:
meta‐criterion‐a function defined on partial
criteria that enables the decision‐maker to utilize
particulardecisions:
u(x)=u[f
1(x),f2(x),…,fs(x)] (1)
Thesimplestmeta‐criterionisaweightedsum:
1
s
kk
k
ux wf x
(2)
Thesolutionforadefinedtaskisadecision,found
inasetofacceptabledecisions,thatinthesenseof
meta‐criterionu(x)isthebest. Itshouldbenoted
that the best decision in the sense of u(x) is a
searchedfortradeoffdecision.
The main
criterion and secondary criteria‐a
function seeking the best solution for the main
criterion
while ensuring the indicated level of
solutionsforthesecondarycriteria
:
1
2, ,
kk
fmax
f
xpdlak s
xD
(3)
The strict hierarchy of objectives‐ordering the
criteria starting from the most important. In this
method, the determination of a tradeoff decision
consists in solving the auxiliary tasks
ks
LL
(k=1,…,s)wherethesolutionforthefinaltaskisa
determinant of the multi‐criteria task tradeoff
decision.
minimizationofthedistancefromtheidealpoint‐
theacceptablesolution is the point nearest to the
idealpoint.Thepoint
1
, ,
s
zz z
pointisthe
ideal point in the space of results,
while
1
, ,
n
x
xx
is the ideal point in the
spaceofsolutionsif:
max{ :
kk k
zfx fxxD
}fork=1,…,s, (4)
if:
x
D,then
x
isanoptimaltask;
x
Doritdoesnotexist,thenweseek
pointx’
D,
where
''
1
[, ,
s
zz z
],whichliesascloseas
possibletotheidealpoint
z ,
where
'
kk
zfx
fork=1,…,s,
while:
0
k
z ,then
0 1, ,
kk
ymax
f
xz k s
xD
(5)
495
where
y–minimumdegreeoftheimplementation
ofparticularobjectives,when:
0
k
z ,then
k
k
k
z
dx
z
k
k
f
x
m
, (6)
where
k
m =min{
:}
k
f
xxD
1, ,
k
wmin
dx wk s
xD
,
where
w‐auxiliaryvariabledeterminingthe
maximumrelativedeviationfromthe
optimalvalueofthecriterion.
For the problems being solved, an n‐dimensional
vectorofthedecisionvariablex={x
1,x2,…,n}inthe
setofsolutionsD.Thetaskistofindthex’vectorthat
minimizes the objective function. Standard
optimization tasks are formulated for a set of
solutions with a series of constraints, where the
considered objective functions conflict with each
other. The optimization of the
objective function for
one solution les to unacceptable results. It is
impossibletoobtainmulti‐criteriasolutionofthetask
where particular objective functions are optimized.
The solution for multicriteria problems is the
examination of a set of solutions D that meets
conditionsatanassumedlevel.
3 MULTICRITERIAOPTMIZATION
BYGENETIC
ALGORITHMS
The concept of a genetic algorithm, a non‐
deterministicmethodforfindinganoptimalsolution,
isderivedfromthetheory ofevolution.The concept
was developed by John Henry Holland in the 1960s
and70s [5]. The mechanism ofgenetic algorithms is
inspired by the theory of evolution,
according to
whichnaturalspeciesthatarenotabletosurvivewill
beextinct.However,strongindividualswilltransmit
their genes to future generations by reproduction.
Over time, strong species that transmit a genetically
correct combination begin to dominate in a
population.
In a long process of natural evolution that
takes
placeinnature,arandomchangeingenesmayoccur.
The changes that bring extra advantages in the
struggletosurviveleadtotheevolutionofthecreated
individuals. Unsuccessful modification is eliminated
bynatureitself.
The greatest probability of evolution comprises
solutions with the highest degree of fitness, defined
bythevalueofthefitnessfunction(objectivefunction
oftheoptimizationtask).Theliteraturepresentsboth
hypothetical descriptions and practical examples of
the genetic algorithm used for finding an optimal
solution. The genetic algorithm is a convenient tool
widely used for solving complex decision‐making
processes[3][8][10][11]
[12].
Geneticalgorithmsbasedonnaturalevolutionare
used for solving optimization tasks with multiple
objectivefunctions.Theessentialcharacteristicofthe
algorithmsisthattheobjectivefunctioncanbeeasily
modified to find secondary acceptable solutions in
one population. The ability to search a few spaces
simultaneously allows the solving
of complex tasks
with multiple objective functions. A number of
algorithmsshowsnouseofscalingorweighing.
Various authors propose the following
classificationsofgeneticalgorithms:
Vector Evaluated Genetic Algorithms, VEGA [16]
[13];
Multi‐objectiveGeneticAlgorithm,MOGA[2];
NichedParetoGeneticAlgorithm[6];
Random
Weighted Genetic Algorithm, RWGA
[14];
NondominatedSortingGeneticAlgorithm[17];
Strength Pareto Evolutionary Algorithm, SPEA
[19];
Pareto‐ArchivedEvolutionStrategy,PAES[7];
Fast Non‐dominated Sorting Genetic Algorithm,
NSGA‐II[1];
Multi‐objective Evolutionary Algorithm, MEA
[15];
Rank‐DensityBasedGeneticAlgorithm,RDGA[9].
Special
attention should be paid to numerous /a
number of varieties of multi‐criteria genetic
algorithms that are widely known and used in
variousfields.
4 EVOLUTIONARYMETHODSOF
MULTICRITERIAOPTIMIZATIONFORA
MODELOFLNGDISTRIBUTION
The solution of the problem, using multi‐criteria
optimization for the LNG distribution
model,
involvestheattributionofweightsw
itoeachdefined
objectivefunction
'
i
f
x .Toobtainonesolution,the
followingmethodofweightedcriteriaisproposed:
'' '
11 2 2
kk
min f w f x w f x w f x (7)
where:
w∈[0,1]and
1
i
w
Using this transformation, we can optimize a
singleobjective function usingmethodsusedfor the
solvingofsingle‐criteriontasks.
An example solution of the task is the
determinationofacyclewithleastlength,if:
eachLNG‐poweredvesselfromaspecifiedregion
must be visited only once
by the LNG bunker
vessel;
starting point is also the final point ( LNG
terminal)‐closedcycle.
The objective function f(c) assumes the following
form:
496
min
cj
jJ
fd d
(8)
where
d
j – a distance travelled by j‐th LNG bunker vessel
betweenLNG‐poweredvessels,j=1….J.
To present an example [4], four points were
selected and presented as a list with their
geographical coordinates. The points represent the
positions of the LNG distribution facility (bunker)
andLNG‐powered
vessels.
1
A
=53.93°N
A
=14.31°E
2
B
=54.20°N
B
=14.73°E
3
C
=54.25°N
C
=14.92°E
4
D
=54.19°N
D
=15.13°E
Fourpointsgivesixcombinationsoftheacceptable
solution:
1 A–B–C–D–A
2 A–C–D–B–A
3 A–D–C–B–A
4 A–C–B–D–A
5 A–D–B–C–A
6 A–B–D–C–A
Firstthedistances,innautical miles, betweenthe
pointswerecalculated(Table1,Figure2):
Table1.Examplesofdistancesbetweenthepoints
_______________________________________________
[Nm] A B C D
_______________________________________________
A0 24 6.727.7
B24 0 20.5 41.6
C6.720.5 0 14.5
D27.7 41.6 14.5 0
_______________________________________________
Figure2.Examplesofdistancesbetweenthepoints
Genetic algorithms were used to generate a list
with the best sequence of the visited points
correspondingtothelengthofthecycle.Accordingto
the principle of elitism, one of the best equipped
chromosomes is copied to the new population. To
ensurethateachsubsequentpopulationadaptsbetter,
it is
assumed that chromosomes from the previous
population with the highest values of the fitness
function have the greatest impact on a new
population.
In each evolutionary step, the chromosomes are
analyzedaccordingtotheassumedcriteriaoffitness
quality.Through selection,theworstindividuals are
eliminated from the population. Best‐
fit individuals
aresubjectinthisexampletoordercrossover(OX)in
which offsprings are created on the basis of
ʹsubroutesʹ taken from the parents, where the
ʹsubrouteʹ of the first offspring is taken from the
second parent while theʹsubrouteʹ of the second
offspringistakenfromthefirst
parent.Subsequently,
thecreatedroutesarecompletedsothatnoconflictof
twoidenticalpointsintheroutearises.Thenrandom
changesareputintothe genotype (mutation) that is
aimed at introducing diversity in the population by
addingnewindividualstothepopulation.
The evolutionary process resulting from the
actions of crossover and mutation operator creates
solutionsfromwhichanextgenerationpopulationis
built.Theconditionforterminationoftheselectionof
the best‐fit chromosome of the evolution process is
eitherreachingthedefinednumberofgenerationsor
asatisfactoryfitnesslevel.
In the case considered herein the
evaluation of
each individual is the criterion of the route length
they represent. Acceptable solutions were generated
basedonthevaluesoftheevaluationfunction,(Table
2).
Table2.Evaluationoftheindividualsandselection
_______________________________________________
ThevalueoftheevaluationfunctionSum[Nm]
_______________________________________________
A–B–C–D–A A‐B‐> B‐C‐> C‐D‐> D‐A‐> 86.7
24.0 20.5 14.5 27.7
A–B–D–C–A A‐B‐> B‐D‐> D‐C‐> C‐A‐> 86.8
24.0 41.6 14.5 6.7
A–D–B–C–A A‐D‐> D‐B‐> B‐C‐> C‐A‐> 96.5
27.7 41.6 20.5 6.7
A–C–D–B–A A‐C‐> C‐D‐> D‐B‐> B‐A‐> 86.8
6.714.5 41.6 24.0
A–D–C–B–A A‐D‐> D‐C‐> C‐B‐> B‐A‐> 86.7
27.7 14.5 20.5 24.0
A–C–B–D–A A‐C‐> C‐B‐> B‐D‐> D‐A‐> 96.5
6.720.5 41.6 27.7
_______________________________________________
Two routes were correctly distinguished,
characterizedbytheleastlengthof86.7Nm.Thusthe
solutionoftheanalyzedproblem:findacycleofthe
leastlengthisrepresentedbytworoutes:
1 A–B–C–D–A
2 A–D–C–
B–A
5 CONCLUSIONS
The main problem concerning LNG vessels is
unavailability of LNG bunker station or any other
infrastructurealongthe wholecoastline.Themodels
of the fuel distribution are built taking into account
twoco‐dependentquantities,suchastheroutelength
of system units and the location
of distribution
facilities. In this case, the distribution problem is a
combinationofaclassicproblemoftheroutelocation
andtheavailabilityofthedistributionfacility.
The problems of planning routes for vehicles are
known in the literature as the multiple traveling
salesmenproblem.TheproblemofLNGdistribution
system is closely related to the problem of route
planning. These problems are characterized by a
497
simpledefinitionofthetask,unlikethesolution.The
problems concerning LNG distribution methods are
therulesthatassumeNP‐completeproblemsthatcan
beeasilyformulated,buttheoptimalsolutionforthe
given problem is very difficult. The presented
methods efficiently analyze the area of solutions for
the problem
considered. Above all, their purpose is
the solution of optimization tasks. Their particular
usefulness is demonstrated in the solution of
problems of combinatorial nature. Finding the
optimal outcome for a great number of points is a
hard and work‐consuming task. Genetic algorithms
areanalternativeforthemethodscommonly
usedso
far.
ACKNOWLEDGEMENTS
Thisresearchoutcome hasbeen achieved under grantNo.
S/1/CIRM/2016,financedfromasubsidyoftheMinistryof
ScienceandHigherEducationforstatutoryactivities.
REFERENCES
[1]Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T., A
fastandelitistmultiobjectivegeneticalgorithm:NSGA‐
II,IEEETransactionsonEvolutionaryComputation6(2)
(2002)182‐197.
[2]Fonseca C.M, Fleming P.J.: Genetic Algorithms for
Multiobjective Optimization: Formulation, Discussion
and Generalization. In Stephanie Forrest, editor,
Proceedings of the Fifth International
Conference on
Genetic Algorithms, pages 416–423, San Mateo,
California, 1993. University of Illinois at Urbana‐
Champaign,MorganKauffmanPublishers.
[3]Goldberg D. E., Algorytmy genetyczne i ich
zastosowanie.Warszawa:WNT,2003.
[4]Gucma M., Bąk A., Chłopińska E.: Concept of LNG
transferandbunkeringmodelofvessels
atSouthBaltic
SeaArena.AnnualofNavigation25/2018,pages79‐91.
[5]Holland, J.H., Adaptation in Natural and Artificial
Systems,UniversityofMichiganPress,AnnArbor,1975.
[6]Horn, J., Nafpliotis, N., and Goldberg, D.E. A niched
Paretogeneticalgorithmformultiobjectiveoptimization.
in Proceedings of the First IEEE Conference
on
Evolutionary Computation. IEEE World Congress on
ComputationalIntelligence,27‐29June1994.
[7]Knowles, J.D. and Corne, D.W., Approximating the
nondominatedfrontusingtheParetoarchivedevolution
strategy,EvolutionaryComputation8(2)149‐172.
[8]Koza J. R., Rice J. P., i Roughgarden J., „Evolution of
food foraging strategies for
the Caribbean Anolis lizard
usinggeneticprogramming.”,AdaptiveBehavior.,t.1,nr2,
ss.47–74,1992.
[9]Lu,H.andYen,G.G.,Rank‐density‐basedmultiobjective
genetic algorithm and benchmark test function study,
IEEE Transactions on Evolutionary Computation 7(4)
(2003)325‐343.
[10]Michalewicz Z., Algorytmy genetyczne + struktury
danych =
programy ewolucyjne. Warszawa:
WydawnictwoNaukowo‐Techniczne,1999.
[11]Migawa K.: Method for control of technical objects
operationprocesswiththeuseofsemi‐Markovdecision
processes,JournalofKONESPowertrainandTransport.,
t.19,nr4,2012.
[12]MitchellM., Anintroductionto genetic algorithms., 1.
wyd.Cambridge:MITPress,
1996.
[13]Mitsuo G., Runwei Ch.: Genetic algorithms and
engineeringoptimization.JohnWiley&Sons,inc.New
York,2000.
[14]Murata, T. and Ishibuchi, H. MOGA: multi‐objective
genetic algorithms. in Proceedings of 1995 IEEE
InternationalConferenceonEvolutionaryComputation,
29Nov.‐1Dec.1995.
[15]Sarker, R., Liang, K.‐H.,
and Newton, C., A new
multiobjectiveevolutionaryalgorithm,EuropeanJournal
ofOperationalResearch140(1)(2002)12‐23.
[16]Schaffer, J.D. Multiple Objective optimization with
vector evaluated genetic algorithms. in International
ConferenceonGeneticAlgorithmandtheirapplications.
1985.
[17]Srinivas, N. and Deb, K., Multiobjective Optimization
Using Nondominated Sorting in
Genetic Algorithms,
Journal of Evolutionary Computation 2(3) (1994) 221‐
248.
[18]Tutorial A., Konak A., Coit D.W., Smith A.E.: Multi‐
Objective Optimization Using Genetic Algorithms: A
tutorial. Reliability Engineering and System Safety 91
(2006),s.992–1007.
[19]Zitzler, E. and Thiele, L., Multiobjective evolutionary
algorithms: a comparative case study and
the strength
Pareto approach, IEEE Transactions on Evolutionary
Computation3(4)(1999)257‐271.
[20]Dyrektywa Parlamentu Europejskiego i Rady
2012/33/UE
