MODEL AND VARIABLE NEIGHBORHOOD SEARCH FOR DIAL-A-RIDE PROBLEM CONSIDERING MINIMUM NUMBER OF CUSTOMERS

• Main Author: Fauzy Amrullah, Iqbal
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/71080
• Institution: Institut Teknologi Bandung

In the dial-a-ride problem (DARP) passengers must be transported from the pick-up point to the drop-off point taking into account the time window limitation and passenger inconvenience time. This study develops a mathematical model and a solution algorithm for the DARP case with multi depot characteristics, a heterogeneous maximum travel time for each passenger and a minimum number of passengers that must be served by each vehicle used. The mathematical model and the solution algorithm in this study have an objective function to minimize the total transportation cost while fulfilling all customer demands. In the problem-solving algorithm, the generation of initial route solution is done using the greedy insertion heuristic method. This initial route solution will then be improved to get a better solution using variable neighborhood search (VNS). In both stages, restrictions on the minimum number of passengers will be ignored. Then at the next stage, a feasible solution will be sought that can fulfill the minimum number of passengers restriction using relocate and destroy operators. The developed algorithm has a faster average computation time with a gap of -94% compared to the analytical calculation of the optimal solution. Meanwhile, the value of the objective function using the algorithm equal to the results of the calculation of the optimal solution analytically for tiny instances.