PENYELESAIAN MINIMUM SPANNING TREE DENGAN ALGORITMA BERBASIS SOFT COMPUTING DAN APLIKASINYA PADA MASALAH LOGISTIK

Shinta Tri Kismanti, Imam Mukhlash

Abstract


Masalah optimasi jaringan adalah pencarian nilai terkecil pada suatu keadaan jaringan. Salah satu masalah optimasi jaringan adalah minimum spanning tree (MST). Masalah MST bertujuan untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang tersebut dapat diminimumkan. Dalam paper ini, akan ditelaah mengenai penelitian peningkatan solusi paa MST dengan pendekatan soft computing dan aplikasinya pada system logistic. Secara umum solusi penyelesaian MST dapat dilakukan dengan metode eksak dan metode heuristik.

Keywords


Heuristik; logistik; MST; Soft Computing;

Full Text:

PDF

References


T.A. Almeida, A. Yamakami, and M.T.

Takahashi, An evolutionary

approach to solve minimum spanning tree problem with

fuzzy parameters, in Proc.

Int. Conf. Computational

Intelligence for Modelling,

Control and Automation,

(2005), 203–208.

F. Altiparmak, M. Gen, L. Lin, and T.

Paksoy, A genetic algorithm

approach for multi-objective

optimization of supply chain

networks, Computers &

Industrial Engineering, 51

(2006), 196–215.

C.F. Bazlamaçci, and K.S. Hindi,

Minimum-weight spanning

tree algorithms a survey and

empirical study, Computers

and Operations Research, 28

(2001), 767-785.

B. Bilgen, Application of fuzzy

mathematical programming

approach to the production

allocation and distribution

supply chain network

problem, Expert Systems with

Applications, 37 (2010),

–4495.

P.T. Chang, and E.S. Lee, Fuzzy

decision networks and

deconvolution, Comput Math

Appl, 37 (1999), 53– 63.

A. Chen, G. Yang, and Z. Wu, Hybrid

discrete particle swarm

optimization algorithm for

capacitated vehicle routing

problem. Chen et al. / J

Zhejiang Univ SCIENCE A,

(4) (2006), 607-614.

W. Chen, Y. Li and W. Ding,

Optimizing the Route

Selection of Transit Based on

Genetic Algorthm. IEEE.

(2008), 974-968.

A.C.B. Delbem, A. Carvalho, and

N.G. Bretas, Main Chain

Representation for

Evolutionary Algorithms

Applied to Distribution System

Reconfiguration, IEEE

TRANSACTIONS ON POWER

SYSTEMS, 20/1 (2005), 425-

M. Dorigo and Di Caro G., Ant Colony

Optimization : A New Meta-

Heuristik. IIEC Transaction on

Evulutionary Computation,

(1990), 1470-1477.

M. Dorigo and C. Blum, Ant colony

optimization theory: A survey,

Theoretical Computer

Science, 344 (2005), 243–

M. Dorigo and T. Stutzle. The ant

colony optimization

metaheuristic: Algorithms,

applications and advances.

In: Glover, F., Kochenberger,

G. (Eds.), Handbook of

Metaheuristics. Kluwer

Academic Publishers. 2002.

E.F.G. Goldbarg, G.R. de Souza, and

M.C. Goldbarg. Particle

Swarm Optimization for the

Bi-objective Degreeconstrained

Minimum

Spanning Tree. IEEE Congress

on Evolutionary Computation,

(2006), 420427.

J. Gao and M. Lu, Fuzzy quadratic

minimum spanning tree

problem. Applied Mathematics

and Computation, 164

(2005), 773–788.

M. Gen, K. Ida, and Y. Li, Bicriteria

Transportation Problem by

Hybrid Genetic Algorithm.

Computers ind. Engng, 35

(1998), 363-366.

M. Gen, K. Ida, and Y. Li, Solving

Bicriteria Transportation

Problem by Hybrid Genetic

Algorithm. Computers ind.

Engng, 35 (1999) 363-366.

M. Gen, Y. Li, & K. Ida, Solving Multi-

Objective Transportation

Problem by Spanning Tree-

Based Genetic Algoritm. IEICE

Trans Fundamentals, E82

(1999), 2802-2810.

M. Gen and A. Syarif, Multi-stage

Supply Chain Network by

Hybrid Genetic Algorithms.

J.L. Verdegay (ed.), Fuzzy

Sets Based Heuristics for

Optimization, (2003), 181-

M. Gen, A. Kumar, and J.R. Kim,

Recent Network Design

Techniques using Evolutionary

Algorithm. Science Direct

Production Economic, 98

(2005), 251-261.

M. Gen, F. Altiparmak, and L. Lin, A

Genetic Algorthm for Two Stage Transportation Problem

using Priority-based Encoding,

Springer-Verlag2006, OR

Spectrum, 28 (2006), 337-

J. Gottlieb, and L. Paulmann, Genetic

algorithms for the fixed

charge transportation

problem, In Proceedings of

IEEE international conference

on evolutionary computation,

(1998), 330–335.

W.J. Gutjahr, A Graph-based Ant

System and its convergence,

Future Generation Computer

Systems, 16 (2000), 873–

T. Itoh and H. Ishii, An approach

based on necessity measure

to the fuzzy spanning tree

problems, J. Oper. Res. Soc.

Jpn.-Keiei Kagaku, 39 (1996),

–257.

A. Janiak and A. Kasperski, The

minimum spanning tree

problem with fuzzy costs,

Fuzzy Optim. Decis Making, 7

(2008), 105–118.

J.B. Jo, Y. Li, and M. Gen, Nonlinear

Fixed Charge Transportation

Problem by Spanning Treebased

Genetic Algorithm,

Science Direct Computer &

Industrial Engineering, 53

(2007), 290-298.

J. Kennedy and R. C. Eberhart,

Particle swarm optimization.

In Proceedings of the IEEE

international conference on

neural networks IV, (1995),

–1948.

M.H. Keshtelli, S.M.A. Zavardehi, and

R.T. Moghaddam, Addressing

a Nonlinear Fixed-charge

Transportation Problem using

a Spanning Tree-based

Genetic Algorithm. Science

Direct Computer & Industrial

Engineering, 59 (2010), 259-

J.B. Kruskal, On the shortest

spanning subtree of a graph

and the travelling salesman

problem. Pric. AMS, 7 (1956),

-50.

S. Kusumadewi, and H. Purnomo,

Penyelesaian Masalah

Optimasi dengan Teknik –

Teknik Heuristik. Edisi

Pertama, Graha Ilmu,

Yogyakarta, (2005).

H.C.W. Lau, T.M. Chan, W.T. Tsui,

F.T.S. Chan, G.T.S. Ho, and

K.L. Choy, A fuzzy guided

multiobjective evolutionary

algorithm model for solving

transportation problem.

Expert Systems with

Applications, 36 (2009),

–8268.

J. E. Lee, M. Gen, & K. G. Rhee,

Network model and

optimization of reverse

logistics by hybrid genetic

algorithm. Computers &

Industrial Engineering, 56

(2009), 951–964.

Y. Li, and Y. Bouchebaba, A New

Genetic Algorithm for the

Optimal Comunication

Spanning Tree Problem.

Springer-Verlag Berlin

Heidelberg, (2000), 162-173.

R. Munir, Matematika Diskrit,

Penerbit Informatika,

Bandung, 2012.

S.C. Narula, Degree-constrained

minimum spanning tree.

Comput Oper Res, 7 (1980),

-249.

N.F. Frank and C. WittRuntime,

Analysis of a Simple Ant

Colony Optimization

Algorithm. T. Asano (Ed.) :

ISAAC 2006, LNCS 4288,

(2006), 618–627.

J. Peng, and S. Li, Spanning tree

problem of uncertain network,

in Proc. 3rd Int. Conf.

Computer Design and

Applications, Xi’an, China,

R. Poli, K. Kennedy, and T. Blackwell,

Particle swarm optimization.

Springer Science + Business

Media, Swarm Intell 1

(2007), 33–57.

R. Poli, Analysis of the Publications

on the Applications of Particle

Swarm Optimisation. Journal

of Artificial Evolution and

Applications. Volume 2008,

Article ID 685175, 10 pages,

A. Prakash, and S.G. Deshmukh, A

multi-criteria customer

allocation problem in supply

chain environment: An

artificial immune system with

fuzzy logic controller based

approach. Expert Systems

with Applications, 38 (2011),

–3208.

R. C. Prim, Shortest connection

networks and some

generalizations. Bell Systems

Techn. J., 36 (1957), 1389-

M., Reimann and M. Laumanns, A

hybrid ACO algorithm for the

Capacitated Minimum

Spanning Tree Problem.

Institute for Operations

Research, Swiss Federal

Institute of Technology

Zurich. 2004.

M. Reimann, and M. Laumanns,

Savings based ant colony

optimization for the

capacitated minimum

spanning tree problem.

Computers & Operations

Research, 33 (2006), 1794–

E. Ruiz, M. A. Sambola, E.

Fernández, and M.G.C.

Resende, A biased randomkey

genetic algorithm for the

capacitated minimum

spanning tree problem.

Computers & Operations

Research, 57 (2015), 95–108.

S. Sivanandam, Introduction to

Genetic Algorithm. New York :

Springer Science + Business

Media. 2008.

S.J. Shyu, P.Y. Yin, B.M.T. Lin, & M.

Haouari, Ant-Tree: an ant

colony optimization approach

to the generalized minimum

spanning tree problem.

J.Expt.Theor.Artif.Intell, 15

(2003), 103–112.

H. Stadtler, Supply chain

management and advanced

planning–basics, overview

and challenges. European

Journal of Operational

Research, 163 (2005), 575–

A. Syarif, Y. Yun, and M. Gen, Study

on Multy-Stage Logistic Chain

Network : a Spanning Treebased

Genetic Algorithm

Approach. Science Direct

Computer & Industrial

Engineering, 43 (2002), 209-

A. Syarif, and M. Gen, Solving

Exclusionary Side Constrained

Transportation Proble by

using a Hybrid Spanning

Tree-based Genetic

Algorithm. Journal of

Intelligent Manufacturing, 14

(2003), 389-399.

M. Tuegeh, A. Soeprijanto, and H. P.

Mauridhi, Optimal Generator

Scheduling Based on Particle

Swarm Optimization. Seminar

Nasional Informatika 2009

(semnasIF 2009). ISSN:

-2328.

B. Tilanus, Introduction to

information system in logistics

and transportation. Elsevier,

London. 1997.

S. Tragantalerngsak, J. Holt, M.

Ronnqvist, Lagrangian

heuristics for the two-echelon,

single-source, capacitate

location problem. Eur J Oper

Res 102 (1997), 611–625.

G. Venter, J. S. Sobieski, Particle

Swarm Optimization. AIAA

JOURNAL, 41/8, (2003),

-1589.

H.F. Wang and H.W.Hsu, A Closedloop

Logistic Model with a

Spanning Tree based Genetic

Algorithm. Science Direct

Computer & Operations

Research, 37 (2010) 376-289.

Yan Wei-min and Wu Wei-min, Data

Structure, Beijing: Tsinghua

Publishing House, 1997.

M.J. Yao and H.W. Hsu, A new

spanning tree-based genetic

algorithm for the design of

multi-stage supply chain

network with nonlinear

transportation costs, Springer

Science, 2009.

W.C. Yeh, A Hibrid Heuristic

Algorithm for the Multi Stage

Suplly Chain Network Problem. Int J adv Manuf

Technol, 26 (2005), 675-685.

W. Yi, and A. Kumar, Ant Colony

Optimization for Disaster

Relief Operations,

Transportation Research Part

E, 43 (2007), 660-672.

S.A. Zaverdehi, M.H. Kesthehi, and

R.T. Moghaddam, Solving

Capacitated Fixed-charge

Transportation Problem by

Artificial Immune and Genetic

Algorthm with a Prufer

Number Representation.

Expert System with

Applications, 38 (2011),

-10474.

Zha, Xuan F., Artificial Intelligence

and Integrated Intelligent

Information Systems

Emerging Technologies and

Aplications, Idea Grup

Publishing. London, 2007.

J. Zhanga, J. Zhoub, and S. Zhong,

Models for inverse minimum

spanning tree problem with

fuzzy edge weights. Journal of

Intelligent & Fuzzy Systems,

(2014), 2691–2702. [60]

G. Zhou and M. Gen, Genetic

Algorithm Approach on Multicriteria

Minimum Spanning

Tree Problem. European

Journal of Operational

Research, 114 (1999), 141-

G. Zhou, H. Min, and M. Gen, A

Genetic Algorthm Approach to

the bi-criteria Allocation of

Customers to werehouses. Int

J Production Economics, 86

(2003), 35-45.

G. Zhou and M. Gen, A Genetic

Algorthm Approach on treelike

Telecomunication

Network Design Problem.

Journal of the Operational

Research Society, 54 (2003),

-254.

J. Zhou, L. Chen, and K. Wang, Path

Optimality Conditions for

Minimum Spanning Tree

Problem with Uncertain Edge

Weights, International Journal

of Uncertainty, Fuzziness and

Knowledge-Based Systems,

/1 (2015), 49–71.




DOI: https://doi.org/10.35334/borneo_saintek.v1i1.880

Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Jurnal Borneo Saintek

slot dana

PODOMORO138 SEDAYU138 JALURDEWA MERAHBET