A travelling salesman problem with limited resources: An optimization approach
Citation
Kookhahi, Elham. A Travelling Salesman Problem with Limited Resources: An Optimization Approach. --In Proceedings: 11th Annual Symposium on Graduate Research and Scholarly Projects. Wichita, KS: Wichita State University, p. 20
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.
Description
Presented to the 11th Annual Symposium on Graduate Research and Scholarly Projects (GRASP) held at the Heskett Center, Wichita State University, April 24, 2015.
Research completed at Department of Industrial and Manufacturing Engineering, College of Engineering