Heuristics for routing vehicles for large scale employee transporatation

Abstract

The considerable potential for vehicle routing methodology for large-scale employee transportation in the Indian context has been the motivating factor for this study. The principal objective of this study has been the development of heuristics for the vehicle routing problem associated with employee transportation. Three heuristics, namely the nearest insertion heuristic, the cheapest insertion heuristic, and the nearest neighbour heuristic, have been adapted to the case of employee transportation. Further, lower bounds have been computed to measure the quality of the solution obtained from the heuristics. Finally, a generalised assignment heuristic has been proposed. The applicability of the heuristics has been demonstrated through two case studies, the data for which pertains to two organisations, namely Indian Telephone Industries Limited and National Aerospace Laboratories. The results of the study can be summarised as follows: (i) The nearest insertion heuristic provides the best solution with respect to the total distance covered by all the vehicles, total number of vehicles used, and the average distance covered by a vehicle. The average distance covered by a vehicle assumes significance in the case of routing of vehicles across shifts as observed in the case of ITI.