Mauro DELL'AMICO - personale UniMoRe

Nuova ricerca

Mauro DELL'AMICO

Professore Ordinario
Dipartimento di Scienze e Metodi dell'Ingegneria

Pubblicazioni

2024 - Compact Models to Solve the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting Times [Articolo su rivista]
Dell’Amico, Mauro; Jamal, Jafar; Montemanni, Roberto
abstract

2024 - Parallel drone scheduling vehicle routing problems with collective drones [Articolo su rivista]
Montemanni, Roberto; Dell’Amico, Mauro; Corsini, Andrea
abstract

2023 - A branch-and-bound algorithm for the Precedence-Constrained Minimum-Cost Arborescence problem [Articolo su rivista]
Dell’Amico, Mauro; Jamal, Jafar; Montemanni, Roberto
abstract

2023 - Compact Models for the Precedence-Constrained Minimum-Cost Arborescence Problem [Relazione in Atti di Convegno]
Dell’Amico, Mauro; Jamal, Jafar; Montemanni, Roberto
abstract

2023 - Constraint Programming models for the parallel drone scheduling vehicle routing problem [Articolo su rivista]
Montemanni, Roberto; Dell'Amico, Mauro
abstract

2023 - Modelling and Solving the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting-Times [Relazione in Atti di Convegno]
Dell'Amico, Mauro; Jamal, Jafar; Montemanni, Roberto
abstract

2023 - Pickup and delivery with lockers [Articolo su rivista]
Dell’Amico, Mauro; Montemanni, R.; Novellani, S.
abstract

2023 - Precedence-Constrained arborescences [Articolo su rivista]
Chou, Xiaochen; Dell’Amico, Mauro; Jamal, Jafar; Montemanni, Roberto
abstract

2023 - Solving the Parallel Drone Scheduling Traveling Salesman Problem via Constraint Programming [Articolo su rivista]
Montemanni, Roberto; Dell’Amico, Mauro
abstract

2022 - Exact models for the flying sidekick traveling salesman problem [Articolo su rivista]
Dell'Amico, M.; Montemanni, R.; Novellani, S.
abstract

This paper presents three enhanced formulations for the flying sidekick traveling salesman problem, where a truck and a drone cooperate to deliver parcels to customers minimizing the completion time. The drone can leave and must return to the truck after visiting one customer, performing flights not exceeding its battery endurance while the truck can serve other customers. The new formulations allow to decrease the number of “big-M” constraints with respect to literature models and improve previous results by solving to optimality several benchmark instances for which an optimal solution was previously unknown. This paper also shows how to modify the new models to include several variants of the problem from the literature.

2022 - Learning the Quality of Machine Permutations in Job Shop Scheduling [Articolo su rivista]
Corsini, A.; Calderara, S.; Dell'Amico, M.
abstract

In recent years, the power demonstrated by Machine Learning (ML) has increasingly attracted the interest of the optimization community that is starting to leverage ML for enhancing and automating the design of algorithms. One combinatorial optimization problem recently tackled with ML is the Job Shop scheduling Problem (JSP). Most of the works on the JSP using ML focus on Deep Reinforcement Learning (DRL), and only a few of them leverage supervised learning techniques. The recurrent reasons for avoiding supervised learning seem to be the difficulty in casting the right learning task, i.e., what is meaningful to predict, and how to obtain labels. Therefore, we first propose a novel supervised learning task that aims at predicting the quality of machine permutations. Then, we design an original methodology to estimate this quality, and we use these estimations to create an accurate sequential deep learning model (binary accuracy above 95%). Finally, we empirically demonstrate the value of predicting the quality of machine permutations by enhancing the performance of a simple Tabu Search algorithm inspired by the works in the literature.

2022 - Skill-Based Joint Order Batching and Picker Routing Problem [Relazione in Atti di Convegno]
Jamal, Jafar; Loske, Dominic; Klumpp, Matthias; Chou, Xiaochen; Di Florio Di Renzo, Andrea; Dell'Amico, Mauro; Montemanni, Roberto
abstract

2021 - A Mixed Integer Linear Program for a Precedence-Constrained Minimum-Cost Arborescence Problem [Relazione in Atti di Convegno]
Dell'Amico, Mauro; Jamal, Jafar; Montemanni, Roberto
abstract

2021 - A Random Restart Local Search Matheuristic for the Flying Sidekick Traveling Salesman Problem [Relazione in Atti di Convegno]
Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
abstract

2021 - Algorithms based on Branch and Bound for the Flying Sidekick Traveling Salesman Problem [Articolo su rivista]
Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
abstract

The use of drones in urban logistics is gaining more and more interest. In this paper we consider the flying sidekick traveling salesman problem, where some customers require a delivery and they can be served either by a truck or by a drone. The aim is minimizing the total time required to service all the customers. We present a branch and bound algorithm especially designed to efficiently target small instances up to 15 customers and a heuristic algorithm, using the branch and bound as a subroutine, to attack larger instances. Extensive experimental results suggest the effectiveness of the exact solver for small instances and shows that the heuristic is able to provide state-of-the-art results for medium/large instances.

2021 - Benchmark instances and optimal solutions for the traveling salesman problem with drone [Working paper]
Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
abstract

2021 - Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem [Articolo su rivista]
Dell'Amico, M.; Montemanni, R.; Novellani, S.
abstract

In this paper we consider a problem related to deliveries assisted by an unmanned aerial vehicle, so-called drone. In particular we consider the Flying Sidekick Traveling Salesman Problem, in which a truck and a drone cooperate to deliver parcels to customers minimizing the completion time. In the following we improve the formulation found in the related literature. We propose three-indexed and two-indexed formulations and a set of inequalities that can be implemented in a branch-and-cut fashion. The methods that we propose are able to find the optimal solution for most of the literature instances. Moreover, we consider two versions of the problem: one in which the drone is allowed to wait at the customers, as in the literature, and one in which waiting is allowed only in flying mode. The solving methodologies are adapted to both versions and a comparison between the two is provided.

2021 - Modeling the Flying Sidekick Traveling Salesman Problem with Multiple Drones [Articolo su rivista]
Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
abstract

This paper considers a version of the flying sidekick travel- ing salesman problem in which parcels are delivered to cus- tomers by either a truck or a set of identical flying drones. The drones’ flights are limited by the battery endurance and each flight is made of a launch, a service to a customer, and a return: launch and return must happen when the truck is stationary. These operations require time and when multi- ple drones are launched and/or collected at the same node, their order becomes relevant. The proposed model takes into account the order of these operations as a scheduling problem, because ignoring it could lead to infeasible solu- tions in the reality due to the possible exceeding of drones endurance. We propose a set of novel formulations for the problem that can improve the size of the largest instances solved in the literature. We provide a comparison among the formulations, between the multiple drones solutions and the single drone ones, and among different variants of the model.

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 - Assessing the Impact of Shared L-Category Electric Vehicles in six European cities [Relazione in Atti di Convegno]
Dell'Amico, M.; Hadjidimitriou, N. S.; Renzi, G.
abstract

This paper proposes a methodology to assess the impact of shared light electric vehicles in urban areas. The proposed approach consists of the comparison between the emissions and costs of travels carried out by traditional cars fueled by gasoline and those performed by shared light electric vehicles in six European cities (Bari, Berlin, Genoa, Malaga, Rome and Trikala) located in four different European countries (Italy, Germany, Spain and Greece). Based on the number of kilometers traveled and a set of conversion factors, the environmental impact and the cost of fuel/electricity are assessed for the two transport modes. Furthermore, the paper proposes a methodology to create a geographical scaled up scenario that allows to evaluate emissions and costs in case of an increased use of shared electric vehicles. The data analyzed revealed that the travel time of L-category electric vehicles might be longer compared to cars. Furthermore, by replacing car trips with L-category electric vehicles, CO 2 emissions could decrease of more than 70% in one year, thus reducing about 6, 082 kg of CO 2 emissions.

2020 - Machine Learning for Severity Classification of Accidents Involving Powered Two Wheelers [Articolo su rivista]
Hadjidimitriou, N. S.; Dell'Amico, M.; Lippi, M.; Skiera, A.
abstract

Road traffic safety is one of the major challenges for the future of smart cities and transportation networks. Despite several solutions exist to reduce the number of fatalities and severe accidents happening daily in our roads, this reduction is smaller than expected and new methods and intelligent systems are needed. The emergency Call is an initiative of the European Commission aimed at providing rapid assistance to motorists thanks to the implementation of a unique emergency number. In this work, we study the problem of classifying the severity of accidents involving Powered Two Wheelers, by exploiting machine learning systems based on features that could be reasonably collected at the moment of the accident. An extended study on the set of features allows to identify the most important factors that allow to distinguish accident severity. The system we develop achieves over 90% of precision and recall on a large, publicly available corpus, using only a set of twelve features.

2020 - Matheuristic algorithms for the parallel drone scheduling traveling salesman problem [Articolo su rivista]
Dell'Amico, M.; Montemanni, R.; Novellani, S.
abstract

In a near future drones are likely to become a viable way of distributing parcels in a urban environment. In this paper we consider the parallel drone scheduling traveling salesman problem, where a set of customers requiring a delivery is split between a truck and a fleet of drones, with the aim of minimizing the total time required to service all the customers. We present a set of matheuristic methods for the problem. The new approaches are validated via an experimental campaign on two sets of benchmarks available in the literature. It is shown that the approaches we propose perform very well on small/medium size instances. Solving a mixed integer linear programming model to optimality leads to the first optimality proof for all the instances with 20 customers considered, while the heuristics are shown to be fast and effective on the same dataset. When considering larger instances with 48 to 229 customers, the results are competitive with state-of-the-art methods and lead to 28 new best known solutions out of the 90 instances considered.

2020 - Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time [Articolo su rivista]
Kramer, A.; Dell'Amico, M.; Feillet, D.; Iori, M.
abstract

This paper addresses the problem of scheduling a set of jobs that are released over the time on a set of identical parallel machines, aiming at the minimization of the total weighted completion time. This problem, referred to as P|rj|∑wjCj, is of great importance in practice, because it models a variety of real-life applications. Despite its importance, the P|rj|∑wjCj has not received much attention in the recent literature. In this work, we fill this gap by proposing mixed integer linear programs and a tailored branch-and-price algorithm. Our branch-and-price relies on the decomposition of an arc-flow formulation and on the use of efficient exact and heuristic methods for solving the pricing subproblem. Computational experiments carried out on a set of randomly generated instances prove that the proposed methods can solve to the proven optimality instances with up to 200 jobs and 10 machines, and provide very low gaps for larger instances.

2020 - 1 A Random Restart Local Search Matheuristic for the Flying Sidekick Traveling Salesman Problem [Relazione in Atti di Convegno]
Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
abstract

2019 - A Decision Support System for Earthwork Activities in Construction Logistics [Capitolo/Saggio]
Dell’Amico, M.; Fuellerer, G.; Hoeflinger, G.; Novellani, S.
abstract

Making decisions in a complex system such as the construction of a highway is a hard task that involves a combinatorial set of possibilities, concerning thousands of interrelated activities and resources over several years. In this paper we describe a decision support system (DSS) developed to assist project managers in decision making for the construction of the Autostrada Pedemontana Lombarda highway, in Italy. The considered problem evaluates the earthwork activities in de- tail and defines the minimum cost earthwork plan satisfying all constraints. The proposed DSS involves the use of linear programming to solve the earthwork pro- blem in a 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 DSS gathers the needed informa- tion directly from the master plan commonly used by the company and provides as output a set of visual solutions. The solution are yielded in short times and can be run many times with different data sets supporting a fast evaluation of different decisions. The provided solutions are also optimized and could substitute the previ- ous manual results. The DSS has been proved to be very effective for assisting the project managers of the above highway construction and is currently in use in other projects

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 - Models and algorithms for the Flying Sidekick Traveling Salesman Problem [Working paper]
Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
abstract

2019 - On f-domination: polyhedral and algorithmic results [Articolo su rivista]
Dell'Amico, M.; Neto, J.
abstract

Given an undirected simple graph G with node set V and edge set E, let fv, for each node v∈ V, denote a nonnegative integer value that is lower than or equal to the degree of v in G. An f-dominating set in G is a node subset D such that for each node v∈ V D at least fv of its neighbors belong to D. In this paper, we study the polyhedral structure of the polytope defined as the convex hull of all the incidence vectors of f-dominating sets in G and give a complete description for the case of trees. We prove that the corresponding separation problem can be solved in polynomial time. In addition, we present a linear-time algorithm to solve the weighted version of the problem on trees: Given a cost cv∈ R for each node v∈ V, find an f-dominating set D in G whose cost, given by ∑ v∈Dcv, is a minimum.

2019 - On total f-domination: Polyhedral and algorithmic results [Articolo su rivista]
Dell'Amico, M.; Neto, Jose'
abstract

Given an undirected simple graph G with node set V and edge set E, let fv, for each node v∈V, denote a nonnegative integer value that is lower than or equal to the degree of v in G. An f-dominating set in G is a node subset D such that for each node v∈V∖D at least fv of its neighbors belong to D. In this paper, we study the polyhedral structure of the polytope defined as the convex hull of all the incidence vectors of f-dominating sets in G and give a complete description for the case of trees. We prove that the corresponding separation problem can be solved in polynomial time. In addition, we present a linear-time algorithm to solve the weighted version of the problem on trees: Given a cost cv∈R for each node v∈V, find an f-dominating set D in G whose cost, given by ∑v∈Dcv, is a minimum.

2018 - Forecasting natural gas flows in large networks [Relazione in Atti di Convegno]
Dell'Amico, M.; Hadjidimitriou, N. S.; Koch, T.; Petkovic, M.
abstract

Natural gas is the cleanest fossil fuel since it emits the lowest amount of other remains after being burned. Over the years, natural gas usage has increased significantly. Accurate forecasting is crucial for maintaining gas supplies, transportation and network stability. This paper presents two methodologies to identify the optimal configuration o parameters of a Neural Network (NN) to forecast the next 24h of gas flow for each node of a large gas network. In particular the first one applies a Design Of Experiments (DOE) to obtain a quick initial solution. An orthogonal design, consisting of 18 experiments selected among a total of 4.374 combinations of seven parameters (training algorithm, transfer function, regularization, learning rate, lags, and epochs), is used. The best result is selected as initial solution of an extended experiment for which the Simulated Annealing is run to find the optimal design among 89.100 possible combinations of parameters. The second technique is based on the application of Genetic Algorithm for the selection of the optimal parameters of a recurrent neural network for time series forecast. GA was applied with binary representation of potential solutions, where subsets of bits in the bit string represent different values for several parameters of the recurrent neural network. We tested these methods on three municipal nodes, using one year and half of hourly gas flow to train the network and 60 days for testing. Our results clearly show that the presented methodologies bring promising results in terms of optimal configuration of parameters and forecast error.

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.

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 two-echelon facility location problem with stochastic demands for urban construction logistics: An application within the SUCCESS project [Relazione in Atti di Convegno]
Dell'Amico, Mauro; Novellani, Stefano
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).

2017 - Classification of Livebus arrivals user behavior [Articolo su rivista]
Hadjidimitriou, N.; Mamei, M.; Dell'Amico, M.; Kaparias, I.
abstract

With the increasing use of Intelligent Transport Systems, large amounts of data are created. Innovative information services are introduced and new forms of data are available, which could be used to understand the behavior of travelers and the dynamics of people flows. This work analyzes the requests for real-time arrivals of bus routes at stops in London made by travelers using Transport for London's LiveBus Arrivals system. The available dataset consists of about one million requests for real-time arrivals for each of the 28 days under observation. These data are analyzed for different purposes. LiveBus Arrivals users are classified based on a set of features and using K-Means, Expectation Maximization, Logistic regression, One-level decision tree, Decision Tree, Random Forest, and Support Vector Machine (SVM) by Sequential Minimal Optimization (SMO). The results of the study indicate that the LiveBus Arrivals requests can be classified into six main behaviors. It was found that the classification-based approaches produce better results than the clustering-based ones. The most accurate results were obtained with the SVM-SMO methodology (Precision of 97%). Furthermore, the behavior within the six classes of users is analyzed to better understand how users take advantage of the LiveBus Arrivals service. It was found that the 37% of users can be classified as interchange users. This classification could form the basis of a more personalized LiveBus Arrivals application in future, which could support management and planning by revealing how public transport and related services are actually used or update information on commuters.

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.

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 - Advanced Services for Electromobility: the Integration of the SmartCEM Project Platform for the Reggio Emilia Pilot Site [Capitolo/Saggio]
Dell'Amico, Mauro; Di Pasquale, Guido; Guidotti, Leandro; Mascolo, Pietro
abstract

This chapter presents the Italian test site currently in progress within the smartCEM project. The EC co‐funded project smartCEM is aimed at implementing an ICT platform for the integration of five electromobility services that includes electric vehicle (EV)‐sharing management, EV‐efficient driving, EV‐navigation, EV‐trip management and EV‐charging station management to be piloted in four different pilot sites across Europe. The smartCEM project provides added value by setting up a common framework for combining the five electromobility services into a more complex integrated system. The Reggio Emilia pilot site main objectives are focused on increasing stakeholder awareness and users' confidence in electric vehicles, by assessing the acceptance of efficient driving, navigation and monitoring management services designed for EVs. Vehicles will be equipped with a data acquisition system and an Android device on which smartCEM services will be installed.

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

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 - Assessing the consistency between observed and modelled route choices through GPS data [Relazione in Atti di Convegno]
Hadjidimitriou, Natalia; Dell'Amico, Mauro; Cantelmo, Guido; Viti, Francesco
abstract

In traffic engineering, different assumptions on user behaviour are adopted in order to model the traffic flow propagation on the transport network. This paper deals with the classical hypothesis that drivers use the shortest possible path for their trip, pointing out the error related to using such approximation in practice, in particular in the context of dynamic origin-destination (OD) matrix estimation. If this problem is already well known in the literature, only few works are available, which provide quantitative and empirical analysis of the discrepancy between observed and modelled route sets and choices. This is mainly related to the complexity of collecting suitable data: to analyse route choice in a systematic way, it is necessary to have observations for a large period of time, since observing trajectories for the single user on a specific day could not be enough. Information is required for several days in order to analyse the repetitiveness and understand which elements influence this choice. In this work the use of the real shortest path for a congested network is evaluated, showing the differences between what we model and what users do. Results show that there is a systematic difference between the best possible choice and the actual choice, and that users clearly consider route travel time reliability in their choice process.

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

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 - DESIGN AND OPTIMIZATION OF PICKING IN THE CASE OF MULTI-ITEM MULTI-LOCATION MULTI-PALLET CUSTOMER ORDERS [Capitolo/Saggio]
Gamberini, Rita; Rimini, Bianca; Dell'Amico, Mauro; Lolli, Francesco; Bianchi, M.
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.

2012 - Innovative Logistics Model and Containers Solution for Efficient Last Mile Delivery [Relazione in Atti di Convegno]
Dell’Amico, Mauro; Hadjidimitriou, Selini
abstract

Urban goods distribution is important for the economy. However urban transport causes traffic, noise and pollution. The European Research project CityLog (part of Framework Programme 7) aims at increasing efficiency in urban distribution by proposing a logistics model based on two types of vehicles and containers solution in the context of parcel delivery. The urban delivery scheme currently consists of a number of vehicles that leave the hub and drive towards the city. The innovative logistics model for urban deliveries introduces a concept which make use of two types of vehicles: a Freight bus which is loaded at the depot with several load units that can carry generic parcels, and a Delivery van which is a light vehicle with high eco-compatible characteristics that make it very suitable to be used in the inner city Each load unit, when transferred from the Freight bus to the Delivery van, replaces the body of the van. These interoperable vehicles and containers form an improved logistics chain, reducing the number of vehicles entering the city, chilometers driven and pollutant emissions. Another source of unnecessary driven chilometers is unsuccessful deliveries when the receiver is not home during the delivery. The Modular BentoBox is the second concept introduced by the project. It allows to obtain a balance between optimisation of logistics and customers' interests by delivering goods to the bentobox, instead that to the customer location.. There parcels are stored in the bentobox until the customer picks them up. The Modular BentoBox System introduces the concept of removable modules that is trolleys with various size drawers. These trolleys and their drawers are filled in with parcels at the depot. The carrier transports the trolleys downtown and inserts them into the bentobox. As soon as the customer is notified, the parcel is ready at the bentobox. To access the parcel, the customer enters his special code on a user interface. The Modular BentoBox System can also be provided with a weighting and payment system and used for shipping parcels. The trolleys with shipments are taken back to the depot by the carrier. These CityLog concepts will be implemented and tested in 2012 in three European cities: Berlin, Lyon and Turin. (C) 2012 Published by Elsevier Ltd. Selection and/or peer review under responsibility of the Programme Committee of the Transport Research Arena 2012

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 - CityLog - Sustainability and efficiency of city logistics: The M-BBX (Modular BentoBox System) [Relazione in Atti di Convegno]
Dell'Amico, M.; Deloof, W.; Hadjidimitriou, N.; Vernet, G.; Schoenewolf, W.
abstract

This paper presents some of the results of CityLog, a European Union project approved in the context of the 7th Framework Programme that is still ongoing and will terminate at the end of 2012. The project is intended to increase the sustainability and the efficiency of urban delivery of goods through an adaptive and integrated mission management and innovative vehicle solutions. Three partners of the CityLog consortium were in charge of the design and realization of a new container concept which had to be adapted to the associated innovative vehicles solutions for load units' handling operation. © 2011 IEEE.

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 - 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 - Heuristic Algorithms for the Multiple-Depot Ring-Star Problem [Articolo su rivista]
R., Baldacci; Dell'Amico, Mauro
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

2009 - A subjective field test on lane departure warning function in the framework of the euroFOT project [Relazione in Atti di Convegno]
Burzio, G.; Mussino, G.; Tadei, R.; Perboli, G.; Dell'Amico, M.; Guidotti, L.
abstract

This paper will present the Italian Field Operation Test (FOT) to be performed within the European Project euroFOT, aimed at assessing a wide variety of Intelligent Transport Systems (ITS) across Europe. This FOT is aimed at investigating an already marketed Lane Departure Warning (LDW) equipped on the Lancia Delta vehicles, deploying a sample of up to 1000 vehicles, and using a wide and differentiated set of self-reported questionnaires. Results will be referred to LDW impact on traffic safety, usefulness, and driving behavior. Given the huge sample, results are expected to accurately depict the actual impact of this function.

2009 - A subjective field test on lane departure warning function in the framework of the eurofot project [Relazione in Atti di Convegno]
Burzio, G.; Mussino, G.; Tadei, R.; Perboli, G.; Dell'Amico, M.; Guidotti, L.
abstract

2009 - Assignment Problems [Monografia/Trattato scientifico]
R., Burkard; Dell'Amico, Mauro; S., Martello
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.

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 - 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 - 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 - Design of an Adaptive Feedback Based Steering Wheel [Relazione in Atti di Convegno]
Dell'Amico, Mauro; Marzani, Stefano; Minin, Luca; Montanari, Roberto; Tesauri, Francesco; Mariani, Michele; Iani, Cristina; Tango, F.
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.

2007 - Heuristic approaches for the Fleet Size and Mix Vehicle Routing Problem with Time Windows [Articolo su rivista]
Dell'Amico, Mauro; M., Monaci; Pagani, Corrado; D., Vigo
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.

2007 - The Capacitated m-Ring Star Problem [Articolo su rivista]
R., Baldacci; Dell'Amico, Mauro; J. J., Salazar
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.

2006 - A Branch and Price Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery [Articolo su rivista]
Dell'Amico, Mauro; G., Righini; M., Salani
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.

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.

2006 - 120 esercizi di ricerca operativa [Monografia/Trattato scientifico]
Dell'Amico, Mauro
abstract

Raccolta di esercizi svolti di ricerca operativa

2005 - A Note on Exact Algorithms for the Identical Parallel Machine Scheduling Problem. [Articolo su rivista]
Dell'Amico, Mauro; S., Martello
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.

2005 - Comparing Metaheuristic Algorithms for Sonet Network Design Problems [Articolo su rivista]
Arinhgieri, R.; Dell'Amico, M.
abstract

This paper considers two problems that arise in the design of optical 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 to a neighboring one, then we apply several diversification and intensification 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.

2005 - On the Integration of Metaheuristic Strategies in Constraint Programming [Capitolo/Saggio]
Dell'Amico, M.; Lodi, A.
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 reinterpret 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.

2005 - On the integration of Tabu Search techniques in Constraint Programming [Capitolo/Saggio]
Dell'Amico, Mauro; Lodi, A.
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.

2005 - Solution of the SONET ring assignment problem with capacity constraints [Capitolo/Saggio]
R., Aringhieri; Dell'Amico, Mauro
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.

2004 - A Tree Partitioning Dynamic Policies for OVSF Codes Assignment in Wideband CDMA. [Articolo su rivista]
Dell'Amico, Mauro; F., Maffioli; Merani, Maria Luisa
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.

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 - The Base-Matroid and Inverse Combinatorial Optimization [Articolo su rivista]
Dell'Amico, Mauro; F., Maffioli; F., Malucelli
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.

2002 - A Linear Time Algorithm for Scheduling Outforests with Communication Delays on Three Processors [Articolo su rivista]
Dell'Amico, Mauro; Finta, L.
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.

2002 - A Lower Bound for the Non-Orineted Two-Dimensionl Bin Packing Problem [Articolo su rivista]
Dell'Amico, Mauro; S. Martello, S.; D., Vigo
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.

2002 - Efficient algorithms for the assignment of OVSF codes in wideband CDMA [Relazione in Atti di Convegno]
Dell’Amico, M.; Merani, M. L.; Maffioli, F.
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.

2002 - Fondamenti di Ricerca Operativa [Monografia/Trattato scientifico]
Baldacci, R.; Dell'Amico, Mauro
abstract

Lezioni di Ricerca Operativa

2001 - Bounds for the Cardinality Constrained P||Cmax Problem [Articolo su rivista]
Dell'Amico, Mauro; S., Martello
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.

2001 - Efficient Algorithms and Codes for k-Cardinality Assignment Problems [Articolo su rivista]
Dell'Amico, Mauro; A., Lodi; S., Martello
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.

2000 - Algorithms and Codes for Dense Assignment Problems: the State of the Art [Articolo su rivista]
Dell'Amico, Mauro; P., Toth
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.

2000 - Combining Linear and Non Linear Objectives in Spanning Tree Problems [Articolo su rivista]
Dell'Amico, Mauro; F., Maffioli
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.

1999 - Exact Solution of the SONET Ring Loading Problem [Articolo su rivista]
Dell'Amico, Mauro; Maffioli, F.; Labbe', M.
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.

1999 - Reduction of the Three-Partition Problem [Articolo su rivista]
Dell'Amico, Mauro; Martello, S.
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.

1999 - Solution of the cumulative assignment problem with a well-structured tabu search method [Articolo su rivista]
Dell'Amico, Mauro; A., Lodi; F., Maffioli
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.

1998 - A Lagrangean Heuristic for Prize Collecting Travelling Salesman Problem [Articolo su rivista]
Dell'Amico, Mauro; F., Maffioli; A., Sciomachen
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.

1998 - Algorithms and Codes for Dense Assignment Problems: the State of the Art [Working paper]
Dell'Amico, M.; Toth, P.
abstract

1998 - New Bounds for Optimum Traffic Assignment in Satellite Communication [Articolo su rivista]
Dell'Amico, Mauro; Maffioli, F.; Trubian, M.
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

1998 - Solution of Large Weighted Equicut Problems [Articolo su rivista]
Dell'Amico, Mauro; M., Trubian
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.

1997 - A Linear Time Algorithm for Scheduling Outforests with Communication Delays on Two or Three Processors [Working paper]
Dell'Amico, M.
abstract

1997 - Annotated Bibliographies in Combinatorial Optimization [Monografia/Trattato scientifico]
Dell'Amico, Mauro; Maffioli, F.; Martello, S.
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.

1997 - Combining Linear and Non-Linear Objectives in Spanning Tree Problems [Working paper]
Dell'Amico, M.; Maffioli, F.
abstract

1997 - Linear Assignment [Capitolo/Saggio]
Dell'Amico, Mauro; S., Martello
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.

1997 - New bounds for optium traffic assignment in satellite communication [Working paper]
Dell'Amico, Mauro; Maffioli, Francesco; Trubian, Marco
abstract

1997 - On the Continuous Relaxation of Packing Problems- Technical Note [Working paper]
Dell'Amico, M.
abstract

1997 - Reduction of the Three- Partition Problem [Working paper]
Dell'Amico, Mauro; Martello, Silvano
abstract

1997 - Solution of the Cumulative Assignment Problem with a Weii-Structured Tabu Search Method [Working paper]
Dell'Amico, Mauro; Lodi, Andrea; Maffioli, Francesco
abstract

1996 - A Lagrangean Heuristic for the Pirze Collecting Travelling Salesman Problem [Working paper]
Dell'Amico, M.; Maffioli, F; Sciomachen, A.
abstract

1996 - Almost-optimal solution of large weighted equicut problems [Working paper]
Dell'Amico, M.; Trubian, M.
abstract

1996 - Complexity of Spanning Tree Problems with Leaf-Dependant Objective Function [Articolo su rivista]
Dell'Amico, Mauro; Labbe', M.; Maffioli, F.
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.

1996 - Exact solution of the SO NET Ring Loading Problem [Working paper]
Dell'Amico, M.; Labbé, M.; Maffioli, F.
abstract

1996 - Flow and open shop scheduling on two machines with transportation times and machine-independent processing times in NP-hard [Working paper]
Dell'Amico, M.
abstract

1996 - On some Multicriteria Arborescence Problems: Complexity and Algorithms [Articolo su rivista]
Dell'Amico, Mauro; Maffioli, F.
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.

1996 - Open Shop, Satellite Communication and a Theorem by Egervary (1931) [Articolo su rivista]
Dell'Amico, Mauro; Martello, S.
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.

1996 - Shop Problems with two Machines and Time-Lags [Articolo su rivista]
Dell'Amico, Mauro
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.

1996 - The K-Cardinality Assignment Problem. [Articolo su rivista]
Dell'Amico, Mauro; S., Martello
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.

1995 - Algorithm 750: CDT A Subroutinefor the Exact Solution ofLarge-Scale, Asymmetric Traveling Salesman Problems [Articolo su rivista]
G., Carpaneto; Dell'Amico, Mauro; P., Toth
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.

1995 - Exact Solution of Large-Scale, Asymmetric Traveling Salesman Problems [Articolo su rivista]
Dell'Amico, Mauro; Carpaneto, G.; Toth, P.
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.

1995 - Minimizing the Sumof Weighted Completion Times with Unrestricted Weights. [Articolo su rivista]
Dell'Amico, Mauro; S., Martello; D., Vigo
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.

1995 - On Prize-CollectingTours and the Asymmetric Travelling Salesman Problem [Articolo su rivista]
Dell'Amico, Mauro; F., Maffioli; P., Varbrand
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.

1995 - Optimal Scheduling of Taskson Identical Parallel Processors [Articolo su rivista]
Dell'Amico, Mauro; S., Martello
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.

1993 - Applying Tabu Search to theJob-Shop Scheduling Problem [Articolo su rivista]
Dell'Amico, Mauro; M., Trubian
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.

1993 - Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem [Articolo su rivista]
Dell'Amico, Mauro; Fischetti, M.; Toth, P.
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.

1989 - A Branch and Bound Algorithm for the Multiple Depot Vehicle Scheduling Problem [Articolo su rivista]
Dell'Amico, Mauro; Carpaneto, G.; Fischetti, M.; Toth, P.
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.

Università degli studi di Modena e Reggio Emilia

Pubblicazioni