Memetic Algorithms for the Technician Routing and Scheduling Problem: Real Case Study of Energy Distribution System Operator (DSO)

This study addresses a real industrial problem faced by a company operating an energy distribution network, namely, the efficient assignment of tasks to their agents. This problem involves determining the best routes for agents to visit multiple tasks, known as the Technician Routing and Scheduling Problem (TRSP). It considers a limited number of agents and tasks that are located in different areas. Each task has a service duration, time window during which the service should be executed, and set of required skills. Additionally, agents possess different skills, multiple availability intervals, and maximum daily working hours. The objective is to minimize the total distance traveled, including the penalties for unrouted tasks. To tackle this problem, we propose an order-first split-second approach that combines a memetic algorithm with giant tour encoding of the chromosome with an extension of the optimal split method. Our primary objective is to evaluate the effectiveness of this approach on a real case of the TRSP problem in the context of energy network management. The second objective is to compare our genetic algorithm, which uses giant tour encoding, with a genetic algorithm scheme that employs an indirect encoding representation proposed in the literature. It is worth noting that this indirect encoding has proved its effectiveness in real instances of an industrial problem, which is similar to our case study. We aim to test different implementations of the proposed genetic algorithms on real instances to evaluate the impact of the extended optimal split, local search, and encoding type.