Multiperiod Multi Traveling Salesmen Problem with Time Window Constraints

Abstract

This study arises from a real world problem. In the problem, a number of university representatives are required to visit a number of exam locations departing from a central location and returning back to the same location. Each location may be visited in one of four different periods; however these visits must be done in pre-specified time windows. Time windows may be different from location to location and across periods for the same location. The problem is modeled as a multi-period multi traveling salesmen problem with time window constraints. Earlier attempts to solve the resulting models using mixed integer linear programming approach proved to be ineffective. Hence two stochastic heuristic search techniques, based on simulated annealing (SA) and robust tabu search (RTS), are used. For this, a new solution representation and associated decoding and encoding mechanisms are developed. Proposed approaches are tested on various problem instances, and performance of the solution approaches are discussed. Finally, a real case is considered for which a method for obtaining travel distance and travel time matrices from Google Distance Matrix API is developed. The results obtained from the real case is also discussed and future research directions are provided.