Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 5769

Search results for: traveling salesman problem

5769 Evaluation of the exIWO Algorithm Based on the Traveling Salesman Problem

Authors: Daniel Kostrzewa, Henryk Josiński


The expanded Invasive Weed Optimization algorithm (exIWO) is an optimization metaheuristic modelled on the original IWO version created by the researchers from the University of Tehran. The authors of the present paper have extended the exIWO algorithm introducing a set of both deterministic and non-deterministic strategies of individuals’ selection. The goal of the project was to evaluate the exIWO by testing its usefulness for solving some test instances of the traveling salesman problem (TSP) taken from the TSPLIB collection which allows comparing the experimental results with optimal values.

Keywords: expanded invasive weed optimization algorithm (exIWO), traveling salesman problem (TSP), heuristic approach, inversion operator

Procedia PDF Downloads 476
5768 Block Based Imperial Competitive Algorithm with Greedy Search for Traveling Salesman Problem

Authors: Meng-Hui Chen, Chiao-Wei Yu, Pei-Chann Chang


Imperial competitive algorithm (ICA) simulates a multi-agent algorithm. Each agent is like a kingdom has its country, and the strongest country in each agent is called imperialist, others are colony. Countries are competitive with imperialist which in the same kingdom by evolving. So this country will move in the search space to find better solutions with higher fitness to be a new imperialist. The main idea in this paper is using the peculiarity of ICA to explore the search space to solve the kinds of combinational problems. Otherwise, we also study to use the greed search to increase the local search ability. To verify the proposed algorithm in this paper, the experimental results of traveling salesman problem (TSP) is according to the traveling salesman problem library (TSPLIB). The results show that the proposed algorithm has higher performance than the other known methods.

Keywords: traveling salesman problem, artificial chromosomes, greedy search, imperial competitive algorithm

Procedia PDF Downloads 360
5767 An Algorithm of Set-Based Particle Swarm Optimization with Status Memory for Traveling Salesman Problem

Authors: Takahiro Hino, Michiharu Maeda


Particle swarm optimization (PSO) is an optimization approach that achieves the social model of bird flocking and fish schooling. PSO works in continuous space and can solve continuous optimization problem with high quality. Set-based particle swarm optimization (SPSO) functions in discrete space by using a set. SPSO can solve combinatorial optimization problem with high quality and is successful to apply to the large-scale problem. In this paper, we present an algorithm of SPSO with status memory to decide the position based on the previous position for solving traveling salesman problem (TSP). In order to show the effectiveness of our approach. We examine SPSOSM for TSP compared to the existing algorithms.

Keywords: combinatorial optimization problems, particle swarm optimization, set-based particle swarm optimization, traveling salesman problem

Procedia PDF Downloads 249
5766 An Improved Genetic Algorithm for Traveling Salesman Problem with Precedence Constraint

Authors: M. F. F. Ab Rashid, A. N. Mohd Rose, N. M. Z. Nik Mohamed, W. S. Wan Harun, S. A. Che Ghani


Traveling salesman problem with precedence constraint (TSPPC) is one of the most complex problems in combinatorial optimization. The existing algorithms to solve TSPPC cost large computational time to find the optimal solution. The purpose of this paper is to present an efficient genetic algorithm that guarantees optimal solution with less number of generations and iterations time. Unlike the existing algorithm that generates priority factor as chromosome, the proposed algorithm directly generates sequence of solution as chromosome. As a result, the proposed algorithm is capable of generating optimal solution with smaller number of generations and iteration time compare to existing algorithm.

Keywords: traveling salesman problem, sequencing, genetic algorithm, precedence constraint

Procedia PDF Downloads 446
5765 An Improved Method to Compute Sparse Graphs for Traveling Salesman Problem

Authors: Y. Wang


The Traveling salesman problem (TSP) is NP-hard in combinatorial optimization. The research shows the algorithms for TSP on the sparse graphs have the shorter computation time than those for TSP according to the complete graphs. We present an improved iterative algorithm to compute the sparse graphs for TSP by frequency graphs computed with frequency quadrilaterals. The iterative algorithm is enhanced by adjusting two parameters of the algorithm. The computation time of the algorithm is O(CNmaxn2) where C is the iterations, Nmax is the maximum number of frequency quadrilaterals containing each edge and n is the scale of TSP. The experimental results showed the computed sparse graphs generally have less than 5n edges for most of these Euclidean instances. Moreover, the maximum degree and minimum degree of the vertices in the sparse graphs do not have much difference. Thus, the computation time of the methods to resolve the TSP on these sparse graphs will be greatly reduced.

Keywords: frequency quadrilateral, iterative algorithm, sparse graph, traveling salesman problem

Procedia PDF Downloads 110
5764 A Second Order Genetic Algorithm for Traveling Salesman Problem

Authors: T. Toathom, M. Munlin, P. Sugunnasil


The traveling salesman problem (TSP) is one of the best-known problems in optimization problem. There are many research regarding the TSP. One of the most usage tool for this problem is the genetic algorithm (GA). The chromosome of the GA for TSP is normally encoded by the order of the visited city. However, the traditional chromosome encoding scheme has some limitations which are twofold: the large solution space and the inability to encapsulate some information. The number of solution for a certain problem is exponentially grow by the number of city. Moreover, the traditional chromosome encoding scheme fails to recognize the misplaced correct relation. It implies that the tradition method focuses only on exact solution. In this work, we relax some of the concept in the GA for TSP which is the exactness of the solution. The proposed work exploits the relation between cities in order to reduce the solution space in the chromosome encoding. In this paper, a second order GA is proposed to solve the TSP. The term second order refers to how the solution is encoded into chromosome. The chromosome is divided into 2 types: the high order chromosome and the low order chromosome. The high order chromosome is the chromosome that focus on the relation between cities such as the city A should be visited before city B. On the other hand, the low order chromosome is a type of chromosome that is derived from a high order chromosome. In other word, low order chromosome is encoded by the traditional chromosome encoding scheme. The genetic operation, mutation and crossover, will be performed on the high order chromosome. Then, the high order chromosome will be mapped to a group of low order chromosomes whose characteristics are satisfied with the high order chromosome. From the mapped set of chromosomes, the champion chromosome will be selected based on the fitness value which will be later used as a representative for the high order chromosome. The experiment is performed on the city data from TSPLIB.

Keywords: genetic algorithm, traveling salesman problem, initial population, chromosomes encoding

Procedia PDF Downloads 169
5763 Comparative Analysis of Two Different Ant Colony Optimization Algorithm for Solving Travelling Salesman Problem

Authors: Sourabh Joshi, Tarun Sharma, Anurag Sharma


Ant Colony Optimization is heuristic Algorithm which has been proven a successful technique applied on number of combinatorial optimization problems. Two variants of Ant Colony Optimization algorithm named Ant System and Max-Min Ant System are implemented in MATLAB to solve travelling Salesman Problem and the results are compared. In, this paper both systems are analyzed by solving the some Travelling Salesman Problem and depict which system solve the problem better in term of cost and time.

Keywords: Ant Colony Optimization, Travelling Salesman Problem, Ant System, Max-Min Ant System

Procedia PDF Downloads 334
5762 Comparison of Heuristic Methods for Solving Traveling Salesman Problem

Authors: Regita P. Permata, Ulfa S. Nuraini


Traveling Salesman Problem (TSP) is the most studied problem in combinatorial optimization. In simple language, TSP can be described as a problem of finding a minimum distance tour to a city, starting and ending in the same city, and exactly visiting another city. In product distribution, companies often get problems in determining the minimum distance that affects the time allocation. In this research, we aim to apply TSP heuristic methods to simulate nodes as city coordinates in product distribution. The heuristics used are sub tour reversal, nearest neighbor, farthest insertion, cheapest insertion, nearest insertion, and arbitrary insertion. We have done simulation nodes using Euclidean distances to compare the number of cities and processing time, thus we get optimum heuristic method. The results show that the optimum heuristic methods are farthest insertion and nearest insertion. These two methods can be recommended to solve product distribution problems in certain companies.

Keywords: Euclidean, heuristics, simulation, TSP

Procedia PDF Downloads 34
5761 Adapting the Chemical Reaction Optimization Algorithm to the Printed Circuit Board Drilling Problem

Authors: Taisir Eldos, Aws Kanan, Waleed Nazih, Ahmad Khatatbih


Chemical Reaction Optimization (CRO) is an optimization metaheuristic inspired by the nature of chemical reactions as a natural process of transforming the substances from unstable to stable states. Starting with some unstable molecules with excessive energy, a sequence of interactions takes the set to a state of minimum energy. Researchers reported successful application of the algorithm in solving some engineering problems, like the quadratic assignment problem, with superior performance when compared with other optimization algorithms. We adapted this optimization algorithm to the Printed Circuit Board Drilling Problem (PCBDP) towards reducing the drilling time and hence improving the PCB manufacturing throughput. Although the PCBDP can be viewed as instance of the popular Traveling Salesman Problem (TSP), it has some characteristics that would require special attention to the transactions that explore the solution landscape. Experimental test results using the standard CROToolBox are not promising for practically sized problems, while it could find optimal solutions for artificial problems and small benchmarks as a proof of concept.

Keywords: evolutionary algorithms, chemical reaction optimization, traveling salesman, board drilling

Procedia PDF Downloads 406
5760 Discrete Group Search Optimizer for the Travelling Salesman Problem

Authors: Raed Alnajjar, Mohd Zakree, Ahmad Nazri


In this study, we apply Discrete Group Search Optimizer (DGSO) for solving Traveling Salesman Problem (TSP). The DGSO is a nature inspired optimization algorithm that imitates the animal behavior, especially animal searching behavior. The proposed DGSO uses a vector representation and some discrete operators, such as destruction, construction, differential evolution, swap and insert. The TSP is a well-known hard combinatorial optimization problem, which seeks to find the shortest path among numbers of cities. The performance of the proposed DGSO is evaluated and tested on benchmark instances which listed in LIBTSP dataset. The experimental results show that the performance of the proposed DGSO is comparable with the other methods in the state of the art for some instances. The results show that DGSO outperform Ant Colony System (ACS) in some instances whilst outperform other metaheuristic in most instances. In addition to that, the new results obtained a number of optimal solutions and some best known results. DGSO was able to obtain feasible and good quality solution across all dataset.

Keywords: discrete group search optimizer (DGSO); Travelling salesman problem (TSP); Variable neighborhood search(VNS)

Procedia PDF Downloads 216
5759 Multi-Objective Optimization for the Green Vehicle Routing Problem: Approach to Case Study of the Newspaper Distribution Problem

Authors: Julio C. Ferreira, Maria T. A. Steiner


The aim of this work is to present a solution procedure referred to here as the Multi-objective Optimization for Green Vehicle Routing Problem (MOOGVRP) to provide solutions for a case study. The proposed methodology consists of three stages to resolve Scenario A. Stage 1 consists of the “treatment” of data; Stage 2 consists of applying mathematical models of the p-Median Capacitated Problem (with the objectives of minimization of distances and homogenization of demands between groups) and the Asymmetric Traveling Salesman Problem (with the objectives of minimizing distances and minimizing time). The weighted method was used as the multi-objective procedure. In Stage 3, an analysis of the results is conducted, taking into consideration the environmental aspects related to the case study, more specifically with regard to fuel consumption and air pollutant emission. This methodology was applied to a (partial) database that addresses newspaper distribution in the municipality of Curitiba, Paraná State, Brazil. The preliminary findings for Scenario A showed that it was possible to improve the distribution of the load, reduce the mileage and the greenhouse gas by 17.32% and the journey time by 22.58% in comparison with the current scenario. The intention for future works is to use other multi-objective techniques and an expanded version of the database and explore the triple bottom line of sustainability.

Keywords: Asymmetric Traveling Salesman Problem, Green Vehicle Routing Problem, Multi-objective Optimization, p-Median Capacitated Problem

Procedia PDF Downloads 26
5758 Detailed Quantum Circuit Design and Evaluation of Grover's Algorithm for the Bounded Degree Traveling Salesman Problem Using the Q# Language

Authors: Wenjun Hou, Marek Perkowski


The Traveling Salesman problem is famous in computing and graph theory. In short, it asks for the Hamiltonian cycle of the least total weight in a given graph with N nodes. All variations on this problem, such as those with K-bounded-degree nodes, are classified as NP-complete in classical computing. Although several papers propose theoretical high-level designs of quantum algorithms for the Traveling Salesman Problem, no quantum circuit implementation of these algorithms has been created up to our best knowledge. In contrast to previous papers, the goal of this paper is not to optimize some abstract complexity measures based on the number of oracle iterations, but to be able to evaluate the real circuit and time costs of the quantum computer. Using the emerging quantum programming language Q# developed by Microsoft, which runs quantum circuits in a quantum computer simulation, an implementation of the bounded-degree problem and its respective quantum circuit were created. To apply Grover’s algorithm to this problem, a quantum oracle was designed, evaluating the cost of a particular set of edges in the graph as well as its validity as a Hamiltonian cycle. Repeating the Grover algorithm with an oracle that finds successively lower cost each time allows to transform the decision problem to an optimization problem, finding the minimum cost of Hamiltonian cycles. N log₂ K qubits are put into an equiprobablistic superposition by applying the Hadamard gate on each qubit. Within these N log₂ K qubits, the method uses an encoding in which every node is mapped to a set of its encoded edges. The oracle consists of several blocks of circuits: a custom-written edge weight adder, node index calculator, uniqueness checker, and comparator, which were all created using only quantum Toffoli gates, including its special forms, which are Feynman and Pauli X. The oracle begins by using the edge encodings specified by the qubits to calculate each node that this path visits and adding up the edge weights along the way. Next, the oracle uses the calculated nodes from the previous step and check that all the nodes are unique. Finally, the oracle checks that the calculated cost is less than the previously-calculated cost. By performing the oracle an optimal number of times, a correct answer can be generated with very high probability. The oracle of the Grover Algorithm is modified using the recalculated minimum cost value, and this procedure is repeated until the cost cannot be further reduced. This algorithm and circuit design have been verified, using several datasets, to generate correct outputs.

Keywords: quantum computing, quantum circuit optimization, quantum algorithms, hybrid quantum algorithms, quantum programming, Grover’s algorithm, traveling salesman problem, bounded-degree TSP, minimal cost, Q# language

Procedia PDF Downloads 44
5757 Roullete Wheel Selection Mechanism for Solving Travelling Salesman Problem in Ant Colony Optimization

Authors: Sourabh Joshi, Geetinder Kaur, Sarabjit Kaur, Gulwatanpreet Singh, Geetika Mannan


In this paper, we have use an algorithm that able to obtain an optimal solution to travelling salesman problem from a huge search space, quickly. This algorithm is based upon the ant colony optimization technique and employees roulette wheel selection mechanism. To illustrate it more clearly, a program has been implemented which is based upon this algorithm, that presents the changing process of route iteration in a more intuitive way. In the event, we had find the optimal path between hundred cities and also calculate the distance between two cities.

Keywords: ant colony, optimization, travelling salesman problem, roulette wheel selection

Procedia PDF Downloads 304
5756 Optimizing Logistics for Courier Organizations with Considerations of Congestions and Pickups: A Courier Delivery System in Amman as Case Study

Authors: Nader A. Al Theeb, Zaid Abu Manneh, Ibrahim Al-Qadi


Traveling salesman problem (TSP) is a combinatorial integer optimization problem that asks "What is the optimal route for a vehicle to traverse in order to deliver requests to a given set of customers?”. It is widely used by the package carrier companies’ distribution centers. The main goal of applying the TSP in courier organizations is to minimize the time that it takes for the courier in each trip to deliver or pick up the shipments during a day. In this article, an optimization model is constructed to create a new TSP variant to optimize the routing in a courier organization with a consideration of congestion in Amman, the capital of Jordan. Real data were collected by different methods and analyzed. Then, concert technology - CPLEX was used to solve the proposed model for some random generated data instances and for the real collected data. At the end, results have shown a great improvement in time compared with the current trip times, and an economic study was conducted afterwards to figure out the impact of using such models.

Keywords: travel salesman problem, congestions, pick-up, integer programming, package carriers, service engineering

Procedia PDF Downloads 323
5755 ACOPIN: An ACO Algorithm with TSP Approach for Clustering Proteins in Protein Interaction Networks

Authors: Jamaludin Sallim, Rozlina Mohamed, Roslina Abdul Hamid


In this paper, we proposed an Ant Colony Optimization (ACO) algorithm together with Traveling Salesman Problem (TSP) approach to investigate the clustering problem in Protein Interaction Networks (PIN). We named this combination as ACOPIN. The purpose of this work is two-fold. First, to test the efficacy of ACO in clustering PIN and second, to propose the simple generalization of the ACO algorithm that might allow its application in clustering proteins in PIN. We split this paper to three main sections. First, we describe the PIN and clustering proteins in PIN. Second, we discuss the steps involved in each phase of ACO algorithm. Finally, we present some results of the investigation with the clustering patterns.

Keywords: ant colony optimization algorithm, searching algorithm, protein functional module, protein interaction network

Procedia PDF Downloads 468
5754 Ant System with Acoustic Communication

Authors: Saad Bougrine, Salma Ouchraa, Belaid Ahiod, Abdelhakim Ameur El Imrani


Ant colony optimization is an ant algorithm framework that took inspiration from foraging behaviour of ant colonies. Indeed, ACO algorithms use a chemical communication, represented by pheromone trails, to build good solutions. However, ants involve different communication channels to interact. Thus, this paper introduces the acoustic communication between ants while they are foraging. This process allows fine and local exploration of search space and permits optimal solution to be improved.

Keywords: acoustic communication, ant colony optimization, local search, traveling salesman problem

Procedia PDF Downloads 437
5753 A Coordinate-Based Heuristic Route Search Algorithm for Delivery Truck Routing Problem

Authors: Ahmed Tarek, Ahmed Alveed


Vehicle routing problem is a well-known re-search avenue in computing. Modern vehicle routing is more focused with the GPS-based coordinate system, as the state-of-the-art vehicle, and trucking systems are equipped with digital navigation. In this paper, a new two dimensional coordinate-based algorithm for addressing the vehicle routing problem for a supply chain network is proposed and explored, and the algorithm is compared with other available, and recently devised heuristics. For the algorithms discussed, which includes the pro-posed coordinate-based search heuristic as well, the advantages and the disadvantages associated with the heuristics are explored. The proposed algorithm is studied from the stand point of a small supermarket chain delivery network that supplies to its stores in four different states around the East Coast area, and is trying to optimize its trucking delivery cost. Minimizing the delivery cost for the supply network of a supermarket chain is important to ensure its business success.

Keywords: coordinate-based optimal routing, Hamiltonian Circuit, heuristic algorithm, traveling salesman problem, vehicle routing problem

Procedia PDF Downloads 43
5752 Comparative Performance Analysis for Selected Behavioral Learning Systems versus Ant Colony System Performance: Neural Network Approach

Authors: Hassan M. H. Mustafa


This piece of research addresses an interesting comparative analytical study. Which considers two concepts of diverse algorithmic computational intelligence approaches related tightly with Neural and Non-Neural Systems. The first algorithmic intelligent approach concerned with observed obtained practical results after three neural animal systems’ activities. Namely, they are Pavlov’s, and Thorndike’s experimental work. Besides a mouse’s trial during its movement inside figure of eight (8) maze, to reach an optimal solution for reconstruction problem. Conversely, second algorithmic intelligent approach originated from observed activities’ results for Non-Neural Ant Colony System (ACS). These results obtained after reaching an optimal solution while solving Traveling Sales-man Problem (TSP). Interestingly, the effect of increasing number of agents (either neurons or ants) on learning performance shown to be similar for both introduced systems. Finally, performance of both intelligent learning paradigms shown to be in agreement with learning convergence process searching for least mean square error LMS algorithm. While its application for training some Artificial Neural Network (ANN) models. Accordingly, adopted ANN modeling is a relevant and realistic tool to investigate observations and analyze performance for both selected computational intelligence (biological behavioral learning) systems.

Keywords: artificial neural network modeling, animal learning, ant colony system, traveling salesman problem, computational biology

Procedia PDF Downloads 391
5751 Impact of Population Size on Symmetric Travelling Salesman Problem Efficiency

Authors: Wafa' Alsharafat, Suhila Farhan Abu-Owida


Genetic algorithm (GA) is a powerful evolutionary searching technique that is used successfully to solve and optimize problems in different research areas. Genetic Algorithm (GA) considered as one of optimization methods used to solve Travel salesman Problem (TSP). The feasibility of GA in finding a TSP solution is dependent on GA operators; encoding method, population size, termination criteria, in general. In specific, crossover and its probability play a significant role in finding possible solutions for Symmetric TSP (STSP). In addition, the crossover should be determined and enhanced in term reaching optimal or at least near optimal. In this paper, we spot the light on using a modified crossover method called modified sequential constructive crossover and its impact on reaching optimal solution. To justify the relevance of a parameter value in solving the TSP, a set comparative analysis conducted on different crossover methods values.

Keywords: genetic algorithm, crossover, mutation, TSP

Procedia PDF Downloads 74
5750 A Comparative Analysis of Heuristics Applied to Collecting Used Lubricant Oils Generated in the City of Pereira, Colombia

Authors: Diana Fajardo, Sebastián Ortiz, Oscar Herrera, Angélica Santis


Currently, in Colombia is arising a problem related to collecting used lubricant oils which are generated by the increment of the vehicle fleet. This situation does not allow a proper disposal of this type of waste, which in turn results in a negative impact on the environment. Therefore, through the comparative analysis of various heuristics, the best solution to the VRP (Vehicle Routing Problem) was selected by comparing costs and times for the collection of used lubricant oils in the city of Pereira, Colombia; since there is no presence of management companies engaged in the direct administration of the collection of this pollutant. To achieve this aim, six proposals of through methods of solution of two phases were discussed. First, the assignment of the group of generator points of the residue was made (previously identified). Proposals one and four of through methods are based on the closeness of points. The proposals two and five are using the scanning method and the proposals three and six are considering the restriction of the capacity of collection vehicle. Subsequently, the routes were developed - in the first three proposals by the Clarke and Wright's savings algorithm and in the following proposals by the Traveling Salesman optimization mathematical model. After applying techniques, a comparative analysis of the results was performed and it was determined which of the proposals presented the most optimal values in terms of the distance, cost and travel time.

Keywords: Heuristics, optimization Model, savings algorithm, used vehicular oil, V.R.P.

Procedia PDF Downloads 305
5749 Decision Support System for Solving Multi-Objective Routing Problem

Authors: Ismail El Gayar, Ossama Ismail, Yousri El Gamal


This paper presented a technique to solve one of the transportation problems that faces us in real life which is the Bus Scheduling Problem. Most of the countries using buses in schools, companies and traveling offices as an example to transfer multiple passengers from many places to specific place and vice versa. This transferring process can cost time and money, so we build a decision support system that can solve this problem. In this paper, a genetic algorithm with the shortest path technique is used to generate a competitive solution to other well-known techniques. It also presents a comparison between our solution and other solutions for this problem.

Keywords: bus scheduling problem, decision support system, genetic algorithm, shortest path

Procedia PDF Downloads 255
5748 Understanding Evolutionary Algorithms through Interactive Graphical Applications

Authors: Javier Barrachina, Piedad Garrido, Manuel Fogue, Julio A. Sanguesa, Francisco J. Martinez


It is very common to observe, especially in Computer Science studies that students have difficulties to correctly understand how some mechanisms based on Artificial Intelligence work. In addition, the scope and limitations of most of these mechanisms are usually presented by professors only in a theoretical way, which does not help students to understand them adequately. In this work, we focus on the problems found when teaching Evolutionary Algorithms (EAs), which imitate the principles of natural evolution, as a method to solve parameter optimization problems. Although this kind of algorithms can be very powerful to solve relatively complex problems, students often have difficulties to understand how they work, and how to apply them to solve problems in real cases. In this paper, we present two interactive graphical applications which have been specially designed with the aim of making Evolutionary Algorithms easy to be understood by students. Specifically, we present: (i) TSPS, an application able to solve the ”Traveling Salesman Problem”, and (ii) FotEvol, an application able to reconstruct a given image by using Evolution Strategies. The main objective is that students learn how these techniques can be implemented, and the great possibilities they offer.

Keywords: education, evolutionary algorithms, evolution strategies, interactive learning applications

Procedia PDF Downloads 231
5747 Cars Redistribution Optimization Problem in the Free-Float Car-Sharing

Authors: Amine Ait-Ouahmed, Didier Josselin, Fen Zhou


Free-Float car-sharing is an one-way car-sharing service where cars are available anytime and anywhere in the streets such that no dedicated stations are needed. This means that after driving a car you can park it anywhere. This car-sharing system creates an imbalance car distribution in the cites which can be regulated by staff agents through the redistribution of cars. In this paper, we aim to solve the car-reservation and agents traveling problem so that the number of successful cars’ reservations could be maximized. Beside, we also tend to minimize the distance traveled by agents for cars redistribution. To this end, we present a mixed integer linear programming formulation for the car-sharing problem.

Keywords: one-way car-sharing, vehicle redistribution, car reservation, linear programming

Procedia PDF Downloads 225
5746 Parallel 2-Opt Local Search on GPU

Authors: Wen-Bao Qiao, Jean-Charles Créput


To accelerate the solution for large scale traveling salesman problems (TSP), a parallel 2-opt local search algorithm with simple implementation based on Graphics Processing Unit (GPU) is presented and tested in this paper. The parallel scheme is based on technique of data decomposition by dynamically assigning multiple K processors on the integral tour to treat K edges’ 2-opt local optimization simultaneously on independent sub-tours, where K can be user-defined or have a function relationship with input size N. We implement this algorithm with doubly linked list on GPU. The implementation only requires O(N) memory. We compare this parallel 2-opt local optimization against sequential exhaustive 2-opt search along integral tour on TSP instances from TSPLIB with more than 10000 cities.

Keywords: parallel 2-opt, double links, large scale TSP, GPU

Procedia PDF Downloads 241
5745 Existence and Stability of Periodic Traveling Waves in a Bistable Excitable System

Authors: M. Osman Gani, M. Ferdows, Toshiyuki Ogawa


In this work, we proposed a modified FHN-type reaction-diffusion system for a bistable excitable system by adding a scaled function obtained from a given function. We study the existence and the stability of the periodic traveling waves (or wavetrains) for the FitzHugh-Nagumo (FHN) system and the modified one and compare the results. The stability results of the periodic traveling waves (PTWs) indicate that most of the solutions in the fast family of the PTWs are stable for the FitzHugh-Nagumo equations. The instability occurs only in the waves having smaller periods. However, the smaller period waves are always unstable. The fast family with sufficiently large periods is always stable in FHN model. We find that the oscillation of pulse widths is absent in the standard FHN model. That motivates us to study the PTWs in the proposed FHN-type reaction-diffusion system for the bistable excitable media. A good agreement is found between the solutions of the traveling wave ODEs and the corresponding whole PDE simulation.

Keywords: bistable system, Eckhaus bifurcation, excitable media, FitzHugh-Nagumo model, periodic traveling waves

Procedia PDF Downloads 84
5744 The Nexus between Social Media Usage and Overtourism: A Survey Study Applied to Hangzhou in China

Authors: Song Qingfeng


This research aims to seek the relationship between social media usage and overtourism from the perspective of tourists based on the theory of Maslow’s hierarchy needs. A questionnaire is formulated to collect data from 400 tourists who have visited the Hangzhou city in China in the last 12 months. Structural Equation Model (SEM) is employed to analysis data. The finding is that social media usage aggravates overtourism. Specifically, social media is used by tourists to information-seeking, entertainment, self-presentation, and socialization for traveling. These roles of social media would evoke the traveling intention to a specific destination at a certain time, which further influences the tourist flow. When the tourist flow concentrate, the overtourism would be aggravated. This study contributes to the destination managers to deep-understand the cause-effect relationship between social media and overtourism in order to address this problem.

Keywords: social media, overtourism, tourist flow, SEM, Maslow’s hierarchy of needs, Hangzhou

Procedia PDF Downloads 31
5743 Evaluation Performance of Transport Vehicle on Different Surfaces

Authors: Hussein Abbas Jebur, Yasir Abd Ulrazzaq


This study was carried out at the farm of El-Gemmaiza Agriculture Research Station, El-Garbia Governorate Egypt, to determine the performance characteristics of an agricultural transport. The performance of this transportation was compared between three surfaces (asphalt, dusty and field). The study was concentrated on the rate of drawbar pull, slip ratio, tractive efficiency and specific energy per unit area. The comparison was made under three different surfaces (asphalt, dusty and field), different traveling speeds from (3.38 to 6.55 km/h) and variable weights (0 and 300 kg). The results showed that the highest value of the tractive efficiency 60.20% was obtained at traveling speed 4.00 km/h with weight on the rear wheel on the asphalt surface. The highest value of specific energy 1.93 kW.h/ton during use of ballast on rear tractor wheels at traveling speed 3.38 km/h on the field surface.

Keywords: tractor, energy, transportation, weight, power

Procedia PDF Downloads 206
5742 Difference between Riding a Bicycle on a Sidewalk or in the Street by Usual Traveling Means

Authors: Ai Fujii, Kan Shimazaki


Bicycle users must ride on the street according the law in Japan, but in practice, many bicycle users ride on the sidewalk. Drivers generally feel that bicycles riding in the street are in the way. In contrast, pedestrians generally feel that bicycles riding on the sidewalk are in the way. That seems to make sense. What, then, is the difference between riding a bicycle on the sidewalk or in the street by usual traveling means. We made 3D computer graphics models of pedestrians, a car, and a bicycle at an intersection. The bicycle was positioned to choose between advancing to the sidewalk or the street after a few seconds. We then made a 2D stimulus picture by changing the point of view of the 3DCG model pictures. Attitudes were surveyed using this 2D stimulus picture, and we compared attitudes between three groups, people traveling by car, on foot, or by bicycle. Here we report the survey result.

Keywords: bicycle, sidewalk, pedestrians, driver, intersection, safety

Procedia PDF Downloads 75
5741 Improved Traveling Wave Method Based Fault Location Algorithm for Multi-Terminal Transmission System of Wind Farm with Grounding Transformer

Authors: Ke Zhang, Yongli Zhu


Due to rapid load growths in today’s highly electrified societies and the requirement for green energy sources, large-scale wind farm power transmission system is constantly developing. This system is a typical multi-terminal power supply system, whose structure of the network topology of transmission lines is complex. What’s more, it locates in the complex terrain of mountains and grasslands, thus increasing the possibility of transmission line faults and finding the fault location with difficulty after the faults and resulting in an extremely serious phenomenon of abandoning the wind. In order to solve these problems, a fault location method for multi-terminal transmission line based on wind farm characteristics and improved single-ended traveling wave positioning method is proposed. Through studying the zero sequence current characteristics by using the characteristics of the grounding transformer(GT) in the existing large-scale wind farms, it is obtained that the criterion for judging the fault interval of the multi-terminal transmission line. When a ground short-circuit fault occurs, there is only zero sequence current on the path between GT and the fault point. Therefore, the interval where the fault point exists is obtained by determining the path of the zero sequence current. After determining the fault interval, The location of the short-circuit fault point is calculated by the traveling wave method. However, this article uses an improved traveling wave method. It makes the positioning accuracy more accurate by combining the single-ended traveling wave method with double-ended electrical data. What’s more, a method of calculating the traveling wave velocity is deduced according to the above improvements (it is the actual wave velocity in theory). The improvement of the traveling wave velocity calculation method further improves the positioning accuracy. Compared with the traditional positioning method, the average positioning error of this method is reduced by 30%.This method overcomes the shortcomings of the traditional method in poor fault location of wind farm transmission lines. In addition, it is more accurate than the traditional fixed wave velocity method in the calculation of the traveling wave velocity. It can calculate the wave velocity in real time according to the scene and solve the traveling wave velocity can’t be updated with the environment and real-time update. The method is verified in PSCAD/EMTDC.

Keywords: grounding transformer, multi-terminal transmission line, short circuit fault location, traveling wave velocity, wind farm

Procedia PDF Downloads 140
5740 Extension of a Competitive Location Model Considering a Given Number of Servers and Proposing a Heuristic for Solving

Authors: Mehdi Seifbarghy, Zahra Nasiri


Competitive location problem deals with locating new facilities to provide a service (or goods) to the customers of a given geographical area where other facilities (competitors) offering the same service are already present. The new facilities will have to compete with the existing facilities for capturing the market share. This paper proposes a new model to maximize the market share in which customers choose the facilities based on traveling time, waiting time and attractiveness. The attractiveness of a facility is considered as a parameter in the model. A heuristic is proposed to solve the problem.

Keywords: competitive location, market share, facility attractiveness, heuristic

Procedia PDF Downloads 404