Field Service Optimization of Transport with Genetic Algorithms

Optimal transportation scheduling remains a big concern in industries such as manufacturing, supply or services. In most field service management scenarios, moving people, devices and tools from one service point to another requires the use of vehicles. An obvious challenge is to find optimal routes between locations in order to save time, reduce fuel consumption, handle more customers and collect items from different warehouses. This conundrum has been known for years, and is called the vehicle routing problem (VRP). This is one of the most frequently analyzed optimization issues. It generalizes the well-known travelling salesman problem (TSP), and its essence is to find a set of routes (possibly, but not necessarily, the shortest) between a set of locations for a group of vehicles.

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).

The Benefits of Field Service Optimization in Transport

Performance tests and previous implementations in the area of field service optimization have demonstrated that this approach scales much better than the standard algorithmic approach. Additionally, can be easily adopted for installations with thousands of employees and work that needs to be planned and distributed in a short time but is loaded in bulk. It gives certainty for Comarch’s customers that all work will be properly distributed with respect to all restrictions, regulations and time constraints. Automated work dispatching relieves back-office employees from the burden of repeating tedious daily tasks. Thanks to the genetic algorithm, fewer dispatchers can better support more technicians on tasks requiring human interaction, or in unusual cases that cannot be handled by the system on its own Probably the most important conclusion is that GA can easily analyze an enormous number of conditions (legal, contractual, physical, etc.) and optimize field service scheduling. With field service management software for transportation of workers in various respects, tailored for each customer, you can provide services faster with the great quality.