Seminario Dottorato: “Exact and Meta-Heuristic Approach for Vehicle Routing Problems”

Wednesday 3 October 2018, h. 16:00 - Room 1BC50 - Nicola Gastaldon

ARGOMENTI: Seminars Ph.D. Program

Our first seminar of 2018/2019 will be held as a special event inside the Opening Day of the Doctoral School (15:00, 1BC50).

Wednesday 3 October 2018 h. 16:00, Room 1BC50
Nicola Gastaldon (Padova, Dip. Mat. and Trans-Cel s.n.c., Albignasego, PD)
“Exact and Meta-Heuristic Approach for Vehicle Routing Problems”

The Vehicle Routing Problem (VRP) includes a wide class of problems studied in Operations Research and relevant from both theoretical and practical perspectives. In its basic formulation, the problem is to find a set of routes for a given fleet of vehicles through a set of locations, so that each location is visited by exactly one vehicle and the total travel cost is minimized. Such problem is often enriched with many attributes rising from real-world applications, such as capacity constraints, pickup and delivery operations, time windows, etc. VRP belongs to the class of combinatorial optimization problems, and it is very hard to solve efficiently and researchers have developed many exact and (meta-)heuristic algorithms. The former takes advantage of the structure of the mathematical model to obtain a speedup through decomposition methods. The latter exploits heuristic techniques to obtain solutions that trade off quality and computational burden, such as evolutionary algorithms and neighborhood search routines.
In our research, we consider the VRP arising at Trans-Cel, a freight transportation company based in Padova. We devised a Tabu Search heuristic implementing different neighborhood search policies, and now embedded in the tool supporting the operation manager at Trans-Cel. The algorithm runs in an acceptable amount of time both in static and dynamic settings, and the quality of the solutions is assessed through comparison with results obtained by a Column Generation algorithm that solves a mathematical programming formulation of the problem. Current research aims at developing data-driven techniques that exploit the information available from the company's repositories to support stochastic transportation demand arising in real time.

Download Seminario Dottorato