MATHEMATICAL MODEL AND VARIABLE NEIGHBORHOOD DESCENT ALGORITHM FOR VEHICLE ROUTING PROBLEM WITH HETEROGENEOUS FLEET, MULTIPLE TRIPS, TIME WINDOWS, AND SIMULTANEOUS PICK-UP AND DELIVERY

• Main Author: Dwi Wangsa Kuswardani, Chintia
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/70467
• Institution: Institut Teknologi Bandung

This study discusses the problem of vehicle routing problem with heterogeneous fleets, multiple trips, time windows, and simultaneous pick-up and delivery or abbreviated as VRP-HMTTWSPD. The research was developed based on Aprilliany (2020) by adding heterogeneous characteristic and modifying the mathematical model for multiple routes. Currently, there is no single model that combines the characteristics of heterogeneous fleets, multiple trips, and simultaneous pick-up and delivery in a mathematical model. The combination of the characteristics is needed to solve a real case problem of a distribution of water gallon refill by PT. X in Surabaya. The purpose of this study is to develop a mathematical model of VRP-HMTTWSPD and develop solving algorithms using the metaheuristic method. The mathematical model developed in this study is in the form of Mixed Integer Linear Programming (MILP) which has performance criteria to minimize the total transportation cost which consists of vehicle variable costs and fixed costs. The Variable Neighborhood Descent (VND) algorithm was developed to overcome the long computation time used in the MILP method. The Sequential Insertion (SI) algorithm is used to determine the initial VND solution. The result is that the mathematical model developed can be used to solve VRP-HMTTWSPD and the VND algorithm developed can produce a relatively good solution for 5-7 customers data with a gap of 23.78% compared to MILP and a computation time less than 3 seconds. The algorithm can be used to solve 20, 50, and 100 customers problems. The model and algorithm developed also can be used in three other MRK models, namely VRP-MTTWSPD for limited homogeneous fleets, VRP-HMTSPD for models without time windows, and VRP-HMTTWSPD for mixed pick-up and delivery.