Representing solutions in genetic algorithms for route optimisation

One of the most important aspects of applying genetic algorithms to route optimisation problems is how each possible solution is represented.

In a genetic algorithm, every individual in the population represents a candidate solution to the problem. In simple problems, this representation can be relatively straightforward. In real distribution, transport and logistics-planning problems, however, representing a solution can become highly complex.

A route is not simply a list of points to visit. A real logistics scenario involves vehicles, orders, schedules, capacities, access restrictions, service times, priorities, breaks, costs, distances, driving times and multiple operational conditions that must be respected.

For this reason, one of the keys to a successful genetic algorithm for route optimisation is designing an appropriate representation for each solution.

The chromosome as a logistics solution

In genetic algorithms, the structure that encodes a solution is usually called a chromosome.

In route optimisation, a chromosome can represent, for example, the assignment of orders to vehicles and the order in which each vehicle must make its deliveries or visits.

A possible simplified representation is as follows:

• Vehicle 1: Order 4, Order 8, Order 2
• Vehicle 2: Order 1, Order 6
• Vehicle 3: Order 7, Order 3, Order 5

This structure contains two fundamental types of information:

• First, it indicates which orders each vehicle handles.
• Second, it indicates the order in which those orders are completed within each route.

Both aspects are critical. It is not enough to know which vehicle serves each order. The visit order can completely change the planning outcome because it affects kilometres travelled, total working time, schedule compliance and the final operating cost.

The difficulty of representing real routes

In simple academic problems, such as the classic travelling salesperson problem, the solution usually consists of a single sequence of visits. The aim is to find the order that minimises total distance travelled.

Real logistics planning, however, is usually far more complex.

There is normally not one vehicle but an entire fleet. Each vehicle may have different characteristics: capacity, departure and arrival times, cost per kilometre, cost per hour, loading restrictions or specific compatibility rules.

Orders are not all alike either. Some may have time windows, different service times, special priority, incompatibilities, a need for a specific vehicle or geographical restrictions.

This makes solution representation decisive. An overly simple encoding may be unable to express all the problem constraints correctly. An overly complex encoding, by contrast, can make crossover, mutation and evaluation more difficult.

The balance between expressiveness and efficiency is one of the most important technical decisions in designing this kind of algorithm.

Valid and invalid solutions

In route optimisation, not every possible combination of orders and vehicles is a valid solution.

• A vehicle may exceed its maximum capacity.
• A delivery may be made outside its time window.
• A route may exceed the permitted maximum working time.
• An order may remain unassigned.
• The same order could appear twice in two different routes if the encoding is not properly controlled.

These cases show that the algorithm must seek not only good solutions, but also feasible ones.

For this reason, chromosome representation should be designed to minimise invalid solutions or, at least, make them easy to detect and correct efficiently.

There are several strategies for addressing this issue.

One option is to allow invalid solutions but penalise them heavily in the evaluation function. This naturally drives the algorithm to discard them during the evolutionary process.

Another option is to apply repair mechanisms. When a mutation or crossover produces an incorrect solution, additional procedures are run to correct it before evaluation.

It is also possible to design an encoding that directly prevents certain errors, although this is not always easy when there are many constraints.

Assignment and sequencing

Route optimisation involves two main decisions that must be made at the same time.

The first is assignment: deciding which vehicle handles each order.

The second is sequencing: deciding the order in which orders are completed within each vehicle.

These two decisions are closely related.

An order may appear suitable for a vehicle when analysed in isolation, but cease to be suitable once the other orders assigned to the same route are considered. Likewise, a route may be distance-efficient but breach a time window if the visit order is unsuitable.

This interdependence means that traditional methods based on sequential decisions can struggle to find good solutions for large real-world problems.

Genetic algorithms, by contrast, can work with complete solutions. Each individual represents an overall plan, and evolution acts on the whole solution rather than on isolated decisions alone.

Diversity in the initial population

How the initial population is generated is also very important.

If all initial individuals are too similar, the algorithm may quickly converge on a particular area of the search space and become trapped in low-quality solutions. This is known as premature convergence.

To avoid this, the initial population should contain diverse solutions.

Some solutions can be generated randomly. Others can be built using simple heuristics, for example by assigning orders to the nearest vehicle, grouping by geographical area or prioritising the most restrictive time windows.

Combining random and heuristic solutions is often effective. Heuristic solutions provide a reasonable starting point, while random solutions introduce diversity and make it possible to explore different regions of the search space.

Genetic operators adapted to the problem

Once the solution representation has been defined, genetic operators must be adapted to it.

In a routing problem, crossover and mutation cannot be applied indiscriminately. Exchanging chromosome fragments without control can produce duplicate orders, missing orders or impossible routes.

For example, a crossover operator may exchange route segments between two parent solutions. Afterwards, however, it is necessary to check that each order appears only once and that the main constraints remain reasonable.

Mutation must also be designed carefully. Common mutations in routing problems include:

• Changing the order of two orders within the same route.
• Moving an order from one vehicle to another.
• Swapping orders between two vehicles.
• Reversing a section of a route.
• Reinserting an order in a different position.

These operations may seem simple, but they have a major impact on solution quality. A small change to a route order can reduce kilometres, correct a delay or free capacity on another vehicle.

Evaluating a solution

Chromosome representation is directly related to the evaluation function.

Once a solution has been built, the system must calculate its quality. Multiple factors can be considered:

• Total distance travelled.
• Total working time.
• Cost per vehicle.
• Number of vehicles used.
• Compliance with time windows.
• Vehicle utilisation level.
• Delays or breaches.
• Balance between routes.
• Unassigned orders.

In real problems, the evaluation function does not usually depend on a single criterion. The best solution is not always the one that travels the fewest kilometres. Sometimes it is preferable to travel a few more kilometres if this reduces the number of vehicles, improves customer schedule compliance or produces a more balanced plan.

Genetic algorithms can therefore work with complex evaluation functions that combine different objectives and penalties.

The practical importance of good representation

A good solution representation helps the algorithm evolve effectively.

If the encoding is appropriate, crossover and mutation tend to generate useful solutions. If the encoding is poor, the algorithm may spend too much effort generating and correcting invalid solutions.

In practice, the performance of a genetic algorithm does not depend solely on available computing power. It also depends on how the problem is modelled, how solutions are represented and how the operators that act on them are designed.

This is especially important in logistics optimisation, where each company may have different business rules. Two problems may look similar from the outside but require different representations because of how vehicles, orders, schedules or operational constraints are managed.

Applying it to route optimisation

In route optimisation, representing a solution correctly means capturing the operational reality of the business.

It is not only about calculating shorter paths. It is about building delivery or transport plans that can be executed in practice while respecting real business conditions.

Genetic algorithms are particularly well suited to this type of problem because they can work with rich, flexible solution structures. They can combine assignments, sequences, constraints and objectives within a single evolutionary process.

This capability makes it possible to tackle problems that would be very difficult to solve with rigid traditional methods or methods that depend excessively on a simplified mathematical formulation.

Conclusion

Solution representation is one of the fundamental elements in applying genetic algorithms to route optimisation.

A well-designed chromosome clearly describes which orders each vehicle handles, the order in which they are visited, which constraints are met and the cost of the resulting plan.

The better this representation fits the reality of the problem, the greater the algorithm?s ability to find efficient, feasible and applicable solutions in real environments.

Ultimately, before evolving solutions, it is necessary to know how to represent them. In complex logistics problems, that representation is an essential part of the system?s intelligence.

Evolution Algorithms? accumulated experience enables the LOGISPLAN optimisation engine to adapt solution representation to real, complex logistics problems with multiple operational constraints.