MODEL AND VARIABLE NEIGHBORHOOD DESCENT ALGORITHM FOR VEHICLE ROUTING PROBLEM WITH HETEROGENOUS FLEET, MULTIPLE TRIPS, MULTIPLE TIME WINDOWS, AND SIMULTANEOUS PICK-UP DELIVERY - Afrianti, Nursinta
Planning vehicle routes is one of the important decisions in the company's operational activities. The distribution of bottled water by PT. X is a vehicle route problem (VRP) with simultaneous pick-up and delivery, which means that there are delivery and pick-up activities at the customer simultaneously. Departing from the problems that occurred at PT. X, this study develop a mathematical model and metaheuristic algorithm for the vehicle route problem with heterogeneous fleets, multiple routes, multiple time windows, and simultaneous pick-up and delivery or abbreviated as MRK-HRMJWMPPS. The mathematical model developed in this study is in the form of Mixed Integer Linear Programming (MILP) with the performance criteria of minimizing the total transportation cost. The search for solutions using the MILP method can be done on small-scale problems, but the computation time increases exponentially as the amount of data increases. The Variable Neighborhood Descent (VND) algorithm was developed to overcome the length of computation time required for the MILP method. The search for the initial VND solution uses the Sequential Insertion (SI) algorithm. The mathematical model and VND algorithm developed in this study can solve the MRK-HRMJWMPPS problem, from computing the data set to produce a feasible solution for 5 to 7 customers with a percentage difference between the MILP and VND solutions, which is 16.88%. Data trials were also conducted with 20, 50, and 100 customers in this study using the SI and VND algorithms. The developed model and algorithm can also be used on other MRK models, namely MRK-RMJWPPS for limited homogeneous vehicles, MRK with multiple routes, single time window, and simultaneous pick-up and delivery, and also for MRK- HRMJWMPPS for mixed pick-up and delivery.