Browsing by Keyword "Traveling salesman problem"
Now showing 1 - 9 of 9
Results Per Page
Sort Options
Item Benchmark dataset for the Asymmetric and Clustered Vehicle Routing Problem with Simultaneous Pickup and Deliveries, Variable Costs and Forbidden Paths(2020-04) Osaba, Eneko; QuantumIn this paper, the benchmark dataset for the Asymmetric and Clustered Vehicle Routing Problem with Simultaneous Pickup and Deliveries, Variable Costs and Forbidden Paths is presented (AC-VRP-SPDVCFP). This problem is a specific multi-attribute variant of the well-known Vehicle Routing Problem, and it has been originally built for modelling and solving a real-world newspaper distribution problem with recycling policies. The whole benchmark is composed by 15 instances comprised by 50–100 nodes. For the design of this dataset, real geographical positions have been used, located in the province of Bizkaia, Spain. A deep description of the benchmark is provided in this paper, aiming at extending the details and experimentation given in the paper A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy (Osaba et al.) [1]. The dataset is publicly available for its use and modification.Item COEBA: A Coevolutionary Bat Algorithm for Discrete Evolutionary Multitasking: A coevolutionary bat algorithm for discrete evolutionary multitasking(Springer Nature, 2020) Osaba, Eneko; Del Ser, Javier; Yang, Xin-She; Iglesias, Andres; Galvez, Akemi; Krzhizhanovskaya, Valeria V.; Závodszky, Gábor; Lees, Michael H.; Sloot, Peter M.A.; Sloot, Peter M.A.; Sloot, Peter M.A.; Dongarra, Jack J.; Brissos, Sérgio; Teixeira, João; Quantum; IAMultitasking optimization is an emerging research field which has attracted lot of attention in the scientific community. The main purpose of this paradigm is how to solve multiple optimization problems or tasks simultaneously by conducting a single search process. The main catalyst for reaching this objective is to exploit possible synergies and complementarities among the tasks to be optimized, helping each other by virtue of the transfer of knowledge among them (thereby being referred to as Transfer Optimization). In this context, Evolutionary Multitasking addresses Transfer Optimization problems by resorting to concepts from Evolutionary Computation for simultaneous solving the tasks at hand. This work contributes to this trend by proposing a novel algorithmic scheme for dealing with multitasking environments. The proposed approach, coined as Coevolutionary Bat Algorithm, finds its inspiration in concepts from both co-evolutionary strategies and the metaheuristic Bat Algorithm. We compare the performance of our proposed method with that of its Multifactorial Evolutionary Algorithm counterpart over 15 different multitasking setups, composed by eight reference instances of the discrete Traveling Salesman Problem. The experimentation and results stemming therefrom support the main hypothesis of this study: the proposed Coevolutionary Bat Algorithm is a promising meta-heuristic for solving Evolutionary Multitasking scenarios.Item A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem(2018-10) Osaba, Eneko; Del Ser, Javier; Sadollah, Ali; Bilbao, Miren Nekane; Camacho, David; Quantum; IAThe water cycle algorithm (WCA) is a nature-inspired meta-heuristic recently contributed to the community in 2012, which finds its motivation in the natural surface runoff phase in water cycle process and on how streams and rivers flow into the sea. This method has been so far successfully applied to many engineering applications, spread over a wide variety of application fields. In this paper an enhanced discrete version of the WCA (coined as DWCA) is proposed for solving the Symmetric and Asymmetric Traveling Salesman Problem. Aimed at proving that the developed approach is a promising approximation method for solving this family of optimization problems, the designed solver has been tested over 33 problem datasets, comparing the obtained outcomes with the ones got by six different algorithmic counterparts from the related literature: genetic algorithm, island-based genetic algorithm, evolutionary simulated annealing, bat algorithm, firefly algorithm and imperialist competitive algorithm. Furthermore, the statistical significance of the performance gaps found in this benchmark is validated based on the results from non-parametric tests, not only in terms of optimality but also in regards to convergence speed. We conclude that the proposed DWCA approach outperforms – with statistical significance – any other optimization technique in the benchmark in terms of both computation metrics.Item DMFEA-II: An adaptive multifactorial evolutionary algorithm for permutation-based discrete optimization problems(Association for Computing Machinery, Inc, 2020-07-08) Osaba, Eneko; Martinez, Aritz D.; Galvez, Akemi; Iglesias, Andres; Ser, Javier Del; Quantum; IAThe emerging research paradigm coined as multitasking optimization aims to solve multiple optimization tasks concurrently by means of a single search process. For this purpose, the exploitation of complementarities among the tasks to be solved is crucial, which is often achieved via the transfer of genetic material, thereby forging the Transfer Optimization field. In this context, Evolutionary Multitasking addresses this paradigm by resorting to concepts from Evolutionary Computation. Within this specific branch, approaches such as the Multifactorial Evolutionary Algorithm (MFEA) has lately gained a notable momentum when tackling multiple optimization tasks. This work contributes to this trend by proposing the first adaptation of the recently introduced Multifactorial Evolutionary Algorithm II (MFEA-II) to permutation-based discrete optimization environments. For modeling this adaptation, some concepts cannot be directly applied to discrete search spaces, such as parent-centric interactions. In this paper we entirely reformulate such concepts, making them suited to deal with permutation-based search spaces without loosing the inherent benefits of MFEA-II. The performance of the proposed solver has been assessed over 5 different multitasking setups, composed by 8 datasets of the well-known Traveling Salesman (TSP) and Capacitated Vehicle Routing Problems (CVRP). The obtained results and their comparison to those by the discrete version of the MFEA confirm the good performance of the developed dMFEA-II, and concur with the insights drawn in previous studies for continuous optimization.Item Hybrid Quantum Computing - Tabu Search Algorithm for Partitioning Problems: Preliminary Study on the Traveling Salesman Problem(Institute of Electrical and Electronics Engineers Inc., 2021) Osaba, Eneko; Villar-Rodriguez, Esther; Oregi, Izaskun; Moreno-Fernandez-de-Leceta, Aitor; QuantumQuantum Computing is considered as the next frontier in computing, and it is attracting a lot of attention from the current scientific community. This kind of computation provides to researchers with a revolutionary paradigm for addressing complex optimization problems, offering a significant speed advantage and an efficient search ability. Anyway, Quantum Computing is still in an incipient stage of development. For this reason, present architectures show certain limitations, which have motivated the carrying out of this paper. In this paper, we introduce a novel solving scheme coined as hybrid Quantum Computing - Tabu Search Algorithm. Main pillars of operation of the proposed method are a greater control over the access to quantum resources, and a considerable reduction of nonprofitable accesses. To assess the quality of our method, we have used 7 different Traveling Salesman Problem instances as benchmarking set. The obtained outcomes support the preliminary conclusion that our algorithm is an approach which offers promising results for solving partitioning problems while it drastically reduces the access to quantum computing resources. We also contribute to the field of Transfer Optimization by developing an evolutionary multiform multitasking algorithm as initialization method.Item On efficiently solving the vehicle routing problem with time windows using the bat algorithm with random reinsertion operators(Springer Verlag, 2018) Osaba, Eneko; Carballedo, Roberto; Yang, Xin She; Fister, Iztok; Lopez-Garcia, Pedro; Del Ser, Javier; IAAn evolutionary and discrete variant of the Bat Algorithm (EDBA) is proposed for solving the Vehicle Routing Problem with Time Windows, or VRPTW. The EDBA developed not only presents an improved movement strategy, but it also combines with diverse heuristic operators to deal with this type of complex problems. One of the main new concepts is to unify the search process and the minimization of the routes and total distance in the same operators. This hybridization is achieved by using selective node extractions and subsequent reinsertions. In addition, the new approach analyzes all the routes that compose a solution with the intention of enhancing the diversification ability of the search process. In this study, several variants of the EDBA are shown and tested in order to measure the quality of both metaheuristic algorithms and their operators. The benchmark experiments have been carried out by using the 56 instances that compose the 100 customers Solomon’s benchmark. Two statistical tests have also been carried out so as to analyze the results and draw proper conclusions.Item Solving the open-path asymmetric green traveling salesman problem in a realistic urban environment(Springer Verlag, 2018) Osaba, Eneko; Del Ser, Javier; Iglesias, Andres; Bilbao, Miren Nekane; Fister, Iztok; Fister, Iztok; Galvez, Akemi; Quantum; IAIn this paper, a driving route planning system for multi-point routes is designed and developed. The routing problem has modeled as an Open-Path and Asymmetric Green Traveling Salesman Problem (OAG-TSP). The main objective of the proposed OAG-TSP is to find a route between a fixed origin and destination, visiting a group of intermediate points exactly once, minimizing the CO2 emitted by the car and the total distance traveled. Thus, the developed transportation problem is a complex and multi-attribute variant of the well-known TSP. For its efficient solving, three classic meta-heuristics have been used: Simulated Annealing, Tabu Search and Variable Neighborhood Search. These approaches have been chosen for its easy adaptation and rapid execution times, something appreciated in this kind of real-world systems. The system developed has been built in a realistic simulation environment, using the open source framework Open Trip Planner. Additionally, three heterogeneous scenarios have been studied in three different cities of the Basque Country (Spain): Bilbao, Gazteiz and Donostia. Obtained results conclude that the most promising technique for solving this problem is the Simulated Annealing. The statistical significance of these findings is confirmed by the results of a Friedman’s non-parametric test.Item A Systematic Literature Review of Quantum Computing for Routing Problems(2022-05) Osaba, Eneko; Villar-Rodriguez, Esther; Oregi, Izaskun; Tecnalia Research & Innovation; QuantumQuantum Computing is drawing a significant attention from the current scientific community. The potential advantages offered by this revolutionary paradigm has led to an upsurge of scientific production in different fields such as economics, industry, or logistics. The main purpose of this paper is to collect, organize and systematically examine the literature published so far on the application of Quantum Computing to routing problems. To do this, we embrace the well-established procedure named as Systematic Literature Review. Specifically, we provide a unified, self-contained, and end-to-end review of 18 years of research (from 2004 to 2021) in the intersection of Quantum Computing and routing problems through the analysis of 53 different papers. Several interesting conclusions have been drawn from this analysis, which has been formulated to give a comprehensive summary of the current state of the art by providing answers related to the most recurrent type of study (practical or theoretical), preferred solving approaches (dedicated or hybrid), detected open challenges or most used Quantum Computing device, among others.Item Traffic data analysis and route planning(Elsevier, 2023-01-01) Osaba, Eneko; Laña, Ibai; Del Ser, Javier; Quantum; IAThe introduction of autonomous vehicles in the transportation ecosystem will lead to the emergence of new opportunities and challenges. Almost all aspects involved in transportation will be affected once autonomous driving is fully established in our daily life. This fact will raise the need of adaptation into many mechanisms to this incipient paradigm. In this study, we focus on two specific off-board aspects which also should be accommodated to this new environment: route planning and traffic prediction. Thus, this study is devoted to providing an overview on these two research fields, making a special emphasis on recent works related to autonomous driving. An equally valuable is the ending of our study, in which we share our envisioned status of this area. To do that, we identify some important challenges and upcoming opportunities which should stimulate research efforts in the next years.