An Application of Genetic Algorithm in Determining Salesmen’s Routes: A Case Study

Abstract

This paper presents a case study of determining vehicles’ routes. The case is taken from a pharmaceutical products distribution problem faced by a distribution company located in the city of Padang, Indonesia. The objective of this paper is to reduce the total distribution time required by the salesmen of the company. Since the company uses more than one salesman, then the problem is modeled as a multi traveling salesman problem (m-TSP). The problem is solved by employing genetic algorithm (GA) and a Matlab® based computer program is developed to run the algorithm. It is found that, by employing two salesmen only, the routes produced by GA results in a 30% savings in total distribution time compared to the current routes used by the company (currently the company employs three salesmen). This paper determines distances based on the latitude and longitude of the locations visited by the salesmen. Therefore, the distances calculated in this paper are approximations. It is suggested that actual distances are used for future research.

Keywords

• Genetic algorithm
• traveling salesman
• vehicle routing