In recent years, researchers have oriented their studies towards new technologies based on quantum physics that should resolve complex problems currently considered to be intractable.This new research area is called Quantum Computing.What makes Quantum Computing so attractive is the particular way with which quantum technology operates and the great potential it can offer to solve real-world problems.This work focuses on solving assignment-like combinatorial optimization problems by exploiting this novel computational approach.A case-study, denoted as the Seating Arrangement Optimization problem, is considered.It is modeled through the Quadratic Unconstrained Binary Optimization paradigm and solved through two tools made available by the D-Wave Systems company, QBSolv, and a quantum-classical hybrid system.The obtained experimental results are compared in terms of solution quality and computational efficiency.

Abstract The transshipment location–allocation problem consists of locating transshipment facilities (e.g., intermodal hubs) of a transportation network and allocating freight flows through them, from several origins to several destinations, to satisfy demand and supply constraints. The objective is to maximize the total net transportation utility given by the total shipping utility minus the total cost to locate the facilities. Moreover, flow synchronization at the facilities must also be ensured. Unfortunately, the flow synchronization depends on a broad set of unknown events, which could cause both unexpected reductions of the facility capacity and uncertain utility of handling operations. In this paper, we first want to evaluate how uncertainty on facility capacity and handling operations utility affects the transshipment location–allocation problem in terms of complexity, net gain, and optimal solutions. Moreover, we extend the problem from a single to a multi‐period setting to have a wider view of future scenarios realizations and consequently synchronize the flows by using different facilities on different periods. We propose a two‐stage stochastic programming formulation with recourse and analyze, over a ground set of instances, some well‐known economic indicators to derive managerial insights on the importance of addressing uncertainty for the problem. Finally, given the computational burden of solving the deterministic equivalent problem, we propose several heuristics based on progressive hedging and test their performance.

Online scheduling has been an attractive field of research for over three decades.Some recent developments suggest that Reinforcement Learning (RL) techniques have the potential to deal with online scheduling issues effectively.Driven by an industrial application, in this paper we apply four of the most important RL techniques, namely Q-learning, Sarsa, Watkins's Q(λ), and Sarsa(λ), to the online single-machine scheduling problem.Our main goal is to provide insights on how such techniques perform.The numerical results show that Watkins's Q(λ) performs best in minimizing the total tardiness of the scheduling process.

Electric vehicles are accelerating the world's transition to sustainable energy.Nevertheless, the lack of a proper charging station infrastructure in many real implementations still represents an obstacle for the spread of such a technology.In this paper, we present a real case application of optimization techniques in order to solve the location problem of electric charging stations in the district of Biella, Italy.The plan is composed by several progressive installations and decision makers pursue several objectives that might be in contrast.For this reason, we present an innovative framework based on the comparison of several ad-hoc Key Performance Indicators for evaluating many different aspects of a location solution.

Due to the diffusion of Internet of Things (IoT), many devices such as water meters, smart dumpsters, and many other objects have the capacity to record data. Gathering these data from the devices is a problem that could be solved in three ways: by building a huge network infrastructure, by using regular workforce or by using opportunistic IoT networks, i.e. by using as mobile hotspots the devices of selected users. The latter is cheaper than the others, requiring only the payment of a reward to the users. In this paper, we introduce a Multi Period Assignment problem, i.e. a problem for planning the operations of Opportunistic IoT networks. The problem minimizes the sum of user rewards, while gathering data from all devices. An effective heuristic method able to deal with realistic-sized instances is presented. The heuristic is able to find, by using a reasonable amount of time, the optimum for 124 out of 128 instances and reach gaps smaller than 0.1% for the remaining 4 instances.

One of the main issues in addressing three-dimensional packing problems is finding an efficient and accurate definition of the points at which to place the items inside the bins, because the performance of exact and heuristic solution methods is actually strongly influenced by the choice of a placement rule. We introduce the extreme point concept and present a new extreme point-based rule for packing items inside a three-dimensional container. The extreme point rule is independent from the particular packing problem addressed and can handle additional constraints, such as fixing the position of the items. The new extreme point rule is also used to derive new constructive heuristics for the three-dimensional bin-packing problem. Extensive computational results show the effectiveness of the new heuristics compared to state-of-the-art results. Moreover, the same heuristics, when applied to the two-dimensional bin-packing problem, outperform those specifically designed for the problem.

Abstract The Internet Protocol Network Design Problem with Reliability and Routing Constraints (IPRR) can be shortly stated as follows. A telecommunication network is given in terms of a set of nodes and a set of traffic demands; we want to define the minimum cost capacity reservation such that all the traffic is routed even under fault scenarios. Capacity is provided by reserving some already installed devices of a given capacity between pairs of nodes and traffic must be loaded on the network according to the OSPF‐ECM (Open Shortest Path First‐Equal Commodity Multipath) protocol, with additional constraints on the maximum number of hops. The problem is 𝒩𝒫‐Hard and literature proposes neighborhood search heuristics that do not take the reliability and max‐hop requirements into account, or assume a simplified OSPF routing. The design and the implementation of the components of any neighborhood search algorithms are strongly conditioned by the reliability and routing constraints, which imply a huge amount of hop‐constrained shortest paths to be taken into account. This work shows how the components of these heuristics can be implemented, with particular emphasis to the setting up of an efficient neighborhood evaluation procedure, the discussion of its incremental version, and the introduction of effective reduced‐size neighborhoods. Computational experiments on instances derived from real networks are also presented, and they show the proposed components make the neighborhood search a viable approach for IPRR. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 65–79 2007

Abstract This article deals with a Hub Location Problem arising in Telecommunication Network Design. The considered network presents two different kinds of nodes: access nodes, that represent source and destination of traffic demands but cannot be directly connected, and transit nodes, that have no own traffic demand but collect traffic from access nodes and route it through the network. Transit nodes are supposed to be fully connected. Given a set of access nodes and a set of potential locations for the transit nodes, the problem is to decide number and positions of the transit nodes to guarantee that all access nodes are allocated to a transit node, satisfying capacity constraints. The goal is to minimize the total cost of the network, which is the sum of connection costs and nodes fixed costs. The problem is a Hub Location Problem, which is known to be NP‐hard. A local search approach is proposed, and different metaheuristic algorithms, such as tabu search, iterated local search and random multistart, have been developed, based on such local search. [A preliminary procedure has been developed in a research project joint with Telecom Italia (Turin Research & Innovation Laboratories) and a patent application has been filed to cover this issue.] © 2004 Wiley Periodicals, Inc. NETWOEKS, Vol. 44(2), 94–105 2004

Abstract The IP (Internet Protocol) Network Design Problem can be shortly stated as follows. Given a set of nodes and a set of traffic demands, we want to determine the minimum cost capacity installation such that all the traffic is routed. Capacity is provided by means of links of a given capacity and traffic must be loaded on the network according to the OSPF‐ECM (Open Shortest Path First—Equal Commodity Multiflow) protocol, with additional constraints on the maximum number of hops. The problem is strongly NP‐Hard, and the literature proposes local search‐based heuristics that do not take into account max‐hop constraints, or assume a simplified OSPF routing. The core in a local search approach is the network loading algorithm for the evaluation of the neighbor solutions costs. It presents critical aspects concerning both computational efficiency and memory requirements. Starting from a tabu search prototype, we show how these aspects deeply impact on the design of a local search procedure, even at the logical level. We present several properties of the related network loading problem, that allow to overcome the critical issues and lead to an efficient solution evaluation. © 2004 Wiley Periodicals, Inc. NETWORKS, VoL. 44(2), 73–83 2004

Introduces a production scheduling problem encountered in COMPAL S.A., a factory located in Lisbon (Portugal) which produces perishable goods for the food market. From the factory specifications the authors show how to derive a scheduling model and a two-step heuristic procedure for its solution.>

The authors propose augmented Lagrangian-based decomposition techniques for solving complex planning and control problems in flexible manufacturing systems. It is shown that the resulting decomposition of the mathematical problem lends itself to control systems with a topological cellular structure, and can be treated very naturally with an object-oriented programming approach. The mathematical formulation of the problem is presented. Its application to a specific example in which all the main features of the method are fully described is presented. Some computational results are presented.>