A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem (2007)
Matteo Fischetti, Andrea Lodi, Paolo Toth
The Vehicle Scheduling Problem is an important combinatorial optimization problem arising in the management of transportation companies. It consists in assigning a set of time-tabled trips to a set...
The symmetric Generalized Travelling Salesman Problem (GTSP) is a variant of the classical symmetric Travelling Salesman Problem, in which the nodes are partitioned into clusters and the salesman has...
Alberto Caprara, David Pisinger, Paolo Toth
The Quadratic Knapsack Problem (QKP) calls for maximizing a quadratic objective function subject to a knapsack constraint, where all coefficients are assumed to be nonnegative and all variables are...
Modeling and Solving the (2007)
Train Timetabling Problem, Alberto Caprara, Matteo Fischetti, Paolo Toth
The Train Timetabling Problem aims at determining a periodic timetable for a set of trains which does not violate track capacities and satises some operational constraints. In particular, we...
We consider a variant of the classical symmetric Travelling Salesman Problem in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. This...
Alberto Caprara, Matteo Fischetti, Paolo Toth, Daniele Vigo, Pier Luigi Guida
Crew management is concerned with building the work schedules of crews needed to cover a planned timetable. This is a well-known problem in Operations Research and has been historically associated...
04. Solution of the Train Platforming Problem (2007)
Caprara, Alberto, Galli, Laura, Toth, Paolo
In this paper we study a general formulation of the train platforming problem, which contains as special cases all the versions previously considered in the literature as well as a case study from...
06. Solving a Real-World Train Unit Assignment Problem (2007)
Cacchiani, Valentina, Caprara, Alberto, Toth, Paolo
We face a real-world train unit assignment problem for an operator running trains in a regional area. Given a set of timetabled train trips, each with a required number of passenger seats, and a set...
Lischke, Andreas, Führer, Bernard, Guida, Pier Luigi, Garavagno, Giampiero, Allegri, Giandomenico, Norde, Henk, ...
Im Abschlussbericht sind die Ergebnisse des Projektes PARTNER sowie die Tests mit dem Demonstartor dargestellt. Es wird ein Übernblick zum Projektauftrag, zum Stand der technischen Entwicklung bei...
An MINLP Solution Method for a Water Network Problem,’’ Algorithms—ESA 2006 (2006)
Christiana Bragalli, Jon Lee, Andrea Lodi, Paolo Toth, Cristiana Bragalli, Jon Lee, ...
LIMITED DISTRIBUTION NOTICE: This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. Ithas been issued as a Research Report for...
Lischke, Andreas, Norde, Henk, Toth, Paolo
The project PARTNER aims to develop an Internet based software demonstrator that provides a common platform for international path allocation for European Infrastructur Managers of railway networks....
Branch and Bound Methods for the Traveling Salesman Problem. (2002)
This paper reviews the state of the art in enumerative solution methods for the traveling salesman problem (TSP). The introduction (Section 1) discusses the main ingredients of branch and bound...
A global method for crew planning in railway applications (2001)
Alberto Caprara, Michele Monaci, Paolo Toth
Abstract. Crew planning is a typical problem arising in the management of large transit systems (such as railway and airline companies). Given a set of train services to be performed every day, the...
Lower Bounds and Algorithms for the 2-Dimensional Vector Packing Problem (2001)
Given n items, each having, say, a weight and a length, and n identical bins with a weight and a length capacity, the 2-Dimensional Vector Packing Problem (2-DVPP) calls for packing all the items...
Solution of real-world train timetabling problems (2001)
Alberto Caprara, Michele Monaci, Paolo Toth, Matteo Fischetti, Pier Luigi Guida
The Train Timetabling Problem (TTP) aims at determining a timetable for a set of trains which does not violate track capacities and satises some operational constraints. We concentrate on the problem...
Lower Bounds and Algorithms for the 2-Dimensional Vector Packing Problem (2001)
Given n items, each having, say, a weight and a length, and n identical bins with a weight and a length capacity, the 2-Dimensional Vector Packing Problem (2-DVPP) calls for packing all the items...
Exact solution of the quadratic knapsack problem (1999)
Alberto Caprara, David Pisinger, Paolo Toth
The Quadratic Knapsack Problem (QKP) calls for maximizing a quadratic objective function subject to a knapsack constraint, where all coefficients are assumed to be nonnegative and all variables are...
Solution of large-scale railway crew planning problems: the italian experience (1999)
Alberto Caprara, Matteo Fischetti, Pier Luigi Guida, Paolo Toth, Daniele Vigo
Crew scheduling is a very well known problem which has been historically associated with airlines and mass transit companies; recently also railway applications have come on the scene. This now...
A heuristic method for the set covering problem (1999)
Alberto Caprara, Matteo Fischetti, Paolo Toth
We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The algorithm was initially designed for solving very large scale SCP instances, involving up to 5,000 rows and...
A Parallel Shortest Augmenting Path Algorithm for the Assignment Problem. (1998)
Balas, Egon, Miller, Donald, Pekny, Joseph, Toth, Paolo
We describe a parallel version of the shortest augmenting path algorithm for the assignment problem. While generating the initial dual solution and partial assignment in parallel does not require...
Solving the orienteering problem through branch-and-cut (1998)
In the Orienteering Problem (OP) we are given an undirected graph with edge weights and node prizes. The problem calls for a simple cycle whose total edge weight does not exceed a given threshold,...
Universit`a degli Studi di Bologna (1998)
Dipartimento Di Elettronica, Alberto Caprara, Alberto Caprara, Matteo Fischetti, Matteo Fischetti, Paolo Toth, ...
The Crew Rostering Problem (CRP) aims at determining an optimal sequencing of a given set of duties into rosters satisfying operational constraints deriving from union contract and company...
Solution of Large-Scale Railway Crew Planning Problems: the Italian Experience (1997)
Alberto Caprara, Matteo Fischetti, Pier Luigi Guida, Paolo Toth, Daniele Vigo
Crew scheduling is a very well known problem which has been historically associated with airlines and mass transit companies; recently also railway applications have come on the scene. This now...
Algorithms for the set covering problem (1996)
Alberto Caprara, Matteo Fischetti, Paolo Toth
The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most...
Vehicle routing problems deal with the optimal use of a eet of vehicles to transport (pick up or deliver) goods between a central depot and a set of clients. Several interesting examples arise in...
A Heuristic Method for the Set Covering Problem (1995)
Alberto Caprara, Matteo Fischetti, Paolo Toth
We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The algorithm was initially designed for solving very large scale SCP instances, involving up to 5,000 rows and...
Modeling and Solving the Crew Rostering Problem (1995)
Alberto Caprara, Alberto Caprara, Matteo Fischetti, Matteo Fischetti, Paolo Toth, Paolo Toth, ...
The Crew Rostering Problem (CRP) aims at determining an optimal sequencing of a given set of duties into rosters satisfying operational constraints deriving from union contract and company...
An evolutionary approach for bandwidth multicoloring problems
In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be...