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
0341-552180
fmipa@um.ac.id
