MANUEL IORI - personale UniMoRe

Nuova ricerca

MANUEL IORI

Professore Ordinario
Dipartimento di Scienze e Metodi dell'Ingegneria

Pubblicazioni

2024 - An Optimization-Based Decision Support System for Multi-trip Vehicle Routing Problems [Articolo su rivista]
Cavecchia, Mirko; ALVES DE QUEIROZ, Thiago; Iori, Manuel; Lancellotti, Riccardo; Zucchi, Giorgio
abstract

Decision support systems (DSS) are used daily to make complex and hard decisions. Developing a DSS is not an easy task and may require combining different approaches to reach accurate and timely responses. In this paper, we present a DSS based on a micro-service architecture that we developed to handle a variant of the vehicle routing problem. The DSS has been implemented for a service company operating in the field of pharmaceutical distribution, and it helps decision-makers define the routes that different types of vehicles need to perform during the day to serve the customers’ demands. The underlying optimization problem assumes that a vehicle can perform multiple routes daily and is constrained to operate within a given time horizon. Customers are characterized by hard time windows on the delivery times. The proposed DSS first handles geo-referencing and distance calculation tasks. Then, it invokes a two-step optimization approach in which vehicle routes are generated and combined to reduce the number of vehicles used. For the latter task, we propose and evaluate four solution methods: two greedy heuristics, a metaheuristic, and a mathematical model. All the methods are applied to solve real and randomly generated instances, showing that the metaheuristic algorithm is superior to the others in terms of solution quality and computing time. The company had a very positive feedback on the proposed DSS and is now using it to support its daily operations.

2024 - An iterated local search for a multi‐period orienteering problem arising in a car patrolling application [Articolo su rivista]
Vidigal Corrêa, Victor Hugo; Dong, Hang; Iori, Manuel; dos Santos, André Gustavo; Yagiura, Mutsunori; Zucchi, Giorgio
abstract

2023 - A Decision Support System for Multi-Trip Vehicle Routing Problems [Relazione in Atti di Convegno]
Cavecchia, Mirko; ALVES DE QUEIROZ, Thiago; Iori, Manuel; Lancellotti, Riccardo; Zucchi, Giorgio
abstract

Emerging trends, driven by industry 4.0 and Big Data, are pushing to combine optimization techniques with Decision Support Systems (DSS). The use of DSS can reduce the risk of uncertainty of the decision-maker regarding the economic feasibility of a project and the technical design. Designing a DSS can be very hard, due to the inherent complexity of these types of systems. Therefore, monolithic software architectures are not a viable solution. This paper describes the DSS developed for an Italian company based on a micro-services architecture. In particular, the services handle geo-referenced information to solve a multi-trip vehicle routing problem with time windows. To face the problem, we follow a two-step approach. First, we generate a set of routes solving a vehicle routing problem with time windows using a metaheuristic algorithm. Second, we calculate the interval in which each route can start and end, and then combine the routes together, with an integer linear programming model, to minimize the number of used vehicles. Computational tests are conducted on real and random instances and prove the efficiency of the approach.

2023 - A GRASP for a real-world scheduling problem with unrelated parallel print machines and sequence-dependent setup times [Articolo su rivista]
Iori, M.; Locatelli, A.; Locatelli, M.
abstract

We consider a real-world scheduling problem arising in the colour printing industry. The problem consists in assigning print jobs to a heterogeneous set of flexographic printer machines and finding a processing sequence for the jobs assigned to each machine. The machines are characterised by a limited sequence of colour groups and can equip additional components (e.g. embossing rollers and perforating rolls) to process jobs that require specific treatments. The process to equip a machine with an additional component or to clean a colour group takes a long time, with the effect of significantly raising the setup times. The aim is to minimise a weighted sum of total weighted tardiness and total setup time. The problem derives from the activities of an Italian food packaging company. To solve it, we developed a greedy randomised adaptive search procedure equipped with several local search procedures. The excellent performance of the algorithm is proved by extensive computational experiments on real-world instances, for which it produced good-quality solutions within a limited computing time. The algorithm is currently in use at the company to support their weekly scheduling decisions.

2023 - A Survey of Attended Home Delivery and Service Problems with a Focus on Applications [Abstract in Atti di Convegno]
Vezzali, Dario; Cordeau, Jean-François; Iori, Manuel
abstract

The research field on Attended Home Delivery (AHD) and Attended Home Service (AHS) problems has experienced fast growing interest in the last two decades, with the rapid diffusion of online platforms and e-commerce transactions. The COVID-19 pandemic has just fostered that interest, raising further challenges, opportunities and shortcomings that have to be tackled to answer the need for innovative methodologies as well as new policy actions. The aim of this work is to provide an extensive literature review on the state of the art for AHD and AHS problems, with a particular focus on real-world applications. A discussion of promising future research directions is also provided.

2023 - A branch-and-regret algorithm for the same-day delivery problem [Articolo su rivista]
Côté, J. F.; Alves de Queiroz, T.; Gallesi, F.; Iori, M.
abstract

We study a dynamic vehicle routing problem where stochastic customers request urgent deliveries characterized by restricted time windows. The aim is to use a fleet of vehicles to maximize the number of served requests and minimize the traveled distance. The problem is known in the literature as the same-day delivery problem, and it is of high importance because it models a number of real-world applications, including the delivery of online purchases. We solve the same-day delivery problem by proposing a novel branch-and-regret algorithm in which sampled scenarios are used to anticipate future events and an adaptive large neighborhood search is iteratively invoked to optimize routing plans. The branch-and-regret is equipped with four innovation elements: a new way to model the subproblem, a new policy to generate scenarios, new consensus functions, and a new branching scheme Extensive computational experiments on a large variety of instances prove the outstanding performance of the branch-and-regret, also in comparison with recent literature, in terms of served requests, traveled distance, and computational effort.

2023 - A survey of attended home delivery and service problems with a focus on applications [Articolo su rivista]
Cordeau, Jean-François; Iori, Manuel; Vezzali, Dario
abstract

The research field of Attended Home Delivery (AHD) and Attended Home Service (AHS) problems has experienced fast growing interest in the last two decades, with the rapid growth of online platforms and e-commerce transactions. The COVID-19 pandemic has reinforced that interest, raising further challenges and opportunities that have to be tackled by innovative methodologies and policies. The aim of this work is to provide an extensive literature review on the state of the art for AHD and AHS problems, with a particular focus on real-world applications. A discussion of promising future research directions is also provided.

2023 - Application of Machine Learning Demand Forecasting Techniques in the Italian Processed Meat Industry [Abstract in Atti di Convegno]
Mucciarini, Mirko; Caselli, Giulia; Iori, Manuel; Lippi, Marco
abstract

2023 - Dynamic scheduling of patients in emergency departments [Articolo su rivista]
de Queiroz, Ta; Iori, M; Kramer, A; Kuo, Yh
abstract

Emergency department overcrowding is a global issue that poses a great threat to patient health and safety. The timeliness of medical services provided to patients is crucial to emergency departments as it directly impacts the mortality and morbidity of urgent patients. However, critical resources (e.g., doctors and nurses) are typically constrained due to the limited financial budget. Thus, hospital administrators may need to investigate solutions to improve the efficiency of the emergency department. In this work, we study the dynamic problem of scheduling patients to doctors, aiming at minimizing the total weighted tardiness. We propose a simple reoptimization heuristic based on multiple queues of patients in accordance with their urgency levels, and then combine it with an effective variable neighborhood search. We also propose a scenario-based planning approach that uses sampled scenarios to anticipate future events and the variable neighborhood search to schedule patients. The methods are adapted to handle a problem variant where information on arrival time and urgency level of some patients can be received in advance by the emergency department. With a comprehensive computational study on two sets of realistic instances from Hong Kong SAR of China and Italy, we validate the performance of the proposed methods, evaluating the benefits of having more doctors and receiving early information.(c) 2023 Elsevier B.V. All rights reserved.

2023 - Exact solution of network flow models with strong relaxations [Articolo su rivista]
de Lima, V. L.; Iori, M.; Miyazawa, F. K.
abstract

We address the solution of Mixed Integer Linear Programming (MILP) models with strong relaxations that are derived from Dantzig–Wolfe decompositions and allow a pseudo-polynomial pricing algorithm. We exploit their network-flow characterization and provide a framework based on column generation, reduced-cost variable-fixing, and a highly asymmetric branching scheme that allows us to take advantage of the potential of the current MILP solvers. We apply our framework to a variety of cutting and packing problems from the literature. The efficiency of the framework is proved by extensive computational experiments, in which a significant number of open instances could be solved to proven optimality for the first time.

2023 - Improving buffer storage performance in ceramic tile industry via simulation [Relazione in Atti di Convegno]
Taccini, Marco; Dotti, Giulia; Iori, Manuel; Subramanian, Anand
abstract

This study aims at identifying the best strategy to temporarily store products within a buffer area in an Italian ceramic tile company. The storage policy is analyzed to maximize the storage capacity, facilitate operators' activities, and, consequently, improve the warehouse logistics performance. A discrete event simulation was conducted using Salabim, a Python based open-source software, in order to determine the best policy. We compare the performance of the current storage policy, based on technical production properties of products, and a newly proposed one, based on products' downstream destination. The results suggested that the proposed strategy significantly improves the performance of the buffer area management. The approach can be applied to different applications, contributing to the literature on simulation-based decision-making in material management. Furthermore, the study provides a functional case study showing the potential and achievable results of Salabim for modeling complex systems.

2023 - Minimizing user inconvenience and operational costs in a dial-a-flight problem for flying safaris [Articolo su rivista]
Cordeau, Jf; Iori, M; Mendes, Nfm; Nelli, D; Tedeschi, R
abstract

We study a Dial-a-Flight Problem faced by one of the major safari airline companies in Tanzania. Given a set of daily passenger requests and a fleet of heterogeneous airplanes, the problem requires to determine the best set of itineraries to transport the passengers from their origins to the requested destinations within specific time windows, while satisfying a number of operational constraints. The aim is to minimize user inconvenience, measured by delays with respect to the pre-defined time windows and by the number of intermediate stops in the itineraries, and operational cost. The problem is complicated by the high number of daily requests in peak touristic periods, and by the fact that refueling is possible only at a limited number of airstrips. We solve the problem by means of an adaptive large neighborhood search, which we enrich with local search operators and a set partitioning model. Extensive computational tests on real-world instances prove the effectiveness of the proposed algorithm, which can improve the solutions found by the company both in terms of operational cost and user inconvenience, in reasonable computational time.

2023 - Solution of a practical Vehicle Routing Problem for monitoring Water Distribution Networks [Articolo su rivista]
Atefi, Reza; Iori, Manuel; Salari, Majid; Vezzali, Dario
abstract

In this work, we introduce a generalisation of the Vehicle Routing Problem for a specific application in the monitoring of a Water Distribution Network (WDN). In this problem, multiple technicians must visit a sequence of nodes in the WDN and perform a series of tests to check the quality of water. Some special nodes (i.e., wells) require technicians to first collect a key from a key centre. The key must then be returned to the same key centre after the test has been performed, thus introducing precedence constraints and multiple visits in the routes. To solve the problem, a Mixed Integer Linear Programming model and an Iterated Local Search have been implemented. The efficiency of the proposed methods is demonstrated by means of extensive computational tests on randomly created and real-world instances.

2023 - Successful implementation of discrete event simulation: integrating design thinking and simulation approach in an emergency department [Articolo su rivista]
Dosi, C.; Iori, M.; Kramer, A.; Vignoli, M.
abstract

We address the overcrowding problem in an emergency department (ED) by designing and developing a hybrid methodology that combines design thinking with discrete event simulation. The case study shows how the tested methodology led to a successful implementation of the proposed organizational change in less than 18months, improving system KPIs (such as patients’ waiting time) and ED professionals’ quality of work. The results confirm a successful combination of the two approaches in practice, by showing (i) how to combine design thinking tools and simulation tools in different design phases (comprehension, abstraction, ideation, and testing), and (ii) how the two tools nurture each other reciprocally. The paper concludes with some final considerations regarding the use of simulation in organizational processes design.

2023 - The transportation problem with packing constraints [Articolo su rivista]
Flamand, T.; Iori, M.; Haouari, M.
abstract

We address a new variant of the transportation problem, where a set of different commodities, available at several supply nodes with different prices, are distributed to demand nodes using a set of heterogeneous vehicle fleets available at each supply node. Since each commodity has a specific weight, there is a packing constraint due to the total capacity of each vehicle. The objective of this problem is to minimize the total supply cost, which includes the purchase cost of commodities and the fixed transportation cost based on the traveled distance. This novel variant of the transportation problem poses computational challenges due to its combinatorial structure. To tackle these challenges and solve large-scale instances to near-optimality in reasonable CPU times, we propose a variable neighborhood search algorithm. The proposed algorithm partitions the problem into smaller, more manageable problems to be solved. In order to initialize this methodology, we also propose a decomposition heuristic that prescribes initial feasible solutions in CPU times ranging from 0.6 s to 133.2 s on average with average optimality gaps ranging from 0.09% to 4.62%. Our proposed methodology provides solutions with 0.06% to 3.78% optimality gaps on average within average CPU times ranging from 0.2 s to 386.2 s, while the commercial solvers are unable to find integer solutions or to solve most of the instances to optimality within one CPU-hour time limit.

2022 - 2DPackLib: a two-dimensional cutting and packing library [Articolo su rivista]
Iori, M.; de Lima, V. L.; Martello, S.; Monaci, M.
abstract

Two-dimensional cutting and packing problems model a large number of relevant industrial applications.The literature on practical algorithms for such problems is very large. We introduce the 2DPackLib, a library on two-dimensional orthogonal cutting and packing problems. The library makes available, in a unified format, 25 benchmarks from the literature for a total of over 3000 instances, provides direct links to surveys and typologies, and includes a list of relevant links.

2022 - An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion [Articolo su rivista]
Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori
abstract

We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a heuristic frame- work, the iterated dual substitution (iDS) algorithm, which iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best scenario–based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best-known records for a number of benchmark instances.

2022 - An Iterated Local Search for a Pharmaceutical Storage Location Assignment Problem with Product-cell Incompatibility and Isolation Constraints [Relazione in Atti di Convegno]
Mendes, N. F. M.; Bolsi, B.; Iori, M.
abstract

In healthcare supply chain, centralised warehouses are used to store large amounts of products close to hospitals and pharmacies in order to avoid shortages and reduce storage costs. To reach these objectives, the warehouses need to have efficient order retrieval and dispatch procedures, as well as a storage allocation policy able to guarantee the safe keeping of items. Considering this scenario, we present a Storage Location Assignment Problem with Product-Cell Incompatibility and Isolation Constraints, that models the targets and restrictions of a storage policy in a pharmaceutical product warehouse. In this problem, we aim to minimise the total distance travelled by the order pickers to recover all products required in a set of orders. We propose an Iterated Local Search algorithm to solve the problem, and present numerical experiments based on simulated data. The results show a relevant improvement with respect to a greedy full turnover procedure commonly adopted in real life operations.

2022 - An Optimization View to the Design of Edge Computing Infrastructures for IoT Applications [Capitolo/Saggio]
de Queiroz, Thiago Alves; Canali, Claudia; Iori, Manuel; Lancellotti, Riccardo
abstract

Internet of Things (IoT) based applications have recently experienced a remarkable diffusion in many different contexts, such as automotive, e-health, public security, industrial applications, energy, and waste management. These kinds of applications are characterized by geographically distributed sensors that collect data to be processed through algorithms of Artificial Intelligence (AI). Due to the vast amount of data to be processed by AI algorithms and the severe latency requirements of some applications, the emerging Edge Computing paradigm may represent the preferable choice for the supporting infrastructure. However, the design of edge computing infrastructures opens several new issues concerning the allocation of data flows coming from sensors over the edge nodes, and the choice of the number and the location of the edge nodes to be activated. The service placement issue can be modeled through a multi-objective optimization aiming at minimizing two aspects: the response time for data transmission and processing in the sensors-edge-cloud path; the (energy or monetary) cost related to the number of turned on edge nodes. Two heuristics, based on Variable Neighborhood Search and on Genetic Algorithms, are proposed and evaluated over a wide range of scenarios, considering a realistic smart city application with 100 sensors and up to 10 edge nodes. Both heuristics can return practical solutions for the given application. The results indicate a suitable topology for a network-bound scenario requires less enabled edge nodes comparatively with a CPU-bound scenario. In terms of performance gain, the VNS outperformed in almost every condition the GA approach, reaching a performance gain up to almost 40% when the network delay plays a significant role and when the load is higher. Hence, the experimental tests demonstrate that the proposed heuristics are useful to support the design of edge computing infrastructures for modern AI-based applications relying on data collected by geographically distributed IoT sensors.

2022 - Arc flow formulations based on dynamic programming: Theoretical foundations and applications [Articolo su rivista]
de Lima, V. L.; Alves, C.; Clautiaux, F.; Iori, M.; Valerio de Carvalho, J. M.
abstract

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 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.

2022 - Demand Forecasting Methods: A Case Study in the Italian Processed Meat Industry [Abstract in Atti di Convegno]
Mucciarini, Mirko; Caselli, Giulia; Iori, Manuel; Lippi, Marco
abstract

2022 - Heuristic algorithms for integrated workforce allocation and scheduling of perishable products [Articolo su rivista]
Bolsi, B.; de Lima, V. L.; Alves de Queiroz, T.; Iori, M.
abstract

We study a problem from a real-world application, in which a daily set of orders must be processed following two stages, consisting of preparing perishable products on benches and allocating them to conveyors to be packed in disposable trays. Daily decisions must be made regarding the number and start time of working shifts, the number of workers and their allocation to machines, and the scheduling of orders in a two-stage flexible flow shop environment. The flow shop environment of the studied problem is common in many industries of perishable products, making the problem very general. The problem involves a number of operational constraints, and three objective functions that are minimised in a lexicographic way. To solve the problem, we implement a constructive heuristic and embed it within three metaheuristics: a Random multi-start algorithm (MR), a Biased random key genetic algorithm (BRKGA), and a Variable neighbourhood search (VNS) based one. We perform computational experiments over a set of realistic instances, and present a lower bound obtained from a constraint programming model for the scheduling counterpart. The results of the experiments show that the BRKGA is the most effective in practice for the integrated problem of workforce allocation and scheduling.

2022 - Industrial Waste Collection Optimization: A Real-World Case Study in Northern Italy [Relazione in Atti di Convegno]
Chiussi, A.; de Paula Felix, G.; Iori, M.; dos Santos, A. G.
abstract

In this work, we present a real case application of a Rollon-Rolloff Vehicle Routing Problem (RRVRP) that arises at a waste collection company in Northern Italy. Compared to other RRVRP applications, where large containers are emptied and moved, our problem presents two additional types of services regarding the collection of bulk waste materials. Moreover, the problem deals with customer selection based on an objective function with two components: outsourcing costs incurred when customers are given to a third-party logistic operator, and internal routing costs. We model the RRVRP as a Mixed Integer Program and we solve it through a commercial solver and a simple but effective Iterated Greedy algorithm. Computational results are provided on 30 real case instances. Solutions provided by the Iterated Greedy are constantly better than the ones implemented by the company, showing that relevant cost reduction can be obtained with a limited computational effort.

2022 - Knapsack problems — An overview of recent advances. Part I: Single knapsack problems [Articolo su rivista]
Cacchiani, V.; Iori, M.; Locatelli, A.; Martello, S.
abstract

After the seminal books by Martello and Toth (1990) and Kellerer, Pferschy, and Pisinger (2004), knapsack problems became a classical and rich research area in combinatorial optimization. The purpose of this survey, which is structured in two parts, is to cover the developments that appeared in this field after the publication of the latter volume. Part I is devoted to problems whose goal is to optimally assign items to a single knapsack. Besides the classical knapsack problems (binary, subset sum, bounded, unbounded, change-making), we review problems with special constraints (setups, multiple-choice, conflicts, precedences, sharing, compartments) as well as relatively recent fields of investigation, like robust and bilevel problems. The subsequent Part II covers multiple, multidimensional, and quadratic knapsack problems, and includes a succinct treatment of online and multiobjective knapsack problems.

2022 - Knapsack problems — An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems [Articolo su rivista]
Cacchiani, V.; Iori, M.; Locatelli, A.; Martello, S.
abstract

2022 - Mixed Integer Linear Programming for CO2 emissions minimization in a Waste Transfer Facility Location Problem [Relazione in Atti di Convegno]
Caselli, Giulia; Columbu, Giomaria; Iori, Manuel; Magni, Carlo Alberto
abstract

In this work, we solve a real-world facility location problem by means of a mixed integer linear programming model. The problem is faced by an Italian multi-utility company operating in the sector of waste management. The company works in several Italian regions to collect and treat the urban waste through a network of facilities. In this problem, a set of demand points is given with a predicted quantity of waste to be collected and a fixed number of visits required over a predetermined time horizon. The flow of different classes of recyclable waste must be optimized by deciding whether and where to open additional intermediate transfer facilities among a set of dedicated points. The aim is to minimize the CO2 emissions involved in the process, including emissions from the use of additional facilities and the transport of waste across the network. We provide a mathematical formulation for the problem, and use it to solve a real-world case study. An optimal solution is obtained with a significant reduction in CO2 emissions and a well-structured network, proving the efficacy of the model.

2022 - Mixed Integer Linear Programming for a Real-World Parallel Machine Scheduling Problem with Workforce and Precedence Constraints [Capitolo/Saggio]
Caselli, G.; Delorme, M.; Iori, M.; Magni, C. A.
abstract

In this work, we consider a real-world scheduling problem occurring in the engineering test laboratory of a multinational company producing hydraulic components for motion systems. Similar problems have been solved in the literature under the framework of resource constrained parallel machine scheduling problems. In our work, the tests on the hydraulic components are the jobs to be scheduled. Each job must be processed on a machine and requires an additional human resource to prepare the machine and supervise the job. Machine and workforce eligibility constraints are also included. Release and due dates are given for jobs. The aim is to minimize the total weighted tardiness. Each job has a processing time expressed in working days that depends on the machine and requires a fixed number of hours per day for its assigned worker. Moreover, precedence and contiguity relations between jobs must be respected. We propose a Mixed Integer Linear Programming formulation to model the problem and demonstrate its effectiveness on both real-world and randomly generated instances.

2022 - Optimizing a Dynamic Outpatient Facility System with Multiple Servers [Capitolo/Saggio]
Bolsi, B.; Kramer, A.; de Queiroz, T. A.; Iori, M.
abstract

The management of queues is a complex problem, and it requires special attention in dynamic environments where information changes over time. This work focuses on an outpatient facility system where patients are attended by identical parallel servers offering different services. Each patient requires service and expects to receive it within a given target time, after which, a tardiness is created. The objective of the problem is to minimize the total tardiness while defining which services each server will offer during the working hours. The arrival of patients is dynamic, and the server’s configurations of services can be updated from time to time. To solve the problem, we propose a local search-based heuristic that locally assigns a configuration to each server based on the improvement reached in terms of total tardiness. The heuristic is tested on realistic instances, considering different settings, showing its superiority over the solution currently implemented on the facility system.

2022 - The double traveling salesman problem with partial last-in-first-out loading constraints [Articolo su rivista]
Chagas, J. B. C.; Toffolo, T. A. M.; Souza, M. J. F.; Iori, M.
abstract

In this paper, we introduce the double traveling salesman problem with partial last-in-first-out loading constraints (DTSPPL). It is a pickup-and-delivery single-vehicle routing problem, where all pickup operations must be performed before any delivery operation because the pickup-and-delivery areas are geographically separated. The vehicle collects items in the pickup area and loads them into its container, a horizontal stack. After performing all pickup operations, the vehicle begins delivering the items in the delivery area. Loading and unloading operations must obey a partial last-in-first-out (LIFO) policy, that is, a version of the LIFO policy that may be violated within a given reloading depth. The objective of the DTSPPL is to minimize the total cost, which involves the total distance traveled by the vehicle and the number of items that are unloaded and then reloaded due to violations of the standard LIFO policy. We formally describe the DTSPPL through two integer linear programming (ILP) formulations and propose a heuristic algorithm based on the biased random-key genetic algorithm (BRKGA) to find high-quality solutions. The performance of the proposed solution approaches is assessed over a broad set of instances. Computational results have shown that both ILP formulations have been able to solve only the smaller instances, whereas the BRKGA obtained good-quality solutions for almost all instances, requiring short computational times.

2022 - Tool Switching Problems in the Context of Overlay Printing with Multiple Colours [Relazione in Atti di Convegno]
Iori, M.; Locatelli, A.; Locatelli, M.; Salazar-Gonzalez, J. -J.
abstract

This paper addresses problems arising in the context of overlay printing with multiple colours, where a finite set of jobs must be sequentially performed by a printing machine which can simultaneously accommodate a limited number of colours. Each job is associated with a subset of colours that the machine must have stored in its magazine before starting the execution. Thus, some colour switches may be required between the execution of two consecutive jobs. Since colour switches imply a reduction of productivity, minimizing them is desirable. In this regard, we address three distinct problems of increasing difficulty. All these problems can be seen as variants of the Tool Switching Problem, where each colour is treated as a tool. For each problem we discuss its complexity and propose a mathematical programming model. We evaluate the effectiveness of the models on several instances that have been generated with the aim of covering different scenarios of interest.

2021 - A Decision Support System for Attended Home Services [Abstract in Atti di Convegno]
PETRATO BRUCK, Bruno; Castegini, Filippo; Cordeau, Jean-François; Iori, Manuel; Poncemi, Tommaso; Vezzali, Dario
abstract

This Talk presents a decision support system (DSS) developed to solve a practical attended home services problem faced by Iren Group, an Italian multiutility company operating in the distribution of electricity, gas, and water. The company operates in several regions across Italy and aims to optimize the organizational system appointed to dispatch technicians to customer locations, where they perform installations, closures, or maintenance activities within time slots chosen by the customers. Indeed, attended home services (AHS) are service delivery systems in which a supplying company and a customer agree on a time window during which the customer will be home and the service will be performed. Typically, the optimization of AHS requires solving a two-stage problem, combining appointment scheduling and vehicle routing. The DSS uses historical data and helps operations managers in performing a number of strategic decisions: grouping municipalities into clusters; designing sets of model-weeks (i.e., matrices of resources distributed among five working days and eight daily time slots of one hour, that define the capacity allocated to a given cluster); evaluating the obtained solutions by means of a dynamic rolling horizon simulator; and providing as output several key performance indicators, as well as visual optimized technician routing plans used to analyze different scenarios. The system integrates simple machine learning techniques, mathematical models, heuristic algorithms and simulation methods that have been specifically developed to take into account different quality of service levels, in accordance with the directives imposed by the authority that regulates the Italian market. Computational experiments carried out on data provided by the company confirm the efficiency of the proposed methods, both in terms of effort reduction and routing costs saving (10% on average) [4]. Additionally, the DSS constitutes a powerful tool that can support the company in the strategical evaluation of existing and potential market opportunities.

2021 - A Decision Support System to Evaluate Suppliers in the Context of Global Service Providers [Relazione in Atti di Convegno]
Bruck, Bruno Petrato; Vezzali, Dario; Iori, Manuel; Magni, Carlo Alberto; Pretolani, Daniele
abstract

In this paper, we present a decision support system (DSS) developed for a global service provider (GSP), which solves a real-world supplier selection problem. The GSP operates in the Italian market of facility management, supplying customers with a variety of services. These services are subcontracted to external qualified suppliers spread all over Italy and chosen on the basis of several criteria, such as service quality, availability and proximity. Selecting the best supplier is a complex task due to the large number of suppliers and the great variety of facility management services offered by the GSP. In the proposed DSS, the choice of the best supplier for a certain service is made according to a thorough multi-criteria analysis. The weights for the criteria were generated by implementing both a simplified analytic hierarchy process and a revised Simos' procedure, later validated by the decision makers at the GSP. The DSS provides quick access to historical performance data, visual tools to aid decisions, and a suggested ranked list of suppliers for each given contract. The effectiveness of the proposed system was assessed by means of extensive simulations on a seven-year period of real-data and several rounds of validation with the company.

2021 - A Mathematical Formulation for Reducing Overcrowding in Hospitals' Waiting Rooms [Relazione in Atti di Convegno]
Caselli, G.; De Santis, D.; Delorme, M.; Iori, M.
abstract

The COVID-19 pandemic has triggered several new measures in public and private companies to limit the spread of the virus. One of the most effective measures was shown to be social distancing, but such measure is not easy to implement for every entity, especially for hospitals. In this work, we study the case of an Italian hospital whose goal is to find the best layout of outpatient services to reduce overcrowding in the waiting rooms. We propose an Integer Linear Programming model to identify the weekly optimal layout and we test it on a set of real data from the year 2019. The results obtained by our model reduce the overcrowding by 80% on average with respect to the results obtained with the configuration used by the hospital, but such results can only be obtained if the layout is allowed to change every week. We then study the case in which we force the layout to be fixed for two or three consecutive weeks and outline that both the computational time and the solution quality worsen significantly.

2021 - A Mixed Approach for Pallet Building Problem with Practical Constraints [Relazione in Atti di Convegno]
Iori, M.; Locatelli, M.; Moreira, M. C. O.; Silveira, T.
abstract

We study a pallet building problem that originates from a case study in a company that produces robotized systems for freight transportation and logistics. We generalize the problem by including the concept of family of items, which allows us to consider specific constraints such as visibility and contiguity. We solve the problem with an algorithm based on a two-step strategy: an Extreme Points heuristic is used to group items into horizontal layers and an exact method is invoked to stack layers one over the other to form pallets. The performance of the algorithm is assessed through extensive computational tests on real-world instances. The results show that the exact model considerably increases the solution quality, creating very compact packings with a limited computational effort.

2021 - A Variable Neighborhood Heuristic for Facility Locations in Fog Computing [Relazione in Atti di Convegno]
Alves de Queiroz, T.; Canali, C.; Iori, M.; Lancellotti, R.
abstract

The current trend of the modern smart cities applications towards a continuous increase in the volume of produced data and the concurrent need for low and predictable latency in the response time has motivated the shift from a cloud to a fog computing approach. A fog computing architecture is likely to represent a preferable solution to reduce the application latency and the risk of network congestion by decreasing the volume of data transferred to cloud data centers. However, the design of a fog infrastructure opens new issues concerning not only how to allocate the data flow coming from sensors to fog nodes and from there to cloud data centers, but also the choice of the number and the location of the fog nodes to be activated among a list of potential candidates. We model this facility location issue through a multi-objective optimization problem. We propose a heuristic based on the variable neighborhood search, where neighborhood structures are based on swap and move operations. The proposed method is tested in a wide range of scenarios, considering a smart city application’s realistic setup with geographically distributed sensors. The experimental evaluation shows that our method can achieve stable and better performance concerning other literature approaches, supporting the given application.

2021 - An integrated task and personnel scheduling problem to optimize distributed services in hospitals [Relazione in Atti di Convegno]
Porto Campana, Nicolas; Zucchi, Giorgio; Iori, Manuel; Magni, Carlo Alberto; Subramanian, Anand
abstract

This paper addresses a real-life task and personnel scheduling problem arising in a large Italian company that needs to provide cleaning services inside a hospital. In this case study, the challenge is to determine a schedule of the employees to clean the whole hospital aiming to minimize the total labor cost, taking into account the fact that the building is a complex structure with multiple levels and each room has different peculiarity. To solve the problem, we propose a three-step approach using mathematical models and metaheuristic algorithms. The solution obtained indicates that the schedule attained by our method is better than the one generated by the company. In addition, to test and validate our approach more thoroughly, a set of artificial instances have been created. The results indicate that our method can help organizations to quickly generate and test a large variety of solutions. Our findings can be of general interest for other personnel scheduling problems involving distributed services.

2021 - Branch-and-Cut and Iterated Local Search for the Weighted k-Traveling Repairman Problem: An Application to the Maintenance of Speed Cameras [Articolo su rivista]
Muritiba, Albert Einstein Fernandes; Bonates, Tibérius O.; Da Silva, Stênio Oliveira; Iori, Manuel
abstract

Private enterprises and governments around the world use speed cameras to control traffic flow and limit speed excess. Cameras may be exposed to difficult weather conditions and typically require frequent maintenance. When deciding the order in which maintenance should be performed, one has to consider both the traveling times between the cameras and the traffic flow that each camera is supposed to monitor. In this paper, we study the problem of routing a set of technicians to repair cameras by minimizing the total weighted latency, that is, the sum of the weighted waiting times of each camera, where the weight is a parameter proportional to the monitored traffic. The resulting problem, called the weighted k-traveling repairman problem (wkTRP), is a generalization of the well- known traveling repairman problem and can be used to model a variety of real-world applications. To solve the wkTRP, we propose an iterated local search heuristic and an exact branch-and-cut algorithm enriched with valid inequalities. The effectiveness of the two methods is proved by extensive computational experiments performed both on in- stances derived from a real-world case study and on benchmark instances from the literature on the wkTRP and on related problems.

2021 - Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem [Articolo su rivista]
Côté, Jean-François; Haouari, Mohamed; Iori, Manuel
abstract

The two-dimensional bin packing problem calls for packing a set of rectangular items into a minimal set of larger rectangular bins. Items must be packed with their edges parallel to the borders of the bins, cannot be rotated, and cannot overlap among them. The problem is of interest because it models many real-world applications, including production, warehouse management, and transportation. It is, unfortunately, very difficult, and instances with just 40 items are unsolved to proven optimality, despite many attempts, since the 1990s. In this paper, we solve the problem with a combinatorial Benders decomposition that is based on a simple model in which the two-dimensional items and bins are just represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but we enrich it with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The resulting algorithm behaved very well on the benchmark sets of instances, improving on average on previous algorithms from the literature and solving for the first time a number of open instances.

2021 - Exact methods for the traveling salesman problem with multiple drones [Articolo su rivista]
Cavani, S.; Iori, M.; Roberti, R.
abstract

Drone delivery is drawing increasing attention in last-mile delivery. Effective solution methods to solve decision-making problems arising in drone delivery allow to run and assess drone delivery systems. In this paper, we focus on delivery systems with a single traditional vehicle and multiple drones working in tandem to fulfill customer requests. We address the Traveling Salesman Problem with Multiple Drones (TSP-MD) and investigate the modeling challenges posed by the presence of multiple drones, which have proven to be hard to handle in the literature. We propose a compact Mixed-Integer Linear Programming (MILP) model to formulate the TSP-MD and several families of valid inequalities. Moreover, we illustrate an exact decomposition approach based on the compact MILP and a branch-and-cut algorithm. We show that this exact approach can solve instances with up to 24 customers to proven optimality, improving upon existing exact methods that can solve similar problems with up to ten customers only.

2021 - Integer Linear Programming for the Tutor Allocation Problem: A practical case in a British University [Articolo su rivista]
Caselli, Giulia; Delorme, Maxence; Iori, Manuel
abstract

In the Tutor Allocation Problem, the objective is to assign a set of tutors to a set of workshops in order to maximize tutors’ preferences. The problem is solved every year by many universities, each having its own specific set of constraints. In this work, we study the tutor allocation in the School of Mathematics at the University of Edinburgh, and solve it with an integer linear programming model. We tested the model on the 2019/2020 case, obtaining a significant improvement with respect to the manual assignment in use and we showed that such improvement could be maintained while optimizing other key metrics such as load balance among groups of tutors and total number of courses assigned. Further tests on randomly created instances show that the model can be used to address cases of broad interest. We also provide meaningful insights on how input parameters, such as the number of workshop locations and the length of the tutors’ preference list, might affect the performance of the model and the average number of preferences satisfied.

2021 - Integrated Workforce Scheduling and Flexible Flow Shop Problem in the Meat Industry [Relazione in Atti di Convegno]
Bolsi, B.; de Lima, V. L.; de Queiroz, T. A.; Iori, M.
abstract

We address a problem from a meat company, in which orders are produced in two stages, consisting of preparing meats on benches and allocating them to conveyors to be packed in disposable trays. In an environment where machines are unrelated, the company has to take daily decisions on the number and start time of working periods, the number of workers and their allocation to machines, and the scheduling of activities to satisfy the required orders. The objective of the problem is to minimize, in a lexicographic way, the number of unscheduled activities, the weighted tardiness, and the total production cost. To solve the problem, we propose a multi-start random constructive heuristic, which tests different combinations of number of workers in the machines and for each combination produces many different schedules of the orders. The results of our computational experiments over realistic instances show that the heuristic is effective and can support the company on its daily decisions.

2021 - Lead time forecasting with machine learning techniques for a pharmaceutical supply chain [Relazione in Atti di Convegno]
Biazon de Oliveira, Maiza; Zucchi, Giorgio; Lippi, Marco; Farias Cordeiro, Douglas; Rosa da Silva, Nubia; Iori, Manuel
abstract

Purchasing lead time is the time elapsed between the moment in which an order for a good is sent to a supplier and the moment in which the order is delivered to the company that requested it. Forecasting of purchasing lead time is an essential task in the planning, management and control of industrial processes. It is of particular importance in the context of pharmaceutical supply chain, where avoiding long waiting times is essential to provide efficient healthcare services. The forecasting of lead times is, however, a very difficult task, due to the complexity of the production processes and the significant heterogeneity in the data. In this paper, we use machine learning regression algorithms to forecast purchasing lead times in a pharmaceutical supply chain, using a real-world industrial database. We compare five algorithms, namely k-nearest neighbors, support vector machines, random forests, linear regression and multilayer perceptrons. The support vector machines approach obtained the best performance overall, with an average error lower than two days. The dataset used in our experiments is made publicly available for future research.

2021 - Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization [Articolo su rivista]
Kramer, A.; Iori, M.; Lacomme, P.
abstract

This paper addresses the parallel machine scheduling problem with family dependent setup times and total weighted completion time minimization. In this problem, when two jobs j and k are scheduled consecutively on the same machine, a setup time is performed between the finishing time of j and the starting time of k if and only if j and k belong to different families. The problem is strongly NP-hard and is commonly addressed in the literature by heuristic approaches and by branch-and-bound algorithms. Achieving proven optimal solution is a challenging task even for small size instances. Our contribution is to introduce five novel mixed integer linear programs based on concepts derived from one-commodity, arc-flow and set covering formulations. Numerical experiments on more than 13000 benchmark instances show that one of the arc-flow models and the set covering model are quite efficient, as they provide on average better solutions than state-of-the-art approaches, with shorter computation times, and solve to proven optimality a large number of open instances from the literature.

2021 - Mathematical models and heuristic algorithms for pallet building problems with practical constraints [Articolo su rivista]
Calzavara, G.; Iori, M.; Locatelli, M.; Moreira, M. C. O.; Silveira, T.
abstract

In the pallet building problem, we aim at loading a given set of items into one or more pallets, by satisfying specific constraints and minimizing the number of pallets used. In this paper, we address a practical case of this problem that originates from a real-world robotized application, subject to some non-trivial operational constraints. In practice, items are grouped into families and must be packed into horizontal layers. To facilitate loading/unloading operations, items of the same type packed into the same layer should be contiguous and at least one of them should be visible from the outside. We present a formal mathematical description for layer and pallet creation subproblems and then we propose heuristic, metaheuristic, matheuristic algorithms to solve the overall problem. The performance of the algorithms is assessed through extensive computational tests on real-world instances.

2021 - Mathematical models and heuristic methods for the assembly line balancing problem with hierarchical worker assignment [Articolo su rivista]
Campana, N. P.; Iori, M.; Moreira, M. C. O.
abstract

This paper proposes new algorithms for the assembly line balancing problem with hierarchical worker assignment (ALBHW). The ALBHW appears in real industrial contexts, where companies deal with a multi-skilled workforce. It considers task execution times that vary depending on the worker type to whom the task is assigned. Qualification levels among workers are ranked hierarchically, where a lower qualified worker costs less but requires larger execution times then a higher qualified one. The aim is to assign workers and tasks to the stations of an assembly line, in such a way that cycle time and precedence constraints are satisfied, and the total cost is minimised. In this paper, we first present a mathematical model and improve it with preprocessing techniques. Then, we propose a constructive heuristic and a variable neighbourhood descent that are useful to solve large instances. Extensive computational experiments on benchmark instances prove the effectiveness of the algorithms.

2021 - New Exact Techniques Applied to a Class of Network Flow Formulations [Relazione in Atti di Convegno]
de Lima, V. L.; Iori, M.; Miyazawa, F. K.
abstract

We propose a number of solution techniques for general network flow formulations derived from Dantzig-Wolfe decompositions. We present an arc selection method to derive reduced network flow models that may potentially provide good feasible solutions. This method is explored as a variable selection rule for branching. With the aim of improving reduced-cost variable-fixing, we also propose a method to produce different dual solutions of network flow models and provide conditions that guarantee the correctness of the method. We embed the proposed techniques in an innovative branch-and-price method for network flow formulations, and test it on the cutting stock problem. In our computational experiments, 162 out of 237 open benchmark instances are solved to proven optimality within a reasonable computational time, consistently improving previous results in the literature.

2021 - On Solving the Time Window Assignment Vehicle Routing Problem via Iterated Local Search [Relazione in Atti di Convegno]
Martins, Lucas Burahem; Iori, Manuel; Moreira, Mayron César O.; Zucchi, Giorgio
abstract

In this paper, we propose a combined algorithm based on an Iterated Local Search (ILS) and a mathematical model to solve the Time Window Assignment Vehicle Routing Problem (TWAVRP). The TWAVRP appears when the volume of customer demands is uncertain and time windows should be allocated to customers so as to minimize expected travel costs. Our goal is to find a heuristic strategy that can efficiently improve the current TWAVRP solution methods in the literature. For this purpose, we first use an ILS algorithm to generate feasible sets of routes. Then, we invoke a Mixed Integer Linear Programming formulation that assigns time windows to customers and selects the subset of routes of minimum expected cost. Computational results performed on benchmark instances show that our algorithm is competitive with respect to the literature, especially for instances with more than 45 clients.

2021 - Personnel scheduling during Covid-19 pandemic [Articolo su rivista]
Zucchi, Giorgio; Iori, Manuel; Subramanian, Anand
abstract

This paper addresses a real-life personnel scheduling problem in the context of Covid19 pandemic, arising in a large Italian pharmaceutical distribution warehouse. In this case study, the challenge is to determine a schedule that attempts to meet the contractual working time of the employees, considering the fact that they must be divided into mutually exclusive groups to reduce the risk of contagion. To solve the problem, we propose a mixed integer linear programming formulation (MILP). The solution obtained indicates that optimal schedule attained by our model is better than the one generated by the company. In addition, we performed tests on random instances of larger size to evaluate the scalability of the formulation. In most cases, the results found using an open-source MILP solver suggest that high quality solutions can be achieved within an acceptable CPU time. We also project that our findings can be of general interest for other personnel scheduling problems, especially during emergency scenarios such as those related to Covid-19 pandemic.

2021 - Scheduling of Parallel Print Machines with Sequence-Dependent Setup Costs: A Real-World Case Study [Relazione in Atti di Convegno]
Iori, M.; Locatelli, A.; Locatelli, M.
abstract

In the present work, we consider a real-world scheduling problem arising in the color printing industry. The problem consists in assigning print jobs to a heterogeneous set of flexographic printer machines, as well as in finding a processing sequence for the sets of jobs assigned to each printer. The aim is to minimize a weighted sum of total weighted tardiness and total setup times. The machines are characterized by a limited sequence of color groups and can equip additional components (e.g., embossing rollers and perforating rolls) to process jobs that require specific treatments. The process to equip a machine with an additional component or to clean a color group takes a long time, with the effect of significantly raising the setup costs. Furthermore, the time required to clean a color group between two different jobs depends directly on the involved colors. To tackle the problem, we propose a constructive heuristic followed by some local search procedures that are used one after the other in an iterative way. Extensive tests on real-world instances prove that the proposed algorithm can obtain very good-quality solutions within a limited computing time.

2021 - Scheduling of Patients in Emergency Departments with a Variable Neighborhood Search [Relazione in Atti di Convegno]
Alves de Queiroz, T.; Iori, M.; Kramer, A.; Kuo, Y. -H.
abstract

The dynamic scheduling of patients to doctors in an emergency department environment is tackled in this work. We consider the case in which patients arrive dynamically during the working hours, and the objective is to minimize the weighted tardiness. We propose a greedy heuristic based on priority queues and a general variable neighborhood search (GVNS). In the greedy heuristic, patients are scheduled by observing their urgency, while in the GVNS, the schedule is optimized every time a patient arrives. The GVNS uses six neighborhood structures and a variable neighborhood descent to perform the local search. The GVNS also handles the static problem whose solution can be used as a reference for the dynamic one. Computational results on 80 instances show that using the GVNS better approximates the static problem, besides giving an overall reduction of 66.8% points over the greedy heuristic.

2021 - Smart-Meter Installation Scheduling in the Context of Water Distribution [Abstract in Atti di Convegno]
Baschieri, Davide; Iori, Manuel; Magni, Carlo Alberto; Marchioni, Andrea; Vezzali, Dario
abstract

In this work, we propose a Mixed Integer Linear Programming (MILP) formulation to model a Smart-Meter Installation Scheduling Problem (SMISP) in the context of water distribution. The model has been used to solve a real case study from a multi-utility company operating in the Italian market. Specifically, in compliance with the European and the Italian regulations on metering, a distribution company is obligated to periodically control meters and substitute them in case they have reached their lifespan. In the examined case study, the multi-utility company has opted for a massive substitution plan in order to install innovative “walk-by smart-meters” in place of traditional mechanical meters. The MILP formulation aims at integrating both the operational and the financial perspective of the SMISP. In particular, the objective function has been carefully defined in order to maximize the Net Present Value (NPV) of the massive substitution plan, including the operational savings produced by using the walk-by smart-meters, the additional incomes originating from the gradual charge of substitution costs on customers’ invoices as considered by the Italian Authority, the depreciation of walk-by smart-meters, the investment costs, and the impact of income taxes on the objective function. The final goal of the proposed formulation is to define a scheduling for the massive substitution plan that satisfies a number of operational constraints and produces the maximum NPV.

2021 - Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events [Articolo su rivista]
Delorme, M.; Iori, M.; Mendes, N. F. M.
abstract

In this work, we study the problem of scheduling jobs and maintenance activities on a set of unrelated parallel machines, by considering that the processing time of a job increases according to a deterioration factor that depends both on the machine and on the set of jobs the machine has processed since its last maintenance. The objective we consider is to minimize the makespan. We introduce four mixed integer linear programming models, two of which using big-M constraints and the other two using an exponential number of variables. We also propose an iterated local search metaheuristic to tackle large size instances and we provide empirical evidence of the performance of the proposed approaches by means of extensive computational experiments.

2020 - A Decision Support System for Attended Home Services [Articolo su rivista]
Bruck, Bruno P.; Castegini, Filippo; Cordeau, Jean-François; Iori, Manuel; Poncemi, Tommaso; Vezzali, Dario
abstract

This paper describes a decision support system developed to solve a practical attended home services problem faced by Iren Group, an Italian multiutility company operating in the distribution of electricity, gas, and water. The company operates in several regions across Italy and aims to optimize the dispatching of technicians to customer lo- cations where they perform installations, closures, or maintenance activities within time slots chosen by the customers. The system uses historical data and helps operations managers in performing a number of strategic decisions: grouping municipalities into clusters; designing sets of model-weeks for each cluster; evaluating the obtained solutions by means of a dynamic rolling horizon simulator; and providing as output several key performance indicators, as well as visual optimized technician routing plans to analyze different scenarios. The system uses mathematical models and heuristic algorithms that have been specifically developed to take into account different service levels. Computational experiments carried out on data provided by the company confirm the efficiency of the proposed methods. These methods also constitute a powerful tool that can be used by the company not only to reduce costs but also to help them in their strategic evaluation of existing and potential market opportunities.

2020 - A Decision Support System for a Multi-trip Vehicle Routing Problem with Trucks and Drivers Scheduling [Relazione in Atti di Convegno]
Iori, Manuel; Mendes, Nilson
abstract

Many real-world transportation problems can be modeled as variants of the well-known vehicle routing problem (VRP), where a fleet of vehicles based at a central depot is used to deliver freight to clients at a minimum cost. Frequently, the problems defined in the VRP literature and the corresponding solution algorithms do not catch all the problem features incurred by the companies in their every-day activity, and further flexibility is needed during the decision process to make adjustments on the fly. In this paper, we present a decision support system developed for an Italian pharmaceutical distribution company to deal with a Multi-Trip VRP characterized by additional constraints and Truck and Driver Scheduling. The problem is solved in the software with a two-phase algorithm: the first phase consists of an Iterated Local Search metaheuristic that defines the vehicle routes, whereas the second phase invokes a mathematical model to assign trucks and drivers to the routes. The software allows, between the two phases, changes in the solution to better fit the company requirements. Computational results prove the effectiveness of the proposed method.

2020 - A Location-allocation model for fog computing infrastructures [Relazione in Atti di Convegno]
De Queiroz, T. A.; Canali, C.; Iori, M.; Lancellotti, R.
abstract

The trend of an ever-increasing number of geographically distributed sensors producing data for a plethora of applications, from environmental monitoring to smart cities and autonomous driving, is shifting the computing paradigm from cloud to fog. The increase in the volume of produced data makes the processing and the aggregation of information at a single remote data center unfeasible or too expensive, while latency-critical applications cannot cope with the high network delays of a remote data center. Fog computing is a preferred solution as latency-sensitive tasks can be moved closer to the sensors. Furthermore, the same fog nodes can perform data aggregation and filtering to reduce the volume of data that is forwarded to the cloud data centers, reducing the risk of network overload. In this paper, we focus on the problem of designing a fog infrastructure considering both the location of how many fog nodes are required, which nodes should be considered (from a list of potential candidates), and how to allocate data flows from sensors to fog nodes and from there to cloud data centers. To this aim, we propose and evaluate a formal model based on a multi-objective optimization problem. We thoroughly test our proposal for a wide range of parameters and exploiting a reference scenario setup taken from a realistic smart city application. We compare the performance of our proposal with other approaches to the problem available in literature, taking into account two objective functions. Our experiments demonstrate that the proposed model is viable for the design of fog infrastructure and can outperform the alternative models, with results that in several cases are close to an ideal solution.

2020 - A branch-and-price algorithm for the temporal bin packing problem [Articolo su rivista]
Dell'Amico, M.; Furini, F.; Iori, M.
abstract

We study an extension of the classical Bin Packing Problem, where each item consumes the bin capacity during a given time window that depends on the item itself. The problem asks for finding the minimum number of bins to pack all the items while respecting the bin capacity at any time instant. A polynomial-size formulation, an exponential-size formulation, and a number of lower and upper bounds are studied. A branch-and-price algorithm for solving the exponential-size formulation is introduced. An overall algorithm combining the different methods is then proposed and tested through extensive computational experiments.

2020 - Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems [Articolo su rivista]
Delorme, Maxence; Iori, Manuel
abstract

We study pseudopolynomial formulations for the classical bin packing and cutting stock problems. We first propose an overview of dominance and equivalence relations among the main pattern-based and pseudopolynomial formulations from the literature. We then introduce reflect, a new formulation that uses just half of the bin capacity to model an instance and needs significantly fewer constraints and variables than the classical models. We propose upper- and lower-bounding techniques that make use of column generation and dual information to compensate reflect weaknesses when bin capacity is too high. We also present nontrivial adaptations of our techniques that solve two interesting problem variants, namely the variable-sized bin packing problem and the bin packing problem with item fragmentation. Extensive computational tests on benchmark instances show that our algorithms achieve state of the art results on all problems, improving on previous algorithms and finding several new proven optimal solutions.

2020 - Exact solution techniques for two-dimensional cutting and packing [Articolo su rivista]
Iori, M.; de Lima, V. L.; Martello, S.; Miyazawa, F. K.; Monaci, M.
abstract

We survey the main formulations and solution methods for two-dimensional orthogonal cutting and packing problems, where both items and bins are rectangles. We focus on exact methods and relaxations for the four main problems from the literature: finding a packing with minimum height, packing the items into the minimum number of bins, finding a packing of maximum value, and determining the existence of a feasible packing.

2020 - Facing Implementation Barriers to Healthcare Simulation Studies [Relazione in Atti di Convegno]
Dosi, C.; Iori, M.; Kramer, A.; Vignoli, M.
abstract

Implementation barriers to simulation studies are a reality in today's healthcare organizations. This work proposes a novel framework to use simulation to maximise successful implementation by (1) framing the right problem to face; (2) using what-if scenarios as an exploration tool for users’ value; (3) supporting knowledge integration in giving tangible results to discuss among different professionals. We successfully tested the framework in an 18-month Emergency Department overcrowding case study, by developing a Discrete Events Simulation model and using it as a decision making tool for a multi-disciplinary group of 21 professionals (doctors, nurses, aid nurses, hospital management and engineers expert in simulation). Results show that the framework helps finding the most implementable solutions in the context of study, under the rationale that a small implemented improvement is preferable than a big one on paper. In the presented case study, after 15 years of absence of organisational change, the hospital was able to implement three new simulated solutions in 18 months.

2020 - Improved flow-based formulations for the skiving stock problem [Articolo su rivista]
Martinovic, J.; Delorme, M.; Iori, M.; Scheithauer, G.; Strasdat, N.
abstract

Thanks to the rapidly advancing development of (commercial) MILP software and hardware components, pseudo-polynomial formulations have been established as a powerful tool for solving cutting and packing problems in recent years. In this paper, we focus on the one-dimensional skiving stock problem (SSP), where a given inventory of small items has to be recomposed to obtain a maximum number of larger objects, each satisfying a minimum threshold length. In the literature, different modeling approaches for the SSP have been proposed, and the standard flow-based formulation has turned out to lead to the best trade-off between efficiency and solution time. However, especially for instances of practically meaningful sizes, the resulting models involve very large numbers of variables and constraints, so that appropriate reduction techniques are required to decrease the numerical efforts. For that reason, this paper introduces two improved flow-based formulations for the skiving stock problem that are able to cope with much larger problem sizes. By means of extensive experiments, these new models are shown to possess significantly fewer variables as well as an average better computational performance compared to the standard arcflow formulation.

2020 - Mathematical Models and Search Algorithms for the Capacitated p-Center Problem [Articolo su rivista]
Ribeiro Kramer, Raphael; Iori, Manuel; Vidal, Thibaut
abstract

The capacitated p-center problem requires one to select p facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility. The problem is well known in the field of facility location, because of the many applications that it can model. In this paper, we solve it by means of search algorithms that iteratively seek the optimal distance by solving tailored subproblems. We present different mathematical formulations for the subproblems and improve them by means of several valid inequalities, including an effective one based on a 0–1 disjunction and the solution of subset sum problems. We also develop an alternative search strategy that finds a balance between traditional sequential search and binary search. This strategy limits the number of feasible subproblems to be solved and, at the same time, avoids large overestimates of the solution value, which are detrimental for the search. We evaluate the proposed techniques by means of extensive computational experiments on benchmark instances from the literature and new larger test sets. All instances from the literature with up to 402 vertices and integer distances are solved to proven optimality, including 13 open cases, and feasible solutions are found in 10 minutes for instances with up to 3,038 vertices.

2020 - Optimization Methods for the Same-Day Delivery Problem [Capitolo/Saggio]
Côté, Jean-François; de Queiroz, Thiago Alves; Gallesi, Francesco; Iori, Manuel
abstract

In the same-day delivery problem, requests with restricted time windows arrive during a given time horizon and it is necessary to decide which requests to serve and how to plan routes accordingly. We solve the problem with a dynamic stochastic method that invokes a generalized route generation function combined with an adaptive large neighborhood search heuristic. The heuristic is composed of destroying and repairing operators. The generalized route generation function takes advantage of sampled-scenarios, which are solved with the heuristic, to determine which decisions should be taken at any instant. Results obtained on different benchmark instances prove the effectiveness of the proposed method in comparison with a consensus function from the literature, with an average decrease of 10.7%, in terms of solution cost, and 24.5%, in terms of runtime.

2020 - Optimizing the Nozzle Path in the 3D Printing Process [Relazione in Atti di Convegno]
Iori, Manuel; Novellani, Stefano
abstract

In this paper, we define the 3D printing routing problem, the problem of finding the optimal path of the nozzle in a fused deposition modeling 3D printing system, so as to minimize the time required to create on object. We formally model the problem with an integer linear programming formulation and then solve it via heuristic algorithms. We test the algorithms on a set of large-size real-life instances, comparing them with one of the most widely used open source software for the problem. We show that large time reductions can be obtained. We finally propose a set of interesting directions for future research.

2020 - Reactive GRASP-Based Algorithm for Pallet Building Problem with Visibility and Contiguity Constraints [Relazione in Atti di Convegno]
Iori, M.; Locatelli, M.; Moreira, M. C. O.; Silveira, T.
abstract

In this paper, we study a pallet building problem that originates from a case study in a company that produces robotized systems for freight transportation and logistics. The problem takes into account well-known constraints, such as rotation and stackability, and other specific constraints such as visibility and contiguity among items belonging to the same family. We formalize the problem and then solve it by means of a GRASP metaheuristic. The algorithm is based on an Extreme Points heuristic and a reactive mechanism. It uses a two-step strategy, in which items are first grouped into horizontal layers, and then layers are stacked one over the other to form pallets. The performance of the algorithm is assessed through extensive computational tests on real-world instances. The results show that the GRASP is able to create very compact packings for most of the instances with a limited computational effort.

2020 - Solution of a practical pallet building problem with visibility and contiguity constraints [Relazione in Atti di Convegno]
Iori, M.; Locatelli, M.; Moreira, M. C. O.; Silveira, T.
abstract

We study a pallet building problem that originates from a case study at a company that produces pallet building robotized systems. The problem takes into account well known constraints, such as rotation and stackability, and we introduce two practical constraints named visibility and contiguity between items of the same type. We formalize the problem and propose heuristic algorithms to solve it, using a strategy that first creates 2D layers and, then, creates the final 3D pallets. The proposed heuristic is based mainly on the Extreme Points heuristic, that is tailored to choose feasible positions to pack items during the construction of the solution. Besides that, we adapt our proposed heuristic using other basic heuristics from the literature, considering different constraints. The performance of the algorithms is assessed through extensive computational tests on real-world instances, and the obtained results show the proposed heuristics are able to create compact packing in a very short time.

2020 - Solution of minimum spanning forest problems with reliability constraints [Articolo su rivista]
Ahani, Ida Kalateh; Salari, Majid; Hosseini, Seyed Mahmoud; Iori, Manuel
abstract

We propose the reliability constrained k-rooted minimum spanning forest, a relevant optimization problem whose aim is to find a k-rooted minimum cost forest that connects given customers to a number of supply vertices, in such a way that a minimum required reliability on each path between a customer and a supply vertex is satisfied and the cost is a minimum. The reliability of an edge is the probability that no failure occurs on that edge, whereas the reliability of a path is the product of the reliabilities of the edges in such path. The problem has relevant applications in the design of networks, in fields such as telecommunications, electricity and transports. For its solution, we propose a mixed integer linear programming model, and an adaptive large neighborhood search metaheuristic which invokes several shaking and local search operators. Extensive computational tests prove that the metaheuristic can provide good quality solutions in very short computing times.

2019 - A Decision Support System to Evaluate Suppliers in the Context of Global Service Providers [Abstract in Atti di Convegno]
Bruck, Bruno Petrato; Iori, Manuel; Pretolani, Daniele; Vezzali, Dario
abstract

In this work, we propose a decision support system (DSS) to evaluate a set of suppliers by considering a multiplicity of variables. The DSS has been implemented to solve a real problem faced by a Global Service Provider (GSP) operating in the Italian market, and is based on a simplified Analytic Hierarchy Process (AHP) application. GSPs operate in the field of facility management, providing customers with general maintenance services for their real estate assets. To realize this purpose, they subcontract to selected suppliers the execution of services. A comprehensive and multi-criteria evaluation of suppliers is the key element to select the most fitting one for a specific service requested by a particular customer. This process of suppliers’ selection directly affects success and duration of the relationship between the GSP and its customers. The content of our work consists of five parts: first, variables identification and description, necessary to create an objective and comprehensive evaluation of GSP’s suppliers; second, weights calculation of defined variables accordingly to the AHP method; third, mathematical model formulation in order to precisely describe the decision problem; fourth, data collection and database creation containing all of the raw data necessary to perform the evaluation; fifth, DSS development and test with potential users through a web application prototype specifically developed for the problem.

2019 - A dial-a-ride problem using private vehicles and alternative nodes [Articolo su rivista]
Brevet, D.; Duhamel, C.; Iori, M.; Lacomme, P.
abstract

This paper addresses the dial-a-ride problem (DARP) using private vehicles and alternative nodes (DARP-PV-AN). The DARP consists of creating vehicle routes in order to ensure a set of users’ transportation requests. Each request corresponds to a client needing to be transported from his/her origin to his/her destination. Routing costs have to be minimized while respecting a set of constraints like time windows and maximum route length. In the classical DARP, vehicles have to start from a depot and come back to it at the end of their route. In the DARP-PV-AN, the on-demand transportation service can be done either by a public fleet or by clients that use their private vehicles. The use of these vehicles adds more flexibility and unclog the public transportation fleet by allowing clients to organize their own transportation. However, it also raises some privacy concerns. The DARP-PV-AN addresses these concerns and focuses on location privacy, i.e., the ability to prevent the third parties from learning clients’ locations, by keeping both original and final locations private. This is addressed by setting several pickup/delivery nodes for the transportation requests, thus masking the private address. A compact mixed integer linear model is presented, and an evolutionary local search (ELS) is proposed to compute solutions of good quality for the problem. These methods are benchmarked on a modified set of benchmark instances. A new set of realistic instances is also provided to test the ELS in a more realistic way.

2019 - A scalable exact algorithm for the vertex p-center problem [Articolo su rivista]
Contardo, Claudio; Iori, Manuel; Kramer, Raphael
abstract

The vertex p-center problem consists in selecting p centers among a finite set of candidates and assigning a set of clients to them, with the aim of minimizing the maximum dissimilarity between a client and its associated center. State-of-the-art algorithms for the problem are based on the solution of a series of covering subproblems, and are particularly efficient when additional reduction rules are used to limit the size of the subproblems. In fact, these algorithms do not scale well when the cardinality of the dissimilarity matrix grows above a few million entries, as the time and space required to compute and store the matrix start dominating those required for solving the subproblems. We introduce a scalable relaxation-based iterative algorithm that does not rely on the computation of the entire matrix, but rather relies on the computation of a typically much smaller sub-matrix that is only enlarged if deemed necessary. This method can solve to proven optimality p-center problems derived from the TSP library and containing up to one million clients for small but realistic values of p.

2019 - An Improved Arcflow Model for the Skiving Stock Problem [Relazione in Atti di Convegno]
Martinovic, John; Delorme, Maxence; Iori, Manuel; Scheithauer, Guntram
abstract

Because of the sharp development of (commercial) MILP software and hardware components, pseudo-polynomial formulations have been established as a viable tool for solving cutting and packing problems in recent years. Constituting a natural (but independent) counterpart of the well-known cutting stock problem, the one-dimensional skiving stock problem (SSP) asks for the maximal number of large objects (specified by some threshold length) that can be obtained by recomposing a given inventory of smaller items. In this paper, we introduce a new arcflow formulation for the SSP applying the idea of reflected arcs. In particular, this new model is shown to possess significantly fewer variables as well as a better numerical performance compared to the standard arcflow formulation.

2019 - Computational Simulation as an Organizational Prototyping Tool [Relazione in Atti di Convegno]
Dosi, Clio; Iori, Manuel; Kramer, Arthur; Vignoli, Matteo
abstract

This case study deals with a redesign effort to face the overcrowding issue in an Emergency Department (ED). A multidiscinary group of healthcare professionals and engineers worked together to improve the actual processes. We integrate the simulation modeling in a human-centered design method. We use the simulation technique as a learning and experimentation tool into a design thinking process: the computational descrete event simulation helps explore the possibile scenarios to be prototyped. We used the simulation to create a virtual prototyping environment, to help the group start a safe ideation and prototyping effort. Virtual prototyping injected into the organizational context the possibility of experimenting. It represented a cognitive low-risk environment where professionals could explore possible alternative solutions. Upon those solutions, we developed organizational prototyping tools. Top management and head physicians gained confidence for a more grounded decision making effort and important choices of change management and investments have been made.

2019 - Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines [Articolo su rivista]
DE LUCENA KRAMER, ARTHUR HARRY FREDERICO; Dell'Amico, Mauro; Iori, Manuel
abstract

We consider the problem of scheduling a set of jobs on a set of identical parallel machines, with the aim of minimizing the total weighted completion time. The problem has been solved in the literature with a number of mathematical formulations, some of which require the implementation of tailored branch-and-price methods. In our work, we solve the problem instead by means of new arc-flow formulations, by first representing it on a capacitated network and then invoking a mixed integer linear model with a pseudo-polynomial number of variables and constraints. According to our computational tests, existing formulations from the literature can solve to proven optimality benchmark instances with up to 100 jobs, whereas our most performing arc-flow formulation solves all instances with up to 400 jobs and provides very low gap for larger instances with up to 1000 jobs.

2019 - Mathematical models and decomposition methods for the multiple knapsack problem [Articolo su rivista]
Dell'Amico, Mauro; Delorme, Maxence; Iori, Manuel; Martello, Silvano
abstract

We consider the multiple knapsack problem, that calls for the optimal assignment of a set of items, each having a profit and a weight, to a set of knapsacks, each having a maximum capacity. The problem has relevant managerial implications and is known to be very difficult to solve in practice for instances of realistic size. We review the main results from the literature, including a classical mathematical model and a number of improvement techniques. We then present two new pseudo-polynomial formulations, together with specifically tailored decomposition algorithms to tackle the practical difficulty of the problem. Extensive computational experiments show the effectiveness of the proposed approaches.

2019 - Mathematical models for Multi Container Loading Problems with practical constraints [Articolo su rivista]
Alonso, M. T.; Alvarez-Valdes, R.; Iori, M.; Parreño, F.
abstract

We address the multi container loading problem of a company that serves its customers’ orders by building pallets with the required products and loading them into trucks. The problem is solved by using integer linear models. To be useful in practice, our models consider three types of constraints: geometric constraints, so that pallets lie completely inside the trucks and do not overlap; weight constraints, defining the maximum weights supported by a truck and by each axle, as well as the position of the centre of gravity of the cargo; and dynamic stability constraints. These last constraints forbid empty spaces between pallets to avoid cargo displacement when the truck is moving, and limit differences between the heights of adjacent pallets to prevent tall pallets tipping over short ones. We also consider extensions of the models to the case of heavy loads, requiring a special configuration of the pallets in the truck, and to the case in which the orders must be served over a set of time periods to meet delivery dates. The computational study that we performed on a large number of real instances with up to 44 trucks shows that the proposed models are able to obtain optimal solutions in most cases and very small gaps when optimality could not be proven.

2019 - Novel formulations and modeling enhancements for the dynamic berth allocation problem [Articolo su rivista]
Kramer, Arthur; Lalla-Ruiz, Eduardo; Iori, Manuel; Voß, Stefan
abstract

This paper addresses the well-known dynamic berth allocation problem (DBAP), which finds numerous applications at container terminals aiming to allocate and schedule incoming container vessels into berthing positions along the quay. Due to its impact on ports’ performance, having efficient DBAP formulations is of great importance, especially for determining optimal schedules in quick time as well as aiding managers and developers in the assessment of solution strategies and approximate approaches. In this work, we propose two novel formulations, a time-indexed formulation and an arc-flow one, to efficiently tackle the DBAP. Additionally, to improve computational performance, we propose problem-based modeling enhancements and a variable-fixing procedure that allows to discard some variables by considering their reduced costs. By means of these contributions, we improve the models’ performance in those instances where the optimal solutions were already known, and we solve to optimality for the first time other instances from the literature.

2019 - Rich vehicle routing with auxiliary depots and anticipated deliveries: An application to pharmaceutical distribution [Articolo su rivista]
Kramer, R.; Cordeau, J. -F.; Iori, M.
abstract

We present and solve a rich vehicle routing problem based on a practical distribution problem faced by a third-party logistics provider, whose aim is to deliver pharmaceutical products to healthcare facilities in Tuscany. The problem is characterized by having multiple depots, a heterogeneous fleet of vehicles, flexible time windows, periodic demands, incompatibilities between vehicles and customers, a maximum duration for the routes, and a maximum number of customers per route. A multi-start iterated local search algorithm making use of several neighborhoods is proposed to solve the problem. The algorithm has been tested on a large number of instances and obtained good results, both on the real case study and on a number of artificially generated instances.

2019 - The Static Bike Sharing Rebalancing Problem with Forbidden Temporary Operations [Articolo su rivista]
Bruck, Bruno; Cruz, Fabio; Iori, Manuel; Subramanian, Anand
abstract

This paper introduces and solves the static bike rebalancing problem with for bidden temporary operations. In this problem, one aims at finding a minimum cost route in which a vehicle performs a series of pickup and delivery operations while satisfying demand and capacity constraints. In addition, a vehicle can visit stations multiple times but cannot use them to temporarily store or provide bikes. Apart from bike rebalancing, the problem also models courier service transportation and repositioning of inventory between retail stores, where temporary operations are frequently disliked because they require additional manual work and service time. We present some theoretical results concerning problem complexity and worst-case analysis, and then propose three exact algorithms based on different mathematical formulations. Extensive computational results on instances involving up to 80 stations show that an exact algorithm based on a minimal extended network produces the best average results.

2018 - A practical time slot management and routing problem for attended home services [Articolo su rivista]
Bruck, Bruno P.; Cordeau, Jean-François; Iori, Manuel
abstract

This paper describes the solution methodology developed to address an attended home delivery problem faced by an Italian provider of gas, electricity, and water services. This company operates in several regions and must dispatch technicians to customer locations where they carry out installation or maintenance activities within time intervals chosen by the customers. The problem consists of creating time slot tables specifying the amount of resources allocated to each region in each time slot, and of routing technicians in a cost-effective way. We propose a large neighborhood search (LNS) heuristic to create time slot tables by relying on various simulation strategies to represent the behavior of customers and on an integer linear program to optimize the routing of technicians. In addition, we also use a second integer program as a repair mechanism inside the LNS heuristic. Computational experiments carried out on data provided by the company confirm the efficiency of the proposed methodology.

2018 - BPPLIB: a library for bin packing and cutting stock problems [Articolo su rivista]
Delorme, Maxence; Iori, Manuel; Martello, Silvano
abstract

The bin packing problem (and its variant, the cutting stock problem) is among the most intensively studied combinatorial optimization problems. We present a library of computer codes, benchmark instances, and pointers to relevant articles for these two problems. The library is available at http://or.dei.unibo.it/library/bpplib. The computer code section includes twelve programs: seven are directly downloadable from the library page, while for the remaining five we provide addresses where they can be obtained or downloaded. Some of the codes for which we provide an original C++ implementation need an integer linear programming solver. For such cases, the library provides two versions: one that uses the commercial solver CPLEX, and one that uses the freeware solver SCIP. The benchmark section provides over six thousands instances (partly coming from the literature and partly randomly generated), together with the corresponding solutions. Instances that are difficult to solve to proven optimality are included. The library also includes a BibTeX file of more than 150 references on this topic and an interactive visual tool to manually solve bin packing and cutting stock instances. We conclude this work by reporting the results of new computational experiments on a number of computer codes and benchmark instances.

2018 - Exact and heuristic algorithms for the interval min-max regret generalized assignment problem [Articolo su rivista]
Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori
abstract

We consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. This problem models many real-world applications in which jobs must be assigned to agents but the costs of assignment may vary after the decision has been taken. We computationally examine two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. We also examine exact algorithmic approaches (Benders-like decomposition and branch-and-cut) and further introduce a more sophisticated algorithm that incorporates various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.

2018 - Mathematical models and decomposition algorithms for makespan minimization in plastic rolls production [Articolo su rivista]
Nesello, Vitor; Delorme, Maxence; Iori, Manuel; Subramanian, Anand
abstract

We study an optimization problem that originates from the packaging industry, and in particular in the process of blown film extrusion, where a plastic film is used to produce rolls of different dimensions and colors. The film can be cut along its width, thus producing multiple rolls in parallel, and setup times must be considered when changing from one color to another. The optimization problem that we face is to produce a given set of rolls on a number of identical parallel machines by minimizing the makespan. The problem combines together cutting and scheduling decisions and is of high complexity. For its solution, we propose mathematical models and heuristic algorithms that involve a nontrivial decomposition method. By means of extensive computational experiments, we show that proven optimality can be achieved only on small instances, whereas for larger instances good quality solutions can be obtained especially by the use of an iterated local search algorithm.

2018 - The Bike sharing Rebalancing Problem with Stochastic Demands [Articolo su rivista]
Dell'Amico, Mauro; Iori, Manuel; Novellani, Stefano; Subramanian, Anand
abstract

In this paper we deal with the stochastic version of a problem arising in the context of self-service bike sharing systems, which aims at determining minimum cost routes for a fleet of homogeneous vehicles in order to redistribute bikes among stations. The Bike sharing Rebalancing Problem with Stochastic Demands is a variant of the one-commodity many-to-many pickup and delivery vehicle routing problem where demands at each station are represented by random variables, with associated probability distributions, that depend on stochastic scenarios. We develop stochastic programming models that are solved using different approaches, in particular, the L-Shaped and branch-and-cut. Moreover, we also propose heuristic algorithms based on an innovative use of positive and negative correlations among stations’ stochastic demands, as well as an efficient strategy for checking feasibility. The proposed solution approaches are evaluated and compared by means of extensive computational experiments on newly realistic benchmark instances.

2018 - The Meet-in-the-Middle Principle for Cutting and Packing Problems [Articolo su rivista]
Côté, Jean-François; Iori, Manuel
abstract

Cutting and packing (C&P) is a fundamental research area that models a large number of managerial and industrial optimization issues. A solution to a C&P problem basically consists of a set of one-dimensional or multidimensional items packed in/cut from one or more bins, by satisfying problem constraints and minimizing a given objective function. Normal patterns are a well-known C&P technique used to build solutions where each item is aligned to the bottom of the bin along each dimension. They are used in several C&P techniques because they can reduce the search space while preserving optimality, but their limit is that their number grows consistently when number of items and size of the bin increase. In this paper we propose a new set of patterns, called meet in the middle, that preserves optimality and leads to several interesting results. Their computation is achieved with the same time complexity as that of the normal patterns, but their number is never higher, and in practical applications it frequently shows reductions of about 50%. These new patterns are applied to improve some exact state-of-the-art C&P techniques, including arc-flow formulations, combinatorial branch-and-bound algorithms, and mixed-integer linear programs. The efficacy of the improved techniques is assessed by extensive computational tests on a number of relevant applications.

2017 - A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints [Articolo su rivista]
Kramer, Raphael; Dell'Amico, Mauro; Iori, Manuel
abstract

In this paper, we propose a generalisation of the bin packing problem, obtained by adding precedences between items that can assume heterogeneous non-negative integer values. Such generalisation also models the well-known Simple Assembly Line Balancing Problem of type I. To solve the problem, we propose a simple and effective iterated local search algorithm that integrates in an innovative way of constructive procedures and neighbourhood structures to guide the search to local optimal solutions. Moreover, we apply some preprocessing procedures and adapt classical lower bounds from the literature. Extensive computational experiments on benchmark instances suggest that the developed algorithm is able to generate good quality solutions in a reasonable computational time.

2017 - A heuristic algorithm for a single vehicle static bike sharing rebalancing problem [Articolo su rivista]
Cruz, Fábio; Subramanian, Anand; Bruck, Bruno P.; Iori, Manuel
abstract

The static bike rebalancing problem (SBRP) concerns the task of repositioning bikes among stations in self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes from a station (even all of them), thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This paper deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to find a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station must be appropriately determined in order to respect such constraints. We propose an iterated local search (ILS) based heuristic to solve the problem. The ILS algorithm was tested on 980 benchmark instances from the literature and the results obtained are competitive when compared to other existing methods. Moreover, our heuristic was capable of finding most of the known optimal solutions and also of improving the results on a number of open instances.

2017 - Logic based Benders' decomposition for orthogonal stock cutting problems [Articolo su rivista]
Delorme, Maxence; Iori, Manuel; Martello, Silvano
abstract

We consider the problem of packing a set of rectangular items into a strip of fixed width, without overlapping, using minimum height. Items must be packed with their edges parallel to those of the strip, but rotation by 90° is allowed. The problem is usually solved through branch-and-bound algorithms. We propose an alternative method, based on Benders' decomposition. The master problem is solved through a new ILP model based on the arc flow formulation, while constraint programming is used to solve the slave problem. The resulting method is hybridized with a state-of-the-art branch-and-bound algorithm. Computational experiments on classical benchmarks from the literature show the effectiveness of the proposed approach. We additionally show that the algorithm can be successfully used to solve relevant related problems, like rectangle packing and pallet loading.

2017 - Mathematical models for multicontainer loading problems [Articolo su rivista]
Alonso, M. T; Alvarez Valdes, R.; Iori, Manuel; Parreño, F.; Tamarit, J. M.
abstract

This paper deals with the problem of a distribution company that has to serve its customers by putting first the products on pallets and then loading the pallets onto trucks. We approach the problem by developing and solving integer linear models. We start with basic models, that include the essential features of the problem, such as respecting the dimensions of the truck, and not exceeding the total weight capacity and the maximum weigh capacity on each axle. Then, we add progressively new conditions to consider the weight and volume of pallet bases and to include other desirable features for the solutions to be useful in practice, such as the position of the center of gravity and the minimization of the number of pallets.The models have been tested on a large set of real instances involving up to 46 trucks and kindly provided to us by a distribution company. The results show that in most cases the optimal solution can be obtained in small running times. Moreover, when optimality cannot be proven, the gap is very small, so we obtain high quality solutions for all the instances that we tested.

2017 - Minimizing CO2 emissions in a practical daily carpooling problem [Articolo su rivista]
Bruck, Bruno P; Incerti, Valerio; Iori, Manuel; Vignoli, Matteo
abstract

Governments, as well as companies and individuals, are increasingly aware of the damages to the environment caused by human activities. In this sense, the reduction of CO2 emissions is an important topic that is pursued through a range of practices. A relevant example is carpooling, which is defined as the act of individuals sharing a single car. In this paper we approach a practical case found in an Italian service company. Our objective is to develop an integrated web application to be used by the employees of this company to organize carpooling crews on a daily basis, so as to reach a common destination. We look for possible crews by the use of mathematical formulations and heuristic algorithms. The heuristic algorithms are then embedded into the web application to provide users with carpooling solutions. Experimental results attest for a great potential in CO2 savings by the use of carpooling in the real-world scenario as well as in newly generated instances.

2017 - Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries [Articolo su rivista]
Bruck, Bruno; Iori, Manuel
abstract

We study the class of one-to-many-to-one single vehicle routing problems with pickups and deliveries, in which a single capacitated vehicle is used to serve a set of customers requiring a delivery, a pickup, or both. These problems have many real-world applications, including beverage distribution, courier service transportation, and reverse logistics. We first concentrate on a well-studied problem in this class, known as the single vehicle routing problem with deliveries and selective pickups (SVRPDSP), in which deliveries are mandatory but pickups are optional and generate a revenue if performed, and customers requiring both a delivery and a pickup (combined demand) can be visited either once or twice. Most exact algorithms in the literature solve SVRPDSP by looking for Elementary tours on an extended network which is obtained by transforming each combined demand customer into two different customers, one requiring only the delivery and the other one only the pickup. Because this can result in a significant loss in performance, in this work we focus instead on the original problem network and present formulations that can yield non-Elementary tours. Through the use of Benders Decomposition, valid inequalities, and tailored optimization techniques based on branch-and-cut frameworks, we develop exact algorithms that outmatch previous results in the literature and obtain proven optimal solutions for all benchmark instances. We then generalize the algorithms to solve several other vehicle routing problems with pickups and deliveries, including the cases of split deliveries, intermediate dropoffs, mandatory pickups, and multiple vehicles.

2017 - Scheduling cleaning activities on trains by minimizing idle times [Articolo su rivista]
Bartolini, Enrico; Dell'Amico, Mauro; Iori, Manuel
abstract

We consider a workforce scheduling problem which consists of determining optimal working shifts for cleaning personnel at a rail station. Trains arrive and depart according to a specified schedule and require a given amount of cleaning time from the personnel before their departure from the station. Working shifts must specify a sequence of trains to be cleaned by a worker together with corresponding cleaning times and are subject to contract regulations which impose both a minimum and a maximum duration of the shift. We model the problem as a mixed-integer program with a pseudo-polynomial number of variables and propose an exponentially sized reformulation obtained through Dantzig–Wolfe reformulation. The reformulation is strengthened by valid inequalities and used to compute lower bounds on the optimal cost. A heuristic algorithm based on column generation and variable fixing is then proposed and computationally evaluated on both a set of instances derived from real data and a larger set of randomly generated ones. The reported computational results show that the algorithm provides solutions very close to the optimal ones within 1 h of computing time.

2017 - Training software for orthogonal packing problems [Articolo su rivista]
Costa, Gianluca; Delorme, Maxence; Iori, Manuel; Malaguti, Enrico; Martello, Silvano
abstract

An open source architecture for the interactive solution of packing problems in two dimensions is presented. Although primarily developed for helping engineering students to understand the algorithmic approaches to the solution of difficult combinatorial optimization problems, the application can be useful to practitioners and developers thanks to its visual tools. The paper gives intuitive and formal definitions of the problems at hand, discusses two natural heuristic approaches, provides technical information on the application, and reports the results of classroom experimental testings.

2016 - A decision support system for highway construction: The Autostrada Pedemontana Lombarda [Articolo su rivista]
Dell'Amico, Mauro; Fuellerer, Guenther; Höfinger, Gerhard; Iori, Manuel; Novellani, Stefano
abstract

In this paper, we present a decision support system (DSS) to optimize activities involving earth excavation, filling, hauling, recycling, and dumping in construction logistics projects. The system was designed through collaboration between operations research experts and a team at Strabag AG, an Austrian construction company. The DSS aids managers in scheduling construction activities by determining the amounts of materials that must be moved, purchased, recycled, and dumped in a given period, and by selecting paths that minimize the costs of performing these activities. Applying our DSS to the highway construction project, Autostrada Pedemontana Lombarda, has significantly improved the speed of decision making at Strabag AG and reduced its logistics costs by 10 percent. Our system, which is based on the use of linear programming, has two phases. In Phase 1, an aggregate mathematical model determines the feasibility of the project. In Phase 2, we execute a detailed model to determine the paths over which to move material in each period. We use graphical tools to visualize the model solutions and facilitate the decision-making process. The DSS, currently in use in several Strabag AG construction projects, is a powerful, flexible, and easy-to-replicate tool for solving construction logistics problems.

2016 - A destroy and repair algorithm for the Bike sharing Rebalancing Problem [Articolo su rivista]
Dell'Amico, Mauro; Iori, Manuel; Novellani, Stefano; Stützle, Thomas
abstract

In this paper, we deal with the Bike sharing Rebalancing Problem (BRP), which is the problem of driving a fleet of capacitated vehicles to redistribute bicycles among the stations of a bike sharing system. We tackle the BRP with a destroy and repair metaheuristic algorithm, which makes use of a new effective constructive heuristic and of several local search procedures. The computational effort required for the neighborhood explorations is reduced by means of a set of techniques based on the properties of feasible BRP solutions. In addition, the algorithm is adapted to solve the one-commodity Pickup and Delivery Vehicle Routing Problem with maximum Duration (1-PDVRPD), which is the variant of the BRP in which a maximum duration is imposed on each route. Extensive computational results on instances from the literature and on newly-collected large-size real-world instances are provided. Our destroy and repair algorithm compares very well with respect to an exact branch-and-cut algorithm and a previous metaheuristic algorithm in the literature. It improves several best-known solutions, providing high quality results on both problem variants.

2016 - An Adaptive Iterated Local Search for the Mixed Capacitated General Routing Problem [Articolo su rivista]
Dell'Amico, Mauro; DIAZ DIAZ, Jose Carlos; Hasle, Geir; Iori, Manuel
abstract

We study the mixed capacitated general routing problem (MCGRP) in which a fleet of capacitated vehicles has to serve a set of requests by traversing a mixed weighted graph. The requests may be located on nodes, edges, and arcs. The problem has theoretical interest because it is a generalization of the capacitated vehicle routing problem (CVRP), the capacitated arc routing problem (CARP), and the general routing problem. It is also of great practical interest since it is often a more accurate model for real-world cases than its widely studied specializations, particularly for so-called street routing applications. Examples are urban waste collection, snow removal, and newspaper delivery. We propose a new iterated local search metaheuristic for the problem that also includes vital mechanisms from adaptive large neighborhood search combined with further intensification through local search. The method utilizes selected, tailored, and novel local search and large neighborhood search operators, as well as a new local search strategy. Computational experiments show that the proposed metaheuristic is highly effective on five published benchmarks for the MCGRP. The metaheuristic yields excellent results also on seven standard CARP data sets, and good results on four well-known CVRP benchmarks, including improvement of the best known upper bound for one instance.

2016 - An Iterated Dual Substitution Approach for the Min-Max Regret Multidimensional Knapsack Problem [Relazione in Atti di Convegno]
Wu, W; Iori, Manuel; Martello, S; Yagiura, M.
abstract

We consider the multidimensional knapsack problem (MKP) with min-max regret criterion under interval profits. We examine three typical algorithms widely applied for min-max regret criterion: fixed-scenario approach, Benders-like decomposition and branch-and-cut. We further propose a new heuristic framework, which we call the iterated dual substitution algorithm. Computational experiments on a wide set of benchmark instances are carried out, and the proposed iterated dual substitution algorithm performs best on all of the tested instances.

2016 - An analysis of drivers route choice behaviour using GPS data and optimal alternatives [Articolo su rivista]
Ciscal Terry, Wilner; Dell'Amico, Mauro; Hadjidimitriou, Natalia Selini; Iori, Manuel
abstract

This work aims to study drivers' route choices using a dataset of low frequency GPS coordinates to identify travels' trajectories. The sample consists of 89 drivers who performed 42 thousand paths in the province of Reggio Emilia, in Italy, during the seventeen considered months. Four attributes that may be important for the driver are identified and four optimal alternative paths are created based on the selected objectives to evaluate route choice behaviour. The comparison between the characteristics of the paths allows to conclude that drivers select routes that are overall longer than their optimal alternatives but that allow for higher speeds. Furthermore the statistical analysis of drivers' route choices in macroareas evidences that drivers have different behaviours depending on the geography of the territory. Specifically, there is higher heterogeneity of route choices in the plain areas compared to the mountains. In the second part of this work, clusters of repetitive travels are identified and a Geographical Route Directness Index is proposed to identify the areas of the province where the deviation from the shortest alternative path is higher. The analysis shows that, among groups of repetitive travels, the value of the index is higher along the ring road of the city of Reggio Emilia and there is a strong negative correlation between the frequency the driver selects the longer alternative that allow for higher speed, and the number of additional kilometres the same driver has to travel.

2016 - Bin packing and cutting stock problems: Mathematical models and exact algorithms [Articolo su rivista]
Delorme, Maxence; Iori, Manuel; Martello, Silvano
abstract

We review the most important mathematical models and algorithms developed for the exact solution of the one-dimensional bin packing and cutting stock problems, and experimentally evaluate, on state-of-the art computers, the performance of the main available software tools.

2015 - A rolling horizon algorithm for auto-carrier transportation [Articolo su rivista]
Cordeau, Jean François; Dell'Amico, Mauro; Falavigna, Simone; Iori, Manuel
abstract

This paper introduces a rolling horizon algorithm to plan the delivery of vehicles to automotive dealers by a heterogeneous fleet of auto-carriers. The problem consists in scheduling the deliveries over a multiple-day planning horizon during which requests for transportation arrive dynamically. In addition, the routing of the auto-carriers must take into account constraints related to the loading of the vehicles on the carriers. The objective is to minimize the sum of traveled distances, fixed costs for auto-carrier operation, service costs, and penalties for late deliveries. The problem is solved by a heuristic that first selects the vehicles to be delivered in the next few days and then optimizes the deliveries by an iterated local search procedure. A branch-and-bound search is used to check the feasibility of the loading. To handle the dynamic nature of the problem, the complete algorithm is applied repeatedly in a rolling horizon framework. Computational results on data from a major European logistics service provider show that the heuristic is fast and yields significant improvements compared to the sequential solution of independent daily problems.

2015 - Bin Packing Problem with General Precedence Constraints [Relazione in Atti di Convegno]
CISCAL TERRY, Wilner; Dell'Amico, Mauro; Iori, Manuel
abstract

In this paper we study the bin packing problem with general precedence constraints, in which a set of weighted items has to be packed in the minimal number of capacitated bins, while satisfying precedence relationships among pair of items. The problem generalizes the well- known Simple Assembly Line Balancing problem, and models relevant real-world situations. To solve the problem we propose a series of lower and upper bounding techniques, including an iterated local search algorithm. Preliminary computational results show the efficiency of the proposed approach in solving complex instances.

2015 - Exact algorithms for the double vehicle routing problem with multiple stacks [Articolo su rivista]
Iori, Manuel; Riera Ledesma, Jorge
abstract

The Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) is a one-to-one pickup-and-delivery single-vehicle routing problem with backhaul deliveries. The vehicle carries a container divided into stacks of fixed height, each following a Last-In-First-Out policy, and the aim is to perform pickups and deliveries by minimizing the total routing cost and ensuring a feasible loading/unloading of the vehicle. A realistic generalization of the DTSPMS arises when a single vehicle is not enough to collect all products, and therefore multiple, and possibly heterogeneous vehicles are needed to perform the transportation operations. This paper introduces and formulates this generalization, that we refer as the Double Vehicle Routing Problem with Multiple Stacks. It proposes three models, the first one based on a three-index formulation and solved by a branch-and-cut algorithm, and the other two based on two set partitioning formulations using different families of columns and solved by a branch-and-price and a branch-and-price-and-cut algorithm, respectively. The performance of these algorithms has been studied on a wide family of benchmark test instances, observing that, although the branch-and-cut algorithm shows a better performance on instances with a small number of vehicles, the performance of the branch-and-price and the branch-and-price-and-cut algorithms improves as the number of vehicles grows. Additionally, the first set partitioning formulation yields tighter lower bounds, but the second formulation, because of its simplicity, provides better convergence properties, solving instances with up to fifty vertices to proven optimality.

2015 - Friendly Bin Packing Instances without Integer Round-up Property [Articolo su rivista]
Caprara, A.; Dell'Amico, Mauro; Diaz Diaz, Jose Carlos; Iori, Manuel; Rizzi, R.
abstract

It is well known that the gap between the optimal values of bin packing and fractional bin packing, if the latter is rounded up to the closest integer, is almost always null. Known counterexamples to this for integer input values involve fairly large numbers. Specifically, the first one was derived in 1986 and involved a bin capacity of the order of a billion. Later in 1998 a counterexample with a bin capacity of the order of a million was found. In this paper we show a large number of counterexamples with bin capacity of the order of a hundred, showing that the gap may be positive even for numbers which arise in customary applications. The associated instances are constructed starting from the Petersen graph and using the fact that it is fractionally, but not integrally, 3-edge colorable.

2015 - Heuristic and exact algorithms for the interval min-max regret knapsack problem [Articolo su rivista]
Furini, Fabio; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori
abstract

We consider a generalization of the 0-1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min-max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the complexity class $\Sigma^p_2$ hence it is most probably not in ${\cal NP}$. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an ${\cal NP}$-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm, and evaluate their performance through extensive computational experiments.

2015 - ICT innovation in logistics services by ICOOR [Capitolo/Saggio]
Iori, Manuel
abstract

ICOOR is a research center that operates in the fields of Optimization and Operations Research, with an emphasis on logistics, manufacturing, and transportatin networks. ICOOR moves between logistics and the needs of companies on the one hand, and ICT tools on the other hand.

2015 - Optimization of a Real-World Auto-Carrier Transportation Problem [Articolo su rivista]
Dell'Amico, Mauro; Falavigna, Simone; Iori, Manuel
abstract

We study a real-world distribution problem arising in the automotive field, in which cars, trucks and other vehicles have to be loaded on auto-carriers and then delivered to dealers. The solution of the problem involves both the computation of the routing of the auto-carriers along the road network and the determination of a feasible loading for each auto-carrier. We solve the problem by means of an iterated local search algorithm, that makes use of several inner local search strategies for the routing part, and mathematical modeling and enumeration techniques for the loading part. Extensive computational results on real-world instances show that good savings on the total cost can be obtained within small computational efforts.

2015 - Two-Phase Earthwork Optimization Model for Highway Construction [Articolo su rivista]
Bogenberger, Christian; Dell'Amico, Mauro; Fuellerer, Guenther; Hoefinger, Gerhard; Iori, Manuel; Novellani, Stefano; Panicucci, Barbara
abstract

One of the main activities in highway construction is earthwork, that is a complex process involving excavation, transportation, and filling of large quantities of different earth material types. Earthwork operations are costly, and undergo several constraints due to the fact that they have large environmental and social impacts on the areas surrounding the construction site. Using mathematical models to produce a minimum-cost earthwork plan that satisfies all constraints is thus of great significance for enhancing the productivity of the overall construction project. This paper presents an earthwork optimization system based on the use of linear programming that operates in a novel two-phase approach. In the first phase an aggregate model determines the feasibility of the overall project, whereas in the second phase disaggregate models determine the actual flows of each material. The two-phase quantitative method for earthwork optimization developed in this paper includes all features derived from the everyday activity of one of the major European companies in construction. It involves classical decisions such as excavations, fillings, use of quarries and dump sites, and the temporary rent of depots, but it also accounts for several novelties, including the use of recycling facilities and the explicit integration with the existing public road network. Extensive computational results are obtained by running the models on a set of realistic instances, and show the efficiency of the proposed approach in solving complex earthwork problems.

2014 - Algorithms for the Min-Max Regret Generalized Assignment Problem with Interval Data [Relazione in Atti di Convegno]
Wu, Wei; Iori, Manuel; Martello, Silvano; Yagiura, Mutsunori
abstract

Many real life optimization problems do not have accurate estimates of the problem parameters at the optimization phase. For this reason, the min-max regret criteria are widely used to obtain robust solutions. In this paper we consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. We show that the decision version of this problem is Σp2-complete. We present two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. For the fixed-scenario approach, we show that solving the classical GAP under a median-cost scenario leads to a solution of the min-max regret GAP whose objective function value is within twice the optimal value. We also propose exact algorithms, including a Benders' decomposition approach and branch-and-cut methods which incorporate various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.

2014 - Combinatorial Benders’ Cuts for the Strip Packing Problem [Articolo su rivista]
Coté Jean, François; Dell'Amico, Mauro; Iori, Manuel
abstract

We study the strip packing problem, in which a set of two-dimensional rectangular items has to be packed in a rectangular strip of fixed width and infinite height, with the aim of minimizing the height used. The problem is important because it models a large number of real-world applications, including cutting operations where stocks of materials such as paper or wood come in large rolls and have to be cut with minimum waste, scheduling problems in which tasks require a contiguous subset of identical resources, and container loading problems arising in the transportation of items that cannot be stacked one over the other. The strip packing problem has been attacked in the literature with several heuristic and exact algorithms, nevertheless, benchmark instances of small size remain unsolved to proven optimality since many years. In this paper we propose a new exact method, that solves a large number of the open benchmark instances within a limited computational effort. Our method is based on a Benders’ decomposition, in which in the master we cut items into unit-width slices and pack them contiguously in the strip, and in the slave we attempt to reconstruct the rectangular items by fixing the vertical positions of their unit-width slices. If the slave proves that the reconstruction of the items is not possible, then a cut is added to the master, and the algorithm is re-iterated. We show that both the master and the slave are strongly NP-hard problems, and solve them with tailored pre-processing, lower and upper bounding techniques, and exact algorithms. We also propose several new techniques to improve the standard Benders’ cuts, using the so-called combinatorial Benders’ cuts, and an additional lifting procedure. Extensive computational tests show that the proposed algorithm provides a substantial breakthrough with respect to previously published algorithms.

2014 - Lower and upper bounds for the Bin Packing Problem with Fragile Objects [Articolo su rivista]
F., Clautiaux; Dell'Amico, Mauro; Iori, Manuel; A., Khanafer
abstract

We are given a set of items, each characterized by a weight and a fragility, and a large number of uncapacitated bins. Our aim is to find the minimum number of bins needed to pack all items, in such a way that in each bin the sum of the item weights is less than or equal to the smallest fragility of an item in the bin. The problem is known in the literature as the Bin Packing Problem with Fragile Objects, and appears in the telecommunication field, when one has to assign cellular calls to available channels by ensuring that the total noise in a channel does not exceed the noise acceptance limit of a call.We propose several techniques to compute lower and upper bounds for this problem. For what concerns lower bounds, we present combinatorial techniques with guaranteed worst case and a more complex bound based on a column generation algorithm. We also present a technique to compute, in a fast heuristic way, dual information that is used to strengthen the convergence of the column generation. For what concerns upper bounds, we present a large set of constructive heuristics followed by a Variable Neighborhood Search algorithm. Our heuristic techniques are aimed at both computing upper bounds and strengthening the behavior of the lower bounds in a matheuristic fashion. Extensive computational tests show the effectiveness of the proposed algorithms.

2014 - Pickup and Delivery Problems for Goods Transportation [Capitolo/Saggio]
Maria, Battarra; Jean François, Cordeau; Iori, Manuel
abstract

Pickup and Delivery Problems (PDPs) constitute an important family of routing problems in which transportation demands require objects or passengers to be moved from different origins to different destinations. These problems are usually defined on a graph in which vertices represent origins or destinations for the different entities (or commodities) to be transported. PDPs can be classified into three main categories according to the type of demand and route structure being considered.

2014 - The Bike Sharing Rebalancing Problem: Mathematical formulations and benchmark instances [Articolo su rivista]
Dell'Amico, Mauro; Eleni, Hadjiconstantinou; Iori, Manuel; Novellani, Stefano
abstract

Bike sharing systems offer a mobility service whereby public bicycles, located at different stations across an urban area, are available for shared use. These systems contribute towards obtaining a more sustainable mobility and decreasing traffic and pollution caused by car transportation. Since the first bike sharing system was installed in Amsterdam in 1965, the number of such applications has increased remarkably so that hundreds of systems are now operating all over the world. In a bike sharing system, users can take a bicycle from a station, use it to perform a journey and then leave it at a station, not necessarily the same one of departure. This behaviour typically leads to a situation in which some stations become full and others are empty. Hence, a balanced system requires the redistribution of bicycles among stations. In this paper, we address the Bike sharing Rebalancing Problem (BRP), in which a fleet of capacitated vehicles is employed in order to re-distribute the bikes with the objective of minimizing total cost. This can be viewed as a special one-commodity pickup-and-delivery capacitated vehicle routing problem. We present four mixed integer linear programming formulations of this problem. It is worth noting that the proposed formulations include an exponential number of constraints, hence, tailor-made branch-and-cut algorithms are developed in order to solve them. The mathematical formulations of the BRP were first computationally tested using data obtained for the City of Reggio Emilia, Italy. Our computational study was then extended to include bike sharing systems from other parts of the world. The information derived from the study was used to build a set of benchmark instances for the BRP which we made publicly available on the web. Extensive experimentation of the branch-and-cut algorithms presented in this paper was carried out and an interesting computational comparison of the proposed mathematical formulations is reported. Finally, several insights on the computational difficulty of the problem are highlighted.

2013 - A Branch-and-Cut Algorithm for the Double Traveling Salesman Problem with Multiple Stacks [Articolo su rivista]
M. A., Alba Martinez; J. F., Cordeau; Dell'Amico, Mauro; Iori, Manuel
abstract

The double traveling salesman problem with multiple stacks is a variant of the pickup and delivery traveling salesman problem in which all pickups must be completed before any delivery. In addition, items can be loaded on multiple stacks in the vehicle and each stack must obey the last-in-rst-out policy. The problem consists in nding the shortest Hamiltonian cycles covering all pickup and delivery locations while ensuring the feasibility of the loading plan. We formulate the problem as two traveling salesman problems linked by infeasible path constraints. We also introduce several strengthenings of these constraints which are used within a branch-and-cut algorithm. Computational results performed on instances from the literature show that the algorithm outperforms existing exact algorithms. Instances with up to 28 requests (58 nodes) have been solved to optimality.

2013 - An Annotated Bibliography of Combined Routing and Loading Problems [Articolo su rivista]
Iori, Manuel; S., Martello
abstract

Transportation problems, involving routing and loading at the same time, are currently a hot topic in combinatorial optimization. The interest of researchers and practitioners is motivated by the intrinsic difficulty of this research area, which combines two computationally hard problems, and by its practical relevance in important real world applications. This annotated bibliography aims at collecting, in a systematic way, the most relevant results obtained in the area of vehicle routing with loading constraints, with the objective of stimulating further research in this promising area.

2013 - Exact Algorithms for the Bin Packing Problem with Fragile Objects [Articolo su rivista]
M. A., Alba Martìnez; F., Clautiaux; Dell'Amico, Mauro; Iori, Manuel
abstract

We are given a set of objects, each characterized by a weight and a fragility, and a large number of uncapacitated bins. Our aim is to find the minimum number of bins needed to pack all objects, in such a way that in each bin the sum of the object weights is less than or equal to the smallest fragility of an object in the bin. The problem is known in the literature as the Bin Packing Problem with Fragile Objects, and appears in the telecommunication field, when one has to assign cellular calls to available channels by ensuring that the total noise in a channel does not exceed the noise acceptance limit of a call. We propose a branch-and-bound and several branch-and-price algorithms for the exact solution of the problem, and improve their performance by the use of lower bounds and tailored optimization techniques. In addition we also develop algorithms for the optimal solution of the related knapsack problem with fragile objects. We conduct an extensive computational evaluation on the benchmark set of instances, and show that the proposed algorithms perform very well.

2013 - Optimal design of fair layouts [Articolo su rivista]
A. E., Fernandes Muritiba; Iori, Manuel; S., Martello; M. J., Negreiros Gomes
abstract

A relevant logistic issue in the organization of a fair is to determine how stands have to be placed in the exhibition space so as to satisfy all constraints on security, ease of access, services, and so on, while maximizing the revenues coming from the exhibitors. We consider in particular the problem of allocating the maximum number of stands by satisfying all the constraints required by practical implementations. We examine a number of real-world cases, and show how basic mathematical programming models can be improved to handle specific requests from the organizers. We report the solutions obtained through an original decision support system, that embeds a number of algorithms to solve the various cases by reduction to one or more linear programs.

2012 - A note on exact and heuristic algorithms for the identical parallel machine scheduling problem [Articolo su rivista]
Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci
abstract

A recent paper (Davidovi'et al 2012) presented a bee colony metaheuristic for scheduling independent tasks to identical processors, evaluating its performance on a benchmark set of instances from the literature. We examine two exact algorithms from the literature, the former published in 1995, the latter in 2008 (and not cited by the authors). We show that both such algorithms solve to proven optimality all the considered instances in a computing time that is several orders of magnitude smaller than the time taken by the new algorithm to produce an approximate solution.

2012 - Multi-Objective Optimization to evaluate the factors influencing drivers' route choice [Abstract in Atti di Convegno]
Dell'Amico, Mauro; S., Hadjidimitriou; Iori, Manuel; W., Ciscal Terry
abstract

This study aims to model drivers' decision making process in response to availability of alternative routes. With the support of geographical information systems (GIS), we present a case study for the transportation flows in reggio Emilia (Italy). We intend to determine the minimum path by identification of the objectives that are important, in practice, for the driver. For this purpose, a multi-objective optimisation problem is solved.

2012 - The Bin Packing Problem with Precedence Constraints [Articolo su rivista]
Dell'Amico, Mauro; DIAZ DIAZ, Jose Carlos; Iori, Manuel
abstract

Given a set of identical capacitated bins, a set of weighted items and a set of precedences among such items, we are interested in determining the minimum number of bins that can accommodate all items and can be ordered in such a way that all precedences are satised. The problem, denoted as the Bin Packing Problem with Precedence Constraints (BPP-P), has a very intriguing combinatorial structure and models many assembly and scheduling issues.According to our knowledge the BPP-P has received little attention in the literature, and in this paper we address it for the first time with exact solution methods. In particular, we develop reduction criteria, a large set of lower bounds, a Variable Neighborhood Search upper bounding technique and a branch-and-bound algorithm. We show the eectiveness of the proposed algorithms by means of extensive computational tests on benchmark instances and comparison with standard integer linear programming techniques.

2011 - A Matheuristic Algorithm for Auto-Carrier Transportation [Relazione in Atti di Convegno]
Dell'Amico, Mauro; Falavigna, Simone; Iori, Manuel
abstract

We study a real-world distribution problem arising in the automotive field, in which cars and other vehicles have to be loaded on auto-carriers and then delivered to dealers. The solution of the problem involves both the computation of the routing of the autocarriers along the road network and the determination of a feasible loading for each auto-carrier. We solve the problem by means of a heuristic algorithm that makes use of simple greedy and local search strategies for the routing part, and more complex mathematical modeling and branch-and-bound techniques for the loading part. Preliminary computational results show that good savings on the total routing distance can be obtained within small computational efforts.

2011 - Efficient computation of upper bounds for the disjunctively constrained knapsack problem [Articolo su rivista]
Y., Yamasaki; R., Schiavoni; Iori, Manuel; M., Yagiura; S., Martello
abstract

ナップサック問題(knapsack problem) は情報科学の分野における基礎的な問題で, これまでに多くの研究がある．また，ナップサック問題に制約を加えた問題も多数存在する．本論文ではそのひとつである排他制的付きナップサック問題(disjunctively constrained knapsack problem) を対象とする．これは，同時に選択できないアイテムに関する制約(排他制約) と容量制約を満たすようにいくつかのアイテムを選択するとき，選択したアイテムの価値の合計を最大化する問題である．これに対し，クリークを用いた上界値計算法を提案する．本計算法により大規模な問題例や辺密度の高い問題例に対して高速に上界値を計算できることを計算実験により確認した．

2011 - Heuristic and Exact Algorithms for the Multi-Pile Vehicle Routing Problem [Articolo su rivista]
F., Tricoire; K. F., Doerner; R. F., Hartl; Iori, Manuel
abstract

The multi-pile vehicle routing problem is a particular combination of loading and routing problems, in which items have to be loaded into different piles within vehicles, and then delivered with minimum cost. The problem is motivated by a real-world timber distribution problem, and is of both theoretical and practical interest. In this paper, we first develop heuristic and exact methods to solve the loading problem. We then include these methods into a tailored combination of Variable Neighborhood Search and Branch-and-Cut, to solve the overall problem. Extensive computational results show how the resulting algorithms are capable of solving to optimality a large number of small-size instances, and of consistently outperforming previous algorithms from the literature on large-size and real-world instances.

2011 - Models and algorithms for the bin packing problem with fragile objects [Relazione in Atti di Convegno]
ALBA MARTINEZ, Manuel Angel; Clautiaux, François; Dell'Amico, Mauro; Iori, Manuel
abstract

In the Bin Packing Problem with Fragile Objects (BPPFO), we are given n objects, each having a given weight and a given fragility, and a large number of uncapacitated bins. The aim is to pack all objects in the minimum number of bins, in such a way that in each bin the sum of the object weights is less than or equal to the smallest fragility of an object.

2010 - A Branch-and-Cut Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading [Articolo su rivista]
J. F., Cordeau; Iori, Manuel; G., Laporte; J. J., Salazar Gonzalez
abstract

In the Traveling Salesman Problem with Pickup and Delivery (TSPPD) a single vehiclemust serve a set of customer requests, each defined by an origin location where a load must be picked up, and a destination location where the load must be delivered. The problem consists of determining a shortest Hamiltonian cycle through all locations while ensuring that the pickup of each request is performed before the corresponding delivery. This article addresses a variant of the TSPPD in which pickups anddeliveries must be performed according to a Last-In First-Out (LIFO) policy. We propose three mathematical formulations for this problem and several families of valid inequalities which are used within a branch-and-cut algorithm. Computational results performed on test instances from the literature show that most instances with up to 17 requests can be solved in less than 10 min, whereas the largest instance solved contains 25 requests.

2010 - Algorithms for the Bin Packing Problem with Conflicts [Articolo su rivista]
A. E., Fernandes Muritiba; Iori, Manuel; E., Malaguti; P., Toth
abstract

We consider a particular Bin Packing Problem in which some pairs of items may be in conflict and cannot be assigned to the same bin. The problem, denoted as the Bin Packing Problem with Conflicts, is of practical and theoretical interest, because of its many real-world applications and because it generalizes both the Bin Packing Problem and the Vertex Coloring Problem. We present new lower bounds, upper bounds and an exact approach, based on a Set Covering formulation solved through a Branch-and-Price algorithm. We investigate the behavior of the proposed procedures by means of extensive computational results on benchmark instances from the literature.

2010 - An aggregate label setting policy for the multi-objective shortest path problem [Articolo su rivista]
Iori, Manuel; S., Martello; Pretolani, Daniele
abstract

We consider label setting algorithms for the multi-objective shortest path problem with any number of sum and bottleneck objectives. We propose a weighted sum aggregate ordering of the labels, specifically tailored to combine sum and bottleneck objectives. We show that the aggregate order leads to a consistent reduction of solution times (up to two-thirds) with respect to the classical lexicographic order.

2010 - Branch-and-Cut for the Pickup and Delivery Traveling Salesman Problem with FIFO Loading [Articolo su rivista]
J. F., Cordeau; Dell'Amico, Mauro; Iori, Manuel
abstract

This paper introduces a branch-and-cut algorithm for a variant of the pickup and delivery traveling salesman problem in which pickups and deliveries must obey the first-in-first-out policy. We propose a new mathematical formulation of the problem and several families of valid inequalities which are used within the branch-and-cut algorithm. Computational experiments on instances from the literature show that this algorithm outperforms existing exact algorithms, and that some instances with up to 25 requests (50 nodes) can be solved in reasonable computing time.

2010 - Fair Layout Optimization [Relazione in Atti di Convegno]
A. E., Fernandes Muritiba; Iori, Manuel; S., Martello; M. J., Negreiros Gomes
abstract

We consider the problem of allocating the maximum number of stands to a fair exhibition area so as to satisfy all the constraints required by practical applications in this field. By examining a number of real world-cases, we show how basic mathematical programming models can be adapted to handle specific requests from the organizers.

2010 - Metaheuristics for Vehicle Routing Problems with Three-Dimensional Loading Constraints [Articolo su rivista]
G., Fuellerer; K. F., Dorner; R., Hartl; Iori, Manuel
abstract

This paper addresses an important combination of three-dimensional loading and vehicle routing, known as the Three-Dimensional Loading Capacitated Vehicle Routing Problem. The problem calls for the combined optimization of the loading of freight into vehicles and the routing of vehicles along a road network, with the aim of serving customers with minimum traveling cost. Despite its clear practical relevance in freight distribution, the literature on this problem is very limited. This is because of its high combinatorial complexity.We solve the problem by means of an Ant Colony Optimization algorithm, which makes use of fast packing heuristics for the loading. The algorithm combines two different heuristic information measures, one for routing and one for packing. In numerical tests all publicly available test instances are solved, andfor almost all instances new best solutions are found.

2010 - Models and algorithms for fair layout optimization problems [Articolo su rivista]
A. E., Fernandes Muritiba; Iori, Manuel; S., Martello; M. J., Negreiros Gomes
abstract

Given a non-convex two-dimensional area and identical rectangular stands, we consider the problem of placing the maximum number of stands in the area, by satisfying a number of operational constraints. We present linear programming models and show the total unimodularity of the matrices associated with their constraint sets. We then give computational results obtained by applying the models to the real-world case of the Beira Mar handcraft fair of Fortaleza (Brazil).

2010 - Rejoinder on: Routing problems with loading constraints [Articolo su rivista]
Iori, Manuel; S., Martello
abstract

We would like to thank Gilbert Laporte, José Fernando Oliveira, Frank Plastria, Juan José Salazar Gonzalez and Paolo Toth for their careful reading and valuable comments. It is interesting to observe that, in general, their comments covered distinct aspects of the survey. Some of their remarks (referring to a preliminary version of the survey) have been incorporated in the current version, leading to a more complete presentation of the considered research area. Other remarks are briefly commented here.

2010 - Routing problems with loading constraints [Articolo su rivista]
Iori, Manuel; S., Martello
abstract

We consider difficult combinatorial optimization problems arising in transportation logistics when one is interested in optimizing both the routing of vehicles and the loading of goods into them. The separate problems (routing and loading) are already NP-hard, and very difficult to solve in practice. A fortiori their combination is extremely challenging and stimulating. Although the specific literature is still quite limited, a first attempt to a systematic view of this field can be useful both to academic researchers and to practitioners. We review vehicle routing problems with twoand three-dimensional loading constraints. Other combinations of routing and special loading constraints arising from industrial applications are also considered.

2009 - Ant Colony Optimization for the Two-Dimensional Loading Vehicle Routing Problem [Articolo su rivista]
G., Fuellerer; K. F., Doerner; R. F., Hartl; Iori, Manuel
abstract

In this paper a combination of the two most important problems in distribution logistics is considered, known as the two-dimensional loading vehicle routing problem. This problem combines the loading of the freight into the vehicles, and the successive routing of the vehicles along the road network, with the aim of satisfying the demands of the customers. The problem is solved by different heuristics for the loading part, and by an ant colony optimization (ACO) algorithm for the overall optimization. The excellent behavior of the algorithm is proven through extensive computational results.The contribution of the paper is threefold: first, on small-size instances the proposed algorithm reaches a high number of proven optimal solutions, while on large-size instances it clearly outperforms previous heuristics from the literature. Second, due to its flexibility in handling different loading constraints, including items rotation and rear loading, it allows us to draw qualitative conclusions of practical interest in transportation, such as evaluating the potential savings by permitting more flexible loading configurations. Third, in ACO a combination of different heuristic information usually did not turn out to be successful in the past. Our approach provides an example where an ACO algorithm successfully combines two completely different heuristic measures (with respect to loading and routing) within one pheromone matrix.

2009 - The single-finger keyboard layout problem [Articolo su rivista]
Dell'Amico, Mauro; J. C., Diaz Diaz; Iori, Manuel; R., Montanari
abstract

The problem of designing new keyboards layouts able to improve the typing speed of an average message has been widely considered in the literature of the Ergonomics domain. Empirical tests with users and simple optimization criteria have been used to propose new solutions. On the contrary, very few papers in Operations Research have addressed this optimization problem. In this paper we firstly resume the most relevant problems in keyboard design, enlightening the related Ergonomics aspects. Then we concentrate on keyboards that must be used witha single finger or stylus, like that of Portable Data Assistant, Smartphones and other small devices.We show that the underlying optimization problem is a generalization of the well known Quadratic Assignment Problem (QAP). We recall some of the most effective metaheuristic algorithms for QAP and we propose some non trivial extensions to the keyboard design problem. We compare the new algorithms through computational experiments with instances obtained from word lists of the English, French, Italian and Spanish languages. We provide on the web benchmark instances for each language and the best solutions we obtained.

2008 - A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints [Articolo su rivista]
M., Gendreau; Iori, Manuel; G., Laporte; S., Martello
abstract

This article addresses the well-known Capacitated Vehicle Routing Problem (CVRP), in the special case where the demand of a customer consists of a certain number of two-dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of the goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two-dimensional packing (2L) must be executed on each vehicle. The overall problem, denoted as 2L-CVRP, is NP-hard and particularly difficult to solve in practice. We propose a Tabu Search algorithm, in which the loading component of the problem is solved through heuristics, lower bounds, and a truncated branch-and-bound procedure. The effectiveness of the algorithm is demonstrated through extensivecomputational experiments.

2008 - Erratum: A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints [Articolo su rivista]
M., Gendreau; Iori, Manuel; G., Laporte; S., Martello
abstract

In the article, “A Tabu Search Heuristic for the Vehicle Routing Problem with Two-Dimensional Loading Constraints” by M. Gendreau et al., which appeared in the January issue of Networks (Networks 51 (2008), 4–18), the last author’s name was misspelled.

2008 - Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem [Articolo su rivista]
Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci
abstract

Given a set of jobs, with associated processing times, and a set of identical machines, each of which can process at most one job at a time, the Parallel Machine Scheduling Problem is to assign each job to exactly one machine so as to minimize the maximum completion time of a job. The problem is strongly NP-hard, and has been intensively studied since the Sixties.We present a metaheuristic and an exact algorithm, and analyze their average behavior on a large set of test instances from the literature.The metaheuristic algorithm, which is based on a scatter search paradigm, computationally proves to be highly effective, and capable of solving to optimality a very high percentage of the publicly available test instances. The exact algorithm, which is based on a specialized binary search and a branch-and-price scheme, was able to quickly solve to optimality all remaining instances.

2008 - Scatter Search Algorithms for Identical Parallel Machine Scheduling Problems [Capitolo/Saggio]
Iori, Manuel; S., Martello
abstract

We address the Identical Parallel Machine Scheduling Problem, one of the most important basic problems in scheduling theory, and some generalizations of it arising from real world situations. We survey the current state of the art for the most performing metaheuristic algorithms for this class of problems, with special emphasis on recent results obtained through Scatter Search. We present insights in the development of this heuristic technique, and discuss the combinatorial difficulties of the problems through the analysis of extensive computational results.

2008 - Shortest Paths in Piecewise Continuous Time-Dependent Networks [Articolo su rivista]
Dell'Amico, Mauro; Iori, Manuel; Pretolani, Daniele
abstract

We consider a shortest path problem, where the travel times on the arcs may vary with time and waiting at any node is allowed. Simple adaptations of the Dijkstra algorithm may fail to solve the problem, when discontinuities exist. We propose a new Dijkstra-like algorithm that overcomes these difficulties.

2007 - A hybrid genetic algorithm for the two-dimensional single large object placement problem [Articolo su rivista]
E., Hadjiconstantinou; Iori, Manuel
abstract

In the two-dimensional single large object placement problem, we are given a rectangular master surface which has to be cut into a set of smaller rectangular items, with the aim of maximizing the total value of the pieces cut. We consider the special case in which the items cannot be rotated and must be cut with their edges always parallel to the edges of the surface. We present new greedy algorithms and a hybrid genetic approach with elitist theory, immigration rate, heuristics online and tailored crossover operators. Extensive computational results for a large number of small and large benchmark test problems are presented. The results show that our approach outperforms existing heuristic algorithms.

2007 - An exact approach for the vehicle routing problem with two-dimensional loading constraints [Articolo su rivista]
Iori, Manuel; J. J., SALAZAR GONZALEZ; D., Vigo
abstract

We consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a maximum weight capacity. The aim is to find a partition of the customers into routes of minimum total cost such that, for each vehicle, the weight capacity is taken into account and a feasible two-Dimensional allocation of the items into the loading surface exists. The problem has several practical applications in freight transportation, and it is -hard in the strong sense. We propose an exact approach, based on a branch-and-cut algorithm, for the minimization of the routing cost that iteratively calls a branch-and-bound algorithm for checking the feasibility of the loadings. Heuristics are also used to improve the overall performance of the algorithm. The effectiveness of the approach is shown by means of computational results.

2007 - Metaheuristics for the Vehicle Routing Problem with Loading Constraints [Articolo su rivista]
K., Doerner; G., Fuellerer; M., Gronalt; R., Hartl; Iori, Manuel
abstract

We consider a combination of the capacitated vehicle routing problem and a class of additional loading constraints involving a parallel machine scheduling problem. The work is motivated by a real-world transportation problem occurring to a wood-products retailer, which delivers its products to a number of customers in a specific region. We solve the problem by means of two different metaheuristics algorithms: a Tabu Search and an Ant Colony Optimization. Extensive computational results are given for both algorithms, on instances derived from the vehicle routing literature and on real-world instances.

2006 - A tabu search algorithm for a routing and container loading problem [Articolo su rivista]
M., Gendreau; Iori, Manuel; G., Laporte; S., Martello
abstract

This article considers a combination of capacitated vehicle routing and three-dimensional loading, with additional constraints frequently encountered in freight transportation. It proposes a tabu search algorithm that iteratively invokes an inner tabu search procedure for the solution of the loading subproblem. The algorithm is experimentally evaluated both on instances adapted from vehicle routing instances from the literature and on new real-world instances.

2006 - Lower bounds and heuristic algorithms for the $k_i$-partitioning problem [Articolo su rivista]
Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci
abstract

We consider the problem of partitioning a set of positive integers values into a given number of subsets, each having an associated cardinality limit, so that the maximum sum of values ill a subset is minimized, and the number of values in each subset does not exceed the corresponding limit. The problem is related to scheduling and bin packing problems. We give combinatorial lower bounds, reduction criteria, constructive heuristics, a scatter search approach, and a lower bound based on column generation. The outcome of extensive computational experiments is presented.

2005 - Metaheuristic algorithms for combinatorial optimization problems [Articolo su rivista]
Iori, Manuel
abstract

We present the main results in the author’s Ph.D. thesis (Iori 2004), defended at the University of Bologna in April 2004 and supervised by S. Martello. The thesis is written in English and is available from the author upon request. It proposes exact and metaheuristic algorithms for solving some relevant combinatorial optimization problems, with particular emphasis on scheduling, two-dimensional cutting and packing and capacitated vehicle routing. The performance of each algorithm is tested through extensive computational experiments and comparison with other approaches in the literature.

2004 - Heuristic Algorithms and Scatter Search for the Cardinality Constrained P||Cmax Problem [Articolo su rivista]
Dell'Amico, Mauro; Iori, Manuel; S., Martello
abstract

We consider the classical P||Cmax problem (assign n jobs tom identical parallel processors by minimizing the makespan) arising when the number of jobs that can be assigned to each processor cannot exceed a given integer k. The problem is strongly NP-hard for any fixed k > 2.We briefly survey lower and upper boundsfrom the literature.We introduce greedy heuristics, local search and a scatter search approach. The effectiveness of these approaches is evaluated through extensive computational comparison with a depth-first branch-and-bound algorithm that includes new lower bounds and dominance criteria.

2003 - Metaheuristic Algorithms for the Strip Packing Problem [Relazione in Atti di Convegno]
Iori, Manuel; S., Martello; M., Monaci
abstract

Given a set of rectangular items and a strip of given width, we consider the problem of allocating all the items to a minimum height strip. We present a Tabu search algorithm, a genetic algorithm and we combine the two into a hybrid approach. The performance of the proposed algorithms is evaluated through extensive computational experiments on instances from the literature and on randomly generated instances.

Università degli studi di Modena e Reggio Emilia

Pubblicazioni