Application of parallel tabu search in solving Ride-sharing problem with HOV Lanes

Ride-sharing can be defined as a system where travelers can share their vehicles and travel cost with others who have a similar destination and time schedule. Ride-sharing problem with High Occupancy Vehicle (HOV) Lanes is a problem of finding an optimal route to serve costumer demand where each demand and vehicle consists of origin and destination point, and some of the route are restricted-use freeways lanes reserved for vehicles with more than a predetermined number of occupants, which called HOV lanes. With the use of ride-sharing and HOV Lanes, it is expected to reduce the number of the vehicles thus will mitigate the congestion. The optimal solution is the one with minimum number of total distance, passenger's ride time, and cost. This study discusses the application of insertion heuristic and parallel tabu search to optimize the use of Ride-sharing with HOV Lanes. Insertion heuristic is applied to obtain an initial solution and parallel tabu search algorithm is applied to improve the initial solution and obtain a better solution. For the case of eight vehicles and eight requests, from insertion heuristic we obtained an initial solution with an objective function value of 425 and with the used of parallel tabu search method we obtained a better solution with an objective function value of 420.