From January 2009 until December 2011, I was a PhD Student in Control System Engineering and Operational Research under the supervision of Prof. Aristide Mingozzi and Prof. Paolo Toth at the Department of Electronics, Computer Science and Systems (DEIS) - University of Bologna - Italy.
From February 2012, I am research fellow at DEIS - University of Bologna under the supervision of Prof. Alberto Caprara.
My research activities involve designing exact algorithms for combinatorial optimization problems, such as traveling salesman problems and routing problems.
Abstract: This paper surveys the most effective mathematical models and exact algorithms proposed for finding the optimal solution of the well known Asymmetric Traveling Salesman Problem (ATSP). The fundamental Integer Linear Programming (ILP) model proposed by Dantzig, Fulkerson and Johnson is first presented, its classical (Assignment, Shortest Spanning r-Arborescence, Linear Programming) relaxations are derived, and the most effective branch-and-bound and branch-and-cut algorithms are described. The polynomial ILP formulations proposed for the ATSP are then presented and analyzed. The considered algorithms and formulations are finally experimentally compared on a set of benchmark instances.
Abstract: The Multi-Trip Vehicle Routing Problem (MTVRP) is a variant of the Capacitated Vehicle Routing Problem (CVRP) where each vehicle can perform a subset of routes, called vehicle schedule, subject to maximum driving time constraints. In spite of its practical importance, the MTVRP has received little attention in the literature. Few heuristics have been proposed, and only an exact algorithm has been presented for a variant of the MTVRP with customer time window constraints and unlimited driving time for each vehicle.We describe two set partitioning-like formulations of the MTVRP. The rst formulation requires the generation of all feasible routes whereas the second formulation is based on the generation of all feasible schedules. We study valid lower bounds, based on the linear relaxations of both formulations enforced with valid inequalities, that are embedded into an exact solution method. The computational results show that the proposed exact algorithm can solve MTVRP instances taken from the literature, with up to 120 customers.
Abstract: This paper provides a review of the recent developments that had a major impact on the current state-of-the-art exact algorithms for the vehicle routing problem (VRP). The paper reviews mathematical formulations, relaxations and recent exact methods for two of the most important variants of the VRP: the Capacitated VRP (CVRP) and the VRP with Time Windows (VRPTW). The paper also reports a comparison of the computational performances of the different exact algorithms for the CVRP and VRPTW.
Abstract: In this paper, we describe an eï¬ective exact method for solving both the Capacitated Vehicle Routing Problem (CVRP) and the Vehicle Routing Problem with Time Windows (VRPTW) that improves the method proposed by Baldacci et al. (2008) for the CVRP. The proposed algorithm is based on the Set Partitioning (SP) formulation of the problem. We introduce a new route relaxation, called ng-route, used by diï¬erent dual ascent heuristics to ï¬］d near-optimal dual solutions of the LP-relaxation of the SP model. We describe a column-and-cut generation algorithm strengthened by valid inequalities that uses a new strategy for solving the pricing problem. The new ng-route relaxation and the diï¬erent dual solutions achieved allow us to generate a reduced SP problem containing all routes of any optimal solution that is ï¬］ally solved by an nteger programming solver. The proposed method solves 4 of the 5 open Solomonâ冱 VRPTW instances and signiſtantly improves the running times of state-of-the-art algorithms for both VRPTW and CVRP.
Abstract: The traveling salesman problem with time windows (TSPTW) is the problem of finding in a weighted digraph a least-cost tour starting from a selected vertex, visiting each vertex of the graph exactly once according to a given time window, and returning to the starting vertex. This NP-hard problem arises in routing and scheduling applications. This paper introduces a new tour relaxation, called ngL-tour, to compute a valid lower bound on the TSPTW obtained as the cost of a near-optimal dual solution of a problem that seeks a minimum-weight convex combination of nonnecessarily elementary tours. This problem is solved by column generation. The optimal integer TSPTW solution is computed with a dynamic programming algorithm that uses bounding functions based on different tour relaxations and the dual solution obtained. An extensive computational analysis on
basically all TSPTW instances (involving up to 233 vertices) from the literature is reported. The results show that the proposed algorithm solves all but one instance and outperforms all exact methods published in the literature so far.
Abstract: This paper presents an exact solution framework for solving some variants of the vehicle routing problem (VRP) that can be modeled as set partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent procedures to ï¬］d a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm attempts to close the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The ï¬］al dual solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring the different bounding procedures to deal with the constraints of the speciſt variant. We describe how this solution framework has been recently used to derive exact algorithms for a broad class of VRPs such as the capacitated VRP, the VRP with time windows, the pickup and delivery problem with time windows, all types of heterogeneous VRP including the multi depot VRP, and the period VRP. The computational results show that the exact algorithmderived for each of these VRP variants outperforms all other exact methods published so far and can solve several test instances that were previously unsolved.
