Foto personale

Pagina personale di Mauro DELL'AMICO

Dipartimento di Scienze e Metodi dell'Ingegneria

Bartolini, Enrico; Dell’Amico, Mauro; Iori, Manuel ( 2017 ) - Scheduling cleaning activities on trains by minimizing idle times - JOURNAL OF SCHEDULING - n. volume 20 - pp. da 493 a 506 ISSN: 1094-6136 [Articolo in rivista (262) - Articolo su rivista]
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.

Kramer, Raphael; Dell’Amico, Mauro; Iori, Manuel ( 2017 ) - A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints - INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH - n. volume 55 - pp. da 6288 a 6304 ISSN: 0020-7543 [Articolo in rivista (262) - Articolo su rivista]
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.

Mauro, Dell'Amico; Stefano, Novellani ( 2017 ) - A two-echelon facility location problem with stochastic demands for urban construction logistics: An application within the SUCCESS project ( 2017 IEEE International Conference on Service Operations and Logistics, and Informatics - - September 18-20, 2017) ( - Service Operations and Logistics, and Informatics (SOLI), 2017 IEEE International Conference on ) [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
Abstract

In this paper we present a two-echelon facility location problem with stochastic demands for the introduction of consolidation centers in the construction supply chain in urban areas. We describe the state of the art and propose a 2-stage model solved with L-shaped algorithms where several novel features are treated all together. The study is part of simulations performed during the European project SUCCESS (Sustainable Urban Consolidation CentrES for construction).

Dell’Amico, Mauro; Díaz Díaz, José Carlos; Hasle, Geir; Iori, Manuel ( 2016 ) - An Adaptive Iterated Local Search for the Mixed Capacitated General Routing Problem - TRANSPORTATION SCIENCE - n. volume 50(4) - pp. da 1223 a 1238 ISSN: 0041-1655 [Articolo in rivista (262) - Articolo su rivista]
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.

Dell'Amico, Mauro; Iori, Manuel; Novellani, Stefano; Stützle, Thomas ( 2016 ) - A destroy and repair algorithm for the Bike sharing Rebalancing Problem - COMPUTERS & OPERATIONS RESEARCH - n. volume 71 - pp. da 149 a 162 ISSN: 0305-0548 [Articolo in rivista (262) - Articolo su rivista]
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.

Dell'Amico, Mauro; Fuellerer, Guenther; Höfinger, Gerhard; Iori, Manuel; Novellani, Stefano ( 2016 ) - A decision support system for highway construction: The Autostrada Pedemontana Lombarda - INTERFACES - n. volume 46 - pp. da 245 a 263 ISSN: 0092-2102 [Articolo in rivista (262) - Articolo su rivista]
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.

Ciscal-Terry, Wilner; Dell'Amico, Mauro; Hadjidimitriou, Natalia Selini; Iori, Manuel ( 2016 ) - An analysis of drivers route choice behaviour using GPS data and optimal alternatives - JOURNAL OF TRANSPORT GEOGRAPHY - n. volume 51 - pp. da 119 a 129 ISSN: 0966-6923 [Articolo in rivista (262) - Articolo su rivista]
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.

Ciscal-Terry, Wilner; Dell'Amico, Mauro; Iori, Manuel ( 2015 ) - Bin Packing Problem with General Precedence Constraints ( 15th IFAC Symposium on Information Control Problems in Manufacturing - - 11/05/2015 - 13/05/2015) ( - 15th IFAC Symposium onInformation Control Problems in Manufacturing INCOM 2015 ) (Elsevier Amsterdam NLD ) - n. volume 48 - pp. da 2027 a 2029 ISSN: - [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

Caprara, A.; Dell’Amico, M.; Díaz Díaz, J. C.; Iori, M.; Rizzi, R. ( 2015 ) - Friendly Bin Packing Instances without Integer Round-up Property - MATHEMATICAL PROGRAMMING - n. volume 150 - pp. da 5 a 17 ISSN: 0025-5610 [Articolo in rivista (262) - Articolo su rivista]
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.

Bogenberger, Christian; Dell'Amico, Mauro; Fuellerer, Guenther; Hoefinger, Gerhard; Iori, Manuel; Novellani, Stefano; Panicucci, Barbara ( 2015 ) - Two-Phase Earthwork Optimization Model for Highway Construction - JOURNAL OF CONSTRUCTION ENGINEERING AND MANAGEMENT - n. volume 141 - pp. da 1 a 11 ISSN: 0733-9364 [Articolo in rivista (262) - Articolo su rivista]
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.

Cordeau, Jean-François; Dell’Amico, Mauro; Falavigna, Simone; Iori, Manuel ( 2015 ) - A rolling horizon algorithm for auto-carrier transportation - TRANSPORTATION RESEARCH PART B-METHODOLOGICAL - n. volume 76 - pp. da 68 a 80 ISSN: 0191-2615 [Articolo in rivista (262) - Articolo su rivista]
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.

Dell’Amico, M.; Falavigna, S.; Iori, M. ( 2015 ) - Optimization of a Real-World Auto-Carrier Transportation Problem - TRANSPORTATION SCIENCE - n. volume 49 - pp. da 402 a 419 ISSN: 0041-1655 [Articolo in rivista (262) - Articolo su rivista]
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.

F. Clautiaux; M. Dell'Amico; M. Iori; A. Khanafer ( 2014 ) - Lower and upper bounds for the Bin Packing Problem with Fragile Objects - DISCRETE APPLIED MATHEMATICS - n. volume 163 - pp. da 73 a 86 ISSN: 0166-218X [Articolo in rivista (262) - Articolo su rivista]
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.

Coté Jean-François; Dell’Amico Mauro; Iori Manuel ( 2014 ) - Combinatorial Benders’ Cuts for the Strip Packing Problem - OPERATIONS RESEARCH - n. volume 62 - pp. da 643 a 661 ISSN: 0030-364X [Articolo in rivista (262) - Articolo su rivista]
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.

Mauro Dell’Amico; Eleni Hadjiconstantinou; Manuel Iori; Stefano Novellani ( 2014 ) - The Bike Sharing Rebalancing Problem: Mathematical formulations and benchmark instances - OMEGA - n. volume 45 - pp. da 7 a 19 ISSN: 0305-0483 [Articolo in rivista (262) - Articolo su rivista]
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.

M.A. Alba Martinez; J.-F. Cordeau; M. Dell’Amico; M. Iori ( 2013 ) - A Branch-and-Cut Algorithm for the Double Traveling Salesman Problem with Multiple Stacks - INFORMS JOURNAL ON COMPUTING - n. volume 25 - pp. da 41 a 55 ISSN: 1091-9856 [Articolo in rivista (262) - Articolo su rivista]
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.

M.A. Alba Martìnez; F. Clautiaux; M. Dell’Amico; M. Iori ( 2013 ) - Exact Algorithms for the Bin Packing Problem with Fragile Objects - DISCRETE OPTIMIZATION - n. volume 10 - pp. da 210 a 223 ISSN: 1572-5286 [Articolo in rivista (262) - Articolo su rivista]
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.

GAMBERINI R.; RIMINI B.; DELL'AMICO M.; LOLLI F.; BIANCHI M. ( 2012 ) - DESIGN AND OPTIMIZATION OF PICKING IN THE CASE OF MULTI-ITEM MULTI-LOCATION MULTI-PALLET CUSTOMER ORDERS ( - Warehousing in the Global Supply Chain: Advanced Models, Tools and Applications for Storage Systems ) (Springer - ITA ) - pp. da 397 a 424 ISBN: 9781447122739 ISSN: - [Contributo in volume (Capitolo o Saggio) (268) - Capitolo/Saggio]
Abstract

Order picking related costs may account for up to 65% of the total expense of warehouse management. Hence, the implementation of robust design and optimization procedures for planning picking is addressed by researchers and practitioners.In this chapter the case of warehouses served by humans, in picker-to-parts systems, with a discrete picking organization is studied. Specifically, the case of orders including multiple different items, located in different aisles and requiring more than one forklift load to completely satisfy customer requests is analyzed, with the aim of minimizing the time for retrieving an order. Specifically, two aspects are studied:•the grouping of orders into a finite number of forklift missions, by assuring that each required item is picked in the required amount•the optimization of the routing to be followed by handling facilities in accordance with the objective of minimizing the total travelled distance and the computation of the number of handling facilities necessary for serving the warehouse aisles.

M. Dell’Amico; J.C. Dìaz Dìaz; M. Iori ( 2012 ) - The Bin Packing Problem with Precedence Constraints - OPERATIONS RESEARCH - n. volume 60 - pp. da 1491 a 1504 ISSN: 0030-364X [Articolo in rivista (262) - Articolo su rivista]
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.

M. Dell'Amico; M. Iori; S. Martello; M. Monaci ( 2012 ) - A note on exact and heuristic algorithms for the identical parallel machine scheduling problem - JOURNAL OF HEURISTICS - n. volume 18 - pp. da 939 a 942 ISSN: 1381-1231 [Articolo in rivista (262) - Articolo su rivista]
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.

M. Dell’Amico; S. Hadjidimitriou; M. Iori; W. Ciscal Terry ( 2012 ) - Multi-Objective Optimization to evaluate the factors influencing drivers' route choice ( RelStat’12 - - 17-20/10/2012) ( - Abstracts of the 12th International Conference on Reliability and Statistics in Transportation and Communication ) (Transport and Telecommunication Institute Riga LVA ) - n. volume 1 - pp. da 136 a 136 ISBN: 9789984818504 ISSN: - [Abstract in Atti di convegno (274) - Abstract in Atti di Convegno]
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.

ALBA MARTINEZ, Manuel Angel; Clautiaux, François; Dell'Amico, Mauro; Iori, Manuel ( 2011 ) - Models and algorithms for the bin packing problem with fragile objects ( 10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011 - - 14 - 16 Giugno 2011) ( - 10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011 - Proceedings of the Conference ) - pp. da 36 a 39 ISSN: - [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

Dell'Amico, Mauro; Falavigna, Simone; Iori, Manuel ( 2011 ) - A Matheuristic Algorithm for Auto-Carrier Transportation ( VII ALIO–EURO – Workshop on Applied Combinatorial Optimization - - 4-6 Maggio 2011) ( - Proceedings of the VII ALIO–EURO ) - pp. da 81 a 84 ISSN: - [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

Baldacci, R.; Dell'Amico, Mauro ( 2010 ) - Heuristic Algorithms for the Multiple-Depot Ring-Star Problem - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH - n. volume 203 - pp. da 270 a 281 ISSN: 0377-2217 [Articolo in rivista (262) - Articolo su rivista]
Abstract

In this paper, we consider the problem of designing urban opticalnetworks. In particular, given a set of telephone exchanges, we must design a collection of ring-stars, where each ring-star is a cycle composed of a telephone exchange, some customers, some "transition points" used to save routing costs and customers not on the cycle connected to the cycle by a single edge. The ring topology is chosen in many fiber optic communication networks since it allows to prevent the loss of connection due to a single edge or even a single node failure. The objective is to minimize the total cost of the optical network which is mainly due to the excavation costs. We call this problem Multi-Depot Ring-Star Problem (\MDRSP) and we formulate it as an optimization problem in Graph Theory. We present lower bounds andheuristic algorithms for the \MDRSP. Computational results onrandomly generated instances and real-life datasets are also

J.F. Cordeau; M. Dell’Amico; M. Iori ( 2010 ) - Branch-and-Cut for the Pickup and Delivery Traveling Salesman Problem with FIFO Loading - COMPUTERS & OPERATIONS RESEARCH - n. volume 37 - pp. da 970 a 980 ISSN: 0305-0548 [Articolo in rivista (262) - Articolo su rivista]
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.

R. BURKARD; M. DELL'AMICO; S. MARTELLO ( 2009 ) - Assignment Problems (SIAM Philadelphia USA ) - pp. da 1 a 382 ISBN: 9780898716634 ISSN: - [Monografia o trattato scientifico (276) - Monografia/Trattato scientifico]
Abstract

This volume presents a comprehensive view of the huge area of the assignment problem, starting from the conceptual foundations laid down since the Twenties by the studies on matching problems, and examining in detail theoretical, algorithmic and practical developments of the various assignment problems. Although the covered area is wide, each of the ten chapters is essentially self contained, and the readers can easily follow a single chapter they are interested in, by encountering few pointers to the essential background given in previous parts.

M. Dell'Amico; J.C. Diaz Diaz; M. Iori; R. Montanari ( 2009 ) - The single-finger keyboard layout problem - COMPUTERS & OPERATIONS RESEARCH - n. volume 36 - pp. da 3002 a 3012 ISSN: 0305-0548 [Articolo in rivista (262) - Articolo su rivista]
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.

M. Dell'Amico; M. Iori; D. Pretolani ( 2008 ) - Shortest Paths in Piecewise Continuous Time-Dependent Networks - OPERATIONS RESEARCH LETTERS - n. volume 36(6) - pp. da 688 a 691 ISSN: 0167-6377 [Articolo in rivista (262) - Articolo su rivista]
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.

M. Dell'Amico; M. Iori; S. Martello; M. Monaci ( 2008 ) - Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem - INFORMS JOURNAL ON COMPUTING - n. volume 20 - pp. da 333 a 344 ISSN: 1091-9856 [Articolo in rivista (262) - Articolo su rivista]
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.

M. Dell'Amico; M. Monaci; C. Pagani; D. Vigo ( 2007 ) - Heuristic approaches for the Fleet Size and Mix Vehicle Routing Problem with Time Windows - TRANSPORTATION SCIENCE - n. volume 41 - pp. da 516 a 526 ISSN: 0041-1655 [Articolo in rivista (262) - Articolo su rivista]
Abstract

The Fleet Size and Mix Vehicle Routing Problem with Time Windows(VRPTW) is the problem of determining, at the same time, the composition and the routing of a fleet of heterogeneous vehicles aimed to serve a given set of customers. The routing problem requires to design a set of minimum cost routes originating and terminating at a central depot and serving customers with known demands, within given time windows. This paper develops a constructive insertion heuristic and a metaheuristic algorithm for VRPTW. Extensive computational experiments on benchmark instances show that the proposed method is robust and efficient, and outperforms the previously published results.

R.BALDACCI; M. DELL'AMICO; J.J. Salazar ( 2007 ) - The Capacitated m-Ring Star Problem (INFORMS:901 Elkridge Landing Road, Suite 400:Linthicum, MD 21090:(800)446-3676, (410)850-0300, EMAIL: informs@informs.org, INTERNET: http://www.informs.org, http://pubsonline.informs.org, Fax: (410)684-2963 ) - OPERATIONS RESEARCH - n. volume 55 - pp. da 1147 a 1167 ISSN: 0030-364X [Articolo in rivista (262) - Articolo su rivista]
Abstract

The Capacitated m-Ring-Star Problem (CmRSP) is the problem of designing a set of rings that pass through a central depot and through some transition points and/or customers, and then assigning each non-visited customer to a visited point or customer. The number of customers visited and assigned to a ring is bounded by an upper limit: the capacity of the ring. The objec-tive is to minimize the total routing cost plus assignment costs. The problem has practical applications in the design of urban optical telecommunication networks. This paper presents and discusses two integer programming formulations for the CmRSP. Valid inequalities are proposed to strengthen the linear programming relaxation, and are used within appropriated separation procedures in a branch-and-cut approach. The procedure is implemented and tested on a large family of instances, including real-world instances, and the good performance of the proposal is demonstrated.

Dell'Amico M.; Marzani S.; Minin L.; Montanari R.; Tesauri F.; Mariani M.; Iani C.; Tango F. ( 2007 ) - Design of an Adaptive Feedback Based Steering Wheel ( HCI International 2007 - - 22-27 July 2007) ( - HCI International 2007 ) (Springer Berlin, Heidelberg DEU ) - pp. da 1 a 10 ISBN: 9783540733522 ISSN: - [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
Abstract

This paper aims at describing the architectural model of an adaptiveforce-feedback for a By Wire steering wheel system. This solution uses asteering wheel to replicate the reactive torque law which allows the driver tocomplete a precise driving scenario or a task with the higher performances.Then, the steering wheel adapts the reactive torque to the driving scenario.Since the design of this system considers the driver performances, it is calledErgonomic Steer-By-Wire. Now a prototype version of the ESBW is connectedon a professional driving simulator and several tests are going to be conductedin order to tune the system components. Adapting the force feedback to thedriving scenario could be a solution for improving driver’s safety and vehiclecontrol.

M. DELL' AMICO; S. MARZANI; L. MININ; R. MONTANARI; F. TESAURI; M. MARIANI; C. IANI; F. TANGO ( 2007 ) - Design of an adaptive feedback based steering wheel ( - Ergonomics and health aspects of working with computers ) (Springer-Verlag BERLIN HEIDELBERG DEU ) - pp. da 180 a 188 ISBN: 03029743 ISSN: - [Contributo in volume (Capitolo o Saggio) (268) - Capitolo/Saggio]
Abstract

This paper aims at describing the architectural model of an adaptive force-feedback for a By Wire steering wheel system. This solution uses a steering wheel to replicate the reactive torque law which allows the driver to complete a precise driving scenario or a task with the higher performances. Then, the steering wheel adapts the reactive torque to the driving scenario. Since the design of this system considers the driver performances, it is called Ergonomic Steer-By-Wire. Now a prototype version of the ESBW is connected on a professional driving simulator and several tests are going to be conducted in order to tune the system components. Adapting the force feedback to the driving scenario could be a solution for improving driver’s safety and vehiclecontrol.

M. Dell'Amico ( 2006 ) - 120 esercizi di ricerca operativa (Pitagora Bologna ITA ) - pp. da 1 a 154 ISBN: 9788837116033 ISSN: - [Monografia o trattato scientifico (276) - Monografia/Trattato scientifico]
Abstract

Raccolta di esercizi svolti di ricerca operativa

M. DELL'AMICO; G. RIGHINI; M. SALANI ( 2006 ) - A Branch and Price Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery (INFORMS:901 Elkridge Landing Road, Suite 400:Linthicum, MD 21090:(800)446-3676, (410)850-0300, EMAIL: informs@informs.org, INTERNET: http://www.informs.org, http://pubsonline.informs.org, Fax: (410)684-2963 ) - TRANSPORTATION SCIENCE - n. volume 40 - pp. da 235 a 247 ISSN: 0041-1655 [Articolo in rivista (262) - Articolo su rivista]
Abstract

The vehicle routing problem with simultaneous distribution and collection (VRPSDC) is the variation of the capacitated vehicle routing problem that arises when the distribution of goods from a depot to a set of customers and the collection of waste from the customers to the depot must be performed by the same vehiclesof limited capacity and the customers can be visited in any order. We study how the branch-and-price technique can be applied to the solution of this problem and in particular we compare two different ways of solving the pricing subproblem: exact dynamic programming and state space relaxation. By applying a bidirectional search we experimentally prove its effectiveness in solving the subproblem. We also devise suitable branching strategies for both the exact and the relaxed approach and we report on an extensive set of computational experiments on benchmark instances with both simple and composite demands.

M. DELL'AMICO; M. IORI; S. MARTELLO; M. MONACI ( 2006 ) - Lower bounds and heuristic algorithms for the $k_i$-partitioning problem - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH - n. volume 171 - pp. da 725 a 742 ISSN: 0377-2217 [Articolo in rivista (262) - Articolo su rivista]
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.

S. Rubichi; C. Iani; M. Mariani; M. Dell'Amico; R. Montanari; F. Tesauri; R. Baldacci ( 2005 ) - Studio metodologico e applicazione di analisi dell'interazione uomo /macchina su display grafici per uso automotive [Altro (298) - Partecipazione a progetti di ricerca]
Abstract

L'obiettivo principale del progetto consiste nella progettazione e valutazione dell’usabilità di un display grafico destinato a trattrici agricole.

R. ARINGHIERI; M. DELL'AMICO ( 2005 ) - Comparing Intensification and Diversification Strategies for Sonet Network Design Problems. (Kluwer Academic Publishers ) - JOURNAL OF HEURISTICS - n. volume 11 - pp. da 35 a 57 ISSN: 1381-1231 [Articolo in rivista (262) - Articolo su rivista]
Abstract

This paper considers two problems that arise in the design of opti-cal telecommunication networks when a ring-based topology is adopted, namely the SONET Ring Assignment Problem and the Intraring Synchronous Optical Network Design Problem. We show that these two network topology problems correspond to graph partitioning problems with capacity constraints: the first is a vertex partitioning problem, while the latter is an edge partitioning problem. We consider solution methods for both problems, based on metaheuristic algorithms. We first describe variable objective functions that depend on the transition from one solution toa neighboring one, then we apply several diversification and intensifiation techniques including Path Relinking, eXploring Tabu Search and Scatter Search. Finally we propose a diversification method based on the use of multiple neighborhoods. A set of extensive computational results is used to compare the behaviour of the proposed methods and objective functions.

M. DELL'AMICO; S. MARTELLO ( 2005 ) - A Note on Exact Algorithms for the Identical Parallel Machine Scheduling Problem. (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598 ) - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH - n. volume 160 - pp. da 576 a 578 ISSN: 0377-2217 [Articolo in rivista (262) - Articolo su rivista]
Abstract

A recently published paper by Mokotoff presents an exact algorithm for the classical PiCmax scheduling problem, evaluating its average performance through computational experiments on a series of randomly generated test problems. It is shown that, on the same types of instances, an exact algorithm proposed 10 years ago by the authors of the present note outperforms the new algorithm by some orders of magnitude.

Dell'Amico, M.; Lodi, A. ( 2005 ) - On the integration of Tabu Search techniques in Constraint Programming ( - Metaheuristic Optimization Via Memory and Evolution ) (Kluwer Norwell USA ) - pp. da 357 a 371 ISBN: 9781402081347 ISSN: - [Contributo in volume (Capitolo o Saggio) (268) - Capitolo/Saggio]
Abstract

In a recent paper, Focacci, Laburthe and Lodi (2002) surveyed the integration between Local Search and Constraint Programming which seems to be suitable to address real-world combinatorial optimization problems. In this paper, we focus on the integration of the machinery developed in the Tabu Search context into incomplete global search algorithms based on CP. The main issue is to re-interpret the techniques developed within Tabu Search for complete solutions so as to apply them to internal nodes of a tree search, i.e., to partial solutions.

R. Aringhieri; M. Dell' Amico ( 2005 ) - A Variable-Neighborhood Variable-Objective Tabu Search Algorithm for the SONET Ring Assignment with Capacity Constraints ( - Adaptive Memory and Evolution: Tabu Search and Scatter Search ) (Kluwer Norwell USA ) - pp. da 93 a 116 ISBN: 9781402081347 ISSN: - [Contributo in volume (Capitolo o Saggio) (268) - Capitolo/Saggio]
Abstract

Synchronous Optical Network (SONET) in North America and Synchronous Digital Hierarchy (SDH) in Europe and Japan are the current transmission and multiplexing standards for high speed signals within the carrier infrastructure. The typical topology of a SONET network is a collection of rings connecting all the customer sites. We deal with a design problem in which each customer has to be assigned to exactly one ring and these rings have to be connected through a single federal ring. A capacity constraint on each ring is also imposed. The problem is to find a feasible assignment of the customers minimizing the total number of rings used.A Tabu Search method is proposed to solve the problem. The key elements are the use of a variable objective function and the strategic use of two neighborhoods. We have also implemented other techniques such as Path Relinking, eXploring Tabu Search and a Scatter Search. Extensive computational experiments have been done using two sets of benchmark instances.The performances of the proposed algorithms have also been compared with those of three multistart algorithms involving greedy methods previously proposed for the problem, and of the CPLEX solver. The computational experiments show the effectiveness of the proposed Tabu Search.

M. DELL'AMICO; M. IORI; S. MARTELLO ( 2004 ) - Heuristic Algorithms and Scatter Search for the Cardinality Constrained P||Cmax Problem (Elsevier Science Limited:Oxford Fulfillment Center, PO Box 800, Kidlington Oxford OX5 1DX United Kingdom:011 44 1865 843000, 011 44 1865 843699, EMAIL: asianfo@elsevier.com, tcb@elsevier.co.UK, INTERNET: http://www.elsevier.com, http://www.elsevier.com/locate/shpsa/, Fax: 011 44 1865 843010 ) - JOURNAL OF HEURISTICS - n. volume 10 - pp. da 169 a 204 ISSN: 1381-1231 [Articolo in rivista (262) - Articolo su rivista]
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.

M. DELL'AMICO; F. MAFFIOLI; M.L. MERANI ( 2004 ) - A Tree Partitioning Dynamic Policies for OVSF Codes Assignment in Wideband CDMA. (IEEE / Institute of Electrical and Electronics Engineers Incorporated:445 Hoes Lane:Piscataway, NJ 08854:(800)701-4333, (732)981-0060, EMAIL: subscription-service@ieee.org, INTERNET: http://www.ieee.org, Fax: (732)981-9667 ) - IEEE TRANSACTIONS ON COMMUNICATIONS - n. volume 3 - pp. da 1013 a 1017 ISSN: 0090-6778 [Articolo in rivista (262) - Articolo su rivista]
Abstract

This paper proposes some novel techniques to accommodate users with different rate requirements in a Wideband CDMA system employing orthogonal variable spreading factor codes. Several static and dynamic code assignment strategies areput forth and their behavior investigated, in terms of call blocking probability and number of required reassignments. The efficiency they exhibit under various traffic profiles is demonstrated, quantitatively comparing their performance to some codeassignment schemes recently presented in literature.

M. DELL'AMICO; F. MAFFIOLI; F. MALUCELLI ( 2003 ) - The Base-Matroid and Inverse Combinatorial Optimization (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598 ) - DISCRETE APPLIED MATHEMATICS - n. volume 128 - pp. da 335 a 353 ISSN: 0166-218X [Articolo in rivista (262) - Articolo su rivista]
Abstract

A new kind of matroid is introduced: this matroid is defined starting from any matroid and one of its bases, hence we call it Base-Matroid. Besides some properties of the base-matroid, a non trivial algorithm for the solution of the related matroid optimization problem is devised. The new matroid has application in the field of inverse combinatorial optimization problems.

M. DELL'AMICO; M. MERANI; F. MAFFIOLI ( 2002 ) - Efficient Algorithms for the Assignment of OVSF Codes in Wideband CDMA ( IEEE ICC, International Conference on Communications - - aprile-maggio 2002) ( - IEEE ICC ) (IEEE Piscataway USA ) - n. volume 5 - pp. da 3055 a 3060 ISBN: 9780780374003 ISSN: - [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
Abstract

This paper proposes some novel techniques to accommodate users with different transmission rate requirements in a CDMA system which employs orthogonal variable spreading factor codes. Several static and dynamic code assignment strategies are put forth and their behavior investigated, in terms of call blocking probability and number of required call reassignments. Their efficiency in dealing with various traffic loads is demonstrated, quantitatively showing the superior performance of our dynamic scheme with respect to a so-called "optimal" code assignment strategy recently presented in the literature.

M. DELL'AMICO; FINTA L. ( 2002 ) - A Linear Time Algorithm for Scheduling Outforests with Communication Delays on Three Processors (Academic Press Incorporated:6277 Sea Harbor Drive:Orlando, FL 32887:(800)543-9534, (407)345-4100, EMAIL: ap@acad.com, INTERNET: http://www.idealibrary.com, Fax: (407)352-3445 ) - JOURNAL OF ALGORITHMS - n. volume 44 - pp. da 287 a 307 ISSN: 0196-6774 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We consider the problem of scheduling n unit-length tasks on identical m parallel processors, when outforest precedence relations and unit interprocessor communication delays exist. Two algorithms have been proposed in the literature for the exact solution of this problem: a linear time algorithm for the special case m=2, and a dynamic programming algorithm which runs in O(n^{2m-2}). In this paper we give a new linear time algorithm for instances with m=3.

Baldacci, R.; Dell'Amico, M. ( 2002 ) - Fondamenti di Ricerca Operativa (Pitagora Bologna ITA ) - pp. da 1 a 116 ISBN: 8837113463 ISSN: - [Monografia o trattato scientifico (276) - Monografia/Trattato scientifico]
Abstract

Lezioni di Ricerca Operativa

M. Dell'Amico; S. Martello S.; D. Vigo ( 2002 ) - A Lower Bound for the Non-Orineted Two-Dimensionl Bin Packing Problem - DISCRETE APPLIED MATHEMATICS - n. volume 118 - pp. da 13 a 24 ISSN: 0166-218X [Articolo in rivista (262) - Articolo su rivista]
Abstract

Given a set of rectangular items, and an unlimited number of identical rectangular bins, we consider the problem of allocating, without overlapping, all the items to the minimum number of bins. We assume that the items may be rotated by 90◦. The problem is strongly NP-hard, and has several industrial applications. No specific lower bound is known for it. We present a lower boundwhich explicitly takes into account the possible item rotation. The bound is embedded into an exact branch-and-bound algorithm. The average performance is evaluated through computationalexperiments.

M. Dell'Amico; A. Lodi; S. Martello ( 2001 ) - Efficient Algorithms and Codes for k-Cardinality Assignment Problems - DISCRETE APPLIED MATHEMATICS - n. volume 110 - pp. da 25 a 40 ISSN: 0166-218X [Articolo in rivista (262) - Articolo su rivista]
Abstract

Given a cost matrix W and a positive integer k, the k-cardinalityassignment problem is to assign k rows to k columns so thatthe sum of the corresponding costs is a minimum.This generalization of the classical assignment problem is solvable in polynomial time, either by transformation to min-cost flow or through specific algorithms.We consider the algorithm recently proposed by Dell'Amico and Martello for the case where W is dense, and derive, for the case of sparse matrices, an efficient algorithm which includes original heuristic preprocessing techniques. The resulting code is experimentally compared with min-cost flow codes from the literature. Extensive computational tests show that the codeis considerably faster, and effectively solves very large sparse and dense instances.

M. Dell'Amico; S. Martello ( 2001 ) - Bounds for the Cardinality Constrained P||Cmax Problem - JOURNAL OF SCHEDULING - n. volume 4 - pp. da 123 a 138 ISSN: 1094-6136 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We consider the generalization of the classical P||Cmax problem arising when a given limit k is imposed on the number of jobs that can be assigned to any machine. This generalization has practicalinterest in the optimization of assembly lines for printed circuit boards (PCB). The problem is strongly NP-hard for general k, it is solvable in O(n log n) time for fixed k=2, while it remains strongly NP-hard for any fixed k >= 3. We consider immediate adaptations of simple upper and lower bounds for P||Cmax, and analyze their worst-case behavior. We show that the cardinality constraint does not strengthen the LP relaxation of the problem, and that the worst-case performance of the bounds for P||Cmax generally worsen when they are adapted to the new problem.New specifically tailored lower bounds are introduced, andtheir average tightness is evaluated through extensive computational experiments on randomly generated test instances.

M. DELL'AMICO; P. TOTH ( 2000 ) - Algorithms and Codes for Dense Assignment Problems: the State of the Art (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598 ) - DISCRETE APPLIED MATHEMATICS - n. volume 100 - pp. da 17 a 48 ISSN: 0166-218X [Articolo in rivista (262) - Articolo su rivista]
Abstract

The paper considers the classic linear assignment problem witha min-sum objective function, and the most efficient and easily available codes for its solution.We first give a survey describing the different approaches in theliterature, presenting their implementations, and pointing out similarities and differences.Then we select eight codes and we introduce a wide set of dense instances containing both randomly generated and benchmark problems.Finally we discuss the results of extensive computational experiments obtained by solving the above instances with the eight codes, both on a workstation with Unix operating system and on a personal computer running under Windows 95.

M. DELL'AMICO; F. MAFFIOLI ( 2000 ) - Combining Linear and Non Linear Objectives in Spanning Tree Problems - JOURNAL OF COMBINATORIAL OPTIMIZATION - n. volume 4 - pp. da 253 a 269 ISSN: 1382-6905 [Articolo in rivista (262) - Articolo su rivista]
Abstract

A classical approach to multicriteria problems asks for the optimization of a suitable linear combination of the objectives. In this work we address such problems when one of the objectives is the linear function, the other is a non-linear one and we seek for a spanning tree of a given graph which optimizes the combination of the two functions.We consider both maximization and minimization problems and present the complexity status of 56 such problems, giving, whenever possible, polynomial solution algorithms.

M. Dell'Amico; A. Lodi; F. Maffioli ( 1999 ) - Solution of the cumulative assignment problem with a well-structured tabu search method - JOURNAL OF HEURISTICS - n. volume 5.2 - pp. da 123 a 145 ISSN: 1381-1231 [Articolo in rivista (262) - Articolo su rivista]
Abstract

The Cumulative Assignment Problem is an NP-complete problemobtained by substituting the linear objective function of the classicLinear Assignment Problem, with a non-linear cumulative function.In this paper we present a first attempt to solve the Cumulative Assignment Problem with metaheuristic techniques.In particular we consider two standard techniques, namely the Simulated Annealing and the Multi-Start methods, and we describe the eXploring Tabu Search: a new structured Tabu Search algorithm which uses an iterative multi-level approach to improve the search.The new method is analyzed through extensive computational experiments and proves to be more effective than the standard methods.

M. DELL'AMICO; MAFFIOLI F.; LABBE' M. ( 1999 ) - Exact Solution of the SONET Ring Loading Problem (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598 ) - OPERATIONS RESEARCH LETTERS - n. volume 25 - pp. da 119 a 125 ISSN: 0167-6377 [Articolo in rivista (262) - Articolo su rivista]
Abstract

In this paper we address the problem of planning the capacity of the local rings in Synchronous Optical NETworks (SONET). We present efficient lower and upper bound procedures and a branch and bound algorithm which is able to find the exact solution of large instances within short computing times.

M. DELL'AMICO; MARTELLO S. ( 1999 ) - Reduction of the Three-Partition Problem - JOURNAL OF COMBINATORIAL OPTIMIZATION - n. volume 3 - pp. da 17 a 30 ISSN: 1382-6905 [Articolo in rivista (262) - Articolo su rivista]
Abstract

The three-partition problem is one of the most famous strongly NP-complete combinatorial problems. We introduce properties which, in many cases, can allow either a quick solution of an instance or a reduction of its size. The average effectiveness of the properties proposed is tested through computational experiments.

M. DELL'AMICO; MAFFIOLI F.; TRUBIAN M. ( 1998 ) - New Bounds for Optimum Traffic Assignment in Satellite Communication (Elsevier Science Limited:Oxford Fulfillment Center, PO Box 800, Kidlington Oxford OX5 1DX United Kingdom:011 44 1865 843000, 011 44 1865 843699, EMAIL: asianfo@elsevier.com, tcb@elsevier.co.UK, INTERNET: http://www.elsevier.com, http://www.elsevier.com/locate/shpsa/, Fax: 011 44 1865 843010 ) - COMPUTERS & OPERATIONS RESEARCH - n. volume 25 - pp. da 729 a 743 ISSN: 0305-0548 [Articolo in rivista (262) - Articolo su rivista]
Abstract

In this paper we assume that a satellite has l receivingand transmitting antennas, and we are given a traffic matrix D tobe transmittedby interconnecting pairs of receiving-transmitting antennas, through anon board switch. We also assume that l is strictly smaller thanthe number of rowsand columns of D, that no preemption of thecommunications is allowed, and that changing the configuration ofthe switch requires a negligible time. We ask for aset of switch configurations that minimizes the totaltime occurring for transmitting the entire traffic matrix.We present some new lower bounds on the optimum solution value anda new technique to combine bounds which obtains a dominating value.We then presentfive heuristics: the first two are obtained modifying algorithmsfrom the literature; two others are obtained with standard techniques;the last algorithm is an implementation of a newand promising tabu search method which is called Exploring Tabu Search.Extensive computational experimentscompare the performances of the heuristics and that of the lower bound,on randomly generated instances

M. Dell'Amico; F. Maffioli; A. Sciomachen ( 1998 ) - A Lagrangean Heuristic for Prize Collecting Travelling Salesman Problem - ANNALS OF OPERATIONS RESEARCH - n. volume 81 - pp. da 289 a 305 ISSN: 0254-5330 [Articolo in rivista (262) - Articolo su rivista]
Abstract

In this paper we consider the Prize Collecting Travelling Salesman Problem (PCTSP), that is a variant of the Travelling Salesman Problem (TSP) where a tour visiting each node at most once in a given graph has to be computed, such that a prize is associated with each node and a penalty has to be paid for every unvisited node; moreover, a knapsack constraint guarantees that a sufficiently large prize is collected. We develop a Lagrangean heuristic and obtain an upper bound in the form of a feasible solution starting from a lower bound to the problem recently proposed in the literature. We evaluate these bounds utilizing both randomly generated instances and real ones with very satisfactory results.

M. Dell'Amico; M. Trubian ( 1998 ) - Solution of Large Weighted Equicut Problems - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH - n. volume 106 - pp. da 500 a 521 ISSN: 0377-2217 [Articolo in rivista (262) - Articolo su rivista]
Abstract

Given a weighted undirected graph, the equicut problem consistsof finding a partition of the vertex set into two subsets ofequal cardinality such that the sum of the weights of the edgesbelonging to the cut defined by the partition is minimized.The problem is NP-hard and has several practical applications.In recent years a number of algorithms based on metaheuristictechniques have been proposed.In this work we first present a survey of the algorithms fromthe literature, then we propose a new tabu search algorithmand compare it with the other heuristics through extensivecomputational experiments on severalclasses of graphs with up to 4,000 nodes and 320,000 edges.The results show that our approach easily determines theoptimal solution for small graphs and its average performancesare greatly superior to those of the other approximating algorithms.

DELL'AMICO M.; MAFFIOLI F.; MARTELLO S. ( 1997 ) - Annotated Bibliographies in Combinatorial Optimization (Wiley Chicester GBR ) - pp. da 1 a 695 ISBN: 9780471965749 ISSN: - [Monografia o trattato scientifico (276) - Monografia/Trattato scientifico]
Abstract

The book presents annotated bibliographies on important toptics within the field of combinatorial optimization. However, the book offers much more than a pure bibliography as each chapter provides a coincise, comprehensive and fully up-to-date survey of that area.

M. Dell'Amico; S. Martello ( 1997 ) - Linear Assignment ( - Annotated Bibliographies in Combinatorial Optimization ) (J. Wiley chichester GBR ) - pp. da 355 a 371 ISBN: 047196574X; 9780471965749 | 9780471965749 ISSN: - [Contributo in volume (Capitolo o Saggio) (268) - Capitolo/Saggio]
Abstract

The Assignment Problem (AP) is one of the most popular and intensivelystudied topics in combinatorial optimization.This paper gives and annotathed bibliography of the most relevant papers presented in the literature.

M. DELL'AMICO; MAFFIOLI F. ( 1996 ) - On some Multicriteria Arborescence Problems: Complexity and Algorithms (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598 ) - DISCRETE APPLIED MATHEMATICS - n. volume 65 - pp. da 191 a 206 ISSN: 0166-218X [Articolo in rivista (262) - Articolo su rivista]
Abstract

The problems of finding an optimum arborescenceof a given digraph with respect to an objective function obtainedcombining linearly two (or more) objective functions of variouskinds are studied.

M. DELL'AMICO; LABBE' M.; MAFFIOLI F. ( 1996 ) - Complexity of Spanning Tree Problems with Leaf-Dependant Objective Function (John Wiley & Sons Incorporated:Customer Service, 111 River Street:Hoboken, NJ 07030:(800)225-5945, (201)748-6000, EMAIL: societyinfo@wiley.com, INTERNET: http://www.wiley.com, Fax: (212)748-6551 ) - NETWORKS - n. volume 27 - pp. da 175 a 181 ISSN: 0028-3045 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We consider the problem of finding an optimal spanning tree with respect toobjective functions which depend on the set of leaves of the tree. Weaddress 18 different such problems and determine their computational complexity.Only few of the problems examined have been given attention in theexisting literature.

M. DELL'AMICO; MARTELLO S. ( 1996 ) - Open Shop, Satellite Communication and a Theorem by Egervary (1931) (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598 ) - OPERATIONS RESEARCH LETTERS - n. volume 18 - pp. da 207 a 211 ISSN: 0167-6377 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We briefly outline recent results showing that the classical Inukai algorithm for the SS/TDMA time slot assignment problem is equivalent to a previously published algorithm for a combinatorial optimization problem, and that both implement a technique developed in 1931 by Egervary.

M. Dell'Amico ( 1996 ) - Shop Problems with two Machines and Time-Lags - OPERATIONS RESEARCH - n. volume 44 - pp. da 777 a 787 ISSN: 0030-364X [Articolo in rivista (262) - Articolo su rivista]
Abstract

We consider Job-Shop and Flow-Shop scheduling problems with twomachines, no more than two operations per job and Time Lags i.e.a minimum time intervalbetween the completion time of the firstoperation and the starting time of the second one.We give complexity results for the preemptive and non preemptive casesand study the relationship between the two problems. For the Flow-Shopproblemwe give lower bounds, upper bounds and analyze their worst-caseperformances. Finally we define a Tabu Search algorithm and provethe effectiveness of the proposed bounds throughextensive computational results.

M. Dell'Amico; S. Martello ( 1996 ) - The K-Cardinality Assignment Problem. - DISCRETE APPLIED MATHEMATICS - n. volume 76 - pp. da 103 a 121 ISSN: 0166-218X [Articolo in rivista (262) - Articolo su rivista]
Abstract

We consider a generalization of the assignment problem in which an integer k is given and onewants to assign k rows to k columns so that the sum of the corresponding costs is a minimum.The problem can be seen as a 2-matroid intersection, hence is solvable in polynomial time; immediatealgorithms for it can be obtained from transformation to min-cost flow or from classicalshortest augmenting path techniques. We introduce original preprocessing techniques for findingoptimal solutions in which g< k rows are assigned, for determining rows and columns whichmust be assigned in an optimal solution and for reducing the cost matrix. A specialized primalalgorithm is finally presented. The average computational efficiency of the different approachesis evaluated through computational experiments.

M. DELL'AMICO; CARPANETO G.; TOTH P. ( 1995 ) - Exact Solution of Large-Scale, Asymmetric Traveling Salesman Problems (ACM / Association for Computing Machinery:1515 Broadway, 17th Floor:New York, NY 10036:(212)869-7440, EMAIL: acmhelp@hq.acm.org, INTERNET: http://www.acm.org, Fax: (212)944-1318 ) - ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE - n. volume 21 - pp. da 394 a 409 ISSN: 0098-3500 [Articolo in rivista (262) - Articolo su rivista]
Abstract

A lowest-first branch and bound algorithmfor the Asymmetric Travelling Salesman Problem is presented.The methodis based on the Assignment Problem relaxation and on a subtour elimination branching scheme.The effectiveness of the algorithm derives fromreduction procedures and parametric solution of therelaxed problems associated with the nodes of the branch-decision tree. Large size uniformly randomly-generated instances of complete digraphswith up to 2,000vertices are solved on a DECstation 5000/240 computer in less than3 minutes of CPU time.In addition, we solved on a PC 486/33 no-wait flow shop problems with up to 1,000 jobs in less than 11 minutes, and real world stacker crane problems with up to 443 movements in less than 6 seconds.

M. Dell'Amico; S. Martello ( 1995 ) - Optimal Scheduling of Taskson Identical Parallel Processors - ORSA JOURNAL ON COMPUTING - n. volume 7 - pp. da 181 a 200 ISSN: 0899-1499 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We consider the classical problem of scheduling n tasks with given processing time on m identical parallel processors so as to minimizethe maximum completion time of a task. We introduce lower bounds, approximationalgorithms and a branch-and-bound procedure for the exact solution of theproblem. Extensive computational results show that, in many cases, large-sizeinstances of the problem can be solved exactly.

M. Dell'Amico; S. Martello; D. Vigo ( 1995 ) - Minimizing the Sumof Weighted Completion Times with Unrestricted Weights. - DISCRETE APPLIED MATHEMATICS - n. volume 63 - pp. da 25 a 41 ISSN: 0166-218X [Articolo in rivista (262) - Articolo su rivista]
Abstract

Given a set of tasks with associated processing times, deadlinesand weights unrestricted in sign,we consider the problem of determining a task schedule on one machineby minimizing the sum of weighted completion times.The problem is NP-hard in the strong sense.We present a lower bound based on task splitting,an approximation algorithm, and two exact approaches, one basedon branch-and-bound and one on dynamic programming. An overall exact algorithmis obtained by combining these two approaches. Extensive computationalexperiments show the effectiveness of the proposed algorithms.

G. Carpaneto; M. Dell'Amico; P. Toth ( 1995 ) - Algorithm 750: CDT A Subroutinefor the Exact Solution ofLarge-Scale, Asymmetric Traveling Salesman Problems - ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE - n. volume 21 - pp. da 410 a 415 ISSN: 0098-3500 [Articolo in rivista (262) - Articolo su rivista]
Abstract

The FORTRAN code CDT, implementing the algorithm of Carpaneto, Dell'Amico and Toth 1995afor the Asymmetric Travelling Salesman Problem, is presented. The method is based on the Assignment Problem relaxation and on a subtour elimination branching scheme. The effectiveness of the implementation derives from reduction procedures and parametric solution of the relaxed problems associated with the nodes of the branch-decision tree.

M. Dell'Amico; F Maffioli; P. Varbrand ( 1995 ) - On Prize-CollectingTours and the Asymmetric Travelling Salesman Problem - INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH - n. volume 2 - pp. da 297 a 308 ISSN: 0969-6016 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We consider a special version of the Travelling Salesman Problemwhich is to determine a tour visitingeach vertex in the graph at most one time;if a vertex is left unrouted a given penalty has to be paid.The objectivefunction is to find a balance between these penalties and the cost of thetour. We call this problem the Profitable Tour Problem (PTP). If,in addition, to each vertex is associated a price andthere is a knapsack constraint which guarantees that a sufficiently largeprice is collected, we have the well knownPrice-Collecting Travelling Salesman Problem (PCTSP).In this paper we summarize the main results presented in the literature,then we give lower bounds for the asymmetric version of PTP and PCTSP. Moreoverwe show, through computational experiments, that large size instances of theAsymmetric PTP can be solved exactly.

M. DELL'AMICO; FISCHETTI M.; TOTH P. ( 1993 ) - Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem (INFORMS:901 Elkridge Landing Road, Suite 400:Linthicum, MD 21090:(800)446-3676, (410)850-0300, EMAIL: informs@informs.org, INTERNET: http://www.informs.org, http://pubsonline.informs.org, Fax: (410)684-2963 ) - MANAGEMENT SCIENCE - n. volume 39 - pp. da 115 a 125 ISSN: 0025-1909 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We consider the NP-hard Multiple Depot Vehicle Scheduling Problem, in which a given set of time-tabled trips have to be assigned to vehicles stationed at different depots, so as to minimize the number of vehicles used and the overall operational cost. The problem arises in the management of transportation companies. In this paper some structural properties of the problem are studied and used to design a new polynomial-time heuristic algorithm which always guarantees the use of the minimum number of vehicles. Several effective refining procedures are also proposed. Extensive computational results on test problems involving up to 1,000 trips and 10 depots are reported, showing that the new approach always produces very tight approximate solutions in small computing times and outperforms other heuristics from the literature.

M. Dell'Amico; M. Trubian ( 1993 ) - Applying Tabu Search to theJob-Shop Scheduling Problem - ANNALS OF OPERATIONS RESEARCH - n. volume 41 - pp. da 231 a 252 ISSN: 0254-5330 [Articolo in rivista (262) - Articolo su rivista]
Abstract

In this paper we apply the tabu-search technique to the job shop scheduling problem , a notoriously difficult problem in combinatorial optimization. We show that our implementation of this methods dominates both a previous approach with tabu search and other heuristics based on iterative improvements.

M. DELL'AMICO; CARPANETO G.; FISCHETTI M.; TOTH P. ( 1989 ) - A Branch and Bound Algorithm for the Multiple Depot Vehicle Scheduling Problem (John Wiley & Sons Incorporated:Customer Service, 111 River Street:Hoboken, NJ 07030:(800)225-5945, (201)748-6000, EMAIL: societyinfo@wiley.com, INTERNET: http://www.wiley.com, Fax: (212)748-6551 ) - NETWORKS - n. volume 19 - pp. da 531 a 548 ISSN: 0028-3045 [Articolo in rivista (262) - Articolo su rivista]
Abstract

The Vehicle Scheduling Problem concerns the assigning of a set of time-tabled trips to vehicles so as to minimize a given cost function. We consider the NP-hard Multiple Depot case in which, in addition, one has to assign vehicles to depots. Different lower bounds based on assigment relaxation and on connectivity constraints are presented and combined in an effective bounding procedure. A strong dominance procedure derived from new dominance criteria also described. A branch and bound algorithm is finally proposed. Computational results are given.