MODEL AND VARIABLE NEIGHBORHOOD DESCENT ALGORITHM FOR VEHICLE ROUTING PROBLEM WITH MULTIPLE TRIPS, MULTIPLE TIME WINDOWS, AND SIMULTANEOUS PICKUP - DELIVERY - Rizky Aprilliany, Diana
The vehicle route problem discussed in this study is the vehicle route problem (VRP) which considers the condition of multiple routes, multiple time windows, simultaneous pickup and delivery at a single depot or VRP-MTMTWSPD. VRP-MTMTWSPD is solved by developing mathematical models and metaheuristic algorithms as a approach method for solution improvement. The objective function of mathematical formulation is to minimize the total transportation cost during the planning horizon. The component of transportation costs is fixed cost and variabel costs. The transportation cost component consists of fixed costs and variable costs. The analytical model solution is Mixed Integer Linear Programming (MILP) and it is proven to be able to provide optimal global values for the small data sets that are tested. The developed Variable Neighborhood Descent (VND) algorithm is generated to solving the problem and using sequential insertion algorithm for an initial solution. Algorithm development is done as an alternative to overcome computational time problems in analytic methods. The VND algorithm solution shows the value of the solution which is almost close to the MILP solution. The gap between MILP and VND solutions is known to be 28.63%. The VRP-MTMTWSPD model can be generalized/used for two other VRP models, that are VRP with multiple routes, single time window, and simultaneous pickup-delivery and for the MRK model with multiple routes, multiple time windows, and simultaneous mix pickup-delivery.