Paolo Toth
Paolo Toth has a total of 47 co-authors. Here are the top co-authors by number of shared publications:
- Valentina Cacchiani
University of Bologna
10 shared publications - Roberto Roberti
University of Padova
3 shared publications - Alan Osorio-Mora
Chair of Logistics, School of Business and Economics RPTU Kaiserslautern‐Landau Kaiserslautern Germany
2 shared publications Alberto Caprara
Department of Electrical and Information Engineering “Guglielmo Marconi” (DEI), University of Bologna, I-40136 Bologna, Italy
2 shared publications- Alberto Caprara
DEIS, University of Bologna
2 shared publications - Andrea Bettinelli
OPTIT Srl
2 shared publications
Latest Publications
- Open Access
- 26 December 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 326 (1) , 1-12
The quadratic knapsack problem
- 26 December 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 326 (1) , 1-12
Open AccessThe quadratic knapsack problem
- Open Access
- 5 November 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 321 (3) , 837-850
A risk-averse latency location-routing problem with stochastic travel times
- 5 November 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 321 (3) , 837-850
Open AccessA risk-averse latency location-routing problem with stochastic travel times
- Open Access
- 21 October 2024
- Published by Elsevier in Computers & Operations Research
- Vol. 173
The quadratic knapsack problem with setup
- 21 October 2024
- Published by Elsevier in Computers & Operations Research
- Vol. 173
Open AccessThe quadratic knapsack problem with setup
- Open Access
- 11 April 2023
- Published by Wiley in International Transactions in Operational Research
- Vol. 30 (6) , 3801-3832
Effective metaheuristics for the latency location routing problem
The latency location routing problem (LLRP), a combination of the facility location problem and the cumulative capacitated vehicle routing problem, is a recently proposed variant of location routing problems. It corresponds to a customer‐centric problem, in which the aim is to minimize the sum of the arrival times at the customers. This paper proposes three novel metaheuristic algorithms to solve the LLRP. They use a simulated annealing framework, which after each temperature reduction is intensified through a variable neighborhood descent procedure. Each algorithm uses a different search strategy as intensification. Results on 76 benchmark instances indicate that the proposed metaheurstics outperform the state‐of‐the‐art algorithms, finding new best solutions for all the large‐sized instances (over 100 customers), or the currently known optimal ones for most of the small‐ and medium‐sized instances, in comparable computing times. Furthermore, in more than 80% of the instances the average value of the solutions found by the proposed algorithms is better than or equal to that of the current best known solution.
- 11 April 2023
- Published by Wiley in International Transactions in Operational Research
- Vol. 30 (6) , 3801-3832
Open AccessEffective metaheuristics for the latency location routing problem
The latency location routing problem (LLRP), a combination of the facility location problem and the cumulative capacitated vehicle routing problem, is a recently proposed variant of location routing problems. It corresponds to a customer‐centric problem, in which the aim is to minimize the sum of the arrival times at the customers. This paper proposes three novel metaheuristic algorithms to solve the LLRP. They use a simulated annealing framework, which after each temperature reduction is intensified through a variable neighborhood descent procedure. Each algorithm uses a different search strategy as intensification. Results on 76 benchmark instances indicate that the proposed metaheurstics outperform the state‐of‐the‐art algorithms, finding new best solutions for all the large‐sized instances (over 100 customers), or the currently known optimal ones for most of the small‐ and medium‐sized instances, in comparable computing times. Furthermore, in more than 80% of the instances the average value of the solutions found by the proposed algorithms is better than or equal to that of the current best known solution.
- 11 May 2021
- Published by Wiley in International Transactions in Operational Research
- Vol. 30 (2) , 655-687
A matheuristic algorithm for the pollution and energy minimization traveling salesman problems
The pollution traveling salesman problem (PTSP) and the energy minimization traveling salesman problem (EMTSP) generalize the well‐known asymmetric traveling salesman problem by including environmental issues and the goal of reducing carbon emissions. Both problems call for determining a Hamiltonian tour that, in the PTSP, minimizes a function of fuel consumption and driver cost (where the fuel consumption depends on the distance traveled, the vehicle speed, and the vehicle load), while, in the EMTSP, minimizes a function depending on the vehicle load and the traveled distances. For both PTSP and EMTSP, we propose a matheuristic algorithm that uses the solution of the linear programming relaxation of a mixed integer linear programming model for the considered problem to determine good initial feasible solutions, applies a multioperator genetic algorithm to improve these solutions, and refines the best solution found through an iterated local search procedure. In order to evaluate the performance of the proposed matheuristics, we compare them with exact and heuristic algorithms from the literature on benchmark instances of both problems.
- 11 May 2021
- Published by Wiley in International Transactions in Operational Research
- Vol. 30 (2) , 655-687
A matheuristic algorithm for the pollution and energy minimization traveling salesman problems
The pollution traveling salesman problem (PTSP) and the energy minimization traveling salesman problem (EMTSP) generalize the well‐known asymmetric traveling salesman problem by including environmental issues and the goal of reducing carbon emissions. Both problems call for determining a Hamiltonian tour that, in the PTSP, minimizes a function of fuel consumption and driver cost (where the fuel consumption depends on the distance traveled, the vehicle speed, and the vehicle load), while, in the EMTSP, minimizes a function depending on the vehicle load and the traveled distances. For both PTSP and EMTSP, we propose a matheuristic algorithm that uses the solution of the linear programming relaxation of a mixed integer linear programming model for the considered problem to determine good initial feasible solutions, applies a multioperator genetic algorithm to improve these solutions, and refines the best solution found through an iterated local search procedure. In order to evaluate the performance of the proposed matheuristics, we compare them with exact and heuristic algorithms from the literature on benchmark instances of both problems.
- 8 March 2021
- Published by Wiley in International Transactions in Operational Research
- Vol. 30 (2) , 1092-1119
The school bus routing problem with student choice: a bilevel approach and a simple and effective metaheuristic
The school bus routing problem (SBRP) involves interrelated decisions such as selecting the bus stops, allocating the students to the selected bus stops, and designing the routes for transporting the students to the school taking into account the bus capacity constraint, with the objective of minimizing the cost of the routes. This paper addresses the SBRP when the reaction of students to the selection of bus stops is taken into account, that is, when students are allowed to choose the selected bus stop that best suits them. A bilevel optimization model with multiple followers is formulated, and its transformation into a single‐level mixed integer linear programming (MILP) model is proposed. A simple and effective metaheuristic algorithm is also developed to solve the problem. This algorithm involves solving four MILP problems at the beginning, which can be used to obtain tight upper bounds of the optimal solution. Extensive computational experiments on SBRP benchmark instances from the literature show the effectiveness of the proposed algorithm in terms of both the quality of the solution found and the required computing time.
- 8 March 2021
- Published by Wiley in International Transactions in Operational Research
- Vol. 30 (2) , 1092-1119
The school bus routing problem with student choice: a bilevel approach and a simple and effective metaheuristic
The school bus routing problem (SBRP) involves interrelated decisions such as selecting the bus stops, allocating the students to the selected bus stops, and designing the routes for transporting the students to the school taking into account the bus capacity constraint, with the objective of minimizing the cost of the routes. This paper addresses the SBRP when the reaction of students to the selection of bus stops is taken into account, that is, when students are allowed to choose the selected bus stop that best suits them. A bilevel optimization model with multiple followers is formulated, and its transformation into a single‐level mixed integer linear programming (MILP) model is proposed. A simple and effective metaheuristic algorithm is also developed to solve the problem. This algorithm involves solving four MILP problems at the beginning, which can be used to obtain tight upper bounds of the optimal solution. Extensive computational experiments on SBRP benchmark instances from the literature show the effectiveness of the proposed algorithm in terms of both the quality of the solution found and the required computing time.
- Open Access
- 23 July 2020
- Published by MDPI AG in Mathematics
- Vol. 8 (8) , 1214
A Partial Allocation Local Search Matheuristic for Solving the School Bus Routing Problem with Bus Stop Selection
This paper addresses the school bus routing problem with bus stop selection, which jointly handles the problems of determining the set of bus stops to visit, allocating each student to one of these bus stops and computing the routes that visit the selected bus stops, so that the total routing cost is minimized and the walking distance of the students is limited by a given value. A fast and efficient matheuristic is developed based on an innovative approach that first partially allocates the students to a set of active stops that they can reach, and computes a set of routes that minimizes the routing cost. Then, a refining process is performed to complete the allocation and to adapt the routes until a feasible solution is obtained. The algorithm is tested on a set of benchmark instances. The computational results show the efficiency of the algorithm in terms of the quality of the solutions yielded and the computing time.
- 23 July 2020
- Published by MDPI AG in Mathematics
- Vol. 8 (8) , 1214
Open AccessA Partial Allocation Local Search Matheuristic for Solving the School Bus Routing Problem with Bus Stop Selection
This paper addresses the school bus routing problem with bus stop selection, which jointly handles the problems of determining the set of bus stops to visit, allocating each student to one of these bus stops and computing the routes that visit the selected bus stops, so that the total routing cost is minimized and the walking distance of the students is limited by a given value. A fast and efficient matheuristic is developed based on an innovative approach that first partially allocates the students to a set of active stops that they can reach, and computes a set of routes that minimizes the routing cost. Then, a refining process is performed to complete the allocation and to adapt the routes until a feasible solution is obtained. The algorithm is tested on a set of benchmark instances. The computational results show the efficiency of the algorithm in terms of the quality of the solutions yielded and the computing time.
- 8 May 2019
- Published by Elsevier in European Journal of Operational Research
- Vol. 278 (1) , 1-2
Egon Balas (1922-2019)
- 8 May 2019
- Published by Elsevier in European Journal of Operational Research
- Vol. 278 (1) , 1-2
Egon Balas (1922-2019)
- 11 February 2019
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 53 (3) , 746-762
An Effective Peak Period Heuristic for Railway Rolling Stock Planning
In this work we tackle a real-world application of railway rolling stock planning, known as the train unit assignment problem (TUAP), arising for a regional train operator in the North of Italy. Given a set of timetabled train trips, each with a demand of passenger seats, as well as a set of train units, each with a cost and a number of available passenger seats, the goal is to determine the minimum cost daily assignment of the train units to the trips, satisfying a set of operational constraints. The context we focus on is that of a competitive bid process whereby a train operator competes to win a contract for providing rolling stock circulation in a regional railway network. From a theoretical perspective, we prove that even a relaxation of the TUAP is NP-hard. To solve the TUAP, we propose a heuristic algorithm based on the optimal solution of the restricted problem associated with a peak period (i.e., a period of the day in which many trips overlapping in time must be performed). The heuristic algori...
- 11 February 2019
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 53 (3) , 746-762
An Effective Peak Period Heuristic for Railway Rolling Stock Planning
In this work we tackle a real-world application of railway rolling stock planning, known as the train unit assignment problem (TUAP), arising for a regional train operator in the North of Italy. Given a set of timetabled train trips, each with a demand of passenger seats, as well as a set of train units, each with a cost and a number of available passenger seats, the goal is to determine the minimum cost daily assignment of the train units to the trips, satisfying a set of operational constraints. The context we focus on is that of a competitive bid process whereby a train operator competes to win a contract for providing rolling stock circulation in a regional railway network. From a theoretical perspective, we prove that even a relaxation of the TUAP is NP-hard. To solve the TUAP, we propose a heuristic algorithm based on the optimal solution of the restricted problem associated with a peak period (i.e., a period of the day in which many trips overlapping in time must be performed). The heuristic algori...