Advanced optimization for real operational constraints.

The vehicle routing problem (VRP)

The vehicle routing problem asks how a fleet leaving one or more depots should visit scattered customers at the lowest total cost. It was introduced in 1959 by Dantzig and Ramser as the “truck dispatching problem” and has been the subject of a large literature since.

Capacity and time windows: CVRP and VRPTW

In the capacitated variant (CVRP) each vehicle can carry a limited load. In the time-window variant (VRPTW) each stop can be visited only within certain hours. In practice both constraints occur together.

• CVRP. The total load on a route cannot exceed the vehicle’s capacity.

• VRPTW. A vehicle reaches a stop inside its window; arriving early means waiting, arriving late is invalid or penalized depending on the rule.

Constraints Trackinia models

These are the constraints the product takes into account today. The list does not cover every rule an operation might have.

• Time windows. One or more intervals per task, defined as required (hard) or preferred (soft).

• Vehicle capacity. Capacity limits for weight, volume and count; capacity is enforced as required.

• Service duration. The time spent at each stop is added to the route timing.

• Drivers and vehicles. Driver working hours, breaks and date exceptions; vehicle shifts; matching driver skills and vehicle features.

• Depot structure. Multiple depots, vehicles with different characteristics and open routes that do not return to the depot.

Objective and cost

Optimization currently aims to minimize cost. Cost is made of items such as distance, time and vehicle use, and the result shows them item by item. Additional objectives such as balanced workload distribution are not supported today.

Why is it hard?

VRP is a combinatorial problem: the number of possible route combinations grows very fast as stops are added. For realistic sizes, proving that a solution is the best one is often impractical.

In practice, heuristic and metaheuristic methods are used that find good solutions in reasonable time. They can produce high-quality plans but do not guarantee that a solution is the best possible.

Evaluating the result operationally

Whether a plan is good is not measured by total distance alone. Trackinia shows the outcome status (optimal, feasible, feasible within the time limit, infeasible) and lists unplanned tasks with their reasons.

The planner reviews the result, changes constraints if needed and recalculates. If something changes during operations, the plan can be replanned.