Route optimization is one of the basic components of transport optimization. Route optimization consists of constructing such routes for vehicles carrying goods that optimize profits and customer service. From the perspective of a company, this usually means minimizing costs and time of transport, and from the perspective of customers – reducing costs and improving the punctuality of deliveries. These objectives are achieved by reducing the number of miles traveled, the ability to adapt to conditions changing in time and new circumstances, the synchronization of transport and the work of warehouses, and the possibility of frequent and quick performance of optimization in order to update the current plan.
From the computer science point of view, optimizing routes in transport and logistics has much in common with the Traveling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP). The TSP problem is a classic combinatorial optimization problem to schedule the shortest (generally the cheapest) cyclical path running through n given points, given the cost of traveling between each pair of points. The VRP problem is a generalization of TSP – there may be many salesmen (many trucks) that can return to the base multiple times before all n locations are visited. Both problems (TSP and VRP) have a lot of generalizations and additional practical limitations, such as restrictions regarding the ordering of visited locations, time windows, various abilities and skills of trucks and drivers, or capacities useful when collecting or delivering products. The VRP problem was described as early as 1959 in this article.
Both problems (TSP and VRP) are NP-hard, which in practice means that for large instances (i.e. with many locations), on traditional computers one will never be able to discover the strictly optimal, best solution within an acceptable period of time. This is why approximate methods (heuristics and metaheuristics) are used which produce good or very good solutions in a reasonable time. Both problems are naturally multi-criteria – time, cost, quality, comfort, safety, and many other factors are optimized.