The current main research interests of Roberto
Baldacci include Operational Research and
Mathematical
Programming methodologies and, in particular, the design of
effective algorithms for Combinatorial
Optimization and Graph Theory problems,
and their application to real-world Transportation, Routing and Location problems. His research has been
mainly devoted to the study of new general techniques for
enumerative methods, and to the definition and evaluation of new
algorithms and software implementations for the exact and
approximate solution of the following problems:
-
Travelling
Salesman with additional constraints;
-
Vehicle Routing
and Scheduling;
-
Car
Pooling;
-
Location;
-
Vehicle Routing
Applications;
-
Telecommunication Network
Design;
-
Packing;
-
Portfolio
management;
-
Arc
Routing.
The main research interests include Operational Research and
Mathematical
Programming methodologies and, in particular, the design of
effective algorithms for Combinatorial
Optimization and Graph Theory problems,
and their application to real-world Transportation, Routing and Location problems. His research has been
mainly devoted to the study of new general techniques for
enumerative methods, and to the definition and evaluation of new
algorithms and software implementations for the exact and
approximate solution of the following problems:
Vehicle Routing
The Capacitated Vehicle Routing
Problem (CVRP) is the problem of designing the routes for a set of
vehicles stationed at a central depot in order to serve a set of
customers minimizing the transportation costs and such that a
constraint on the capacity of each vehicle is satisfied.
The CVRP is one of the most
studied problems in combinatorial optimisation. However, the exact
algorithms proposed in the literature are able to solve problems of
small dimension only. Moreover, the single constraint on the
vehicle capacity represents, with wide approximation only, the real
problems characterized by several and difficult constraints that
make the VRP one of the most difficult problems among combinatorial
optimisation problems. The purpose of the research on the VRP is to
develop new mathematical methodologies in order to design new exact
and heuristic solution algorithms that are able to handle real
constraints.
Car Pooling
Car pooling is a transportation
service organized by a large company which encourages its employees
to pick up colleagues while driving to/from work in order to
minimize the number of private cars travelling to/from the company
site. The benefits which can be obtained are particularly relevant
both in terms of reduction of the use of private cars and of the
parking space required. The Car Pooling Problem (CPP) consists in
defining the subsets of employees that will share each car and the
paths the drivers should follow, so that sharing is maximized and
the sum of the path costs is minimized. The purpose of the research
on the CPP is to develop new mathematical methodologies in order to
design new exact and heuristic solution algorithms that are able to
handle real constraints.
Telecommunication Network
Design
Telecommunications represent one
of the technological area that has had major development during
last years and that is subject to changes and huge investments.
During this last years Operations Research has developed
optimisation and simulation methods on graphs that can be
effectively used to solve real problems in this area. In
particular, the frame of this research is the one of wide-band
telecommunication network, on cable or wireless. The design of such
network is a complex task and is generally subject to a number of
complex constraints of different type, such as, geographical,
technological, organizational, etc. The direct consequence of this
fact is that the design of telecommunication network is generally
tackled in successive phases.
Packing problems
Packing problems find many
practical applications in many real world problems, e.g. container
and pallet loading. In the Two-Dimensional Bin Packing Problems
(2DBPP), Two-Dimensional Strip Packing Problem (2DSPP), and
Two-Dimensional Knapsack Problem (2DKP), items are rectangles to be
packed with the height parallel to the height of the bins. Bins are
finite rectangles in the case of 2DBPP and 2DKP, while in 2DSPP one
is given a unique rectangular bin having finite width and infinite
height. In 2DBPP one has to pack all the items by minimizing the
number of used bins, while in 2DSPP one has to pack all the items
in the unique rectangle, by minimizing the overall height of the
packing; finally, in 2DKP the aim is to pack a maximum-profit
subset of items fit into a unique (finite) bin. Many practical
applications are characterized by the additional constraint
requiring that items are packed in shelves ("shelf packing").
Moreover, even when not explicitly required by the operational
constraints, such a requirement widely simplifies the solution
process. Concerning packing problems, the research propose to
develop exact and heuristic algorithms for their
solution.
Portfolio
optimization
Each of the larger fund management
companies in the U.E. and the U.S.A. are responsible for the
investment of several billion Euro and Dollars. This money is
invested on behalf of pension funds, mutual funds and other
institutions. The selection of an appropriate portfolio of assets
in which to invest is an essential component of fund management.
Although, a large proportion of portfolio selection decisions are
taken on a qualitative basis, quantitative approaches to selection
are becoming more widely adopted. In this context, a relevant
financial problem is the periodical rebalance of a portfolio of
assets, such that the portfolio's total value exhibits certain
characteristics. For performing a periodical rebalance following a
quantitative approach, it is necessary to have a model which
represents the future state space evolution of the corresponding
economy and where the asset values are some given function of a
particular state. Since the size of the problem can be very large
even for simple financial model (for a practical problems it is
easy to have more than one million variables and constraints), the
objective is to device different algorithms based on decomposition
methods (i.e. Lagrangean relaxation, Dantzig-Wolfe decomposition
and Benders' decomposition).
