1,721,325 research outputs found
Correction to: Metaheuristics for combinatorial optimization (Metaheuristics for combinatorial optimization, (2021) AISC 1332, 10.1007/978-3-030-68520-1)
No full textCorrection to: S. Greco et al. (Eds.): Metaheuristics for Combinatorial Optimization, AISC 1332, https://doi.org/10.1007/978-3-030-68520-1 The book was inadvertently published with the incorrect volume number (1336) and this has been corrected now (1332)
Exact solution of the two-dimensional finite bin packing problem
No full textGiven a set of rectangular pieces to be cut from an unlimited number of standardized stock pieces (bins), the Two-Dimensional Finite Bin Packing Problem is to determine the minimum number of stock pieces that provide all the pieces. The problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. We analyze a well-known lower bound and determine its worst-case performance. We propose new lower bounds which are used within a branch-and-bound algorithm for the exact solution of the problem. Extensive computational testing on problem instances from the literature involving up to 120 pieces shows the effectiveness of the proposed approach
A Branch-and-Cut Algorithm for the Resource-Constrained Minimum-Weight Arborescence Problem
No full textIn 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
Routing one million customers in a handful of minutes
Full text linkThis paper proposes a new dataset of Capacitated Vehicle Routing Problem instances, up to two orders of magnitude larger than those in the currently used benchmarks. Although these sizes might not have an immediate application to real -world logistic scenarios, we believe they could foster fresh new research efforts on the design of effective and efficient algorithmic components for routing problems. We provide computational results for such instances by running FILO2, an adaptation of the FILO algorithm proposed in Accorsi and Vigo (2021), designed to handle extremely large-scale CVRP instances. Solutions for such instances are obtained using a standard personal computer in a considerably short computing time, thus showing the effectiveness of the acceleration and pruning techniques already proposed in FILO. Finally, results of FILO2 on well-known literature instances show that the newly introduced changes improve the overall scalability of the approach with respect to the previous FILO design
An exact algorithm for the vehicle routing problem with backhauls
No full textThe Vehicle Routing Problem with Backhauls is an extension of the capacitated Vehicle Routing Problem where the customers' set is partitioned into two subsets. The first is the set of Linehaul, or Delivery, customers, while the second is the set of Backhaul, or Pickup, customers. The problem is known to be NP-hard in the strong sense and finds many practical applications in distribution planning. In this paper we consider, in a unified framework, both the symmetric and the asymmetric versions of the vehicle routing problem with backhauls, for which we present a new integer linear programming model and a Lagrangian lower bound which is strengthened in a cutting plane fashion. The Lagrangian lower bound is then combined, according to the additive approach, with a lower bound obtained by dropping the capacity constraints, thus obtaining an effective overall bounding procedure. A branch-and-bound algorithm, reduction procedures and dominance criteria are also described. Computational tests on symmetric and asymmetric instances from the literature, involving up to 100 customers, are given, showing the effectiveness of the proposed approach
Models, relaxations and exact approaches for the capacitated vehicle routing problem
No full textIn this paper we review the exact algorithms based on the branch and bound approach proposed in the last years for the solution of the basic version of the vehicle routing problem (VRP), where only the vehicle capacity constraints are considered. These algorithms have considerably increased the size of VRPs that can be solved with respect to earlier approaches. Moreover, at least for the case in which the cost matrix is asymmetric, branch and bound algorithms still represent the state-of-the-art with respect to the exact solution. Computational results comparing the performance of different relaxations and algorithms on a set of benchmark instances are presented. We conclude by examining possible future directions of research in this field. © 2002 Elsevier Science B.V
The granular tabu search and its application to the vehicle-routing problem
No full textWe 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
A new hybrid distribution paradigm: Integrating drones in medicines delivery
Full text linkThis 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
Exact solutions for the carrier-vehicle traveling salesman problem
No full textCarrier-vehicle systems generally consist of a slow carrier (e.g., a ship) with a long operational range and a faster vehicle (e.g., an aircraft) with a limited operational range. The carrier has the role of transporting the faster vehicle and of deploying, recovering, and servicing it. The goal of the carrier-vehicle traveling salesman problem (CVTSP) is to permit the faster vehicle to visit a given collection of targets in the shortest time while using the carrier as a base for possible multiple trips. As a consequence, the carrier and vehicle should be synchronized. The visiting sequence of the targets is not given a priori. We present a mixed-integer, second-order conic programming (MISOCP) formulation for the CVTSP. Computational results are shown for the resolution of the model with commercial solvers. The MISOCP structure and the relationship to the traveling salesman problem are exploited for developing a ranking-based solution algorithm that outperforms the commercial solvers
Heuristic algorithms for the three-dimensional bin packing problem
No full textThe Three-Dimensional Bin Packing Problem (3BP) consists of allocating, without overlapping, a given set of three-dimensional rectangular items to the minimum number of three-dimensional identical finite bins. The problem is NP-hard in the strong sense, and finds many industrial applications. We introduce a Tabu Search framework exploiting a new constructive heuristic for the evaluation of the neighborhood. Extensive computational results on standard benchmark instances show the effectiveness of the approach with respect to exact and heuristic algorithms from the literature. © 2002 Elsevier Science B.V. All rights reserved
- …
