 |
Roberto MONTEMANNI
Professore Ordinario
Dipartimento di Scienze e Metodi dell'Ingegneria
|
Home |
Curriculum(pdf) |
Didattica |
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
- Exploring the performance impact of unit load selection in order picking: evidence from a cold retail supply chain
[Articolo su rivista]
Loske, Dominic; Modica, Tiziana; Klumpp, Matthias; Montemanni, Roberto
abstract
2024
- On Solving the Set Orienteering Problem
[Articolo su rivista]
Montemanni, Roberto; Smith, Derek H.
abstract
2024
- Parallel drone scheduling vehicle routing problems with collective drones
[Articolo su rivista]
Montemanni, Roberto; Dell’Amico, Mauro; Corsini, Andrea
abstract
2023
- A Constraint Programming Model for the B-Coloring Problem
[Relazione in Atti di Convegno]
Montemanni, Roberto; Carraretto, Gabriel Henrique; Mele, Umberto Junior; Gambardella, Luca Maria
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
- Ergonomics and Storage Base Position for U-shaped Picking Zones
[Relazione in Atti di Convegno]
Montemanni, Roberto; Landolfo, Alfredo; Chou, Xiaochen; Loske, Dominic; Klumpp, Matthias
abstract
2023
- Mathematical Models for Order Batching and Assignment in a Deep-Frozen Warehouse
[Relazione in Atti di Convegno]
Pretolani, Daniele; Chou, Xiaochen; Loske, Dominic; Klumpp, Matthias; Montemanni, Roberto
abstract
2023
- Maximum Independent Sets and Supervised Learning
[Articolo su rivista]
Montemanni, Roberto; Smith, Derek H.; Chou, Xiaochen
abstract
The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem. In particular, it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted, with measurable effects on the quality of the solutions provided on unseen instances. Empirical results are presented to validate the idea.
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
2023
- The missing Moore graph as an optimization problem
[Articolo su rivista]
Smith, Derek H.; Montemanni, Roberto
abstract
2022
- A decision support tool for intelligent manufacturing systems via an elevator kinematic optimisation based method
[Articolo su rivista]
Luangpaiboon, Pongchanun; Aungkulanon, Pasura; Montemanni, Roberto
abstract
2022
- AMR-Assisted Order Picking: Models for Picker-to-Parts Systems in a Two-Blocks Warehouse
[Articolo su rivista]
Pugliese, Giulia; Chou, Xiaochen; Loske, Dominic; Klumpp, Matthias; Montemanni, Roberto
abstract
2022
- An Elevator Kinematics Optimization Algorithm based on a Large Neighborhood Search for Optimizing Simulated Industrial Problems
[Relazione in Atti di Convegno]
Luangpaiboon, Pongchanun; Aungkulanon, Pasura; Ruekkasaem, Lakkana; Montemanni, Roberto
abstract
2022
- An Iterative Matheuristic Algorithm for the B-Coloring Problem
[Relazione in Atti di Convegno]
Montemanni, R.; Smith, D. H.
abstract
B-coloring is a problem in graph theory at the basis of several real applications and also used to improve solution methods for the classical coloring problem. Enhanced solutions for the classical coloring problem have in turn impacts on several other practical applications in scheduling, timetabling and telecommunications. Namely, given a graph G = (V, E), the b-coloring problem consists of maximizing the number of colors used while assigning a color to every vertex in V such that no pair of adjacent vertices receive the same color and every color has a representative, called a b-vertex. A vertex can be a b-vertex if it is adjacent to vertices colored with all the colors apart from the one assigned to it. In this paper we present a novel Iterative Matheuristic Algorithm based on considerations about the structure of promising solutions and a mathematical programming model. A vast section of computational experiments shows how the approach is able to find high quality solutions for commonly established datasets from the literature. In particular, the method we propose is able to improve the best known heuristic solution for 38 instances of the 137 considered. The optimality of the bounds previously known for another 5 instances has also been proved by running the approach we propose exhaustively.
2022
- Assessing the duration of intralogistics forklift operations via machine learning
[Relazione in Atti di Convegno]
Chou, X.; Loske, D.; Klumpp, M.; Montemanni, R.
abstract
In the ongoing transition to Logistics 4.0, humans and technologies are increasingly interacting in operations systems. An example is the use of wireless devices for operation logs in the warehouse management systems. The performance and quality of such systems depend on human behaviors to a noticeable extent. Valid data from compliant operations provide great value for follow-up researches, while in actual operations deviant behaviors occur and contaminate the data. Quantitative studies on whether and to which extent operators do infringe or fulfill the organizational norms in the execution of digital workflows are limited. To close this gap, in this work we conduct a data-driven assessment of the duration of forklift operations in a German warehouse owned by a grocery retailing chain. By predicting the execution time of forklift picking tasks with given features, we study the proportion of standardized operations performed by different operators based on predicting accuracy. This could serve as an effective indicator before further developing systems using machine learning technologies for better distribution of the tasks based on the relevance of the operators' skills and the tasks' characteristics.
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
- Machine Learning Constructives and Local Searches for the Travelling Salesman Problem
[Relazione in Atti di Convegno]
Vitali, T; Mele, U; Gambardella, Lm; Montemanni, R
abstract
The ML-Constructive heuristic is a recently presented method and the first hybrid method capable of scaling up to real scale traveling salesman problems. It combines machine learning techniques and classic optimization techniques. In this paper we present improvements to the computational weight of the original deep learning model. In addition, as simpler models reduce the execution time, the possibility of adding a local-search phase is explored to further improve performance. Experimental results corroborate the quality of the proposed improvements.
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
2022
- The Maximum Clique Problem for Permutation Hamming Graphs
[Articolo su rivista]
Barta, János; Montemanni, Roberto
abstract
2022
- The Picking and Packing Problem in Buy-Online-Pick-up-in-Store Retailing
[Relazione in Atti di Convegno]
Pietri, No; Chou, Xc; Loske, D; Klumpp, M; Jamal, J; Montemanni, R
abstract
With the rapid increase of digitization and desire for contactless shopping during the COVID-19 pandemic, online grocery sales keep growing fast. Correspondingly, optimized policies for order picking are nowadays central in omnichannel supply chains, not only within dedicated warehouses but also in grocery stores while processing online orders. In this work, we apply the Buy-Online-Pick-up-in-Store concept and optimize the in-store picking and packing procedure.The approach we propose, which is based on two mathematical programming models, guides pickers on how to organize articles into bags while collecting items. In this way bags are filled up evenly and they are ready to be handled to the customers at the end of each picking task, with no further rearrangement needed.
2022
- Upper and lower bounds based on linear programming for the b-coloring problem
[Articolo su rivista]
Montemanni, Roberto; Chou, Xiaochen; Smith, Derek H.
abstract
2021
- 3-opt Metaheuristics for the Probabilistic Orienteering Problem
[Relazione in Atti di Convegno]
Chou, Xiaochen; Maria Gambardella, Luca; Luangpaiboon, Pongchanun; Aungkulanon, Pasura; 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 New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem
[Articolo su rivista]
Junior Mele, Umberto; Maria Gambardella, Luca; 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
- A Tabu Search algorithm for the Probabilistic Orienteering Problem
[Articolo su rivista]
Chou, X.; Gambardella, L. M.; Montemanni, R.
abstract
The Orienteering Problem is a routing problem aiming at selecting a subset of a given set of customers to be visited within a given time budget, so that a total revenue is maximized. Multiple variants of the problem have been studied. The Probabilistic Orienteering Problem is one of these variants, where customers will require a visit according to a certain given probability. Stochasticity makes the model more practical, but concurrently more difficult to solve. Tabu Search is a method widely used in combinatorial optimization problems to escape from local optima in heuristic local search procedures. In this work, we solve the Probabilistic Orienteering Problem by embedding a Monte Carlo evaluator into a Tabu Search algorithm, exploiting their interaction in an innovative way. A detailed computational study of the new approach is presented, with the aim of studying the performance of the metaheuristic algorithm in terms of precision and speed, while positioning the new method within the existing literature.
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
- In-store Picking Strategies for Online Orders in Grocery Retail Logistics
[Capitolo/Saggio]
Chou, X.; Loske, D.; Klumpp, M.; Gambardella, L. M.; Montemanni, R.
abstract
Customers shifting from stationary to online grocery shopping and the decreasing mobility of an ageing population pose major challenges for the stationary grocery retailing sector. To fulfill the increasing demand for online grocery shopping, traditional bricks-and-mortar retailers use existing store networks to offer customers click-and-collect services. The current COVID-19 pandemic is substantially accelerating the transition to such a mixed offline/online model, and companies like the one behind this study are facing the urgent need of a re-design of their business model to cope with the change. Currently, a majority of the operations to service online demand consists of in-store picker-to-parts order picking systems, where employees go around the shelves of the shop to pick up the articles of online orders. The optimization of such operations is entirely left to the experience of the staff at the moment. Since in-store operations are a major cost-driver in retail supply chains, this paper proposes optimization ideas and solutions for these in-store operations. With experimental simulations run on a real store with real online orders, we show that a simple optimization tool can improve the situation substantially. The method is easy to apply and adaptable to stores with complex topologies.
2021
- Machine Learning Approaches for the Traveling Salesman Problem: A Survey
[Relazione in Atti di Convegno]
Mele Junior, Umberto; Maria Gambardella, Luca; Montemanni, Roberto
abstract
2021
- Machine learning and combinatorial optimization, editorial
[Articolo su rivista]
Di Caro, G. A.; Maniezzo, V.; Montemanni, R.; Salani, M.
abstract
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.
2021
- Multi-objective periodic maintenance scheduling and optimization via krill herd algorithm
[Articolo su rivista]
Aungkulanon, P.; Luangpaiboon, P.; Montemanni, R.
abstract
This study addresses a multi-objective programming model for optimizing periodic maintenance scheduling of department assets with a specified set of machines and instruments under a given planning time period. An aim is to minimize the overall variance of human resources and maintenance costs. The principle of the desirability function is incorporated into the optimization model while considering diminishing marginal utility concepts. The classic krill herd algorithm is modified via three swap mechanisms. After conducting a case study in the large retailer company in Thailand, one of the modified krill herd algorithms is proved to be highly effective in providing high quality solutions. This method is powerful to find out the desired degree of desirability and shows superior in learning preference structures with respect to the alternative solutions examined.
2021
- Optimization Strategies for In-Store Order Picking in Omnichannel Retailing
[Relazione in Atti di Convegno]
Chou, X.; Pietri, N. O.; Loske, D.; Klumpp, M.; Montemanni, R.
abstract
The COVID-19 pandemic is changing consumer behavior and accelerating the interest for online grocery purchases. Hence, traditional brick-and-mortar retailers are developing omnichannel solutions enabling online purchases in parallel to normal activities. Buy-Online-Pick-up-in-Store concepts are flourishing in this context, and they are the topic of this work. In this paper we propose a novel application of the sequential ordering problem to model products picking throughout the store shelves. The result is an optimized picking sequence that however takes also into account the characteristics of the goods (fragility, weight, etc.). The aim is to preserve goods integrity while allowing the pickers to optimize their route through the shop. The approach is exemplified on historical online orders of a real German shop.
2021
- Re-Initialising Solutions in a Random Restart Local Search for the Probabilistic Orienteering Problem
[Relazione in Atti di Convegno]
Chou, Xc; Mele, Uj; Gambardella, Lm; Montemanni, R
abstract
The Probabilistic Orienteering Problem is an optimization problem where a set of customers, each with an associated prize and probability of requiring a service, a time budget and travel times between customers are given. The objective is to select the subset of customers that maximize the expected total prize collected in the given time (taking into account of the total travel time spent visiting them).Random Restart Local Search is a heuristic method widely used to solve combinatorial optimization problems. In particular, it is used in conjunction with local search procedures to escape from local optima. The method works by restarting the optimization search once no further improvement is possible by the embedded local search component. Each restart is associated with a new initial solution for the optimization, and selecting such restart initial solutions play an important role in the success of the overall algorithm. In this work we propose a method to effectively selecting such solutions, and we present an empirical study to validate our ideas.
2021
- Reinforcement Learning and Additional Rewardsfor the Traveling Salesman Problem
[Relazione in Atti di Convegno]
Mele, Uj; Chou, Xc; Gambardella, Lm; Montemanni, R
abstract
A comprehensive literature on the Traveling Salesman Problem (TSP) is available, and this problem has become a valuable benchmark to test new heuristic methods for general Combinatorial Optimisation problems. For this reason, recently developed Deep Learning-driven heuristics have been tried on the TSP. These Deep Learning frameworks use the city coordinates as inputs, and are trained using reinforcement learning to predict a distribution over the TSP feasible solutions. The aim of the present work is to show how easy-to-calculate Combinatorial Optimization concepts can improve the performances of such systems. In particular, we show how passing Minimum Spanning Tree information during training can lead to significant improvements to the quality of TSP solutions.As a side result, we also propose a Deep Learning architecture able to predict in real time the optimal length of a TSP instance.The proposed architectures have been tested on random 2D Euclidean graphs with 50 and 100 nodes, showing significant results.
2021
- The Buy-Online-Pick-Up-in-Store Retailing Model: Optimization Strategies for In-Store Picking and Packing
[Articolo su rivista]
Ognibene Pietri, Nicola; Chou, Xiaochen; Loske, Dominic; Klumpp, Matthias; Montemanni, Roberto
abstract
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
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
- Multi-Objective Periodic Maintenance Scheduling and Optimisation via Krill Herd Algorithm
[Articolo su rivista]
Aungkulanon, Pasura; Luangpaiboon, Pongchanun; Montemanni, Roberto
abstract
2020
- Notice of Removal: Re-Initialising Solutions in a Random Restart Local Search for the Probabilistic Orienteering Problem
[Relazione in Atti di Convegno]
Chou, X.; Mele, U. J.; Gambardella, L. M.; Montemanni, R.
abstract
The Probabilistic Orienteering Problem is an optimization problem where a set of customers, each with an associated prize and probability of requiring a service, a time budget and travel times between customers are given. The objective is to select the subset of customers that maximize the expected total prize collected in the given time (taking into account of the total travel time spent visiting them). Random Restart Local Search is a heuristic method widely used to solve combinatorial optimization problems. In particular, it is used in conjunction with local search procedures to escape from local optima. The method works by restarting the optimization search once no further improvement is possible by the embedded local search component. Each restart is associated with a new initial solution for the optimization, and selecting such restart initial solutions play an important role in the success of the overall algorithm. In this work we propose a method to effectively selecting such solutions, and we present an empirical study to validate our ideas.
2020
- Notice of Removal: Reinforcement Learning and Additional Rewardsfor the Traveling Salesman Problem
[Relazione in Atti di Convegno]
Mele, Umberto Junior; Chou, Xiaochen; Gambardella, Luca Maria; Montemanni, Roberto
abstract
A comprehensive literature on the Traveling Salesman Problem (TSP) is available, and this problem has become a valuable benchmark to test new heuristic methods for general Combinatorial Optimisation problems. For this reason, recently developed Deep Learning-driven heuristics have been tried on the TSP. These Deep Learning frameworks use the city coordinates as inputs, and are trained using reinforcement learning to predict a distribution over the TSP feasible solutions. The aim of the present work is to show how easy-to-calculate Combinatorial Optimization concepts can improve the performances of such systems. In particular, we show how passing Minimum Spanning Tree information during training can lead to significant improvements to the quality of TSP solutions. As a side result, we also propose a Deep Learning architecture able to predict in real time the optimal length of a TSP instance. The proposed architectures have been tested on random 2D Euclidean graphs with 50 and 100 nodes, showing significant results.
2020
- Preface
[Relazione in Atti di Convegno]
Montemanni, R.
abstract
2020
- Preface
[Relazione in Atti di Convegno]
Montemanni, R.
abstract
2020
- The Use of an Exact Algorithm Within a Tabu Search Maximum Clique Algorithm
[Articolo su rivista]
Smith, Derek H.; Montemanni, Roberto; Perkins, Stephanie
abstract
Let G = (V, E) be an undirected graph with vertex set V and edge set E. A clique C of G is a subset of the vertices of V with every pair of vertices of C adjacent. A maximum clique is a clique with the maximum number of vertices. A tabu search algorithm for the maximum clique problem that uses an exact algorithm on subproblems is presented. The exact algorithm uses a graph coloring upper bound for pruning, and the best such algorithm to use in this context is considered. The final tabu search algorithm successfully finds the optimal or best known solution for all standard benchmarks considered. It is compared with a state-of-the-art algorithm that does not use exact search. It is slower to find the known optimal solution for most instances but is faster for five instances and finds a larger clique for two instances.
2019
- A Hybrid Meta heuristic Algorithm for the Balanced Line Production under Uncertainty
[Relazione in Atti di Convegno]
Aungkulanon, Pasura; Luangpaiboon, Pongchanun; Montemanni, Roberto
abstract
This study proposes a hybrid Golden Ball Algorithm for solving a balanced line production for a garment firm in Thailand. At present, production lines are those in which the timing of the job movement between stations is coordinated in such a way that all of the jobs are indexed simultaneously via some heuristic sequencing or dispatching rules. This research studies the balanced line production problem with some stochastic patterns, and develops a Golden Ball Algorithm or GBA and its variants to solve the problem. To assess the effectiveness of the proposed hybrid algorithm, a computational study is conducted for both deterministic and stochastic patterns of the problem. The comparisons are made for two different levels of processing times and due date. It can be concluded that the variant HGBA2 of the algorithm by adjusting answers of the successor function on both custom training and successor phases, is slightly more effective than the other hybrid approaches in terms of quality of solutions under uncertainty.
2019
- A metaheuristic algorithm for the probabilistic orienteering problem
[Relazione in Atti di Convegno]
Chou, X.; Gambardella, L. M.; Montemanni, R.
abstract
The Probabilistic Orienteering Problem (POP) is a variant of the orienteering problem where customers are available with a certain probability. In a previous work, we approximated its objective function value by using a Monte Carlo Sampling method. A heuristic speed-up criterion is considered in the objective function evaluator. In this work we study systematically the impact of the heuristic speed-up criterion in terms of precision and speed on the Monte Carlo evaluator, as well as the performance of a POP solver we propose, based on the embedding of the Monte Carlo evaluator into a Random Restart Local Search metaheuristic algorithm.
2019
- Artificial intelligence for healthcare and rescuing technology: technical developments and thoughts about employment impacts
[Articolo su rivista]
Montemanni, Roberto; Guzzi, Jerome; Giusti, Alessandro
abstract
Introduction: To evaluate the overall impact of Artificial Intelligence (AI) and Robotics on employment and work organization is complicated by the fact that these technologies are expected to revolutionize many application fields, which are very different from each other. In this paper, we consider two specific applications emerging from recent research projects: one applies AI and Robotics technologies to the healthcare sector, and one to Search and Rescue in wilderness areas. We generalize from these case studies to speculate on how this kind of innovative applications, that are likely to become increasingly common and widespread, might impact employment and work organization in general. Objectives: To understand how innovative applications might impact employment and work organization in general and specifically on healthcare and social services. Methods: Two recent research developments based on the use of Artificial Intelligence (AI) in the fields of healthcare and rescuing, respectively, are discussed. Therefore, our research work and main results have been achieved within a Swiss National Science Foundation project and a simplified view of the innovative classification component of the architecture is presented. Results: AI and Robotics technologies have specific application on healthcare and social services and demand new professional skills to manage those new methods. Conclusions: We conclude that, depending on the application field, a reduction in the workforce required to carry out tasks that will be taken over by automation might be counterbalanced by either a drastic increase in demand (healthcare services), or a shift in the required competences/skills (search and rescue); in both cases, we can expect a positive societal impact, also motivated by an increased standard of service.
2019
- Hyperparameter search in periodic vehicle routing problem
[Relazione in Atti di Convegno]
Grakova, Ekaterina; Golasowski, Martin; Montemanni, Roberto; Slaninova, Katerina; Martinovivc, Jan; Jamal, Jafar; Janurova, Katerina; Salani, Matteo
abstract
The large number of real-world applications have shown that the use of computational method for distribution process planning produces substantial savings. Many of these applications lead to problem generally known as Vehicle Routing Problem. The real-world applications are highly computationally demanding for larger instances. This article aims to show the possibilities and benefits of using hyperparameter search for solving the Periodic Vehicle Routing Problem for exhausted oil collection by execution on the supercomputing infrastructure using HyperLoom platform. HyperLoom is an open source platform for defining and executing scientific pipelines in a distributed environment. This experiment was run on the supercomputer Salomon operated by IT4Innovations.
2019
- Models and algorithms for the Flying Sidekick Traveling Salesman Problem
[Working paper]
Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
abstract
2019
- Monte Carlo sampling for the tourist trip design problem
[Articolo su rivista]
Chou, Xiaochen; Maria Gambardella, Luca; Montemanni, Roberto
abstract
Introduction: The Tourist Trip Design Problem is a variant of a route-planning problem for tourists interested in multiple points of interest. Each point of interest has different availability, and a certain satisfaction score can be achieved when it is visited. Objectives: The objective is to select a subset of points of interests to visit within a given time budget, in such a way that the satisfaction score of the tourist is maximized and the total travel time is minimized. Methods: In our proposed model, the calculation of the availability of a POI is based on the waiting time and / or the weather forecast. However, research shows that most tourists prefer to travel within a crowded and limited area of very attractive POIs for safety reasons and because they feel more in control. Results: In this work we demonstrate that the existing model of the Probabilistic Orienteering Problem fits a probabilistic variant of this problem and that Monte Carlo Sampling techniques can be used inside a heurist solver to efficiently provide solutions. Conclusions: In this work we demonstrate the existing model of the Probabilistic Orienteering Problem fits the stochastic Tourist Trip Design Problem. We proposed a way to solve the problem by using Monte Carlo Sampling techniques inside a heuristic solver and discussed several possible improvements on the model. Further extension of the model will be developed for solving more practical problems.
2019
- Permutation Codes, Hamming Graphs and Turan Graphs
[Relazione in Atti di Convegno]
Barta, Janos; Montemanni, Roberto
abstract
This paper investigates the properties of permutation Ham- ming graphs, a class of graphs in which the vertices are the permutations of n symbols and the edges connect pairs of vertices at a Hamming dis- tance greater than or equal to a value d. Despite a remarkable regularity, permutation Hamming graphs elude general formulas for relevant indica- tors like the clique number. The clique number plays a crucial role in the Maximum Permutation Code Problem (MPCP), a well-known optimiza- tion problem. This work focuses on the relationship between permutation Hamming graphs and a particular type of Tura ́n graphs. The main re- sult is a theorem asserting that permutation Hamming graphs are the intersection of a set of Tur ́an graphs. This equivalence has implications on the MPCP. In fact it enables a reformulation as a hitting set problem, which in turn can be translated into a binary integer program.
2019
- Setting the Configuration Parameters of the Algorithm for the Periodic Vehicle Routing Problem by HPC Power
[Articolo su rivista]
Grakova, Ekaterina; Martinovič, Jan; Slaninová, Kateřina; Janurová, Kateřina; Cima, Vojtěch; Golasowski, Martin; Montemanni, Roberto; Salani, Matteo
abstract
The quality of an optimal solution of the Vehicle Routing Problem is strongly depended on the setting of the configuration parameters of the algorithm. The paper is focused on the introduction of hyperparameter search for solving the Vehicle Routing Problem using a HyperLoom platform for defining and executing scientific pipelines in a distributed environment. To give a concrete example, we focused on Periodic Vehicle Routing Problem for the waste collection. HyperLoom platform was used to define and execute the hyperparameters sweep pipeline. The heuristic algorithm was tested on a real benchmark of the waste collection in Ostrava, Czech Republic. The aim of our case was to effectively combine the minimization of the total travelled distance and the optimization of the fairness of the routes in terms of the standard deviation of a tour length. The waste collection problem was very extensive and computationally demanding, so it was necessary to use high performance computing architecture for testing a large number of different settings of configuration parameters. The experiments were run on the supercomputer Salomon operatedby IT4InnovationsNationalSupercomputingCenterintheCzech Republic.
2019
- Solving the maximum clique problem with a hybrid algorithm
[Articolo su rivista]
Smith Derek, H; Perkins, Stephanie; Montemanni, Roberto
abstract
A hybrid algorithm for the maximum clique problem is presented. A heuristic is used to generate cliques and these are improved by some simple optimisations and Tabu search. All components of the algorithm make use of an exact algorithm or a pseudoexact algorithm, which is an exact algorithm with some specialised pruning. Pre-processing is useful for some instances. The algorithm is shown to be successful using standard and new benchmarks.
2019
- Steepest ant sense algorithm for parameter optimisation of multi-response processes based on taguchi design
[Articolo su rivista]
Luangpaiboon, P; Boonhao, S; Montemanni, R
abstract
Due to the continuous refinements in engineering operations, process parameters need to be optimised in order to improve the production quality. In this study we present a novel method based on the hybridisation of an ant colony system search mechanism with a steepest ascent method to achieve such a parameter optimisation. The proposed algorithm has been implemented and run on two real time industrial applications. Experimental results showed that the optimised parameters for a stealth laser dicing process provided by the new method were able to increase the production quality by improving production precision, which is measured in terms of average deviation from the expected result and relative variance. The novel method we propose was able to identify improved settings for a stealth laser dicing process with five parameters, resulting in a greatly reduced rate of product failures. Additionally six parameters were optimised for another industrial application, namely a grease filling system with twin towers, using only 23 experiments, leading to an increase in the tool life (objective of the optimisation) from the previous average of 9236 U produced to 13,883 U. The new method performed better than conventional response surface methods, showing therefore to be promising for other similar industrial applications.
2019
- Stochastic Search in Metaheuristics
[Capitolo/Saggio]
Gutjahr Walter, J; Montemanni, Roberto
abstract
Stochastic search is a key mechanism underlying many metaheuristics. The chapter starts with the presentation of a general framework algorithm in the form of a stochastic search process that contains a large variety of familiar metaheuristic techniques as special cases. Based on this unified view, questions concerning convergence and runtime are discussed on the level of a theoretical analysis. Concrete examples from diverse metaheuristic fields are given. In connection with runtime results, important topics as instance difficulty, phase transitions, parameter choice, No-Free-Lunch theorems, or fitness landscape analysis are addressed. Furthermore, a short sketch of the theory of black-box optimization is given, and generalizations of results to stochastic search under noise are outlined.
2018
- A prize-collecting Steiner tree application for signature selection to stratify diffuse large B-cell lymphoma subtypes
[Working paper]
Akhmedov, Murodzhon; Galbusera, Luca; Montemanni, Roberto; Bertoni, Francesco; Kwee, Ivo
abstract
Background: With the explosion of high-throughput data available in biology, the bottleneck is shifted to effective data interpretation. By taking advantage of the available data, it is possible to identify the biomarkers and signatures to distinguish subtypes of a specific cancer in the context of clinical trials. This requires sophisticated methods to retrieve the information out of the data, and various algorithms have been recently devised.
Results: Here, we applied the prize-collecting Steiner tree (PCST) approach to obtain a gene expression signature for the classification of diffuse large B-cell lymphoma (DLBCL). The PCST is a network-based approach to capture new insights about genomic data by incorporating an interaction network landscape. Moreover, we adopted the ElasticNet incorporating PCA as a classification method. We used seven public gene expression profiling datasets (three for training, and four for testing) available in the literature, and obtained 10 genes as signature. We tested these genes by employing ElasticNet, and compared the performance with the DAC algorithm as current golden standard. The performance of the PCST signature with ElasticNet outperformed the DAC in distinguishing the subtypes. In addition, the gene expression signature was able to accurately stratify DLBCL patients on survival data.
Conclusions: We developed a network-based optimization technique that performs unbiased signature selection by integrating genomic data with biological networks. Our classifier trained with the obtained signature outperformed the state-of-the-art method in subtype distinction and survival data stratification in DLBCL. The proposed method is a general approach that can be applied on other classification problems.
2018
- An Elevator Kinematics Optimisation Method for Aggregate Production Planning Based on Fuzzy MOLP Model
[Articolo su rivista]
Aungkulanon, Pasura; Luangpaiboon, Pongchanun; Montemanni, Roberto
abstract
This study proposes a multi-objective linear programming model for solving the multi-product aggregate production planning (APP) decision problem for Topline Co., Ltd. in Thailand. The model attempts to minimise total production and work force costs and carrying inventory costs to bring a planning framework for the industrial resources management under complex information environment. The proposed model yields an efficient compromise solution and the overall levels of decision making satisfaction with the multiple objectives via the fuzzy programming using the elevator kinematics optimisation (EKO) algorithm including its hybridisations of harmony search and bee algorithms. The comparisons are made for two different levels of inventory. It can be concluded that the EKO is slightly more effective than the other hybrid approaches in terms of quality of solutions. However, there is no difference in required computation time. The basic idea is to produce reliable solution in search space with the random external command in escaping from local trap during searching for a better solution. Numerical results demonstrate the robustness and effectiveness of the developed EKO method.
2018
- Challenges and opportunities in deploying a mobility platform integrating public transport and car-pooling services
[Relazione in Atti di Convegno]
Derboni, Marco; Rizzoli Andrea, Emilio; Montemanni, Roberto; Jamal, Jafar; Kovacs, Nikolett; Cellina, Francesca
abstract
This paper introduces a new mobility platform that favours reducing individual car use, by combining car flexibility with advantages offered by public transport, such as punctuality, comfort, safety and low environmental impact. Such platform services are delivered by means of a smartphone app that, thanks to advanced artificial intelligence algorithms, performs multi- modal vehicle routing by accounting for walking, public transport and car-pooling rides. To explore citizens’ attitudes and perceptions towards SocialCar, and assess its overall business potential, we tested a prototype version in Canton Ticino (Southern Switzerland), engaging common citizens and their everyday mobility needs.
In this paper we first present the app and the route planning algorithms we developed to match travel demand and offer, commenting on the challenges to be addressed when using real-life data (shortcomings in mapping, public transport and car-pooling data). Then, we describe the methodology used to assess the SocialCar overall potential, based on focus group meetings run before and after the field test, and summarize the results obtained, in terms of strengths, weaknesses, threats and opportunities for a large-scale diffusion of the SocialCar platform. Finally, we comment on the lessons learnt and provide recommendations for future similar "mobility as a service" platforms.
2018
- Industrial Cluster Symbiosis Optimisation Based on Linear Programming
[Articolo su rivista]
Jamal, JAFAR MOHAMMAD JEHAD A R; Montemanni, Roberto
abstract
Industrial Symbiosis is a symbiotic relationship between dissimilar industries that is achieved by the flow of waste and byproducts as an output from one production unit to another as a resource to be used for production. The described symbiosis has many environmental and economical benefits generated from reducing the cost of resources used in the production process. The main concern with implementing such a system is the guarantee for an even distribution among the participating production units of the extra profit generated through the trading process. Otherwise, it would be intuitively difficult to convince the participants to implement the system we suggest. In this work, we model the problem through mathematical programming and we propose a solution based on a series of linear programmes that maximises and balances the profit between the production units. A first model focuses on pure byproducts trading, and a more advanced model that considers the trading process within a dynamic electricity market where electricity costs vary over time. Computational experiments to validate the proposed approach are finally presented and discussed.
2018
- Industrial cluster optimization based on linear programming
[Relazione in Atti di Convegno]
Montemanni, Roberto; Jamal, Jafar
abstract
Industrial Symbiosis is a symbiotic relationship between different production plants in a same area that is achieved by the flow of waste and byproducts from a production unit, that generates them during its activities, to another, that uses it as resource for its own production. The described symbiosis has many evident environmental and economic benefits. The main concern with implementing such system is the guarantee for an even distribution of the extra profit generated through the byproducts exchange process among the participating production units. In this work, we model the problem through mathematical programming and we propose a solution based on a series of linear programs that maximises and balances the profit between the production units participating in the symbiosis.
2018
- Machine learning and monte carlo sampling for the probabilistic orienteering problem
[Relazione in Atti di Convegno]
Montemanni, R.; D'Ignazio, F.; Chou, X.; Gambardella, L. M.
abstract
The Probabilistic Orienteering Problem is a stochastic optimization problem about the delivery or goods to customers. Only a subset of the customer can be served in the given time, so the problem consists in the selection of the customers providing more revenues and in the optimization of a truck tour to serve them. The presence of the customers is however stochastic, and this has to be taken into account while evaluating the objective function of each solution. Due to the high computational complexity of such an objective function, Monte Carlo sampling method is used to estimate it in a fast way. There is one crucial parameter in a Monte Carlo sampling evaluator which is the number of samples to be used. More samples mean high precision, less samples mean high speed. An instance-dependent trade-off has to be found. The topic of this paper is a Machine Learning-based method to estimate the best number of samples, given the characteristics of an instance. Two methods are presented and compared from an experimental point of view. In particular, it is shown that a less intuitive and slightly more complex method is able to provide more precise estimations.
2018
- Monte Carlo Sampling for the Probabilistic Orienteering Problem
[Relazione in Atti di Convegno]
Chou, Xiaochen; Gambardella Luca, Maria; Montemanni, Roberto
abstract
The Probabilistic Orienteering Problem is a variant of the orienteering problem where customers are available with a certain probability. Given a solution, the calculation of the objective function value is complex since there is no linear expression for the expected total cost. In this work we approximate the objective function value with a Monte Carlo Sampling technique and present a computational study about precision and speed of such a method. We show that the evaluation based on Monte Carlo Sampling is fast and suitable to be used inside heuristic solvers. Monte Carlo Sampling is also used as a decisional tool to heuristically understand how many of the customers of a tour can be effectively visited before the given deadline is incurred.
2017
- A Comparison of Heuristic Methods for the Prize-Collecting Steiner Tree Problem and Their Application in Genomics
[Relazione in Atti di Convegno]
Akhmedov, Murodzhon; Kwee, Ivo; Montemanni, Roberto
abstract
The prize-collecting Steiner tree (PCST) problem is a broadly studied problem in combinatorial optimization. It has been used to model several real world problems related to utility networks. More recently, researchers have started using PCSTs to study biological networks. Biological networks are typically very large in size. This can create a considerable challenge for the available PCST solving methods. Taking this fact into account, we have developed methods for the PCST that efficiently scale up to large biological network instances. Namely, we have devised a heuristic method based on the Minimum Spanning Tree and a matheuristic method composed of a heuristic clustering phase and a solution phase. In this work, we provide a performance comparison for these methods by testing them on large gene interaction networks. Experimental results are reported for the methods, including running times and objective values of the solutions.
2017
- A Multi-Modal and Multi-Objective Journey Planner for Integrating Carpooling and Public Transport
[Articolo su rivista]
Jamal, Jafar; Montemanni, Roberto; Huber, David; Derboni, Marco; Rizzoli, Andrea
abstract
SocialCar is a research project that aims at integrating carpooling with traditional transportation systems in urban areas, while benefiting from social media to enhance the user’s experience. The system is based on route planning and ride matching algorithms to provide the users with alternatives for their trips. In this work, we overview the multiple approaches in the literature to model transportation networks and carpooling services, and a route planning algorithm which integrates multiple transportation types together. Finally, the performance measures of the route planner are reported.
2017
- A fast prize-collecting steiner forest algorithm for functional analyses in biological networks
[Relazione in Atti di Convegno]
Akhmedov, Murodzhon; Lenail, Alexander; Bertoni, Francesco; Kwee, Ivo; Fraenkel, Ernest; Montemanni, Roberto
abstract
The Prize-collecting Steiner Forest (PCSF) problem is NP-hard, requiring extreme computational effort to find exact solutions for large inputs. We introduce a new heuristic algorithm for PCSF which preserves the quality of solutions obtained by previous heuristic approaches while reducing the runtime by a factor of 10 for larger graphs. By decreasing the draw on computational resources, this algorithm affords systems biologists the opportunity to analyze larger biological networks faster and narrow their analyses to individual patients.
2017
- Correlations Between Experimentally-Determined Melting Temperatures and GC-Content for Short DNA Strands
[Articolo su rivista]
Tulpan, Dan; Montemanni, Roberto; Smith Derek, H
abstract
Background: The hybridization stability of single and double stranded DNA sequences has been studied extensively and its impact on bio-computing, bio-sensing and bio-quantification technologies such as microarrays, Real-time PCR and DNA sequencing is significant. In many bioinformatics applications DNA duplex hybridization is traditionally estimated using GC-content and melting temperature calculations based on the sequence base composition.
Objective: In this study we explore the equivalence of the two approaches when estimating DNA sequence hybridization and we show that GC-content is a far from perfect predictor of DNA strand hybridization strength compared to experimentally-determined melting temperatures.
Method: To test the assumption that DNA GC-content is a good indicator of its melting temperature, we formulate a research hypothesis and we apply the Pearson product-moment correlation statistical model to measure the strength of a linear association between the GC-content and melting temperatures.
Results: We built a manually curated set of 373 experimental data points collected from 21 publications, each point representing a DNA strand with length between 4 and 35 nucleotides and its corresponding experimentally determined melting temperature measured under specific sequence and salt concentrations. For each data point we calculated the corresponding GC-content and we separated the set into 12 subsets to minimize the variability of experimental conditions.
Conclusion: Based on calculated Pearson product-moment correlation coefficients we conclude that GC-content only seldom correlates well with experimentally determined melting temperatures and thus it is not a strictly necessary constraint when used to control the uniformity of DNA strands.
2017
- Hamming Graphs and Permutation Codes
[Relazione in Atti di Convegno]
Barta, Janos; Montemanni, Roberto
abstract
A permutation code can be represented as a graph, in which the nodes correspond to the permutation codewords and the weights on the edges are the Hamming distances between the codewords. Graphs belonging to this class are called permutation Hamming graphs. This paper explores the Maximum Permutation Code Problem (MPCP), a well-known optimization problem in coding theory, by means of a graph theoretical approach. Permutation Hamming graphs turn out to satisfy strong regularity properties, such as vertex transitivity and r-partiteness. In addition, exact formulas for the degree of the vertices and for the number of the edges are presented. Furthermore, a remarkable similarity between permutation Hamming graphs and Turán graphs is enlightened. The new link with Turán graphs might help to improve current results on the MPCP.
2017
- OmicsNet: Integration of Multi-Omics Data using Path Analysis in Multilayer Networks
[Working paper]
Akhmedov, Murodzhon; Arribas, Alberto; Montemanni, Roberto; Bertoni, Francesco; Kwee, Ivo
abstract
2017
- PCSF: An R-package for network-based interpretation of high-throughput data
[Articolo su rivista]
Akhmedov, Murodzhon; Kedaigle, Amanda; Chong Renan, Escalante; Montemanni, Roberto; Bertoni, Francesco; Fraenkel, Ernest; Kwee, Ivo
abstract
With the recent technological developments a vast amount of high-throughput data has been profiled to understand the mechanism of complex diseases. The current bioinformatics challenge is to interpret the data and underlying biology, where efficient algorithms for analyzing heterogeneous high-throughput data using biological networks are becoming increasingly valuable. In this paper, we propose a software package based on the Prize-collecting Steiner Forest graph optimization approach. The PCSF package performs fast and user-friendly network analysis of high-throughput data by mapping the data onto a biological networks such as protein-protein interaction, gene-gene interaction or any other correlation or coexpression based networks. Using the interaction networks as a template, it determines high-confidence subnetworks relevant to the data, which potentially leads to predictions of functional units. It also interactively visualizes the resulting subnetwork with functional enrichment analysis.
2017
- Solving the sequential ordering problem using branch and bound
[Relazione in Atti di Convegno]
Jamal, Jafar Mohammad Jehad A R; Shobaki, G; Papapanagiotou, Vassilis; Gambardella Luca, Maria; Montemanni, Roberto
abstract
The Sequential Ordering Problem (SOP) is an NP-hard problem with a wide range of applications in the domains of scheduling, logistics and compilers. The development of powerful computers and effective algorithmic techniques has made it possible to devise exact algorithms that can solve larger instances of this problem. In this paper, we present an enhanced exact algorithm for this problem using a branch-and-bound (B&B) approach. The proposed algorithm is based on a new lower-bound technique and a local-search domination technique. The new lower-bound technique uses the dynamic Hungarian algorithm to solve a Minimum-Cost Perfect Matching relaxation of the SOP. The local search domination technique prunes the sub-tree below the current node in the B&B tree if a better partial solution is found. The performance of the proposed algorithm is evaluated experimentally using three different benchmark suites: TSPLIB, SOPLIB and COMPILERS. The results of the experimental evaluation show that the proposed algorithm finds exact solutions considerably faster than previously proposed algorithms. The proposed approach significantly reduces the optimality gap to 0.217, 0.122, and 0.004 for the three respective benchmark sets, and closes five instances that were previously open.
2016
- A divide and conquer matheuristic algorithm for the Prize-collecting Steiner Tree Problem
[Articolo su rivista]
Akhmedov, Murodzhon; Kwee, Ivo; Montemanni, Roberto
abstract
The Prize-collecting Steiner Tree Problem (PCSTP) is a well-known problem in graph theory and combinatorial optimization. It has been successfully applied to solve real problems such as fiber-optic and gas distribution networks design. In this work, we concentrate on its application in biology to perform a functional analysis of genes. It is common to analyze large networks in genomics to infer a hidden knowledge. Due to the NP-hard characteristics of the PCSTP, it is computationally costly, if possible, to achieve exact solutions for such huge instances. Therefore, there is a need for fast and efficient matheuristic algorithms to explore and understand the concealed information in huge biological graphs. In this study, we propose a matheuristic method based on clustering algorithm. The main target of the method is to scale up the applicability of the currently available exact methods to large graph instances, without loosing too much on solution quality. The proposed matheuristic method is composed of a preprocessing procedures, a heuristic clustering algorithm and an exact solver for the PCSTP, applied on sub-graphs. We examine the performance of the proposed method on real-world benchmark instances from biology, and compare its results with those of the exact solver alone, without the heuristic clustering. We obtain solutions in shorter execution time and with negligible optimality gaps. This enables analyzing very large biological networks with the currently available exact solvers.
2016
- A sampling-based metaheuristic for the Orienteering Problem with Stochastic Travel Times
[Relazione in Atti di Convegno]
Papapanagiotou, Vassilis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
In this paper we propose a new metaheuristic approach based on sampling for the Orienteering Problem with Stochastic Travel Times (OPSTS). As in many Stochastic Combinatorial Optimization Problems, the computational bottleneck of OPSTS is in the objective function evaluation. For this reason, this study is mainly devoted to the development and integration of on-purpose, sampling-based fast objective function evaluations into metaheuristic methods. In details, we show how a Variable Neighbourhood Search Metaheuristic can be enhanced by adopting such evaluators. Experimental results show that the new sampling-based method is faster than conventional methods for the given problem, and the improvement is particularly relevant for large-scale instances.
2016
- Ant colony optimisation for a 2-stage capacitated vehicle routing problem with probabilistic demand increases
[Articolo su rivista]
Toklu Nihat, Engin; Papapanagiotou, Vassilis; Klumpp, Matthias; Gambardella Luca, Maria; Montemanni, Roberto
abstract
In this paper we address a 2-stage capacitated vehicle routing problem (CVRP) in which the demands are probabilistic and can only increase. In this CVRP variant the routes used by the fleet to satisfy the customers must be minimised. The customers' demands may increase with a probability after the beginning of the tours like the unexpected events that happen in a realistic environment. The existence of these events make sometimes the fleet fail to satisfy all the customers at their first try (1st stage). In this case, additional vehicles will be used to cover the rest of the demand (2nd stage). In this paper, an ant colony system is used to generate solutions and the effect of different objective functions used is shown. Conclusions are drawn on which evaluation method leads to near optimum routes and which to near optimum number of vehicles.
2016
- Comparison of Objective Function Evaluators for a Stochastic Orienteering Problem
[Relazione in Atti di Convegno]
Papapanagiotou, Vassilis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
The Orienteering Problem is a combinatorial optimization problem where a set of potential customers, each one with an associated profit, is given together with a deadline. The target is to select the customers to be visited in the available time, maximizing the profit of the visited customers. In this paper we consider a variant of the problem where travel and service times are affected by uncertainty, and are expressed through probabilities. For such a problem, the computational bottleneck is the calculation of the objective function value associated with each solution. In this paper we show how hybrid sampling-based objective functions evaluators can be effectively embedded into a state-of-the-art metaheuristic algorithm (a Variable Neighborhood Search method). Our conclusions are supported by extensive experimental results.
2016
- Graph colouring and branch and bound approaches for permutation code algorithms
[Relazione in Atti di Convegno]
Montemanni, Roberto; Barta, Janos; Smith Derek, H
abstract
A considerable amount of research has been devoted to permutation codes in recent years. This has been motivated by some real-world applications. Permutation codes are important because of their robustness against transmission errors and noise. This study addresses the problem of the construction of the largest possible permutation codes with given parameters, namely a specified length and minimum Hamming distance. The problem is modelled in terms of maximum cliques and it is shown how a well-known upper bound based on colouring can be successfully embedded inside a branch and bound method. Experimental results are presented to evaluate the effectiveness of the new idea.
2016
- Green Bullwhip Effect Cost Simulation in Distribution Networks
[Relazione in Atti di Convegno]
Klumpp, Matthias; Toklu Nihat, Engin; Papapanagiotou, Vassilis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
Sustainability is a modern day requirement toward global supply chains and also in most cases an efficiency challenge for logistic companies. Complementary objectives in decreasing carbon footprint and costs of transports are assumed or claimed, e.g., for an increase in load factors, reduction in transport intervals, and other green transport approaches in scheduling and tour planning. And also conflicting objectives can be identified with a decrease in flexibility due to lower transport intervals and higher load factors, as this research approach shows with a meta-heuristic approach for delivery transports under uncertainty of demand conditions. This uncertainty regarding increasing cost of necessary changes in transport planning due to probabilistic demand changes can be seen as excess flexibility costs. These can lead to increased security stock levels based on bullwhip behavior of logistics deciders, creating an additional green bullwhip effect for supposed sustainable supply chains. Therefore, the overall business and sustainability improvement in measures such as, e.g., reduced delivery intervals are to be evaluated taking this new perspective into account.
2016
- Homecare planning, a challenging task in a growing market
[Relazione in Atti di Convegno]
Nordlander Tomas, Eric; Lamorgese, Leonardo; Nguyen Thi Viet, Ly; Montemanni, Roberto
abstract
The homecare services market is large and rapidly growing due to ageing populations and increasingly skewed age demographics. Human resources are the dominant factor simultaneously determining quality of care and driving costs. The planning of homecare services involves allocating personnel among shifts, assigning staff members to patients, routing staff members’ client visits and scheduling treatments. Homecare planning is primarily done manually even though optimisation techniques have aided in solving similar problems in other domains. Efficient homecare planning requires optimisation techniques, but current, related optimisation research suffers from several shortcomings (above all, a lack of integration in handling the different planning sub-problems) and needs certain changes. This paper highlights these shortcomings and suggests approaches to realise the benefits of optimisation techniques in homecare planning.
2016
- Integrated home health care optimization via genetic algorithms and mathematical programming
[Relazione in Atti di Convegno]
Nguyen Thi Viet, Ly; Montemanni, Roberto
abstract
This study is a novel contribution to the field of optimization in home health care services, both model and solution approach. We address an integration of interrelated optimization problems: rostering, assignment, routing, and scheduling in multi-period workforce planning under uncertainty in nurse availability. Our model explicitly handles the constraints related to workload balancing and multi-period planning, and the principles of robust optimization approach are followed to find a robust solution. We introduce a matheuristic algorithm that works based on a genetic algorithm mechanism to tackle four optimization problems sequentially but interactively. Two nested genetic algorithms are integrated. Steady-state reproduction is applied to both the inner and outer ones to reduce computational time/memory requirements. Two replacement strategies are carried out: replacing solutions at random and replacing the worst solutions. Experiments are conducted on instances based on real historical data from a company operating in Lugano, Switzerland. The obtained results show that, in genetic algorithm, the strategy of replacing solutions at random outperforms the strategy of replacing the worst solutions in our case. Addressing the four optimization problems in a unified approach results in a more efficient solution. In addition, the proposed algorithm: i) is able to handle large instances and to provide a weekly workforce planning solution in a reasonable time, which is reliable against uncertainty in nurse availability; ii) can be used to efficiently support managers in evaluating the trade off between the robustness and the operational cost of a solution.
2016
- Mathematical programming models for home healthcare service optimisation
[Relazione in Atti di Convegno]
Nguyen Thi Viet, Ly; Montemanni, Roberto
abstract
In this paper, we address the home healthcare services problem in terms of routing and scheduling. The aim of the study is to determine a feasible working plan for nurses in order to offer patients the best possible solution in terms of quality of service and economy while satisfying the demands of patients and nurses as well as the related constraints. Besides giving a brief overview of related literature, we describe a new extended version of the existing home healthcare service problems and propose two mixed integer linear programming formulations. Computational results conducted based on a set of randomly generated home healthcare scenarios reveal that the proposed model based on Big-M method is more flexible and applicable in practice when compared to another model based on arc timing method.
2016
- Packing regularity of permutation codes
[Relazione in Atti di Convegno]
Barta, Janos; Montemanni, Roberto; Smith Derek, H
abstract
Permutation codes have been extensively investigated, both because of their intrinsic mathematical interest and because of relevant applications based on error-correcting codes. The Maximum Permutation Code Problem (MPCP) is a challenging packing problem on permutations. The objective is to maximize the size of permutation codes with a given minimum Hamming distance between the codewords. In a similar way to the well-known sphere packing problem, an optimal permutation packing usually has a highly regular structure. In this paper a new idea of regularity degree of permutation codes is developed and the relationship between packing density and regularity degree of permutation codes is investigated. Computational experiments on random permutation packings run on different MPCPs confirm that, analogously to the sphere packing problem, the regularity degree of permutation codes tends to increase as the code size approaches to the optimum.
2016
- Preface
[Relazione in Atti di Convegno]
Montemanni, R.; Figueira, M.
abstract
2016
- Preface
[Relazione in Atti di Convegno]
Montemanni, R.; Figueira, M.
abstract
2016
- Robust home health care services: an enhanced matheuristic optimization
[Working paper]
Nguyen Thi Viet, Ly; Montemanni, Roberto
abstract
During the last decades, optimization for home health care services has become increas- ingly important. In this study, we model a home health care model which is close to reality by taking uncertainty in nurse availability (e.g. they might call sick on a short notice) into account. Different features arising from the home health care services in the reality are also stated. A mixed integer linear programming formulation is developed to present the deter- ministic case of the studied problem in which uncertainty is ignored. A nonlinear formulation formulated based on the principles of robust optimization is also developed to represent the robust home health care model in which uncertainty is taken into account. An algorithm based on the integration of mathematical models, genetic algorithm, and robust optimization is proposed. Experimental results on real historical data from a company operating in Lugano Switzerland show that the method we propose is efficient to provide a weekly operational plan.
2016
- Tour planning and ride matching for an urban social carpooling service
[Relazione in Atti di Convegno]
Jamal, J; Rizzoli, Ae; Montemanni, R; Huber, D
abstract
SocialCar is a research project aiming at integrating carpooling with existing transportation systems in urban and peri-urban environments. The system, that also takes benefit from social network interactions, is based on tour planning and ride matching algorithms to suggest the users the available alternatives for their trips. In this paper we overview some approaches to model general public transportation networks and carpooling services. A route planning algorithm, able to integrate different types of public transportation, bike rentals and carpooling services is finally presented.
2016
- Vehicle Routing Problem with Uncertain Costs via a Multiple Ant Colony System
[Relazione in Atti di Convegno]
Toklu Nihat, Engin; Gambardella Luca, Maria; Montemanni, Roberto
abstract
We consider the capacitated vehicle routing problem (VRP) withuncertain travel costs, where the uncertainty represents the realistic factors like unfriendly weather conditions, traffic jams, etc. In this chapter, we present a multiple ant colony system approach in which ant colony optimization processes work concurrently to produce multiple solutions. Experimental results on different types of VRP instances (with clustered customers, randomly placed customers, and a mixed of the previous two), each instance having 200 customers, are finally discussed.
2015
- A comparison of two exact algorithms for the sequential ordering problem
[Relazione in Atti di Convegno]
Papapanagiotou, Vassilis; Jamal, J; Montemanni, Roberto; Shobaki, Ghassan; Gambardella Luca, Maria
abstract
The sequential ordering problem is an NP-hard combinatorial optimization problem that arises in many real-world applications in logistics and scheduling. In this paper, we experimentally compare two exact algorithms that have been recently proposed for solving this problem. The comparison is done on a large set of benchmarks used in published work. In addition to comparing the performance of two different algorithms, this paper reports the closing of nine instances for the first time as well as seventeen improved upper and lower bounds.
2015
- A matheuristic algorithm for the Prize-collecting Steiner Tree Problem
[Relazione in Atti di Convegno]
Akhmedov, Murodzhon; Kwee, Ivo; Montemanni, Roberto
abstract
The Prize-collecting Steiner Tree Problem (PCSTP) is a well studied problem in combinatorial optimization. It has a wide range of applications in the literature, for instance in fiber optics such as gas distribution and district heating. In this study, we focus on its application in functional analysis of genes on bio-genetic graphs. In bio-genetics its extremely possible to have a huge graphs to interpret. Since the PCSTP is NP-hard, it is time consuming to obtain solutions for large instances. Thus, there is a need for efficient and fast heuristic algorithms to discover the hidden knowledge behind the vast bio-genetic networks. We propose a matheuristic composed of heuristic clustering algorithm and existing mixed integer liner programming to solve PCSTP. We evaluated the performance of our matheuristic on available real-world benchmark instances from the biology and compared it with existing heuristic approach in the literature. With respect to heuristic results, we obtained solutions with similar or better objective function values. On the other hand the existing heuristic solved the benchmark instances with smaller running time compared to proposed matheuristic.
2015
- Combinatorial optimization algorithms for the design of codes: a survey
[Articolo su rivista]
Montemanni, Roberto
abstract
Code design problems are central in information theory and have applications in different fields ranging from telecommunications to bioinformatics. In this paper we survey the results achieved in the last decades for different types of codes, covering constant weight binary codes, quaternary codes and permutation codes. The focus of the survey is mainly on approaches based on combinatorial optimization and graph theory that have gained popularity in the last decade and are likely to play a central role in the codes design research in the forthcoming years, possibly in a fashion where the new ideas are hybridized with the older contributions.
2015
- Hybrid sampling-based evaluators for the orienteering problem with stochastic travel and service times
[Articolo su rivista]
Papapanagiotou, Vassilis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
Stochastic Combinatorial Optimization Problems (SCOPs) are many times used to model more accurately realistic situations. However, the stochasticity introduced also perplexes the computation of the objective function making it either difficult to solve or in our case very time-consuming. In this paper, we present different techniques of evaluating the objective function of the Orienteering Problem with Stochastic Travel and Service Times, that combine analytical, sampling and deterministic parts. We then compare these methods experimentally on well-known datasets.
2015
- Matheuristic optimization for robust home health care services
[Relazione in Atti di Convegno]
Nguyen Thi Viet, Ly; Toklu Nihat, Engin; Montemanni, Roberto
abstract
In modern societies, home health care services are becoming increasingly important. Having optimized solutions on operational issues can play a potential role in offering patients high quality medical service as well as taking in better regard, the needs of care providers. An important issue to consider is the uncertainty on the problem data. In more details, an optimal solution that was obtained under the assumption that the collected problem data are accurate, can turn out to be infeasible when it is implemented in the reality, because the data encountered in the reality might differ from the assumed data in the optimization model. In this paper, we consider the uncertainty on the availability of the nurses (e.g. they might call sick on short notice), and we follow a robust optimization approach to handle the case when nurses are unexpectedly unable to operate. A matheuristic method based on a constructive heuristic combined with a genetic algorithm and mathematical programming is proposed to provide a near-optimal solution both in terms of nurse-patient assignment and nurse scheduling and routing.
2015
- Permutation codes via fragmentation of group orbits
[Relazione in Atti di Convegno]
Barta, Janos; Montemanni, Roberto; Smith Derek, H
abstract
This work presents an approach to the Maximum Permutation Code Problem (MPCP) that exploits the orbits of permutation groups in a new way. Several scientific works of recent years studied the principle of building feasible codes by combining the orbits of single permutation groups. However, the idea of combining orbits stemming from more than one group has not been explored yet. This paper presents some experiments and results with a multi-group approach. Furthermore, it explores the potential of using subsets of orbits (fragments) instead of entire orbits. The concept of minimum distance code is introduced and studied in the special case of the orbits of cyclic groups. Computational experiments carried out with a branch and bound algorithm show the potential of this approach to obtain new lower bounds on open MPCP problems.
2015
- Software support for sustainable supply chain configuration and management
[Capitolo/Saggio]
Rizzoli Andrea, Emilio; Montemanni, Roberto; Bettoni, Andrea; Canetta, Luca
abstract
A methodology for the inclusion of sustainability assessment in the design of supply chains is introduced, with the aim of taking into account a sustainability perspective in logistics and industrial allocation choices. The presented approach is based on the initial collection and organization of data related to all stages of the product life cycle and of the possible alternative choices to be made for each production and transport stage. An optimization algorithm is then used to prune the space of alternative solutions and an advanced and flexible graphical user interface allows the exploration of the solution space.
2015
- The Orienteering Problem with Stochastic Travel and Service: Times New approaches to sampling-based objective function evaluation
[Relazione in Atti di Convegno]
Papapanagiotou, Vassilis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
In recent years, the interest on Stochastic Combinatorial Optimization Problems has increased a lot, since through them it is possible to model the reality more accurately than with their deterministic counterparts. However, for many problems the added stochastic element introduces intricacies that make the objective function either difficult to solve or very time-consuming. In this paper, we propose alternative sampling-based techniques for approximating the objective function of the Orienteering Problem with Stochastic Travel and Service Times, a combinatorial optimization problem arising in logistic applications. The sampling-based techniques are finally compared from an experimental point of view.
2015
- The design of permutation codes via a specialized maximum clique algorithm
[Relazione in Atti di Convegno]
Montemanni, Roberto; Barta, Janos; Smith Derek, H
abstract
Permutation codes have received considerable interest in recent years, motivated by some real-world applications. These applications take advantage of their robustness against transmission errors and noise. The problem addressed in this study is the construction of the largest possible permutation codes with a specified length and minimum Hamming distance. In this paper the problem is modelled in terms of maximum cliques and it is shown how a classic branch and bound method for maximum cliques can specialized for the design of permutation codes. This leads to a much faster technique. Experimental results support this claim.
2014
- A branch and bound approach to permutation codes
[Relazione in Atti di Convegno]
Barta, Janos; Montemanni, Roberto; Smith Derek, H
abstract
The Maximum Permutation Code Problem (MPCP) is a well-known combinatorial optimization problem in coding theory. The aim is to generate the largest possible permutation codes, having a given length n and a minimum Hamming distance d between the codewords. In this paper we present a new branch and bound algorithm, which combines combinatorial techniques with an approach based on group orbits. Computational experiments lead to interesting considerations about the use of group orbits for code generation.
2014
- A fast heuristic for the prize-collecting Steiner tree problem
[Relazione in Atti di Convegno]
Akhmedov, Murodzhon; Kwee, Ivo; Montemanni, Roberto
abstract
The Prize-Collecting Steiner Tree Problem (PCSTP) is a generalized version of the Steiner Tree Problem. PCSTP is well known and well studied problem in Combinatorial Optimization. Since PCSTP is NP-hard, it is computationally costly to achieve solutions for large instances. However, many real life network problems come with a wide range of variables and large instance sizes. Therefore, there is a need for efficient and fast heuristic algorithms to discover the hidden knowledge behind vast networks. There exists a fast heuristic algorithm for the Steiner Tree Problem in the literature, which is based on Minimum Spanning Trees. In this paper, we propose to extend the existing heuristic algorithm to solve PCSTP. The performance of the extended heuristic (MST-PCST) is evaluated on available benchmark instances from the literature. We also test MST-PCST on randomly generated huge graph instances with up to 40000 nodes and 120000 edges. We report the average gap percentage between the solutions of MST-PCST and existing solution approaches in the literature. Results show that overall performance of MST-PCST is promising with tolerable gap percentage and reasonable running time on larger instances. It has a significantly faster running time when graphs scale up which can shed light on large real world network instances.
2014
- A multiple ant colony system for a vehicle routing problem with time windows and uncertain travel times
[Articolo su rivista]
Toklu Nihat, Engin; Gambardella Luca, Maria; Montemanni, Roberto
abstract
In this paper, we study the capacitated vehicle routing problem with time window constraints, under travel time uncertainty. The uncertainty here represents the perturbation on the data caused by the effects of the unpredictable events in the reality, like traffic jams, road constructions, etc. To be able to near-optimally solve the large-instances of this problem without encountering memory errors or without taking too much time, we propose a heuristic approach based on ant colony optimization, which generates multiple solutions at the end of its execution, each solution with a different protection against the uncertainty. The trade-off between robustness and cheapness shown by these generated multiple solutions are then discussed.
2014
- An enhanced ant colony system for the probabilistic traveling salesman problem
[Relazione in Atti di Convegno]
Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
In this work we present an Enhanced Ant Colony System algorithm for the Probabilistic Traveling Salesman Problem. More in detail, we identify drawbacks of the well-known Ant Colony System metaheuristic when applied to the Probabilistic Traveling Salesman Problem. We then propose enhancements to overcome those drawbacks. Comprehensive computational studies on common benchmark instances reveal the efficiency of this novel approach. The Enhanced Ant Colony System algorithm clearly outperforms the original Ant Colony System metaheuristic. Additionally, improvements over best-known results for the Probabilistic Traveling Salesman Problem could be obtained for many instances.
2014
- An exact algorithm for the k-robust shortest paths problem with interval data
[Articolo su rivista]
Mastromatteo, Fabio; Montemanni, Roberto; Gambardella Luca, Maria; Rizzoli Andrea, Emilio
abstract
Companies operating in the textile sector aim at reducing the overall environmental impact of their products in order to obtain certification for them. This implies on optimization of the whole supply chain. The intrinsically high uncertainty that characterizes environmental impacts has to be taken into account during such an optimization. This problem can be modeled as a k-robust shortest paths problem with interval data, and we present an exact algorithm to tackle it. The method presented, based on some theoretical insights, is validated through some experimental results that show its effectiveness in solving problems arising in different sectors and not only in the supply chain optimization domain.
2014
- Objective function evaluation methods for the orienteering problem with stochastic travel and service times
[Articolo su rivista]
Papapanagiotou, Vassilis; Montemanni, Roberto; Gambardella, Lm
abstract
In this paper, a variant of the orienteering problem in which the travel and service times are stochastic, is examined. Given a set of potential customers, a subset of them has to be selected to be serviced by the end of the day. Every time a delivery to a selected customer is fulfilled before the end of the day, a reward is received, otherwise, if the delivery is not completed, a penalty is incurred. The target is to maximise the expected income (rewards-penalties) of the company. The focus of this paper is to evaluate faster ways to approximate the objective function and compare them to an analytical way previously proposed in the literature. K
2014
- Permutation codes: a new upper bound for M (7, 5)
[Relazione in Atti di Convegno]
Montemanni, Roberto; Barta, Janos; Smith Derek, H
abstract
This paper deals with permutation codes. These codes have a main application in error correction in telecommunications. An algorithm based on combinatorial optimization concepts such as branch and bound, and graph theoretical concepts such as graph isomorphism, is discussed. The new theoretical result M(7,5) ≤ 122, obtained by this approach, is finally disclosed.
2014
- Proceedings of the 6th international conference of applied operational research
[Curatela]
Sheibani, Kaveh; Montemanni, R; Nordlander, T; Hirsch, P; Vanhoucke, Mario
abstract
Operational Research is an important scientific discipline with many new theoretical developments and practical applications. The International Conference on Applied Operational Research (ICAOR) is an annual forum bringing together academics and practitioners from around the world to discuss the most recent developments in operational research and management science (OR/MS). The conference covers all aspects of our subject, but with a particular emphasis on applications. This year, the sixth event in our planned series of conferences – ICAOR 2014 takes place in the city of Vancouver, Canada. We received quality submissions from approximately 21 countries around the world and finally could accept 28 papers for presentation at the conference and publication in these proceedings. The papers that appear in this volume were carefully and thoroughly refereed. Our sincere thanks go to the members of the scientific programme committee who gave a significant amount of their valuable time to this task. We are also very grateful to all those who have helped in organising the conference. We are sure that their contributions will add significantly to the success of the conference. We very much hope that you will enjoy the conference programme and the planned social events. We wish you all a very pleasant stay in Vancouver and trust that you will find the conference to be of value and leave us having made many new friends.
2014
- Thermodynamic post-processing versus GC-content pre-processing for DNA codes satisfying the hamming distance and reverse-complement constraints
[Articolo su rivista]
Tulpan, Dan; Smith Derek, H; Montemanni, Roberto
abstract
Stochastic, meta-heuristic and linear construction algorithms for the design of DNA strands satisfying Hamming distance and reverse-complement constraints often use a GC-content constraint to pre-process the DNA strands. Since GC-content is a poor predictor of DNA strand hybridization strength the strands can be filtered by post-processing using thermodynamic calculations. An alternative approach is considered here, where the algorithms are modified to remove consideration of GC-content and rely on post-processing alone to obtain large sets of DNA strands with satisfactory melting temperatures. The two approaches (pre-processing GC-content and post-processing melting temperatures) are compared and are shown to be complementary when large DNA sets are desired. In particular, the second approach can give significant improvements when linear constructions are used.
2014
- Three metaheuristics for the construction of constant GC-content DNA codes
[Relazione in Atti di Convegno]
Montemanni, Roberto; Smith Derek, H; Koul, N
abstract
DNA codes are sets of words of fixed length n over the alphabet {A, C, G, T} which satisfy a number of combinatorial conditions. The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC-content and, in some cases (iii) minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords. In this paper three different meta-heuristic approaches for the problem are discussed, and the outcome of an extensive experimental campaign, leading to many new best-known codes, is presented.
2013
- A metaheuristic framework for stochastic combinatorial optimization problems based on GPGPU with a case study on the probabilistic traveling salesman problem with deadlines
[Articolo su rivista]
Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
In this work we propose a general metaheuristic framework for solving stochastic combinatorial optimization problems based on general-purpose computing on graphics processing units (GPGPU). This framework is applied to the probabilistic traveling salesman problem with deadlines (PTSPD) as a case study. Computational studies reveal significant improvements over state-of-the-art methods for the PTSPD. Additionally, our results reveal the huge potential of the proposed framework and sampling-based methods for stochastic combinatorial optimization problems.
2013
- A robust multiple ant colony system for the capacitated vehicle routing problem
[Relazione in Atti di Convegno]
Toklu, Ne; Montemanni, Roberto; Gambardella Luca, Maria
abstract
In transportation problems like the vehicle routing problem, the decision makers are increasingly adopting the idea that the problem data can be subject to uncertainty. The uncertainty can be encountered because of events that are not exactly predictable, like weather conditions, traffic jams, etc. In this paper, we study vehicle routing problem with uncertain travel costs. Then, to solve the problem, we propose a robust multiple ant colony system: a metaheuristic in which multiple ant colonies work in parallel to generate a collection of solutions with different levels of protection against the uncertainty. The uncertainty is handled by incorporating linear formulations from the field of robust optimization into the metaheuristic approach.
2013
- A sampling-based approximation of the objective function of the orienteering problem with stochastic travel and service times
[Relazione in Atti di Convegno]
Papapanagiotou, V; Weyland, D; Montemanni, R; Gambardella, Lm
abstract
In this paper, a variant of the orienteering problem in which the travel and service times are stochastic, is examined. Given a set of potential customers, a subset of them has to be selected to be serviced by the end of the day. Every time a delivery to a selected customer is fulfilled before the end of the day, a reward is received, otherwise, if the delivery is not completed, a penalty is incurred. The target is to maximise the expected income (rewards-penalties) of the company. The focus of this paper is to evaluate a sampling based way to approximate the objective function which is designed to be later embedded in metaheuristics.
2013
- An ant colony system for the capacitated vehicle routing problem with uncertain travel costs
[Relazione in Atti di Convegno]
Toklu, Ne; Montemanni, Roberto; Gambardella Luca, Maria
abstract
In this study, we consider a capacitated vehicle routing problem where the objective function is to minimize the total travel cost.We also consider that the travel costs between the locations are subject to uncertainty, therefore they are expressed as intervals, rather than fixed numbers. The motivation of this study is to solve this problem by using a metaheuristic approach. We base our approach on a variant of ant colony optimization metaheuristic, called ant colony system, which was originally implemented for solving the deterministic version of the problem (i.e. the classical version of the problem without the uncertainty), previously reported in the literature. We modify the algorithm to incorporate a robust optimization methodology, so that the uncertainty on traveling costs can be handled.
2013
- An improved heuristic for the probabilistic traveling salesman problem with deadlines based on GPGPU
[Relazione in Atti di Convegno]
Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
Stochastic combinatorial optimization problems have received increasing attention in recent years. These problems can be used to obtain more realistic models for real world applications. The drawback is that stochastic combinatorial optimization problems are usually much harder to solve than their non-stochastic counterparts and therefore efficient heuristics for these problems are of great importance. In this paper we focus on the Probabilistic Traveling Salesman Problem with Deadlines, a well-known stochastic vehicle routing problem. This problem can be efficiently solved using a heuristic based on general-purpose computing on graphics processing units. We show how such a heuristic can be further improved to allow a more efficient utilization of the graphics processing unit. We extensively discuss our results and point out how our techniques can be generalized for solving other stochastic combinatorial optimization problems.
2013
- Computational sequence design techniques for DNA microarray technologies
[Capitolo/Saggio]
Tulpan, D.; Ghiggi, A.; Montemanni, R.
abstract
In systems biology and biomedical research, microarray technology is a method of choice that enables the complete quantitative and qualitative ascertainment of gene expression patterns for whole genomes. The selection of high quality oligonucleotide sequences that behave consistently across multiple experiments is a key step in the design, fabrication and experimental performance of DNA microarrays. The aim of this chapter is to outline recent algorithmic developments in microarray probe design, evaluate existing probe sequences used in commercial arrays, and suggest methodologies that have the potential to improve on existing design techniques.
2013
- EcoLogTex: a software tool supporting the design of sustainable supply chains for textiles
[Relazione in Atti di Convegno]
Rizzoli Andrea, Emilio; Zeller, Heinz; Faist, Mireille; Montemanni, Roberto; Gioacchini, Michela; Nembrini, Nicola
abstract
This paper describes the design and the initial phases of the project EcoLogTex that aims to deliver a new methodology and a software tool to support the design of textile supply chains taking into account the impact on the environment as well as costs and time, while satisfying corporate social responsibility constraints. The key idea of EcoLogTex is to gather information on the environmental impacts of single steps in a supply chain in order to perform anex ante life- cycle assessment which will produce indicators to be used in the design and choice of the supply chain to be implemented. In other words, the designers of clothing apparel will be able to select the composition, colours, styles of their garments taking into account not only the cost and time required for the production, but also the environmental impact, thus al- lowing a more conscious use of resources.
2013
- Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling
[Articolo su rivista]
Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a Stochastic Vehicle Routing Problem with a computationally demanding objective function. In this work we propose an approximation for that objective function based on Monte Carlo Sampling and using the novel approach of quasi-parallel evaluation of samples. We perform comprehensive computational studies that reveal the efficiency of this approximation. Additionally, we examine different Local Search Algorithms and present a Random Restart Local Search Algorithm for solving the PTSPD together with an extensive computational study on a large set of benchmark instances.
2013
- Permutation codes with specified packing radius
[Articolo su rivista]
Smith, Derek H.; Montemanni, Roberto
abstract
Most papers on permutation codes have concentrated on the minimum Hamming distance of the code. An (n, d) permutation code (or permutation array) is simply a set of permutations on n elements in which the Hamming distance between any pair of distinct permutations (or codewords) is at least d. An (n, 2e + 1) or (n, 2e + 2) permutation code is able to correct up to e errors. These codes have a potential application to powerline communications. It is known that in an (n, 2e) permutation code the balls of radius e surrounding the codewords may all be pairwise disjoint, but usually some overlap. Thus an (n, 2e) permutation code is generally unable to correct e errors using nearest neighbour decoding. On the other hand, if the packing radius of the code is defined as the largest value of e for which the balls of radius e are all pairwise disjoint, a permutation code with packing radius e can be denoted by [n, e]. Such a permutation code can always correct e errors. In this paper it is shown that, in almost all cases considered, the number of codewords in the best [n, e] code found is substantially greater than the largest number of codewords in the best known (n, 2e + 1) code. Thus the packing radius more accurately specifies the requirement for an e-error-correcting permutation code than does the minimum Hamming distance. The techniques used include construction by automorphism group and several variations of clique search They are enhanced by two theoretical results which make the computations feasible.
2013
- Scheduling and routing in home health care service
[Relazione in Atti di Convegno]
Nguyen Thi Viet, Ly; Montemanni, Roberto
abstract
In this paper we address the home health care services problem in terms of routing and scheduling. The aim of the study is to determine a feasible working plan for nurses in order to offer patients the best possible solution in terms of quality of service and economy while satisfying the demands of patients and nurses as well as the related constraints. Besides giving a brief overview of related literature, we describe a new extended version of the existing home health case service problems and propose a mixed integer linear programming formulation. Computational results conducted based on a set of randomly generated home health case scenarios reveal that the proposed model is flexible and applicable in practice.
2013
- Supply chain design and sustainability in the textile sector
[Relazione in Atti di Convegno]
Montemanni, R; Valeri, C; Nevsic, S; Gambardella, Lm; Gioacchini, M; Fumagalli, T; Zeller, H; Meyer, K; Faist, M; Rizzoli, Ae
abstract
A project where optimization techniques and life cycle assessment methods are used to select a supply chain balancing economical and ecological factors is described. In particular, the optimization component will be analysed, modelled in mathematical terms and solved with methods previously appeared in the literature. The supply chain considered is the one of a top-brand firm in the textile sector.
2013
- Vehicle routing for exhausted oil collection
[Articolo su rivista]
Weyland, Dennis; Salani, Matteo; Montemanni, Roberto; Gambardella Luca, Maria
abstract
In this paper we present a Vehicle Routing Problem for the collection of exhausted cooking oil in Bali (Indonesia). This is an integral part of a recycling project initiated by the Caritas Suisse, where cooking oil is collected and recycled to obtain bio diesel fuel. The main goals of this project are to help the people in this region, to protect the environment and to make a contribution to combat climate change. In our work we present the underlying real world problem and show how it can be modeled as a Vehicle Routing Problem. We propose a heuristic to tackle this problem and show that we could support the decision process about the optimal location for the processing plant and the optimal number of vehicles with our approach.
2012
- A branch and bound approach for the sequential ordering problem
[Relazione in Atti di Convegno]
Mojana, Marco; Montemanni, Roberto; Di Caro, Gianni; Gambardella Luca, M
abstract
Many different real problems can be modeled in mathematical terms as a Sequential Ordering Problem. This combinatorial optimization problem can be seen as a scheduling problem with precedence constraints among the jobs. In the present paper a branch and bound method that exploits the structure of the precedence constraints is introduced and tested on some benchmark instances commonly adopted in the literature.
2012
- A matheuristic algorithm for a large-scale energy management problem
[Relazione in Atti di Convegno]
Anghinolfi, Davide; Gambardella Luca, Maria; Montemanni, Roberto; Nattero, Cristiano; Paolucci, Massimo; Toklu, Ne
abstract
The demand for electrical energy is globally growing very quickly. For this reason, the optimization of power plant productions and power plant maintenance scheduling have become important research topics. A Large Scale Energy Management (LSEM) problem is studied in this paper. Two types of power plants are considered: power plants of type 1 can be refueled while still operating. Power plants of type 2 need to be shut down from time to time, for refueling and ordinary maintenance (these are typically nuclear plants). Considering these two types of power plants, LSEM is the problem of optimizing production plans and scheduling of maintenances of type 2 plants, with the objective of keeping the production cost as low as possible, while fulfilling the customers demand. Uncertainty about the customers demand is taken into account in the model considered. In this article, a matheuristic optimization approach based on problem decomposition is proposed. The approach involves mixed integer linear programming and simulated annealing optimization methods. Computational results on some realistic instances are presented.
2012
- A new table of permutation codes
[Articolo su rivista]
Smith Derek, H; Montemanni, Roberto
abstract
Permutation codes (or permutation arrays) have received considerable interest in recent years, partly motivated by a potential application to powerline communication. Powerline communication is the transmission of data over the electricity distribution system. This environment is rather hostile to communication and the requirements are such that permutation codes may be suitable. The problem addressed in this study is the construction of permutation codes with a specified length and minimum Hamming distance, and with as many codewords (permutations) as possible. A number of techniques are used including construction by automorphism group and several variations of clique search based on vertex degrees. Many significant improvements are obtained to the size of the best known codes.
2012
- A note on the article “A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem”
[Articolo su rivista]
Montemanni, R; Gambardella, Lm
abstract
In the paper Li et al. [A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem. Omega 2012;40:210–7] it is claimed that a theoretical result appeared in Montemanni and Gambardella [Exact algorithms for the minimum power symmetric connectivity problem in wireless networks. Computers and Operations Research 2005;32:2891–904] is wrong. In this note we show that the original result is correct, and that the counter-example used to prove the wrongness of the original result is incorrect.
2012
- A shared incumbent environment for the minimum power broadcasting problem in wireless networks
[Relazione in Atti di Convegno]
Toklu, Ne; Montemanni, R; Di Caro, Ga; Gambardella, Lm
abstract
In this study, we consider the minimum power broadcasting problem in wireless actuator networks. We attack the problem with a method - the shared incumbent environment - that executes two algorithms in parallel: a mathematical programming approach and a simulated annealing approach. According to the shared incumbent environment paradigm, when an incumbent solution is found by one method, the other method is notified and profits from the information received. Experimental results show that the shared incumbent environment lead to results which are better than those of the two algorithms combined in it taken singularly.
2012
- Aggregate blending via robust linear programming
[Articolo su rivista]
Montemanni, R; Toklu, Ne; Toklu, Sc; Toklu, Y Cengiz
abstract
Aggregate blending is a problem frequently encountered in the construction industry. In this article, it is shown that robust linear programming can be used to produce solutions protected against noisy data with the same computational complexity of the classic optimization methods for the problem. It is also shown that nonlinear cost functions can be approximated by piecewise linear functions, keeping complexity at a low level. Finally, experimental results are presented. The aim is to understand how robust linear programming solutions compare with those of other methods previously described in the literature and to evaluate the actual quality of the robust solutions.
2012
- An enhanced ant colony system for the sequential ordering problem
[Relazione in Atti di Convegno]
Gambardella Luca, Maria; Montemanni, Roberto; Weyland, Dennis
abstract
A well-known Ant Colony System algorithm for the Sequential Ordering Problem is studied to identify its drawbacks. Some criticalities are identified, and an Enhanced Ant Colony System method that tries to overcome them, is proposed. Experimental results show that the enhanced method clearly outperforms the original algorithm and becomes a reference method for the problem under investigation.
2012
- Coupling ant colony systems with strong local searches
[Articolo su rivista]
Gambardella Luca, Maria; Montemanni, Roberto; Weyland, Dennis
abstract
Ant colony system is a well known metaheuristic framework, and many efficient algorithms for different combinatorial optimization problems have been derived from this general framework. In this paper some directions for improving the original framework when a strong local search routine is available, are identified. In particular, some modifications able to speed up the method and make it competitive on large problem instances, on which the original framework tends to be weaker, are described. The resulting framework, called Enhanced Ant Colony System is tested on three well-known combinatorial optimization problems arising in the transportation field. Many new best known solutions are retrieved for the benchmarks available for these optimization problems.
2012
- Hardness results for the probabilistic traveling salesman problem with deadlines
[Relazione in Atti di Convegno]
Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a Stochastic Vehicle Routing Problem considering time dependencies. Even the evaluation of the objective function is considered to be a computationally demanding task. So far there is no evaluation method known that guarantees a polynomial runtime, but on the other hand there are also no hardness results regarding the PTSPD objective function. In our work we show that the evaluation of the objective function of the PTSPD, even for Euclidean instances, is #P-hard. In fact, we even show that computing the probabilities, with which deadlines are violated is #P-hard. Based on this result we additionally show that the decision variant of the Euclidean PTSPD, the optimization variant of the Euclidean PTSPD and delta evaluation in reasonable local search neighborhoods is #P-hard.
2012
- Minimum power multicasting on wireless networks: a shared incumbent environment approach
[Relazione in Atti di Convegno]
Toklu, Ne; Montemanni, R
abstract
Shared incumbent environment is a new approachwhere a mixed integer linear programming solverand a meta-heuristic search algorithm work in paralleland inform each other when they improve the best knownsolution. In this study, we implement a shared incumbentenvironment by combining simulated annealing with amathematical programming formulation for solving theminimum power multicasting problem, where the goal isto find a topology for the wireless network terminals suchthat the source terminal will be able send data to alldestination terminals with minimized total transmissionpower. We present our results and analyze the success ofshared incumbent environment approach on instances ofdifferent sizes.
Keywords: minimum power multicasting problem; wire
2012
- Robust multicasting on stochastic wireless actuator networks: an algorithmic approach
[Articolo su rivista]
Toklu Nihat, Engin; Montemanni, Roberto
abstract
In this paper, we study the minimum power multicasting problem where the transmission power required for one network terminal to transmit to another is subject to uncertainty. We present our algorithmic approach which executes a classical mixed integer linear programming approach on the problem and then executes algorithmic procedures on the solution to improve its robustness. We then show our experimental procedures which test our approach on different levels of uncertainty and study the trade-off provided by the approach between solution cost and robustness. We also mathematically verify the correctness of the sampling method used in the experiments.
2012
- Scheduling problems with precedence constraints: Models and algorithms
[Relazione in Atti di Convegno]
Montemanni, R.
abstract
The sequential ordering problem is a basic scheduling problem with precedence constraints. It can be used to model many real world applications arising in different fields in terms of combinatorial optimization. In this paper we review two approaches to the problem recently appeared in the literature. Both the methods are based on a mixed integer linear programming, which is in turn introduced and discussed. Experimental results are presented to analyze the performance of the algorithms. © 2012 EUROSIS-ETI.
2012
- Some constant weight codes from primitive permutation groups
[Articolo su rivista]
Smith Derek, H; Montemanni, Roberto
abstract
In recent years the detailed study of the construction of constant weight codes has been extended from length at most 28 to lengths less than 64. Andries Brouwer maintains web pages with tables of the best known constant weight codes of these lengths. In many cases the codes have more codewords than the best code in the literature, and are not particularly easy to improve. Many of the codes are constructed using a specified permutation group as automorphism group. The groups used include cyclic, quasi-cyclic, affine general linear groups etc. sometimes with fixed points. The precise rationale for the choice of groups is not clear.
In this paper the choice of groups is made systematic by the use of the classification of primitive permutation groups. Together with several improved techniques for finding a maximum clique, this has led to the construction of 39 improved constant weight codes.
2012
- Using statistical tests for improving state-of-the-art heuristics for the probabilistic traveling salesman problem with deadlines
[Relazione in Atti di Convegno]
Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a Stochastic Vehicle Routing Problem with a computationally demanding objective function. Currently heuristics using an approximation of the objective function based on Monte Carlo Sampling are the state-of-the-art methods for the PTSPD. We show that those heuristics can be significantly improved by using statistical tests in combination with the sampling-based evaluation of solutions for the pairwise comparison of solutions.
2012
- Wireless multicasting under probabilistic node failures: a heuristic approach
[Articolo su rivista]
Barta, Janos; Montemanni, Roberto
abstract
The minimum power multicast (MPM) problem is a well-known optimization problem in wireless networks. The aim of the MPM problem is to assign transmission powers to the nodes of a wireless sensor network in such a way that multi-hop communication between a source node and a set of destination nodes is guaranteed, while the total transmission power expenditure over the network is minimized. Several extensions to the basic problem have been proposed, in order to obtain more realistic mathematical models. In this paper we deal with the probabilistic minimum power multicast (PMPM) problem, where node failure probabilities are considered and a global reliability level of the transmission is required. Since the so far available exact approach can handle only small-sized instances of the PMPM problem, in this paper we focus on the study of a heuristic approach. A heuristic algorithm for the PMPM problem is presented, together with a fast method for the reliability calculation based on previously unexplored combinatorial properties of the model. Computational experiments are finally discussed.
2011
- A branch and price algorithm for the minimum power multicasting problem in wireless sensor networks
[Articolo su rivista]
Montemanni, Roberto; Leggieri, Valeria
abstract
The Minimum Power Multicast Problem arises in wireless sensor networks and consists in assigning a transmission power to each node of a network in such a way that the total power consumption over the network is minimized, while a source node is connected to a set of destination nodes, toward which a message has to be sent periodically. A new mixed integer programming model for the problem, based on paths, is presented. A practical exact algorithm based on column generation and branch and price is derived from this model. A comparison with state-of-the-art exact methods is presented, and it is shown that the new approach compares favorably to other algorithms when the number of destination nodes is moderate. Under this condition, the proposed method is able to solve previously unmanageable instances.
2011
- A hybrid particle swarm optimization approach for the sequential ordering problem
[Articolo su rivista]
Anghinolfi, Davide; Montemanni, Roberto; Paolucci, Massimo; Gambardella Luca, Maria
abstract
The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are fulfilled, and the objective is to find a feasible solution with minimum cost.
A particle swarm optimization approach hybridized with a local search procedure is discussed in this paper. The method is shown to be very effective in guiding a sophisticated local search previously introduced in the literature towards high quality regions of the search space. Differently from standard particle swarm algorithms, the proposed hybrid method tends to fast convergence to local optima. A mechanism to self-adapt a parameter and to avoid stagnation is therefore introduced.
Extensive experimental results, where the new method is compared with the state-of-the-art algorithms, show the effectiveness of the new approach.
2011
- A linear programming-based evolutionary algorithm for the minimum power broadcast problem in wireless sensor networks
[Articolo su rivista]
Montemanni, Roberto; Mahdabi, Parvaz
abstract
A matheuristic approach, where concepts from linear programming are integrated into an evolutionary algorithm, is proposed. It is tested on a problem arising in wireless sensor networks: a topology with minimum total power expenditure, that connects a source node to all the other nodes of the network, has to be identified. Experimental results are presented.
2011
- A three-stage robust approach for minimum power multicasting in wireless sensor networks
[Relazione in Atti di Convegno]
Toklu, Ne; Montemanni, R
abstract
In this paper we study the minimum power multicasting problem in wireless sensor networks, where the transmission power required for one network terminal to transmit to another is subject to uncertainty.
We propose a three-stage approach based on linear programming.
Our novel approach adds two polynomial time stages to a first stage corresponding to a classical approach well known in the literature and based on a mathematical programming formulation. Stages two and three are introduced to adjust the transmission power of nodes in such a way to achieve a better protection against uncertainty, without increasing the total power consumption.
Experimental results show that our three-stage approach increases the robustness of the solutions obtained using the classical approach.
2011
- An enhanced ant colony system for the team orienteering problem with time windows
[Relazione in Atti di Convegno]
Montemanni, R; Weyland, D; Gambardella, Lm
abstract
The Team Orienteering Problem with Time Windows (TOPTW) is a combinatorial optimization problem arising both in industrial scheduling and in transportation. Ant Colony System (ACS) is a well-known metaheuristic framework, and many efficient algorithms for different optimization problems - among them the TOPTW - have been derived from this general framework. In this paper some directions for improving an ACS algorithm for the TOPTW recently appeared in the literature are identified. The resulting algorithm, called Enhanced Ant Colony System is experimentally shown to be extremely effective on some well-known benchmark instances available in the literature.
2011
- An optimization model for a large-scale energy management problem
[Relazione in Atti di Convegno]
Anghinolfi, D; Nattero, C; Paolucci, M; Gambardedlla, Lm; Montemanni, R; Toklu, Ne
abstract
With the growth in the demand for electrical energy globally, optimization of power plant productions and power plant maintenance scheduling have become important research topics. In this paper a Large Scale Energy Management (LSEM) problem is studied, where two types of power plants are considered. Power plants of the first type can be refueled while still operating. Power plants of the second type are
nuclear plants, which need to be shut down from time to time, for refueling and maintenance. Considering these two types of power plants, LSEM is the problem of optimizing production plans and scheduling of maintenances of nuclear plants, with the objective of keeping the production cost as low as possible. In this article, a matheuristic optimization approach based on the successive solutions of simplified sub-problems guided by a local search exploration is proposed to solve LSEM. The approach involves mixed integer linear programming and simulated annealing optimization methods. Computational results on some realistic instances are presented.
2011
- Convergence results for vehicle routing problems with stochastic demands
[Relazione in Atti di Convegno]
Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria
abstract
In this work we investigate two variants of the Stochastic Vehicle Routing Problem: The Vehicle Routing Prob- lem with Stochastic Demands and the Vehicle Routing Problem with Stochastic Demands and Customers. We show that under some moderate conditions there is an asymptotic equivalence between the Vehicle Routing Problem with Stochastic Demands and the Traveling Salesman Problem, as well as between the Vehicle Routing Problem with Stochastic Demands and Cus- tomers and the Probabilistic Traveling Salesman Problem. Based on our results we give explanations for different observations in literature and we provide ideas for the development of new approximation algorithms and heuristics for these problems.
2011
- Linear and nonlinear constructions of DNA codes with Hamming distance d and constant GC-content
[Articolo su rivista]
Smith Derek, H; Aboluion, Niema; Montemanni, Roberto; Perkins, Stephanie
abstract
Coding theory has several applications in genetics and bioengineering. This paper constructs codes over an alphabet
relevant to the design of synthetic DNA strands used in DNA microarrays, as DNA tags in chemical libraries and in DNA computing. The codes are designed to avoid unwanted hybridizations and to ensure uniform melting temperatures. Specifically, the codes considered here satisfy a Hamming distance constraint and a
-content constraint. In comparison with previous work, longer codes are constructed, the examination of cyclic and extended cyclic codes is more comprehensive, attention is paid to the mapping from field or ring elements to
, cosets of codes are used and a nonlinear shortening operation is performed. Many new best codes are constructed, and are reproducible from the information presented here.
2011
- Minimum power multicasting in wireless networks under probabilistic node failures
[Articolo su rivista]
Barta, Janos; Leggieri, Valeria; Montemanni, Roberto; Nobili, Paolo; Triki, Chefi
abstract
In this paper we deal with a probabilistic extension of the minimum power multicast (MPM) problem for wireless networks. The deterministic MPM problem consists in assigning transmission powers to the nodes, so that a multihop connection can be established between a source and a given set of destination nodes and the total power required is minimized. We present an extension to the basic problem, where node failure probabilities for the transmission are explicitly considered. This model reflects the necessity of taking uncertainty into account in the availability of the hosts. The novelty of the probabilistic minimum power multicast (PMPM) problem treated in this paper consists in the minimization of the assigned transmission powers, imposing at the same time a global reliability level to the solution network. An integer linear programming formulation for the PMPM problem is presented. Furthermore, an exact algorithm based on an iterative row and column generation procedure, as well as a heuristic method are proposed. Computational experiments are finally presented.
2010
- An Exact algorithm for the minimum power multicasting problem in wireless sensor networks
[Articolo su rivista]
Montemanni, Roberto; Leggieri, Valeria
abstract
The Minimum Power Multicast Problem arises in wireless sensor networks and consists in assigning a transmission power to each node of a network in such a way that it is minimized the total power consumption requested for maintaining a source node connected to a set of destination nodes. We propose an exact algorithm based on column generation and branch and price for the solution of the problem.
2010
- Heuristic manipulation, tabu search and frequency assignment
[Articolo su rivista]
Montemanni, Roberto; Smith Derek, H
abstract
Heuristic manipulation attempts to modify the search space of an optimization problem, using information provided by an underlying heuristic method. In this paper it is applied in combination with tabu search to the fixed spectrum frequency assignment problem.
The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimize interference and the spectrum required. In fixed spectrum frequency assignment the frequency spectrum available is given and the target is to minimize the interference in the network.
Computational experiments confirm that the manipulation technique is able to drive the underlying tabu search algorithm towards improved solutions.
2010
- Integer programming formulations for maximum lifetime broadcasting problems in wireless sensor networks
[Articolo su rivista]
Montemanni, Roberto
abstract
Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show that it is possible to accommodate realistic models for energy consumption and communication protocols into integer linear programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models that are also shown to provide efficient and practical solving tools. We present a strategy to substantially speed up the convergence of the solving process of our algorithm. This strategy introduces a practical drawback, however, in the characteristics of the optimal solutions retrieved. A method to overcome this drawback is discussed. Computational experiments are reported.
2010
- Radio Frequency Assignment: Optimization Techniques
[Monografia/Trattato scientifico]
Montemanni, R
abstract
The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimise interference and the spectrum required.
Some different variations of the problem are presented in this report to- gether with the results obtained so far for them. In this work we will study mainly the so-called “Fixed Spectrum Problem”, where there is a fixed avail- able spectrum of frequencies and the aim is to minimise interference.
There are two main approaches to model the frequency assignment prob- lem: the so-called “Binary Constraints Model”, historically the most studied in the literature, where only interference from a single transmitter at a time is considered, and the more realistic “Multiple Interference Model”, where interferences from more than one transmitter are considered at the same mo- ment. For this last model a deeply theoretical study does not yet exist in the literature.
The fixed spectrum problem, represented by the binary constraints model has been heavily studied in the last few years, but no general-purpose lower bound has been presented yet. We analyse some Integer Programming for- mulation to understand whether they can be suitable for developing lower bounds.
The multiple interference model is studied and some new algorithms, both heuristic and exact, are presented for it, together with the relevant computational results. Our aim is to understand the potential of this model.
The report concludes by outlining some proposals for future work.
2010
- Some valid inequalities for the probabilistic minimum power multicasting problem
[Articolo su rivista]
Barta, Janos; Leggieri, Valeria; Montemanni, Roberto; Nobili, Paolo; Triki, Chefi
abstract
In this paper we describe some results on the linear integer programming formulation of the Probabilistic Minimum Power Multicast (PMPM) problem for wireless networks. The PMPM problem consists in optimally assigning transmission powers to the nodes of a given network in order to establish a multihop connection between a source node and a set of destination nodes. The nodes are subject to failure with some probability, however the assignment should be made so that the reliability of the connection is above a given threshold level. This model reflects the necessity of taking into account the uncertainty of hosts' availability in a telecommunication network.
2009
- An ant colony system for team orienteering problems with time windows
[Articolo su rivista]
Montemanni, Roberto; Gambardella Luca, Maria
abstract
This paper discusses a heuristic approach for Team Orienteering Problems with Time Windows. The method we propose takes advantage of a solution model based on a hierarchic generalization of the original problem, which is combined with an Ant Colony System algorithm. Computational results on benchmark instances previously adopted in the literature suggest that the algorithm we propose is effective in practice.
2009
- Heuristic algorithms for constructing binary constant weight codes
[Articolo su rivista]
Montemanni, Roberto; Smith Derek, H
abstract
Constant weight binary codes are used in a number of applications. Constructions based on mathematical structure are known for many codes. However, heuristic constructions unrelated to any mathematical structure can become of greater importance when the parameters of the code are larger. This paper considers the problem of finding constant weight codes with the maximum number of codewords from a purely algorithmic perspective. A set of heuristic and metaheuristic methods is presented and developed into a variable neighborhood search framework. The proposed method is applied to 383 previously studied cases with lengths between 29 and 63. For these cases it generates 153 new codes, with significantly increased numbers of codewords in comparison with existing constructions. For 10 of these new codes the number of codewords meets a known upper bound, and so these 10 codes are optimal. As well as the ability to generate new best codes, the approach has the advantage that it is a single method capable of addressing many sets of parameters in a uniform way.
2009
- Maximum lifetime broadcasting topologies in wireless sensor networks: advanced mathematical programming models
[Relazione in Atti di Convegno]
Montemanni, Roberto
abstract
Mathematical programming has been always regarded as an over-theoretical tool in the field of topology optimization for wireless sensor networks. Our aim is to show that it is possible to accommodate the last advances in the field of energy consumption and communication models into mathematical programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models, that are also shown to provide efficient and practical solving tools.
2009
- Sequential ordering problems for crane scheduling in port terminals
[Articolo su rivista]
Montemanni, Roberto; Smith Derek, H; Rizzoli Andrea, Emilio; Gambardella Luca, Maria
abstract
The Sequential Ordering Problem (SOP) is a version of the Asymmetric Travelling Salesman Problem (ATSP) where precedence constraints on vertices are imposed. A tour is feasible if these constraints are respected, and the objective is to find a feasible solution with minimum cost. The SOP models many real world applications, mainly in the fields of transportation and production planning. In particular, it can be used to optimise quay crane assignments. In this paper, we experimentally evaluate the contributions of the basic ingredients of the state-of-the-art algorithm for the SOPs: Local Searches (LSs), ant colony and heuristic manipulation.
2008
- A heuristic manipulation technique for the sequential ordering problem
[Articolo su rivista]
Montemanni, Roberto; Smith, Dh; Gambardella Luca, Maria
abstract
The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are respected, and the objective is to find a feasible solution with minimum cost.
The sequential ordering problem models many real-world applications, mainly in the fields of transportation and production planning.
A problem manipulation technique to be used in conjunction with heuristic algorithms is discussed. The aim of the technique is to make the search space associated with each problem more attractive for the underlying heuristic algorithms.
This novel methodology is tested in combination with the state-of-the-art method for the sequential ordering problem. Improved results are obtained, particularly for the largest problems considered.
2008
- Construction of constant GC-content DNA codes via a variable neighbourhood search algorithm
[Articolo su rivista]
Montemanni, Roberto; Smith Derek, H
abstract
DNA codes are sets of words of fixed length n over the alphabet {A,C,G,T} which satisfy a number of combinatorial conditions. They have application in DNA computing, in DNA microarray technologies and as molecular bar codes. The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC content and, in some cases (iii) minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords. In this paper the construction of DNA codes is studied from an algorithmic perspective. Four local search algorithms are developed and combined in a variable neighbourhood search framework. The algorithm has been run extensively. Over 254 problems considered, it was able to match or improve the best known lower bounds in 180 cases, with 52 new bests.
2008
- Frequency assignment, multiple interference and binary constraints
[Articolo su rivista]
Graham, Js; Montemanni, Roberto; Moon Jim, Nj; Smith, Dh
abstract
The most accurate approaches to frequency assignment problems minimize a cost function based on signal-to-interference ratios at points where reception is required. The merits of this approach are counterbalanced by much greater requirements for computational resources than for the traditional approach using binary frequency separation constraints. This can make run times unrealistic for the largest problems. In this paper the merits of the signal-to-interference based cost function are confirmed, but it is shown that algorithms are faster and give better quality results if this cost function is combined with the binary constraint approach. Two types of algorithm are used to illustrate the combined approach, simulated annealing and a new ant colony system algorithm. The combined approach studied is applicable to all the main classes of frequency assignment problem.
2008
- Mixed integer formulations for the probabilistic minimum energy broadcast problem in wireless networks
[Articolo su rivista]
Montemanni, Roberto; Leggieri, Valeria; Triki, Chefi
abstract
In this paper we study a new variant of the minimum energy broadcast (MEB) problem, namely the probabilistic MEB (PMEB). The objective of the classic MEB problem is to assign transmission powers to the nodes of a wireless network is such a way that the total energy dissipated on the network is minimized, while a connected broadcasting structure is guaranteed by the assigned transmission powers. In the new variant of the problem treated in this paper, node failure is taken into account, aiming at providing solutions with a chosen reliability level for the broadcasting structure. Three mixed integer linear programming formulations for the new problem are presented, together with efficient formulation-dependent methods for their solution. Computational results are proposed and discussed. One method emerges as the most promising one under realistic settings. It is able to handle problems with up to fifty nodes.
2008
- Power-Optimized Topology Formation and Configuration in Bluetooth Sensor Networks: An Experimental Approach
[Articolo su rivista]
Negri, Luca; Zanetti, Davide; Montemanni, Roberto; Giordano, Silvia
abstract
Low power consumption is a critical issue in wireless sensor networks. To achieve it, a number of arguments exist in favor of ad-hoc architectures and communication protocols, with high power optimization potential. These architectures, however, lack interoperability, as opposite to standardized wireless protocols. In this paper we present and validate experimentally a variable-granularity power model of Bluetooth and apply it to solve variable-complexity power optimization problems, with the goal of making the protocol viable for wireless sensor network scenarios. Among such optimizations, a set of heuristic rules is derived to build power-optimal Bluetooth scatternet topologies, which unlike most Bluetooth topology formation schemes stem directly from experimental evidence.
2008
- Robust shortest path problems with uncertain costs
[Working paper]
Montemanni, Roberto; Gambardella Luca, M
abstract
Data coming from real-world applications are very often affected by uncertainty. On theother hand, it is difficult to translate uncertainty in terms of combinatorial optimization. Inthis paper we study a combinatorial optimization model to deal with uncertainty in arc costsin shortest path problems. We consider a model where feasible arc cost scenarios are describedvia a convex polytope. We present a computational complexity result and we discuss exactalgorithms for two different robust optimization criteria. We finally present experimentalresults showing that the proposed approaches are suitable to be used on realistic size instances.
2008
- Sequential ordering problems for crane scheduling in port terminals
[Relazione in Atti di Convegno]
Montemanni, R.; Rizzoli, A. E.; Smith, D. H.; Gambardella, L. M.
abstract
The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are respected, and the objective is to find a feasible solution with minimum cost. The sequential ordering problem models many real world applications, mainly in the fields of transportation and production planning. In particular, it can be used to optimise quay crane assignments. In this paper we experimentally evaluate the contributions of the basic ingredients of the state-of-the-art algorithm for the sequential ordering problems: local searches, ant colony and heuristic manipulation. Copyright © (2008) by CAL-TEK S.r.l.
2008
- Sequential ordering problems for crane scheduling in port terminals
[Relazione in Atti di Convegno]
Montemanni, R.; Rizzoli, A. E.; Smith, D. H.; Gambardella, L.
abstract
2008
- Time dependent vehicle routing problem with a multi ant colony system
[Articolo su rivista]
Donati Alberto, V; Montemanni, Roberto; Casagrande, Norman; Rizzoli Andrea, E; Gambardella Luca, M
abstract
The Time Dependent Vehicle Routing Problem (TDVRP) consists in optimally routing a fleet of vehicles of fixed capacity when travel times are time dependent, in the sense that the time employed to traverse each given arc, depends on the time of the day the travel starts from its originating node. The optimization method consists in finding solutions that minimize two hierarchical objectives: the number of tours and the total travel time.
Optimization of total travel time is a continuous optimization problem that in our approach is solved by discretizing the time space in a suitable number of subspaces. New time dependent local search procedures are also introduced, as well as conditions that guarantee that feasible moves are sought for in constant time.
This variant of the classic Vehicle Routing Problem is motivated by the fact that in urban contexts variable traffic conditions play an essential role and can not be ignored in order to perform a realistic optimization. In this paper it is shown that when dealing with time constraints, like hard delivery time windows for customers, the known solutions for the classic case become unfeasible and the degree of unfeasibility increases with the variability of traffic conditions, while if no hard time constraints are present, the classic solutions become suboptimal.
Finally an application of the model to a real case is presented. The model is integrated with a robust shortest path algorithm to compute time dependent paths between each customer pairs of the time dependent model.
2007
- A mixed integer programming formulation for the total flow time single machine robust scheduling problem with interval data
[Articolo su rivista]
Montemanni, Roberto
abstract
We consider a version of the total flow time single machine scheduling problem where uncertainty about processing times is taken into account. Namely an interval of equally possible processing times is considered for each job, and optimization is carried out according to a robustness criterion. We propose the first mixed integer linear programming formulation for the resulting optimization problem and we explain how some known preprocessing rules can be translated into valid inequalities for this formulation. Computational results are finally presented.
2007
- Ant colony optimization for real-world vehicle routing problems
[Articolo su rivista]
Rizzoli Andrea, Emilio; Montemanni, Roberto; Lucibello, Enzo; Gambardella Luca, Maria
abstract
Ant colony optimization (ACO) is a metaheuristic for combinatorial optimization problems. In this paper we report on its successful application to the vehicle routing problem (VRP). First, we introduce the VRP and some of its variants, such as the VRP with time windows, the time dependent VRP, the VRP with pickup and delivery, and the dynamic VRP. These variants have been formulated in order to bring the VRP closer to the kind of situations encountered in the real-world.
Then, we introduce the basic principles of ant colony optimization, and we briefly present its application to the solution of the VRP and of its variants.
Last, we discuss the applications of ACO to a number of real-world problems: a VRP with time windows for a major supermarket chain in Switzerland; a VRP with pickup and delivery for a leading distribution company in Italy; a time dependent VRP for freight distribution in the city of Padua, Italy, where the travel times depend on the time of the day; and an on-line VRP in the city of Lugano, Switzerland, where customers’ orders arrive during the delivery process.
2007
- Ant colony systems for large sequential ordering problems
[Relazione in Atti di Convegno]
Montemanni, Roberto; Smith Derek, H; Gambardella Luca, Maria
abstract
The sequential ordering problem is a version of the asymmetric traveling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are respected, and the objective is to find a feasible solution with minimum cost. The sequential ordering problem models a lot of real world applications, mainly in the fields of transportation and production planning. In this paper we propose an extension of a well known ant colony system for the problem, aiming at making the approach more efficient on large problems. The extension is based on a problem manipulation technique that heuristically reduces the search space. Computational results, where the extended ant colony system is compared to the original one, are presented
2007
- Heuristic algorithms for the robust traveling salesman problem with interval data
[Relazione in Atti di Convegno]
Montemanni, R; Barta, J; Mastrolilli, M; Gambardella, Lm
abstract
The traveling salesman problem is one of the most famous combinatorial optimization problems, and has been intensively studied in the last decades. Many extensions to the basic problem have been also proposed, with the aim of making the resulting mathematical models as much realistic as possible.
2007
- Measuring the effectiveness of frequency assignment algorithms
[Articolo su rivista]
Smith Derek, H; Hughes Lesley, A; Moon Jim, Nj; Montemanni, Roberto
abstract
algorithms used to obtain them. This paper makes three contributions. First, a technique is described for modifying an effective existing lower bound for the span to take account of multiple interference. Multiple interference may increase the span and the modification captures some or all of this increase. Second, new results are given for a lower bound for some of the two level penalty-based COST259 problems. It remains true that for these problems, the gap between upper and lower bounds is large, by comparison with other benchmarks. Third, some evidence is presented to suggest that the assignments available today for problems of the COST259 type are still capable of very significant improvements.
2007
- The robust traveling salesman problem with interval data
[Articolo su rivista]
Montemanni, Roberto; Barta, Janos; Mastrolilli, Monaldo; Gambardella Luca, Maria
abstract
The traveling salesman problem is one of the most famous combinatorial optimization problems and has been intensively studied. Many extensions to the basic problem have also been proposed, with the aim of making the resulting mathematical models as realistic as possible. We present a new extension to the basic problem, where travel times are specified as a range of possible values. This model reflects the intrinsic difficulties of estimating travel times in reality. We apply the robust deviation criterion to drive optimization over the interval data problem so obtained. Some interesting theoretical properties of the new optimization problems are identified and discussed, together with a new mathematical formulation and some exact and heuristic algorithms. Computational experiments are finally presented.
2006
- A Benders decomposition approach for the robust spanning tree problem with interval data
[Articolo su rivista]
Montemanni, Roberto
abstract
The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.
Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.
This paper describes a new exact method, based on Benders decomposition, for the robust spanning tree problem with interval data. Computational results highlight the efficiency of the new method, which is shown to be very fast on all the benchmarks considered, and in particular on those that were harder to solve for the methods previously known.
2006
- Design patterns from biology for distributed computing
[Articolo su rivista]
Babaoglu, Ozalp; Canright, Geoffrey; Deutsch, Andreas; Di Caro Gianni, A; Ducatelle, Frederick; Gambardella Luca, M; Ganguly, Niloy; Jelasity, Mark; Montemanni, Roberto; Montresor, Alberto; Urnes, T
abstract
Recent developments in information technology have brought about important changes in distributed computing. New environments such as massively large-scale, wide-area computer networks and mobile ad hoc networks have emerged. Common characteristics of these environments include extreme dynamicity, unreliability, and large scale. Traditional approaches to designing distributed applications in these environments based on central control, small scale, or strong reliability assumptions are not suitable for exploiting their enormous potential. Based on the observation that living organisms can effectively organize large numbers of unreliable and dynamically-changing components (cells, molecules, individuals, etc.) into robust and adaptive structures, it has long been a research challenge to characterize the key ideas and mechanisms that make biological systems work and to apply them to distributed systems engineering. In this article we propose a conceptual framework that captures several basic biological processes in the form of a family of design patterns. Examples include plain diffusion, replication, chemotaxis, and stigmergy. We show through examples how to implement important functions for distributed computing based on these patterns. Using a common evaluation methodology, we show that our bio-inspired solutions have performance comparable to traditional, state-of-the-art solutions while they inherit desirable properties of biological systems including adaptivity and robustness.
2006
- Heuristic and preprocessing techniques for the robust traveling salesman problem with interval data
[Working paper]
Montemanni, R; Barta, J; Gambardella, Lm
abstract
We study a version of the traveling salesman problem where travel times are specified as a range of possible values. This model reflects the difficulties to estimate travel times exactly in reality. Robustness concepts are used to drive optimization. We propose some efficient heuristic and preprocessing techniques. Computational experiments are presented.
2005
- A Benders decomposition approach for the robust shortest path problem with interval data
[Relazione in Atti di Convegno]
Montemanni, R; Gambardella, Lm
abstract
Many real problems can be modelled as robust shortest path problems on digraphs with interval costs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible conflguration of the arc costs. A Benders decomposition approach for this problem is presented.
2005
- A branch and bound algorithm for the robust spanning tree problem with interval data
[Articolo su rivista]
Montemanni, Roberto; Gambardella Luca, Maria
abstract
The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.
Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.
In this paper a branch and bound algorithm for the robust spanning tree problem is proposed. The method embeds the extension of some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted.
Computational results obtained by the algorithm are presented. The technique we propose is up to 210 times faster than methods recently appeared in the literature.
2005
- Ant colony system for a dynamic vehicle routing problem
[Articolo su rivista]
Montemanni, Roberto; Gambardella Luca, Maria; Rizzoli Andrea, Emilio; Donati Alberto, V
abstract
An aboundant literature on vehicle routing problems is available. However, most of the work deals with static problems, where all data are known in advance, i.e. before the optimization has started.
The technological advances of the last few years give rise to a new class of problems, namely the dynamic vehicle routing problems, where new orders are received as time progresses and must be dynamically incorporated into an evolving schedule.
In this paper a dynamic vehicle routing problem is examined and a solving strategy, based on the Ant Colony System paradigm, is proposed.
Some new public domain benchmark problems are defined, and the algorithm we propose is tested on them.
Finally, the method we present is applied to a realistic case study, set up in the city of Lugano (Switzerland).
2005
- Exact algorithms for the minimum power symmetric connectivity problem in wireless networks
[Articolo su rivista]
Montemanni, Roberto; Gambardella Luca, Maria
abstract
In this paper we consider the problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized.
Two mixed integer programming formulations are presented together with some new valid inequalities for the polytopes associated. A preprocessing technique and two exact algorithms based on the formulations previously introduced are also proposed.
Comprehensive computational results, which show the effectiveness of the new valid inequalities and of the preprocessing technique are presented. The experiments also show that the exact approaches we propose outperform more complex methods recently appeared in the literature.
2005
- Minimum Power Symmetric Connectivity Problem in Wireless Networks: A New Approach
[Capitolo/Saggio]
Montemanni, Roberto; Gambardella Luca, Maria
abstract
We consider the problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes of the network are connected by bidirectional links and the total power consumption is minimized.
A new exact algorithm, based on a new integer programming model, is described in this paper together with a new preprocessing technique.
2005
- Models and Algorithms for the MPSCP: An Overview Roberto Montemanni, Luca M. Gambardella, and Arindam Kumar Das
[Capitolo/Saggio]
Montemanni, Roberto; Maria Gambardella, Luca; Das, Arindam
abstract
2005
- Models and algorithms for the MPSCP: an overview
[Capitolo/Saggio]
Montemanni, Roberto; Luca Maria, Gambardella; Arindam Kumar, Das
abstract
Ad hoc wireless networks have received significant attention in recent years due to their potential applications in battlefields, emergency disasters relief, and other application scenarios (see, for example, Blough et al.,2 Chu and Nikolaidis,4 Clementi et al.,5,7, Kirousis et al.,10 Lloyd et al.,11 Ramanathan and Rosales-Hain,17 Singh et al.,19 Wan et al.,20 and Wieselthier et al.22). Unlike wired networks of cellular networks, no wired backbone infrastructure is installed in ad hoc wireless networks. A communication session is achieved either through single-hop transmission if the recipient is within the transmission range of the source node, or by relaying through intermediate nodes.
2005
- Swarm approach for a connectivity problem in wireless networks
[Relazione in Atti di Convegno]
Montemanni, Roberto; Gambardella Luca, Maria
abstract
We consider the problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized. Since no central authority (with a global vision of the network) exists in wireless networks, only distributed, swarm approaches can be used. We present a distributed protocol that embeds well-known centralized techniques for power minimization, here used in a local, distributed fashion. The result can be seen as a complex adaptive system (the global network), where global optimization emerges as a result of the behavior of local nodes, each one carrying out a myopic, local optimization. Computational results, proving the effectiveness of the new protocol, are finally presented.
2005
- The minimum power broadcast problem in wireless networks: a simulated annealing approach
[Relazione in Atti di Convegno]
Montemanni, Roberto; Gambardella Luca, Maria; Das Arindam, Kumar
abstract
Broadcasting in wireless networks, unlike wired networks, inherently reaches several nodes with a single transmission. For an omnidirectional wireless broadcast to a node, all nodes closer to the transmitting node are also reached. This property can be used to compute routing trees which minimize the sum of the transmitter powers. We present a mixed integer programming formulation and a simulated annealing algorithm for the problem. Extensive experimental results for the heuristic approach are presented. They show that the proposed algorithm is capable of improving the results of state-of-the-art algorithms for most of the problems considered. The solutions provided by the simulated annealing algorithm can be improved by applying a very fast post-optimization procedure. This leads to the best known mean results for the problems considered.
2005
- The robust shortest path problem with interval data via Benders decomposition
[Articolo su rivista]
Montemanni, Roberto; Gambardella Luca, Maria
abstract
Many real problems can be modelled as robust shortest path problems on digraphs with interval costs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs.
In this paper we discuss the application of a Benders decomposition approach to this problem.
Computational results confirm the efficiency of the new algorithm. It is able to clearly outperform state-of-the-art algorithms on many classes of networks. For the remaining classes we identify the most promising algorithm among the others, depending of the characteristics of the networks.
2004
- A branch and bound algorithm for the robust shortest path problem with interval data
[Articolo su rivista]
Montemanni, Roberto; Gambardella Luca, Maria; Donati Alberto, V
abstract
Many real problems can be modelled as robust shortest path problems on interval digraphs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs.
A branch and bound algorithm for this problem is presented.
2004
- A comparison of two new exact algorithms for the robust shortest path problem
[Relazione in Atti di Convegno]
Montemanni, Roberto; Gambardella Luca, Maria; Donati, Av
abstract
Real road networks can be modelled in mathematical terms as interval digraphs, where an interval of travel times (costs) is associated with each arc. Intervals represent uncer- tainty, typical of real situations, about exact travel times.
A robust shortest path is a path which is not too far from the shortest one, whatever the exact values of arc costs are. This concept, expressed in mathematical terms, is used to drive optimization.
In this paper we compare the performance of two exact methods recently presented on some real road networks.
2004
- An exact algorithm for the robust shortest path problem with interval data
[Articolo su rivista]
Montemanni, Roberto; Gambardella Luca, Maria
abstract
The robust deviation shortest path problem with interval data is studied in this paper.
After the formulation of the problem in mathematical terms, an exact algorithm, based on a very simple concept, is described. Some practical improvements to the basic idea, which speed up the method, are also presented.
Computational results corroborate the correctness of the conjecture on which the algorithm is based and the potential of the approach. In particular, our method is proven to be able to retrieve high-quality solutions very quickly on some families of networks. For this reason, it could alternatively be used as a fast heuristic method.
2004
- An improved algorithm to determine lower bounds for the fixed spectrum frequency assignment problem
[Articolo su rivista]
Montemanni, Roberto; Smith, Dh; Allen Stuart, M
abstract
Frequencies have to be assigned to transmitters whenever a radio network is established or modified. This is ideally done is a way which minimises interference in the network. Lower bounds are necessary to establish the effectiveness of the heuristic algorithms used for this task and to assess the quality of the assignments obtained.
In the fixed spectrum frequency assignment problem the available frequencies are known in advance. The constraints are often binary constraints, specifying the necessary frequency separation between given pairs of transmitters. There may be penalties (or weights) associated with the violation of each constraint; it is then either necessary to minimise the number of constraints violated or, increasingly often, to minimise the sum of the weights associated with violated constraints.
A technique for generating lower bounds for these quantities is presented. This is an evolution of a technique which has recently appeared in the literature. It produces better quality bounds, is in general significantly faster and allows larger problems to be handled.
2004
- Ant Colony Optimisation for vehicle routing problems: from theory to applications
[Working paper]
Rizzoli Andrea, Emilio; Oliverio, F; Montemanni, R; Gambardella Luca, Maria
abstract
Ant Colony Optimisation is a metaheuristic for combinatorial optimisation problems.
In this paper we show its successful application to the Vehicle Routing Problem (VRP).
First, we introduce VRP and its many variants, such as VRP with Time Windows, Time
Dependent VRP, Dynamic VRP, VRP with Pickup and Delivery. These variants have
been formulated in order to bring the VRP as close as possible to the kind of situations
encountered in real-world distribution processes. Two case studies are presented: the
application of Ant Colony Optimisation to the solution of the Time Dependent VRP,
where the travel times depend on the time of the day, and Ant Colony Optimisation
for Dynamic VRP, where customers’ orders arrive during the delivery process. Finally,
two real-world, industrial-scale applications are presented. The former is an application
solving a VRP with Time Windows for a major supermarket chain in Switzerland; the
latter is an application solving a VRP with Pickup and Delivery for a leading distribution company in Italy. The results for these two real-world cases, in particular the increase in the vehicle routes performances and their potential use as strategic planning tools, are presented and discussed.
2004
- Power-aware distributed protocol for a connectivity problem in wireless sensor networks
[Relazione in Atti di Convegno]
Montemanni, Roberto; Gambardella Luca, Maria
abstract
We consider the problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized.
We present a distributed protocol, obtained by extending a connectivity protocol recently appeared in the literature. The new extended protocol is obtained by using in a local, distributed fashion, well-known centralized techniques for power minimization. The result is a self-organization framework where a set of rules, implemented locally at each node, guarantees global properties, i.e. connectivity and power expenditure minimization.
Preliminary computational results are finally presented. They show that the new extended protocol guarantees a substantial saving in the total transmission power.
2003
- A new algorithm for a dynamic vehicle routing problem based on ant colony system
[Relazione in Atti di Convegno]
Montemanni, Roberto; Gambardella Luca, M; Rizzoli Andrea, E; Donati Alberto, V
abstract
Most of the literature available on vehicle routing problems is about static problems, where all data are known in advance. The technological advances of the last few years rise a new class of problems about dynamic vehicle routing, where new orders are received as time progresses and must be dynamically incorporated into an evolving schedule. In this work an algorithm for this problem, based on the Ant Colony System paradigm, is proposed.
Computational results on some problems derived from widely-available benchmarks confirm the efficiency of the method we propose.
A realistic case study, based on the road network of the city of Lugano (Switzerland) will be finally presented.
2003
- An improved tabu search algorithm for the fixed-spectrum frequency-assignment problem
[Articolo su rivista]
Montemanni, Roberto; Moon Jim, Nj; Smith Derek, H
abstract
A tabu search algorithm with a dynamic tabu list for the fixed-spectrum frequency-assignment problem is presented. For cellular problems, the algorithm can be combined with an efficient cell reoptimization step. The algorithm is tested on several sets of test problems and compared with existing algorithms of established performance. In particular, it is used to improve some of the best existing assignments for COST 259 benchmarks. These results add support to the claim that the algorithm is the most effective available, at least when solution quality is a more important criterion than solution speed. The algorithm is robust and easy to tune.
2003
- Ant colony optimization for vehicle routing in advanced logistics systems
[Relazione in Atti di Convegno]
Gambardella Luca, Maria; Rizzoli Andrea, E; Oliverio, Fabrizio; Casagrande, Norman; Donati, Alberto; Montemanni, Roberto; Lucibello, Enzo
abstract
Many distribution companies service their customers with non homogeneous fleets of trucks. Their problem is to find a set of routes minimising the number of travelled kilometres and the number of used vehicles, while satisfying customer demand. There are three major problems why traditional Operations Research techniques are not enough to deal with this problem, which is known as the Vehicle Routing Problem. First of all, it is inherently combinatorial, and exact algorithms fail when the dimension of the problem (number of customers and orders) reaches a reasonable size. Secondly, the problem can be extended and made more complex in many ways, for instance, adding more than one depot, considering more than one vehicle type, accounting for stochastic customer demand (the exact requested quantity is known only at delivery time), considering time windows during which the customers must be served, taking into account vehicle accessibility restrictions (some customers cannot be served by some vehicles). Finally, the problem can become very different when we consider on-line distribution, that is, we accept delivery orders for lorries which are en route. There, geolocation of customers and vehicles, online data transfer among lorries and the base station, have an impact as great as the solution strategy.
In this paper we present DyvOil and AntRoute, two software tools which assist the tour planner during the different stages of goods distribution, from pre-planning on the basis of reorder forecasts, to online planning, through offline planning based on an advanced metaheuristic such as Ant Colony System. We also describe the case of Pina Petroli, a fuel oil distribution company located in Canton Ticino, Switzerland, which operates a fleet of 12 vehicles and serves customers using DyvOil and Migros, the largest Swiss supermarket chain, which uses AntRoute operates daily a fleet of hundreds of trucks distributing goods to its shops.
2003
- Integration of a robust shortest path algorithm with a time dependent vehicle routing model and applications
[Relazione in Atti di Convegno]
Donati Alberto, V; Montemanni, Roberto; Gambardella Luca, M; Rizzoli Andrea, E
abstract
This paper describes a way of combining two techniques, in order to define a framework that can deal with the following problem: find an optimized set of routes when the customers set is a proper subset of an entire network, and variable traffic conditions have to be taken into account. This is accomplished on one hand by extending the vehicle routing problem (VRP) to a time dependent case (TDVRP), on the other hand by using an appropriate algorithm, the robust shortest path (RPS) that can provide itineraries when moving to a location to another, and guarantee good performance under any possible road network situation. Once a proper description of the TDVRP model is given, we discuss the optimization technique, based on the ant colony system (ACS), and the robust shortest path (RPS) algorithm. Different ways of integrating these techniques are discussed The one presented here consists in using the RPS algorithm for the calculation of the paths among each pair of customers, so that this information can to be used by the TDVRP optimization in a very efficient way. In the case of a real road network, some tests have been made, that show that the optimal solutions obtained for the classic VRP case are sub optimal when considered in a time dependent context, revealing that the approximation of constant speeds is sometimes inadequate.
2003
- Planning and optimisation of vehicle routes for fuel oil distribution
[Relazione in Atti di Convegno]
Rizzoli Andrea, E; Casagrande, Norman; Donati Alberto, V; Gambardella Luca, Maria; Lepori, Daniele; Montemanni, Roberto; Pina, Piero; Zaffalon, Marco
abstract
Fuel oil distribution companies service their customers with fleets of tanker lorries. The problem is to find a set of routes minimising the number of travelled kilometres and the number of used vehicles, while satisfying customer demand. There are three major problems why traditional Operations Research techniques are not enough to deal with this problem, which is known as the Vehicle Routing Problem. First of all, it is inherently combinatorial, and exact algorithms fail when the dimension of the problem (number of customers and orders) reaches a reasonable size. Secondly, the problem can be extended and made more complex in many ways, for instance, adding more than one depot, considering more than one vehicle type, accounting for stochastic customer demand (the exact requested quantity is known only at delivery time), considering time windows during which the customers must be served, taking into account vehicle accessibility restrictions (some customers cannot be served by some vehicles). Finally, the problem can become very different when we consider on-line distribution, that is, we accept delivery orders for lorries which are en route. There, geolocation of customers and vehicles, online data transfer among lorries and the base station, have an impact as great as the solution strategy.
2003
- Upper and lower bounds for the fixed spectrum frequency assignment problem
[Articolo su rivista]
Montemanni, R.
abstract
A survey of the results described in the author's PhD thesis (Montemanni 2001) is presented. The thesis, which was supervised by Prof. Derek H. Smith and Dr. Stuart M. Allen, has been defended in January 2002 at the University of Glamorgan (U.K.). The thesis proposes new heuristic algorithms, based on well-known meta-heuristic paradigms, and new lower bounding techniques, based on linear programming, for the fixed spectrum frequency assignment problem. © 2003 Springer-Verlag Berlin/Heidelberg.
2002
- An ANTS algorithm for the minimum span frequency assignment problem with multiple interference
[Articolo su rivista]
Montemanni, R; and Smith, Dh; and Allen, Sm
abstract
The frequency assignment problem is concerned with the assignment of discrete channels to the transmitters of a radio network Separation of the frequencies assigned to transmitters is necessary to avoid interference However unnecessary separation causes an excess requirement for sp ectrum the cost of which may b e very high
We present an ANTS
level of reception quality in a network The mo del takes multiple interference into consideration
given
2002
- An algorithm for the relative robust shortest path problem with interval data
[Working paper]
Montemanni, Roberto; Gambardella Luca, M
abstract
Many real transport and telecommunications problems can be rep-resented in mathematical terms as shortest path problems on weighteddigraphs, where a fixed cost is associated with each arc. Sometimes thelevel of abstraction induced by this model is too high, and consequentlymore complex representations of reality have to be considered.In this paper the interval data model, where an interval of costs isassociated with each arc of the graph, is adopted and the concept of relative robustness is used to drive optimization.An exact algorithm, which is able to manage large problems, is pre-sented. This algorithm can also be used as a heuristic method, being ableto find high quality solutions very quickly.Computational results, which highlight the high performance of theapproach we propose, are finally presented.
2002
- Time dependent vehicle routing problem with an ant colony system
[Articolo su rivista]
Donati Alberto, V; Gambardella Luca, M; Rizzoli Andrea, E; Casagrande, Norman; Montemanni, Roberto
abstract
The Time Dependent Vehicle Routing Problem (TDVRP) consists in optimally routing a fleet of vehicles of fixed capacity when travel times are time dependent, in the sense that the time employed to traverse each given arc, depends on the time of the day the travel starts from its originating node. The optimization method consists in finding solutions that minimize two hierarchical objectives: the number of tours and the total travel time.
Optimization of total travel time is a continuous optimization problem that in our approach is solved by discretizing the time space in a suitable number of subspaces. New time dependent local search procedures are also introduced, as well as conditions that guarantee that feasible moves are sought for in constant time.
This variant of the classic Vehicle Routing Problem is motivated by the fact that in urban contexts variable traffic conditions play an essential role and can not be ignored in order to perform a realistic optimization. In this paper it is shown that when dealing with time constraints, like hard delivery time windows for customers, the known solutions for the classic case become unfeasible and the degree of unfeasibility increases with the variability of traffic conditions, while if no hard time constraints are present, the classic solutions become suboptimal.
Finally an application of the model to a real case is presented. The model is integrated with a robust shortest path algorithm to compute time dependent paths between each customer pairs of the time dependent model.
2001
- A tabu search algorithm with a dynamic tabu list for the frequency assignment problem
[Working paper]
Montemanni, R; Smith, Dh
abstract
The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such a s a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimise interference and the spectrum required. In this paper we study the spectrum frequency assignment prob-lem, where the frequency spectrum available is given and the target is to minimise (a measure of) the interference in the network. In particular a tabu search algorithm with some non-standard features, together with implementation details, is described for this problem. Computational results connrm the quality of the algorithm we propose, in comparison with methods of other authors.
2001
- Lower Bounds for Fixed Spectrum Frequency Assignment
[Articolo su rivista]
Montemanni, R.; Smith, D. H.; Allen, S. M.
abstract
Determining lower bounds for the sum of weighted constraint violations in fixed spectrum frequency assignment problems is important in order to evaluate the performance of heuristic algorithms. It is well known that, when adopting a binary constraints model, clique and near-clique subproblems have a dominant role in the theory of lower bounds for minimum span problems. In this paper we highlight their importance for fixed spectrum problems. We present a method based on the linear relaxation of an integer programming formulation of the problem, reinforced with constraints derived from clique-like subproblems. The results obtained are encouraging both in terms of quality and in terms of computation time.
1999
- An approach to frequency assignment problem based on an ANTS heuristic
[Relazione in Atti di Convegno]
Maniezzo, V; Carbonaro, A; Montemanni, R
abstract
An algorithm based on the ANTS paradigm is proposed for a frequency assignment problem.