José Manuel Valério de Carvalho
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
José Manuel Valério de Carvalho has a total of 53 co-authors. Here are the top co-authors by number of shared publications:
- Cláudio Alves
University of Minho
45 shared publications - Telmo Pinto
University of Coimbra, CEMMPRE, ARISE
14 shared publications - Filipe Alvelos
University of Minho
10 shared publications Jürgen Rietz
University of Minho
7 shared publications- Elsa Silva
Department of Production and Systems, School of Engineering Universidade do Minho Rua da Universidade Braga 4710‐057 Portugal
6 shared publications - Jürgen Rietz
Universidade do Minho
6 shared publications
Latest Publications
- 25 January 2025
- Published by Elsevier in European Journal of Operational Research
- Vol. 323 (3) , 753-766
A new effective heuristic for the Prisoner Transportation Problem
- 25 January 2025
- Published by Elsevier in European Journal of Operational Research
- Vol. 323 (3) , 753-766
A new effective heuristic for the Prisoner Transportation Problem
- Open Access
- 31 January 2023
- Published by MDPI AG in Mathematics
- Vol. 11 (3) , 713
A Matheuristic Approach to the Integration of Three-Dimensional Bin Packing Problem and Vehicle Routing Problem with Simultaneous Delivery and Pickup
This work presents a hybrid approach to solve a distribution problem of a Portuguese company in the automotive industry. The objective is to determine the minimum cost for daily distribution operations, such as collecting and delivering goods to multiple suppliers. Additional constraints are explicitly considered, such as time windows and loading constraints due to the limited capacity of the fleet in terms of weight and volume. An exhaustive review of the state of the art was conducted, presenting different typology schemes from the literature for the pickup and delivery problems in the distribution field. Two mathematical models were integrated within a matheuristic approach. One model reflects the combination of the Vehicle Routing Problem with Simultaneous Delivery and Pickup with the Capacitated Vehicle Routing Problem with Time Windows. The second one aims to pack all the items to be delivered onto the pallets, reflecting a three-dimensional single bin size Bin Packing Problem. Both formulations proposed—a commodity-flow model and a formulation of the Three-Dimensional Packing Problem must be solved within the matheuristic. All the approaches were tested using real instances from data provided by the company. Additional computational experiments using benchmark instances were also performed.
- 31 January 2023
- Published by MDPI AG in Mathematics
- Vol. 11 (3) , 713
Open AccessA Matheuristic Approach to the Integration of Three-Dimensional Bin Packing Problem and Vehicle Routing Problem with Simultaneous Delivery and Pickup
This work presents a hybrid approach to solve a distribution problem of a Portuguese company in the automotive industry. The objective is to determine the minimum cost for daily distribution operations, such as collecting and delivering goods to multiple suppliers. Additional constraints are explicitly considered, such as time windows and loading constraints due to the limited capacity of the fleet in terms of weight and volume. An exhaustive review of the state of the art was conducted, presenting different typology schemes from the literature for the pickup and delivery problems in the distribution field. Two mathematical models were integrated within a matheuristic approach. One model reflects the combination of the Vehicle Routing Problem with Simultaneous Delivery and Pickup with the Capacitated Vehicle Routing Problem with Time Windows. The second one aims to pack all the items to be delivered onto the pallets, reflecting a three-dimensional single bin size Bin Packing Problem. Both formulations proposed—a commodity-flow model and a formulation of the Three-Dimensional Packing Problem must be solved within the matheuristic. All the approaches were tested using real instances from data provided by the company. Additional computational experiments using benchmark instances were also performed.
- Open Access
- 4 December 2021
- Published by Springer Nature in Optimization Letters
- Vol. 16 (8) , 2333-2358
Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups
The aim of this letter is to design and computationally test several improvements for the compact integer linear programming (ILP) formulations of the temporal bin packing problem with fire-ups (TBPP-FU). This problem is a challenging generalization of the classical bin packing problem in which the items, interpreted as jobs of given weight, are active only during an associated time window. The TBPP-FU objective function asks for the minimization of the weighted sum of the number of bins, viewed as servers of given capacity, to execute all the jobs and the total number of fire-ups. The fire-ups count the number of times the servers are activated due to the presence of assigned active jobs. Our contributions are effective procedures to reduce the number of variables and constraints of the ILP formulations proposed in the literature as well as the introduction of new valid inequalities. By extensive computational tests we show that substantial improvements can be achieved and several instances from the literature can be solved to proven optimality for the first time.
- 4 December 2021
- Published by Springer Nature in Optimization Letters
- Vol. 16 (8) , 2333-2358
Open AccessVariable and constraint reduction techniques for the temporal bin packing problem with fire-ups
The aim of this letter is to design and computationally test several improvements for the compact integer linear programming (ILP) formulations of the temporal bin packing problem with fire-ups (TBPP-FU). This problem is a challenging generalization of the classical bin packing problem in which the items, interpreted as jobs of given weight, are active only during an associated time window. The TBPP-FU objective function asks for the minimization of the weighted sum of the number of bins, viewed as servers of given capacity, to execute all the jobs and the total number of fire-ups. The fire-ups count the number of times the servers are activated due to the presence of assigned active jobs. Our contributions are effective procedures to reduce the number of variables and constraints of the ILP formulations proposed in the literature as well as the introduction of new valid inequalities. By extensive computational tests we show that substantial improvements can be achieved and several instances from the literature can be solved to proven optimality for the first time.
- Open Access
Arc Flow Formulations Based on Dynamic Programming: Theoretical Foundations and Applications
Network flow formulations are among the most successful tools to solve optimization problems. Such formulations correspond to determining an optimal flow in a network. One particular class of network flow formulations is the arc flow, where variables represent flows on individual arcs of the network. For $\mathcal{NP}$-hard problems, polynomial-sized arc flow models typically provide weak linear relaxations and may have too much symmetry to be efficient in practice. Instead, arc flow models with a pseudo-polynomial size usually provide strong relaxations and are efficient in practice. The interest in pseudo-polynomial arc flow formulations has grown considerably in the last twenty years, in which they have been used to solve many open instances of hard problems. A remarkable advantage of pseudo-polynomial arc flow models is the possibility to solve practical-sized instances directly by a Mixed Integer Linear Programming solver, avoiding the implementation of complex methods based on column generation. In this survey, we present theoretical foundations of pseudo-polynomial arc flow formulations, by showing a relation between their network and Dynamic Programming (DP). This relation allows a better understanding of the strength of these formulations, through a link with models obtained by Dantzig-Wolfe decomposition. The relation with DP also allows a new perspective to relate state-space relaxation methods for DP with arc flow models. We also present a dual point of view to contrast the linear relaxation of arc flow models with that of models based on paths and cycles. To conclude, we review the main solution methods and applications of arc flow models based on DP in several domains such as cutting, packing, scheduling, and routing.
Open AccessArc Flow Formulations Based on Dynamic Programming: Theoretical Foundations and Applications
Network flow formulations are among the most successful tools to solve optimization problems. Such formulations correspond to determining an optimal flow in a network. One particular class of network flow formulations is the arc flow, where variables represent flows on individual arcs of the network. For $\mathcal{NP}$-hard problems, polynomial-sized arc flow models typically provide weak linear relaxations and may have too much symmetry to be efficient in practice. Instead, arc flow models with a pseudo-polynomial size usually provide strong relaxations and are efficient in practice. The interest in pseudo-polynomial arc flow formulations has grown considerably in the last twenty years, in which they have been used to solve many open instances of hard problems. A remarkable advantage of pseudo-polynomial arc flow models is the possibility to solve practical-sized instances directly by a Mixed Integer Linear Programming solver, avoiding the implementation of complex methods based on column generation. In this survey, we present theoretical foundations of pseudo-polynomial arc flow formulations, by showing a relation between their network and Dynamic Programming (DP). This relation allows a better understanding of the strength of these formulations, through a link with models obtained by Dantzig-Wolfe decomposition. The relation with DP also allows a new perspective to relate state-space relaxation methods for DP with arc flow models. We also present a dual point of view to contrast the linear relaxation of arc flow models with that of models based on paths and cycles. To conclude, we review the main solution methods and applications of arc flow models based on DP in several domains such as cutting, packing, scheduling, and routing.
- 2 January 2020
- Published by Wiley in International Transactions in Operational Research
- Vol. 29 (1) , 526-553
An arc flow formulation to the multitrip production, inventory, distribution, and routing problem with time windows
The multitrip production, inventory, distribution, and routing problem with time windows (MPIDRPTW) is an integrated problem that combines a production and distribution problem, a multitrip vehicle routing problem, and an inventory routing problem. In the MPIDRPTW, a set of customers, which have a time‐varying demand during a finite planning horizon, is served by a single production facility. The distribution is accomplished by a fleet of homogeneous vehicles that deliver the customer orders within their specific time windows. Production management has to be done according to the inventories at the facility and at the customers. An exact arc flow model based on a graph is proposed to solve the MPIDRPTW, where the nodes represent instants of time. The main goal of the problem is to minimize the costs associated with the entire system. The proposed approach was implemented and a set of experimental tests were conducted based on a set of adapted instances from the literature.
- 2 January 2020
- Published by Wiley in International Transactions in Operational Research
- Vol. 29 (1) , 526-553
An arc flow formulation to the multitrip production, inventory, distribution, and routing problem with time windows
The multitrip production, inventory, distribution, and routing problem with time windows (MPIDRPTW) is an integrated problem that combines a production and distribution problem, a multitrip vehicle routing problem, and an inventory routing problem. In the MPIDRPTW, a set of customers, which have a time‐varying demand during a finite planning horizon, is served by a single production facility. The distribution is accomplished by a fleet of homogeneous vehicles that deliver the customer orders within their specific time windows. Production management has to be done according to the inventories at the facility and at the customers. An exact arc flow model based on a graph is proposed to solve the MPIDRPTW, where the nodes represent instants of time. The main goal of the problem is to minimize the costs associated with the entire system. The proposed approach was implemented and a set of experimental tests were conducted based on a set of adapted instances from the literature.
- 25 February 2019
- Published by Wiley in International Transactions in Operational Research
- Vol. 26 (5) , 1633-1654
A strong integer linear optimization model to the compartmentalized knapsack problem
The compartmentalized knapsack problem (CKP) is a relatively new type of problem with a wide application in industrial processes, arising, for instance, in the case of cutting steel coils in two phases in the metallurgical industry.In the literature, there are two mathematical formulations for the CKP: a classical formulation, which is a nonlinear integer programming (IP) model, and a recent (linear) IP formulation, obtained by discretizing the compartments that can be built for each class of items; the latter is an important contribution, because it makes the problem amenable to solution by mixed‐integer linear programming tools. Combinatorial enumeration algorithms and several pseudo‐polynomial decomposition heuristics were also developed for the CKP.This paper presents a new model for the exact solution of the CKP, denoted as the strong integer linear model, derived from the (linear) IP formulation by strengthening data, reducing symmetry, and lifting, and also a new pseudo‐polynomial heuristic, the heuristic of the strong capacities. Computational experiments are presented with a large set of instances that show the advantage of the new approaches. The strong model solves the CKP exactly more than seven times faster, and the new heuristic is more efficient, presenting a good balance in the terms of effectiveness.
- 25 February 2019
- Published by Wiley in International Transactions in Operational Research
- Vol. 26 (5) , 1633-1654
A strong integer linear optimization model to the compartmentalized knapsack problem
The compartmentalized knapsack problem (CKP) is a relatively new type of problem with a wide application in industrial processes, arising, for instance, in the case of cutting steel coils in two phases in the metallurgical industry.In the literature, there are two mathematical formulations for the CKP: a classical formulation, which is a nonlinear integer programming (IP) model, and a recent (linear) IP formulation, obtained by discretizing the compartments that can be built for each class of items; the latter is an important contribution, because it makes the problem amenable to solution by mixed‐integer linear programming tools. Combinatorial enumeration algorithms and several pseudo‐polynomial decomposition heuristics were also developed for the CKP.This paper presents a new model for the exact solution of the CKP, denoted as the strong integer linear model, derived from the (linear) IP formulation by strengthening data, reducing symmetry, and lifting, and also a new pseudo‐polynomial heuristic, the heuristic of the strong capacities. Computational experiments are presented with a large set of instances that show the advantage of the new approaches. The strong model solves the CKP exactly more than seven times faster, and the new heuristic is more efficient, presenting a good balance in the terms of effectiveness.
- 1 April 2018
- Published by Elsevier in European Journal of Operational Research
- Vol. 266 (2) , 458-471
A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems
- 1 April 2018
- Published by Elsevier in European Journal of Operational Research
- Vol. 266 (2) , 458-471
A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems
- 15 February 2018
- Published by Springer Nature
- p. 313-324
Models and Advanced Optimization Algorithms for the Integrated Management of Logistics Operations
- 15 February 2018
- Published by Springer Nature
- p. 313-324
Models and Advanced Optimization Algorithms for the Integrated Management of Logistics Operations
- 1 February 2018
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 64, 155-164
Column Generation Based Approaches for Combined Routing and Scheduling
- 1 February 2018
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 64, 155-164
Column Generation Based Approaches for Combined Routing and Scheduling
- 1 February 2018
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 64, 135-144
Column generation based primal heuristics for routing and loading problems
- 1 February 2018
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 64, 135-144
Column generation based primal heuristics for routing and loading problems