🧡 Bussiness Contest🧡
🥇WIRAUSAHA MUDA FMIPA🥇
Khusus bagi Mahasiswa FMIPA
Rebut Hadiahnya….
Juara 1 Rp. 400.000,-
Juara 2 Rp. 300.000,-
Juara 3 Rp. 200.000,-
Semua peserta akan mendapatkan sertifikat “ WIRAUSAHA MUDA FMIPA 2020”
Link Pendaftaran Klik
Implementasi Metode TSP dalam program Komputer dan Analisis Kinerjanya-Jurnal Matematika Vol 1 Nomor 1, Januari 2013
Sapti Wahyuningsih dan Darmawan Satyananda
Pengembangan Modul Penarapan Teori Graph berbasis ICT sebagai pedoman praktek kerja lapangan (PKL) Mahasiswa Jurusan Matematika di Industri
Oleh Sapti Wahyuningsih dan Darmawan Stayananda
2014 – KNM XVII ITS – Sapti-Darmawan
CHARACTERISTIC STUDIES OF SOLUTION THE MULTIPLE TRIP VEHICLE
ROUTING PROBLEM (MTVRP) AND ITS APPLICATION
IN OPTIMIZATION OF DISTRIBUTION PROBLEM
Sapti Wahyuningsih1, Darmawan Satyananda2
1,2State University of Malang,
1saptiw81@gmail.com, 2dsatyananda@gmail.com
Abstract
Distribution is a delivery process of goods or service from producer to customer. Usually,
distribution process done for fulfills a customer demand, which have far distance relatively
and need more time. The problem can be modeled into a graph form. In more specific case,
the problem can be grouped as Vehicle Routing Problem (VRP). VRP is a problem to look
for a number of minimum routes where each customer served precisely once and early and
end in depot. Multiple Trip Vehicle Routing Problem (MTVRP) is one of theVRP variant
with capacities and time constraint in addition, besides that; the vehicle can serve more than
one route. The MTVRP problem was solved by using insertion heuristic method, Brandao
and Mercers, Self-Developed algorithm and Saving Procedure for Multiple Use of Vehicle
(SPMU), Tabu Search Algorithm which represented by a graph. There are three stages
completion of tabu search algorithm on the problem of MTVRP. The stages are
initialization stage, development stage and stage that determines the optimum solution
within the tabu from the solution result of nearest insertion method on the initialization
stage with tabu solution from development stage and its solved by using sequential
insertion algorithm. Study of this MTVRP gives some analysis, insertion heuristic method
in MTVRP give more optimal solution than Brandao and Mercers method, but insertion
heuristic method require longer seeking step in comparison with Brandao and Mercers
method. This Matter caused of insertion heuristic method based on two matters that is
arround time and profitability. The excellence of Self-Developed algorithm lays in the
iteration step. This algorithm uses FI method to determine the visited customer sequence in
a combined route. The uses of FI method is meant to obtain a route with minimum distance.
In the other side, the excellence of SPMU lays in inisialisation step. There are several
criteria for sequential insertion algorithm to selection of initial customers (seed
customers) of which is the shortest time window and longest travel time. Searching seed
customer with the fastest turn around time takes a long time because they have to calculate
all time points then select the most minimum time. While the criteria for the farthest
distance from the depot, seed customer is obtained by finding the distance from any
point to the farthest depot then selected as the seed customer. Result of analysis tabu
search algorithm with cheapest insertion heuristic algorithm and insertion heuristic are,
tabu search produces more optimum travel time solution than other comparative algorithms
cheapest insertion heuristic algorithm and insertion heuristic. The search of solutions on
tabu search is done deeper in the development stage. MTVRP problem is solved by using
sequential insertion algorithm. These arch process in the algorithm begins with the
customer selecting initial (seed customers) with the criteria of the farthest distance from the
depot, then continues to find the shortest distance from the seed customer then insert the
best position.
Keywords: Distribution, MTVRP, Customer, Depot
DEVELOPING MST, TSP, AND VRP APPLICATION
Darmawan Satyananda
Department of Mathematics Education, State University of Malang
dsatyananda@gmail.com
Abstract
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