A travelling salesman problem with limited resources: An optimization approach

Abstract

In this paper, a mathematical model is developed to address two problems: the first problem is on healthcare delivery planning in which the objective is to diagnose and treat as many patients as possible by determining the locations to be visited assuming that patients have ability to travel a predetermined distance, e.g., to clinics in different locations. For example, a doctor may plan to visit many locations with Ebola patients in a country in Africa. In the case of a natural disaster, where there may be significant damage to the existing infrastructure, a similar scenario may happen. The second problem considers a politician who would like to visit as many locations as possible while attracting voters who would consider travelling to the campaign centers from other locations. In both applications, it is assumed that there is a limited budget and duration to achieve these objectives. These problems are modeled as a mixed integer mathematical model - a variation of travelling salesman problem with covering, budget and time constraints. The resulting mathematical program is known to be an NP-Hard problem. The objective is to find the best sub tour to maximize the demand that can be served using the limited resources. In order to solve this problem efficiently in a reasonable amount of time, a hybrid genetic algorithm is developed. In this algorithm, instead of mutation, a second level of optimization based on clustering method is proposed. This method is compared with the traditional genetic algorithm. Extensive computational results are presented to measure the efficiency of the proposed method. It is observed that where there is very limited budget and time, or very extensive resources, solving the resulting problem takes significantly less computational resources. The computational experimentation provides also insights about the effect of budget and distribution of potential visit locations on service rate and profit.