Trip route optimization based on bus transit using genetic algorithm with different crossover techniques: a case study in Konya/Türkiye

With the importance of time and cost in today's world, it is essential to solve problems in the best way possible. Optimization is a process used to achieve this goal and is applied in several areas, one of which is route planning. Route optimization minimizes the use of resources such as fuel, distance, and time. This study aims to optimize the traveler's route, allowing the traveler to save money on fuel and visit more tourist attractions by utilizing the time saved. For this purpose, an application is developed that presents the attractions in a chosen province and then finds the acceptable route between the selected attractions. According to the obtained visit order, the bus or buses that will provide the fastest transportation between both locations are presented. The route is determined with a genetic algorithm (GA), which is known as one of the most effective optimization algorithms. In order to select the most appropriate crossover operator of the genetic algorithm, the performances of seven methods, namely One Point Crossover (OX1), Two Point Crossover (OX2), Position Based Crossover (PBX), Order Based Crossover (OBX), Partially Mapped Crossover (PMX), Cycle Crossover (CX) and Inversion Crossover (IX) are tested on the real-world problem in Konya/Türkiye. In addition, parameter tuning is performed for the values of the algorithm's parameters such as population size, number of iterations, crossover rate, and mutation rate. As a result of the comparison, PBX is defined as the most suitable method for the problem. In addition, combinations of the four crossover methods (PMX, PBX, OX1, OX2) that obtained the best results according to the experimental analyses were compared. The comparison show that combinations of the PBX method are found to be the most suitable and the use of crossover techniques as ensemble is more effective than crossover techniques used separately. Furthermore, the best combination method named PBX + OX1 of GA was compared with ABC, ACO, SA, TSA, and PSO methods. This method is determined to find the maximum number of feasible solutions for a 14-stop real-world problem and it's the shortest route in all trials and handling them in fewer iterations.