China
Africa
Explore chapters and articles related to this topic
Cockroach Swarm Optimization Modifications and Application
Published in Adam Slowik, Swarm Intelligence Algorithms, 2020
The goal of the traveling salesman problem is to find the path of shorter length or minimum cost between all the requested points (cities), visiting each point exactly once and returning to the starting point. The salesman starts at a point, visiting all the points one by one and returns to the initial point. For a given set of cities from 1 to N and a cost matrix C = [ci,j], where each value ci,j represents the cost of traveling between cities i and j, each possible tour can be represented as a permutation π = (π(1),..., π(N)), where π(i) ∈ N represents the city visited in step i, i = 1,..., N. Therefore, the goal is to find the minimal cost of the closed tour which minimizes the following objective function [8]: f(π)=∑i=1N−1cπ(i),π(i+1)+cπ(N),π(1)
Introduction
Published in A Vasuki, Nature-Inspired Optimization Algorithms, 2020
The TSP and the knapsack problem are two typical famous examples in computer science for discrete combinatorial optimization. In the TSP, the objective function is the total distance of the Hamiltonian tour and depends on the set of cities visited and the total distance covered which is the sum of the distance of the edges connecting the cities, and in the knapsack problem the combination of the weights of the items loaded into the knapsack and their total cost determines the objective function value. Consider the traveling salesman problem which is a typical combinatorial optimization problem in computer science that has been found to be intractable or NP-hard. There are a set of cities that are interconnected. The cities are represented by nodes in a graph and the connections between the nodes are edges. Each edge has a value associated with it that could represent distance or cost. The problem is for a traveling salesman to visit each of these cities once and only once (without retracing) and go back to the starting city traveling a total minimum distance and hence incurring the minimum cost. The path in the graph traced by the traveling salesman is called the Hamiltonian tour. This is illustrated in Figure 1.9 which shows one possible Hamiltonian tour in the graph.
The Journey Continues
Published in Nicolas Sabouret, Lizete De Assis, Understanding Artificial Intelligence, 2020
The difficulty that arises in the traveling salesman problem comes from the size of the solution space. If we have N cities to visit in addition to our departure city, there are N choices for the first city, N − 1 for the next, and so on. In total, we’ll have N×(N−1)×(N−2)×⋯×3×2×1
The ‘Idiot’ crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems
Published in Optimization Methods and Software, 2020
The quadratic assignment problem (QAP) is a combinatorial optimization problem, being a special case of the facility location problem. It concerns a set of facilities and a set of locations. For each pair of locations there is a distance, and for each pair of facilities there is a weight or flow specified, for instance the number of items transported between the two facilities. The problem is to assign all facilities to different locations so that the sum of the distances multiplied by the corresponding flows is minimized. QAPs are well known for being very difficult to solve, even for small instances. They are NP-hard and the travelling salesman problem can be seen as a special case. Often, rather than the quadratic problem itself, an equivalent linearization is solved. A comprehensive survey of QAP problems and their solution is given by Loiola et al. [11].
An activity chain optimization method with comparison of test cases for different transportation modes
Published in Transportmetrica A: Transport Science, 2020
Domokos Esztergár-Kiss, Zoltán Rózsa, Tamás Tettamanti
Finally, TSP solutions with different constraints have the most connection to our paper, as we also intend to solve a complex TSP problem in order to generate optimal activity chains. Ghiani et al. (2011) solved the Traveling Salesman Problem with heuristic algorithms. Two approaches are compared, a sample-scenario planning and an anticipatory insertion version. The first one provides exact and optimal results, but it has a higher computational effort, while the second one approaches the optimal solution, but provides quicker solutions. This is much appreciated, especially in case of activity scheduling problems. Here the implementation of daily activities solved the TSP, and this was the main contribution. However, neither flexibility nor a complex utility function were elaborated. The idea of heuristic algorithms and the application of TSP to solve activity chain optimization were used in our approach.
Reinforcement learning-enabled genetic algorithm for school bus scheduling
Published in Journal of Intelligent Transportation Systems, 2022
Eda Köksal Ahmed, Zengxiang Li, Bharadwaj Veeravalli, Shen Ren
The objective function is a linear combination of the two objective functions, as shown in the formulation. However, in our case, owing to the requirement of the identification of individual route segments and their travel time predictions within 15 min time interval becomes challenging. Moreover, the two-way tour distances between two nodes are not strictly equal, and the starting roadside is unknown. Unfortunately, it falls with the variants of the Traveling Salesman Problem (TSP), which is also NP-Hard. Furthermore, SBS is our test case, and this study is a part of our intelligent Transport Management System (TMS), where we have generic cases with dynamic demand. Therefore, the proposed solution approach falls under heuristic approaches.