This problem belongs to an NP-Hard (nondeterministic polynomial time) complexity class. That means there is no efficient algorithm for finding a solution in a reasonable time for the number of elements (technicians, tasks, resources, etc.) involved. In real life it can be further complicated by additional constraints such as time windows, as well as vehicle capacity and resource limitations (for example, an item’s availability in depots, the number of vehicles available to be shared or the need to refuel them). Each additional criterion complicates optimization and makes it more time-consuming. For the most expanded cases, even graphical processing units (GPUs) are utilized as very efficient co-processors that enable work parallelization.
How Can Genetic Algorithms Optimize Transport in Field Service Management?To optimize transport in field service, the Comarch team adopted for FSM a genetic algorithm (GA) implementation, being a heuristic search inspired by the process of natural selection. A possible solution to the routing problem is modeled as a chromosome, where each gene has a meaning for a given part of the solution (such as a task assigned to a selected technician). Moving through subsequent populations (this is called evolution), using bio-inspired operators such as crossover, mutation or selection, the system is able to explore potential solutions without analyzing all possible combinations. The crossover operator enables the algorithm to drive the evolution in a desired direction, towards the optimal solution. Mutation aids evolution, because it prevents generic algorithm (GA) from becoming stuck on one solution, where the population cannot evolve with the available genetic material (as in real evolution, it’s impossible to breed a blue rabbit if no blue genetic material is available in any rabbit population).
Each solution represented as a chromosome is scored with a fitness function. An expected solution will be close optimal, but the cost will be significantly lower. Of course, it’s also possible that the optimal solution will be the best one. Additionally, it’s much easier to reflect different constraints as a fitness function then to design an algorithm taking all of them into consideration. Adding a new condition or coding a set of them for a new customer requires nothing more than writing simple functions assigning points to all calculated solutions. The more points (or fewer when penalty points are used), the better the solution, which yields the highest probability that it’s chromosome will be used to create new individuals (inheritance). However, adjustment of a standard algorithm can be a challenge. Having so many conditions, it’s easy to break an existing set of rules while adding a new one (regression).