Glossario IA
Il dizionario completo dell'Intelligenza Artificiale
Vehicle Routing Problem (VRP)
A generalization of the TSP that consists of designing a set of optimal routes for a fleet of vehicles to serve a set of customers, often under capacity and time constraints.
Nearest Neighbor Heuristic
A greedy algorithm that builds a solution to the TSP by starting from a city and systematically visiting the closest unvisited city until all cities have been visited.
Clarke and Wright Algorithm
A construction heuristic for the VRP that iteratively merges initial routes in order to minimize the total distance, based on the distance savings achieved by merging two routes.
Simulated Annealing
A metaheuristic inspired by the metal cooling process, which accepts worse solutions with a decreasing probability to escape local minima and converge toward a near-optimal solution.
Ant Colony Optimization (ACO)
A metaheuristic inspired by the behavior of ants that use pheromones to mark paths, allowing the algorithm to gradually discover the shortest routes in a graph.
Branch and Cut
An exact combinatorial optimization method that combines implicit enumeration (Branch and Bound) with cutting plane techniques to tighten the linear relaxation of the problem and accelerate resolution.
Time Window
A constraint in the VRP that specifies a time interval during which a customer must be served, adding temporal complexity to the optimization of logistics routes.
VRP with Time Windows (VRPTW)
A variant of the VRP where each customer has a service time window, making the problem much more complex as it requires optimizing both distance and compliance with temporal constraints.
Insertion Heuristic
A family of heuristics for the VRP that builds a solution by progressively inserting customers into existing routes while minimizing the increase in total cost, often using criteria such as marginal insertion cost.
Linear Relaxation
A technique used in exact methods where the integrality constraints of a combinatorial optimization problem are relaxed to obtain a lower bound on the optimal value of the objective function.
2-opt
A local search operator for the TSP that improves a solution by swapping two edges to break and reconnect the tour, eliminating crossings and reducing the total path length.
Or-opt
An improvement of 2-opt that moves a chain of one, two, or three customers to another position in the tour, offering greater flexibility for improving routing solutions.
Periodic Vehicle Routing Problem (PVRP)
An extension of the VRP where planning is performed over a multi-day time horizon, with some customers requiring visits at specific frequencies (e.g., once per week).
Cost Matrix
A fundamental data structure that stores the costs (distance, time, etc.) between every pair of points in a routing problem, serving as the basis for optimization calculations.