Dataset for the electric capacitated traveling salesman problem.

Regarding climate change and energy resource problems, cargo movement in the urban environment is essential to shift to a more sustainable mode. As cities seek to slash transport-related emissions and tackle traffic congestion, the cargo bike is showing itself to be an attractive and versatile last-mile delivery alternative. To this end, this article presents a series of datasets for the Electric Capacitated Travelling Salesman Problem (EC-TSP). This problem has been built for modeling and solving the e-cargo bike parcel distribution problem in urban environments. For the design of these datasets, real geographical data have been used that are in the city centers of Athens, Thessaloniki, Patra, and Larisa in Greece. These datasets have been used for the assessment of e-cargo bikes versus typical delivery vans in terms of operational efficiency and CO2e emissions. The entire benchmark is composed of 9 instances comprised of 14-29 nodes each. The datasets are publicly available for use and modification.

The Economy of Motion for Laparoscopic Ball Clamping Surgery: A Feedback Educational Tool.

The Ball Clamping module of the Laparoscopic Surgery Training Box involves the transfer of beads across the training board using laparoscopic tools. Fundamentals of Laparoscopic Surgery (FLS) requires practitioners to move their hands at as short a distance as possible to perform the functions in the shortest amount of time. This study introduces a feedback tool that presents to the student, after attempting their exam, the right direction (step by step) of obtaining the optimal pathway for minimizing distance traveled in the Ball Clamping Module of the Laparoscopic Surgery Training Box. The shortest distance tour for the ball clamping task is determined using the Traveling Salesman Model (TSM). A sensitivity analysis is conducted to assess the model's applicability to different types and settings of trainer boxes.•Find the best sequence of points resulting in the shortest distance tour for the ball clamping task.•The effects of adding or removing columns from the box cannot be intuitively predicted.

A new hybrid Artificial Intelligence (AI) approach for hydro energy sites selection and integration.

The increase of energy demand in this era leads exploration of new renewable energy sites. Renewable energy offers multiple benefits; hence it is suitable to be harnessed to meet power needs. In Sarawak, exploitation of hydro energy is a very feasible potential due to the abundant river flows and high rainfall volume. Thus, in this paper, 155 potential Hydro Energy Sites (HES) are identified and divided into six districts using a raw and unprocessed data provided by Sarawak Energy Berhad (SEB). Since there are no similar researches previously done for identification and integration of hydro energy sources, in this paper, two stage complex data management was built using 155 HES locations in Sarawak. New spatial mapping technique were used for the first stage. From the new spatial mapping technique, the mapped data were categorized into groups, analysed and created new accurate mapping locations on the Sarawak map in terms of the districts using GIS Spatial tools. Their exact geographical locations were identified, and their coordinate systems have been retrieved as complete final data with geo-referencing technique in QGIS with ID numbers. Moreover, the power capacity of each location of all the 155 HES was quantified. By employing this data, the identified locations have been integrated into the already created 155 HES sites. For the second stage, a new two-part AI hybrid approach has been proposed and applied to improve optimal transmission line routing for each district to locate transmission line paths. The first part of hybrid AI implemented in this paper was TSP-GA and second part implemented in this paper was based on improved fuzzy logic with TSP-GA together. To ensure the optimal results are reliably achieved, both first part of TSP-GA and second part of improved fuzzy TSP-GA are utilized to generate the transmission line routing. These two approaches are required to obtain the minimal values of total distance and total elevation difference of each HES. Based on the benchmarking results, fuzzy TSP-GA successfully improved 12.99% for Song district, 7.52% for Kapit district, 3.71% for Belaga district, 1.54% for Marudi district, 18.01% for Limbang district, 11.00% for Lawas district when comparing against the ordinary TSP-GA approach.

Algorithm for DNA sequence assembly by quantum annealing.

BACKGROUND: The assembly task is an indispensable step in sequencing genomes of new organisms and studying structural genomic changes. In recent years, the dynamic development of next-generation sequencing (NGS) methods raises hopes for making whole-genome sequencing a fast and reliable tool used, for example, in medical diagnostics. However, this is hampered by the slowness and computational requirements of the current processing algorithms, which raises the need to develop more efficient algorithms. One possible approach, still little explored, is the use of quantum computing. RESULTS: We present a proof of concept of de novo assembly algorithm, using the Genomic Signal Processing approach, detecting overlaps between DNA reads by calculating the Pearson correlation coefficient and formulating the assembly problem as an optimization task (Traveling Salesman Problem). Computations performed on a classic computer were compared with the results achieved by a hybrid method combining CPU and QPU calculations. For this purpose quantum annealer by D-Wave was used. The experiments were performed with artificially generated data and DNA reads coming from a simulator, with actual organism genomes used as input sequences. To our knowledge, this work is one of the few where actual sequences of organisms were used to study the de novo assembly task on quantum annealer. CONCLUSIONS: Proof of concept carried out by us showed that the use of quantum annealer (QA) for the de novo assembly task might be a promising alternative to the computations performed in the classical model. The current computing power of the available devices requires a hybrid approach (combining CPU and QPU computations). The next step may be developing a hybrid algorithm strictly dedicated to the de novo assembly task, using its specificity (e.g. the sparsity and bounded degree of the overlap-layout-consensus graph).

Optimizing leaf sweeping and collection in the Argentine city of Trenque Lauquen.

A solution strategy based on integer linear programming models has been developed for leaf sweeping operations in the Argentine city of Trenque Lauquen. The aim is to achieve efficiency in the assignment of sweepers to city blocks, the identification of leaf bag deposit points and the routes to be followed by collection trucks for leaf bag pickup. Previous to this strategy, sweeper assignments were improvised and inefficient, with blocks often left unswept. Furthermore, no method was available for accurately determining the number of sweepers needed to ensure either full coverage of all city zones within the working day or a balanced work load distribution across all sweepers. Application of the solution strategy by the city has resulted in efficient definitions of sweeper requirements while optimizing sweeper assignments such that all blocks are covered. Once the strategy is fully implemented, the number of bag deposit points under the manual definitions should be reduced by roughly one-half and the total travel distance of the truck routes, modelled as an asymmetric travelling salesman problem, should be cut by 10-15% with the consequent savings in time, vehicle use and fuel consumption.

Feature-Based Diversity Optimization for Problem Instance Classification.

Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Travelling Salesperson Problem (TSP). In this article, we present a general framework that is able to construct a diverse set of instances which are hard or easy for a given search heuristic. Such a diverse set is obtained by using an evolutionary algorithm for constructing hard or easy instances which are diverse with respect to different features of the underlying problem. Examining the constructed instance sets, we show that many combinations of two or three features give a good classification of the TSP instances in terms of whether they are hard to be solved by 2-OPT.

Application of Improved Particle Swarm Optimization for Navigation of Unmanned Surface Vehicles.

Multi-sensor fusion for unmanned surface vehicles (USVs) is an important issue for autonomous navigation of USVs. In this paper, an improved particle swarm optimization (PSO) is proposed for real-time autonomous navigation of a USV in real maritime environment. To overcome the conventional PSO's inherent shortcomings, such as easy occurrence of premature convergence and human experience-determined parameters, and to enhance the precision and algorithm robustness of the solution, this work proposes three optimization strategies: linearly descending inertia weight, adaptively controlled acceleration coefficients, and random grouping inversion. Their respective or combinational effects on the effectiveness of path planning are investigated by Monte Carlo simulations for five TSPLIB instances and application tests for the navigation of a self-developed unmanned surface vehicle on the basis of multi-sensor data. Comparative results show that the adaptively controlled acceleration coefficients play a substantial role in reducing the path length and the linearly descending inertia weight help improve the algorithm robustness. Meanwhile, the random grouping inversion optimizes the capacity of local search and maintains the population diversity by stochastically dividing the single swarm into several subgroups. Moreover, the PSO combined with all three strategies shows the best performance with the shortest trajectory and the superior robustness, although retaining solution precision and avoiding being trapped in local optima require more time consumption. The experimental results of our USV demonstrate the effectiveness and efficiency of the proposed method for real-time navigation based on multi-sensor fusion.

Automatic Configuration of Multi-Objective Local Search Algorithms for Permutation Problems.

Automatic algorithm configuration (AAC) is becoming a key ingredient in the design of high-performance solvers for challenging optimisation problems. However, most existing work on AAC deals with configuration procedures that optimise a single performance metric of a given, single-objective algorithm. Of course, these configurators can also be used to optimise the performance of multi-objective algorithms, as measured by a single performance indicator. In this work, we demonstrate that better results can be obtained by using a native, multi-objective algorithm configuration procedure. Specifically, we compare three AAC approaches: one considering only the hypervolume indicator, a second optimising the weighted sum of hypervolume and spread, and a third that simultaneously optimises these complementary indicators, using a genuinely multi-objective approach. We assess these approaches by applying them to a highly-parametric local search framework for two widely studied multi-objective optimisation problems, the bi-objective permutation flowshop and travelling salesman problems. Our results show that multi-objective algorithms are indeed best configured using a multi-objective configurator.

Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism.

Choosing a better move correctly and quickly is a fundamental skill of living organisms that corresponds to solving a computationally demanding problem. A unicellular plasmodium of Physarum polycephalum searches for a solution to the travelling salesman problem (TSP) by changing its shape to minimize the risk of being exposed to aversive light stimuli. In our previous studies, we reported the results on the eight-city TSP solution. In this study, we show that the time taken by plasmodium to find a reasonably high-quality TSP solution grows linearly as the problem size increases from four to eight. Interestingly, the quality of the solution does not degrade despite the explosive expansion of the search space. Formulating a computational model, we show that the linear-time solution can be achieved if the intrinsic dynamics could allocate intracellular resources to grow the plasmodium terminals with a constant rate, even while responding to the stimuli. These results may lead to the development of novel analogue computers enabling approximate solutions of complex optimization problems in linear time.

The multi-stripe travelling salesman problem.

In the classical Travelling Salesman Problem (TSP), the objective function sums the costs for travelling from one city to the next city along the tour. In the q-stripe TSP with [Formula: see text], the objective function sums the costs for travelling from one city to each of the next q cities in the tour. The resulting q-stripe TSP generalizes the TSP and forms a special case of the quadratic assignment problem. We analyze the computational complexity of the q-stripe TSP for various classes of specially structured distance matrices. We derive NP-hardness results as well as polynomially solvable cases. One of our main results generalizes a well-known theorem of Kalmanson from the classical TSP to the q-stripe TSP.

Modelo matemático para la planificación de servicios y programación de rutas en empresas prestadoras de servicios de control de plagas

Este artículo aborda el problema de la programación de servicios y planificación de rutas para empresas prestadoras de servicio de control de plagas (CP) considerando la minimización de los costos relacionados con las distancias recorridas por los vehículos usados y el costo del tiempo ocioso de los operarios. El problema considera actividades programadas, fechas de atención no disponibles, capacidad instalada, y datos de demanda previa obtenida de los clientes. La problemática consiste en la programación de los servicios y la planificación de las rutas de atención considerando ventanas de tiempo. En particular, se ha propuesto un modelo de programación lineal entera mixta, que busca mejorar la gestión logística de empresas que pertenecen a este sector. El modelo se ha probado con datos de una compañía colombiana que presta los servicios de CP en las principales ciudades colombianas. Los resultados obtenidos reflejan la importancia y eficiencia de la metodología propuesta como alternativa para la solución de la problemática en cuestión.

This paper addresses the problem of scheduling of services and planning of routes for companies which offer the service of pest control (CP) by considering the minimization of costs related to the distance traveled by the used vehicles and the cost of the cost of idle time of operators. The problem considers scheduled activities, dates not available and installed capacity, and data of demand previously provided by the customers. The problem consists of the scheduling and planning of the routes by considering time windows. In particular it is proposed a mixed integer linear programming model to improve the logistic management process of companies belonging to this sector The model has been tested with data obtained from a Colombian company that provides the CP services in the main Colombian cities. The results show the importance and efficiency of the proposed methodology as an alternative to the solution of the considered problem.

Este artigo discute o problema do agendamento de serviços e planejamento de rota para o controle de empresas de serviços de pragas (CP), considerando a minimização de custos relacionados com as distâncias percorridas pelos veículos usados e o custo do tempo ocioso de operadores . O problema considera actividades programadas, as datas não importa disponível, capacidade e dados de demanda obtidos a partir de clientes anteriores instalado. O problema é o de serviços de programação e cuidado planeamento da rota, considerando janelas de tempo. Em particular, ele propôs um modelo de programação linear inteira mista, que visa melhorar as empresas de gestão logística pertencentes a este sector. O modelo foi testado com dados de uma empresa colombiana, que fornece serviços de CP nas principais cidades colombianas. Os resultados mostram a importância e eficiência da metodologia proposta como uma alternativa para resolver o problema em questão.

Modelling and optimizing a system for testing electronic circuit boards.

In this article we consider a difficult combinatorial optimization problem arising from the operation of a system for testing electronic circuit boards (ECB). This problem was proposed to us by a company that makes a system for testing ECBs and is looking for an efficient way of planning the tests on any given ECB. Because of its difficulty, we first split the problem into a covering subproblem and a sequencing subproblem. We also give a global formulation of the test planning problem. Then we present and discuss results pertaining to the covering and sequencing subproblems. These results demonstrate that their solution yields testing plans that are much better than those currently used by the company. Finally we conclude our article by outlining avenues for future research.

An Analysis of the Fitness Landscape of Travelling Salesman Problem.

The fitness landscape of the travelling salesman problem is investigated for 11 different types of the problem. The types differ in how the distances between cities are generated. Many different properties of the landscape are studied. The properties chosen are all potentially relevant to choosing an appropriate search algorithm. The analysis includes a scaling study of the time to reach a local optimum, the number of local optima, the expected probability of reaching a local optimum as a function of its fitness, the expected fitness found by local search and the best fitness, the probability of reaching a global optimum, the distance between the local optima and the global optimum, the expected fitness as a function of the distance from an optimum, their basins of attraction and a principal component analysis of the local optima. The principal component analysis shows the correlation of the local optima in the component space. We show how the properties of the principal components of the local optima change from one problem type to another.

[Formula: see text]-Approximation for Graphic TSP.

The Travelling Salesman Problem is one of the fundamental and intensively studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides's algorithm with an approximation factor of [Formula: see text], even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only [Formula: see text]. Very recently, significant progress has been made for the important special case of graphic metrics, first by Oveis Gharan et al. (FOCS, 550-559, 2011), and then by Mömke and Svensson (FOCS, 560-569, 2011). In this paper, we provide an improved analysis of the approach presented in Mömke and Svensson (FOCS, 560-569, 2011) yielding a bound of [Formula: see text] on the approximation factor, as well as a bound of [Formula: see text] for any ε>0 for a more general Travelling Salesman Path Problem in graphic metrics.