DEVELOPING MST, TSP, AND VRP APPLICATION-Proceedings of International Seminar on Mathematics Education and Graph Theory 2014

Darmawan Satyananda
Department of Mathematics Education, State University of Malang

In course of Graph Theory Graf and Application of Graph Theory in Mathematics
Department State University of Malang, students learn some algorithms for optimization
problem, such as for searching Minimum Spanning Tree (MST), Travelling Salesman
Problem (TSP), and Vehicle Routing Problem (VRP). For helping solving problems, for
example for research purposes or Field Work (
Praktek Kerja Lapangan), usually students
use software for Graph application. Two of them are Grin and Giden. They have not been
updated for a long time; meanwhile there are some new algorithms that are not contained in
them. Algorithms studied in the course and are not contained in both software must be
made as separate application. Skills developing the application is learned in Data Structure
course, as discussed how structuring and operating data, with Graph and its application as
one of the subject. An application is made to unify important algorithms studied in lectures
and required in problem solving. The software implements algorithms grouped on problems
of MST, TSP, and VRP. For data benchmark, TSPLIB dataset in XML format (Extensible
Markup Language) is used.
Keywords: Graph Application, TSPLIB, XML

2014 – InaCombs Unisma – Darmawan