Evaluation functions and penalties in genetic algorithms applied to route optimisation

In a genetic algorithm, it is not enough to generate many possible solutions. It is also necessary to know how to compare one solution with another.

This is done using an evaluation function, also known as a fitness function. This function measures the quality of each individual in the population and determines which solutions are more likely to survive, reproduce and pass their characteristics on to subsequent generations.

In the context of route optimisation, the evaluation function is one of the most important elements of the system. Its design determines what the algorithm understands to be a good plan.

A solution may appear good because it reduces mileage, yet be infeasible because it breaches schedules. Another may meet every time window but use too many vehicles. A third may be inexpensive in terms of distance but produce unbalanced or excessively long working days for certain drivers.

For this reason, in real logistics problems, the evaluation function must be able to integrate many different criteria.

What is an evaluation function?

The evaluation function is the mechanism that assigns a score to each candidate solution.

In a routing problem, a solution may consist of the set of vehicles used, the orders assigned to each one and the sequence in which the different locations are visited.

The evaluation function analyses that solution and calculates its quality according to the objectives of the problem.

These objectives may include:

• Reducing total distance travelled.
• Reducing total driving time.
• Minimising operating cost.
• Using as few vehicles as possible.
• Meeting customer time windows.
• Avoiding delays.
• Using vehicle capacity correctly.
• Balancing workloads across routes.
• Reducing idle time.
• Avoiding unassigned orders.

The difficulty is that these criteria do not always point in the same direction.

For example, reducing the number of vehicles may make some routes longer. Minimising mileage may lead to missed time windows. Balancing work more evenly between vehicles may slightly increase total cost but improve operational feasibility.

The evaluation function must therefore represent the real priorities of the business correctly.

Evaluation is not only about measuring distance

A common mistake when addressing route optimisation is to assume that the main objective is simply to travel fewer miles.

Although distance is an important factor, it is rarely sufficient to define the quality of a logistics plan.

In a real operation, a route must be executable. It must respect schedules, capacities, service times, access restrictions, breaks, labour costs and the specific limitations of each vehicle or driver.

A very short route may be useless if it reaches an important customer late. An apparently inexpensive route may be unacceptable if it requires the maximum working day to be exceeded. A solution using few vehicles may be infeasible if it causes overloads or breaches.

For this reason, the evaluation function must go beyond calculating distance. It must assess the solution from an operational perspective.

Common route evaluation criteria

The evaluation function can be built by combining different components.

One of the most common criteria is total distance travelled. Reducing mileage usually means lower fuel consumption, less vehicle wear and lower operating cost.

Another important criterion is total working time. In many companies, cost depends not only on mileage but also on the hours spent by drivers and vehicles.

The number of vehicles used can also be considered. In some scenarios, removing one vehicle can produce a very significant saving even if total distance increases slightly.

Time windows are another critical element. Many customers can receive goods only within specific periods. Missing these windows may cause waiting, rejection, penalties or poorer service quality.

Vehicle capacity must also form part of the evaluation. A solution that assigns more load than a vehicle can carry cannot be considered valid, even if it is efficient in terms of distance.

There may also be specific constraints: incompatible products, vehicles with special requirements, restricted-access areas, loading schedules, particular drivers, departure and return depots, mandatory breaks or commercial priorities.

All these factors must be reflected in some way in the final score assigned to each solution.

Penalties

In genetic algorithms applied to routing, penalties make it possible to handle solutions that breach a condition of the problem.

A penalty is an additional cost added to a solution when it contains a violation.

For example, if a route reaches a customer late, a penalty proportional to the delay can be added. If a vehicle exceeds its capacity, a penalty can be added for excess load. If an order remains unassigned, the penalty may be very high to indicate that the solution is highly undesirable.

Penalties allow the algorithm to avoid necessarily discarding every imperfect solution from the outset.

This matters because, during the evolutionary process, some initially poor solutions may contain useful components. An individual may breach a constraint but still contain a good visit sequence or an interesting assignment of particular orders.

If the algorithm immediately eliminated every solution with a small violation, it could lose valuable genetic material for future generations.

Penalties make it possible to grade the seriousness of errors and guide the search towards progressively better solutions.

Hard and soft penalties

Not all constraints have the same importance.

Some constraints are absolutely mandatory. For example, a vehicle cannot carry goods for which it is not authorised, nor can it exceed a legal working-time limit. These are generally treated as hard constraints.

Other constraints may be preferable but not necessarily invalidating. For example, it may be desirable to balance workloads between vehicles, reduce waiting or avoid small deviations from a preferred time. These are generally treated as soft constraints.

Hard constraints require very high penalties or repair mechanisms that prevent the final solution from breaching them.

Soft constraints, by contrast, can influence solution quality without invalidating it completely.

This balance is fundamental. If every constraint is treated as absolute, the algorithm may struggle to find feasible solutions. If every constraint is treated as flexible, the result may appear operational but prove of little practical use.

Weighting each criterion

One of the most delicate decisions when designing an evaluation function is determining the weight of each criterion.

Not every company has the same priorities. For one business, minimising the number of vehicles may be essential. For another, strict compliance with delivery times may be the most important factor. In other cases, balancing routes to avoid excessively long working days may be the priority.

The evaluation function must reflect these priorities.

For example, a simple function might combine distance, time and penalties as follows:

Total cost = mileage cost + time cost + penalties

In real problems, however, this formula can be extended considerably. Fixed vehicle costs, variable costs, delay penalties, capacity-excess penalties, penalties for unassigned orders or bonuses for meeting certain objectives can all be added.

Designing these weights is not trivial. If a penalty is too low, the algorithm may accept solutions that breach important constraints. If it is too high, it may block exploration and cause the algorithm to concentrate too early on a limited region of the search space.

Feasible solutions and high-quality solutions

In route optimisation, it is important to distinguish between a feasible solution and a high-quality solution.

A feasible solution is one that meets the minimum constraints of the problem.

A high-quality solution not only is feasible but also optimises the defined objectives: it reduces costs, improves timings, uses resources effectively and produces routes that can be executed efficiently.

The genetic algorithm must progress in two directions at the same time.

On the one hand, it must move towards feasibility by reducing violations and eliminating unworkable solutions.

On the other, it must improve the quality of feasible solutions by seeking increasingly efficient plans.

Penalties are particularly helpful for the first objective. Cost and optimisation criteria are especially important for the second.

The role of the evaluation function in selection

The evaluation function does more than measure the quality of a solution. It also directly influences which individuals are selected to participate in the next generation.

Better-scoring individuals are more likely to be selected for crossover and to generate offspring.

This means that the evaluation function acts like the environment in biological evolution. It defines which individuals are better adapted and which are less likely to survive.

If the evaluation function is poorly designed, the algorithm will evolve in the wrong direction.

For example, if reducing mileage is valued too highly and schedule compliance too little, the system will tend to generate short but unrealistic routes. If every deviation is penalised excessively, the algorithm may become too conservative and lose its ability to explore.

The quality of the evaluation determines the quality of the evolution.

Multi-criteria evaluation

Many route optimisation problems are multi-criteria problems.

This means that there is not a single objective, but several objectives that must be balanced.

Some of these objectives may conflict with one another.

• Reducing mileage may conflict with reducing time.
• Reducing the number of vehicles may conflict with meeting schedules.
• Balancing routes may conflict with minimising total cost.
• Maximising vehicle utilisation may conflict with preserving operational flexibility.

In these cases, the evaluation function must transform all these objectives into a comparable score.

A common approach is to combine the different criteria using weights. Another possibility is to use a hierarchy of objectives, giving absolute priority to some criteria over others.

Approaches can also be used in which the algorithm does not seek one single optimum, but a set of alternative solutions offering different balances between cost, time and service quality.

In real environments, this view is particularly useful because the mathematically best solution is not always the best operational decision.

Dynamic penalties

In some cases, penalties can vary during the execution of the algorithm.

At the beginning of the evolutionary process, it may be useful to allow a certain degree of violation in order to explore broad areas of the search space. As generations progress, penalties can become stricter to force convergence towards feasible solutions.

This approach makes it possible to combine exploration and refinement.

During the first generations, the algorithm can experiment with diverse assignments and sequences. In the final stages, greater importance is placed on strict compliance with constraints.

Dynamic penalties are particularly interesting in complex problems where finding feasible solutions from the outset may be difficult.

Repairing solutions

Penalties are not the only way to deal with violations.

Another strategy is to repair solutions before or after evaluating them.

For example, if an order appears twice on two routes, it can be removed from one of them. If an order remains unassigned, an attempt can be made to insert it into the most suitable route. If a vehicle exceeds capacity, some orders can be moved to other vehicles.

These repair mechanisms can improve algorithm efficiency by reducing the number of clearly invalid solutions.

However, they must also be designed carefully. Overly aggressive repair may alter the original solution too much and reduce genetic diversity. Repair that is too weak may fail to correct the relevant problems.

In practice, penalties and repair mechanisms are often used together.

The importance of fast evaluation

A genetic algorithm evaluates many solutions over many generations.

For this reason, the evaluation function must be accurate but also efficient.

If evaluating one solution is too slow, the entire algorithm becomes impractical. This is particularly important in routing problems involving many orders and vehicles, where each individual may represent a complex plan.

Evaluation efficiency depends on many factors: how distances are calculated, how time windows are checked, how service times are accumulated, how violations are detected and how costs are updated when a route changes.

A good implementation should avoid recalculating from scratch everything that has not changed. In many cases, small local changes to a route can be evaluated incrementally.

This efficiency makes it possible to explore more solutions in less time and improve the final quality of the optimisation.

Evaluation functions and operational reality

The evaluation function must represent the reality of the logistics operation.

This means that it should not be limited to a simplified theoretical model, but should incorporate the conditions that genuinely affect day-to-day planning.

For example, it may be necessary to consider loading and unloading times, warehouse schedules, traffic restrictions, priority customers, geographical areas, breaks, different costs by vehicle or specific conditions attached to certain orders.

The more accurately the evaluation function reflects operational reality, the more useful the solutions generated by the algorithm will be.

By contrast, if the evaluation function ignores important elements, the system may find solutions that appear optimal but are difficult or impossible to execute.

Conclusion

The evaluation function is the criterion that guides the evolution of a genetic algorithm.

In route optimisation, this function must assess many aspects at the same time: distance, time, cost, vehicles used, time windows, capacity, route balance and compliance with constraints.

Penalties make it possible to incorporate violations and constraints into the evolutionary process, guiding the algorithm towards feasible, higher-quality solutions.

Designing this function correctly is as important as defining the representation of solutions or the genetic operators. A good evaluation function enables the algorithm to find not only shorter routes, but logistics plans that are genuinely useful, feasible and adapted to the needs of each operation.

Evolution Algorithms' accumulated experience enables the LOGISPLAN optimisation engine to apply these evaluation criteria to real, complex logistics problems with multiple operational constraints.