This paper analyses a new hybrid paradigm resulting from the integration of unmanned aerial vehicles (UAV), commonly referred to as drones, in logistics and distribution processes. This work is motivated by a real application, where the company Connect Robotics, the first drone delivery provider in Portugal, made a partnership with a pharmacy located at a rural region to start implementing the delivery of medicines by drone. The pharmacy receives orders throughout the day and has to deliver in the same day with tight lead-times. The resulting problem is modelled as a Dynamic Parallel Drone Scheduling Vehicle Routing Problem with Lead-Time. A solution method is devised to solve it, thus helping the pharmacist to plan the car and drone delivery routes during the day. The results obtained on real instances revealed that the solution method is effective when compared to the optimal solutions of the static version of the problem, since the dynamic solution only differs, on average, about 7% from the static one. Moreover, some managerial insights about the impact of adding drones to the distribution operation are discussed, namely the economic and environmental impacts with cost savings up to 41% and reduction of monthly CO2 emissions of 310 kg, the use of spare batteries which increase the benefit from 16% to 41%, and same-day versus next-day delivery.

Decomposition techniques are an important component of modern heuristics for large instances of vehicle routing problems. The current literature lacks a characterization of decomposition strategies and a systematic investigation of their impact when integrated into state-of-the-art heuristics. This paper fills this gap: We discuss the main characteristics of decomposition techniques in vehicle routing heuristics, highlight their strengths and weaknesses, and derive a set of desirable properties. Through an extensive numerical campaign, we investigate the impact of decompositions within two algorithms for the capacitated vehicle routing problem: the Adaptive Large Neighborhood Search of Pisinger and Ropke (2007 ) and the Hybrid Genetic Search of Vidal et al. (2012 ). We evaluate the quality of popular decomposition techniques from the literature and propose new strategies. We find that route-based decomposition methods, which define subproblems by means of the customers contained in selected subsets of the routes of a given solution, generally appear superior to path-based methods, which merge groups of customers to obtain smaller subproblems. The newly proposed decomposition barycenter clustering achieves the overall best performance and leads to significant gains compared with using the algorithms without decomposition. History: Erwin Pesch, Area Editor for Heuristic Search and Approximation Algorithms. Funding: This work was supported by the U.S. Air Force [Grant FA9550-17-1-0234], the Ministerio de Ciencia e Innovación (Juan de la Cierva Formación), H2020 Marie Skłodowska-Curie Actions [Grant 945380], the Ministero dell’Università e della Ricerca [Grant 2015JJLC3E_002], the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grant 308528/2018-2], and the Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro [Grant E-26/202.790/2019]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.1288 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0048 ) at ( http://dx.doi.org/10.5281/zenodo.7613129 ).

This paper is motivated by the concept that the successful, effective, and sustainable implementation of the smart city paradigm requires a close cooperation among researchers with different, complementary interests and, in most cases, a multidisciplinary approach. It first briefly discusses how such a multidisciplinary methodology, transversal to various disciplines such as architecture, computer science, civil engineering, electrical, electronic and telecommunication engineering, social science and behavioral science, etc., can be successfully employed for the development of suitable modeling tools and real solutions of such sociotechnical systems. Then, the paper presents some pilot projects accomplished by the authors within the framework of some major European Union (EU) and national research programs, also involving the Bologna municipality and some of the key players of the smart city industry. Each project, characterized by different and complementary approaches/modeling tools, is illustrated along with the relevant contextualization and the advancements with respect to the state of the art.

This paper proposes a novel methodology for the spatial downscaling ofreal-world deploymentsof wireless networks, running protocols, and/or applications for the Internet of Things (IoT). These networks are often deployed in environments not easily accessible and highly unpredictable, where doing experiments is very expensive and time consuming. The latter calls for the need to develop downscaled testbeds, deployed in controlled environments, where tests can be conducted under predictable conditions. This paper presents a methodology to realize the downscaling of a real deployment on an experimental platform, calledcontrollable testbedthat has a much larger number of nodes with respect to the real one. The downscaling procedure proposed is based on the identification of the most appropriate subset of nodes of the controllable testbed, to be used to reproduce the channel gains between each node pair in the real world. The latter, in fact, results in obtaining the same network topologies, bringing to the same performance on average, when the same protocol stack and software are run. After the description of the procedure, an example of its implementation is provided. Comparison of results, in terms of packet loss rate (PLR), network throughput, and topologies achieved on the downscaled testbed and on the real-world deployment, is given; results show a very good fit and demonstrate the efficacy of the proposed methodology.

Abstract In the well‐known vehicle routing problem (VRP), a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. An important variant of the VRP arises when a mixed fleet of vehicles, characterized by different capacities and costs, is available for distribution activities. The problem is known as fleet size and mix VRP with fixed costs FSMF and has several practical applications. In this article, we present a new mixed integer programming formulation for FSMF based on a two‐commodity network flow approach. New valid inequalities are proposed to strengthen the linear programming relaxation of the mathematical formulation. The effectiveness of the proposed cuts is extensively tested on benchmark instances. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

We consider the problem of orthogonally packing a given set of rectangular-shaped boxes into the minimum number of three-dimensional rectangular bins. The problem is NP-hard in the strong sense and extremely difficult to solve in practice. We characterize relevant subclasses of packing and present an algorithm which is able to solve moderately large instances to optimality. Extensive computational experiments compare the algorithm for the three-dimensional bin packing when solving general orthogonal packings and when restricted to robot packings.

We consider the problem of orthogonally packing a given set of rectangular items into a given strip, by minimizing the overall height of the packing. The problem is NP-hard in the strong sense, and finds several applications in cutting and packing. We propose a new relaxation that produces good lower bounds and gives information to obtain effective heuristic algorithms. These results are used in a branch-and-bound algorithm, which was able to solve test instances from the literature involving up to 200 items.

We describe a new variant, called granular tabu search, of the well-known tabu-search approach. The method uses an effective intensification/diversification tool that can be successfully applied to a wide class of graph-theoretic and combinatorial-optimization problems. Granular tabu search is based on the use of drastically restricted neighborhoods, not containing the moves that involve only elements that are not likely to belong to good feasible solutions. These restricted neighborhoods are called granular, and may be seen as an efficient implementation of candidate-list strategies proposed for tabu-search algorithms. Results of computational testing of the proposed approach on the well-known symmetric capacitated and distance-constrained vehicle-routing problem are discussed, showing that the approach is able to determine very good solutions within short computing times.

Two-dimensional bin packing problems consist of allocating, without overlapping, a given set of small rectangles (items) to a minimum number of large identical rectangles (bins), with the edges of the items parallel to those of the bins. According to the specific application, the items may either have a fixed orientation or they can be rotated by 90°. In addition, it may or not be imposed that the items are obtained through a sequence of edge-to-edge cuts parallel to the edges of the bin. In this article, we consider the class of problems arising from all combinations of the above requirements. We introduce a new heuristic algorithm for each problem in the class, and a unified tabu search approach that is adapted to a specific problem by simply changing the heuristic used to explore the neighborhood. The average performance of the single heuristics and of the tabu search are evaluated through extensive computational experiments.

In this paper, we investigate the possibility of integrating Artificial Intelligence (AI) and Operations Research (OR) techniques for solving the Crew Rostering Problem (CRP). CRP calls for the optimal sequencing of a given set of duties into rosters satisfying a set of constraints. The optimality criterion requires the minimization of the number of crews needed to cover the duties. This kind of problem has been traditionally solved by OR techniques. In recent years, a new programming paradigm based on Logic Programming, named Constraint Logic Programming (CLP), has been successfully used for solving hard combinatorial optimization problems. CLP maintains all the advantages of logic programming such as declarativeness, non-determinism and an incremental style of programming, while overcoming its limitations, mainly due to the inefficiency in exploring the search space. CLP achieves good results on hard combinatorial optimization problems which, however, are not comparable with those achieved by OR approaches. Therefore, we integrate both techniques in order to design an effective heuristic algorithm for CRP which fully exploits the advantages of the two methodologies: on the one hand, we maintain the declarativeness of CLP, its ease of representing knowledge and its rapid prototyping; on the other hand, we inherit from OR some efficient procedures based on a mathematical approach to the problem. Finally, we compare the results we achieved by means of the integration with those obtained by a pure OR approach, showing that AI and OR techniques for hard combinatorial optimization problems can be effectively integrated. © 1998 John Wiley & Sons, Ltd.

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.g., in the design of distribution networks in which finite resources are available at each node. Some main classes of cuts are described, and the corresponding separation algorithms are presented. Also, we outline a procedure to extend to RMWA some known classes of valid inequalities for the asymmetric traveling salesman problem. New heuristic procedures to compute near-optimal feasible solutions are proposed, which proved to be very effective to reduce the overall computing time spent by the branch-and-cut algorithm. Computational experience on three classes of test problems involving up to 500 vertices is reported, showing that the proposed approach outperforms other published methods. © 1997 John Wiley & Sons, Inc.