Graph-based model of cast planning problem and its optimization

This paper investigates a type of cast planning problem arising in real-life engineering application. The problem is mathematically modeled based on a directed graph. The number of casts is unknown in advance whereas all the charges should be assigned. The problem falls into an extension of the traditional multiple traveling salesman problem (m-TSP). In the extended m-TSP, there are multiple city types, one salesman can visit only one type of cities, and the distances between cities are asymmetric. The objective of the problem is to minimize both the total distance and the number of salesman involved. An improved genetic algorithm is developed to solve the problem and validated by using numerical experiments. The results indicate that the algorithm is relatively fast, stable, and effective.