China
Africa
Explore chapters and articles related to this topic
Storage and Warehousing
Published in Sunderesh S. Heragu, Facilities Design, 2022
We may also use 2-opt, simulated annealing, genetic algorithm, and the other general-purpose techniques studied in Chapter 12 for the order-picking problem. The application is straightforward. For example, given an initial tour, the 2-opt algorithm exchanges the position of two points and finds the cost associated with the new tour. This is done for all possible pairs, that is, n(n − 1)/2 pairs, and the one with the least cost replaces the initial tour. Starting with this as the initial tour, the preceding procedure of examining the n(n − 1)/2 two-way exchanges and replacing the initial tour with the least cost tour is continued until it is no longer possible to improve the current initial tour. Instead of checking all the possible exchanges, the greedy 2-opt heuristic algorithm replaces the initial tour with the first better tour encountered. The stopping criterion is the same as that for the 2-opt heuristic algorithm, that is, the preceding procedure is continued until no 2-way exchange leads to an improvement in the initial solution. Similarly, the simulated annealing algorithm discussed in Chapter 12 may be modified as follows for order picking.
Smart Bike-Sharing Systems for Smart Cities
Published in Amir H. Alavi, William G. Buttlar, Data Analytics for Smart Cities, 2018
Hesham A. Rakha, Mohammed Elhenawy, Huthaifa I. Ashqar, Mohammed H. Almannaa, Ahmed Ghanem
In this section, we propose an algorithm for solving the SBRP. The proposed algorithm consists of two stages: tour construction and tour improvement. In the tour construction stage, we model the SBRP using two sets of disjointed players. Each player constructs their own set of preferences for the opposite set of players, then the deferred acceptance algorithm (Gale and Shapley 1962) is used to find stable matches between the two sets. In the tour improvement stage, a 2-opt algorithm is used to search the neighborhood of the constructed tour to find a better tour. The proposed algorithm has the advantage of being able to easily consider a change in the constraints by restricting each player’s preference list changes to the new constraints. Accordingly, this algorithm can be easily used for dynamic rebalancing provided the demand predictions are known. Moreover, the matching algorithm and local search algorithm run in polynomial time, which means the proposed algorithm can solve large instances and is suitable for real-time application.
Heuristic and Metaheuristic Techniques for Optimization
Published in Michael W. Carter, Camille C. Price, Ghaith Rabadi, Operations Research, 2018
Michael W. Carter, Camille C. Price, Ghaith Rabadi
To illustrate the kinds of rearrangements of problem elements that have been found to be effective, we look at a few classical combinatorial optimization problems. In the traveling salesman problem, a solution is any sequence of cities that includes each city exactly once, in the order visited. A very effective local improvement mechanism for generating a new configuration, known as 2-opt, is to select a pair of (directed) edges (i,j) and (m,n) and replace them with the crossing edges, (i,m) and (j,n) in such a way that the result is a new tour. For example, the tour shown on the left in Figure 10.1 is represented by the sequence 1–2–3–4–5–6–1. If we select the edges (1,2) and (4,5), the resulting sequence 1–4–3–2–5–6–1 represents the tour shown on the right in the figure. The quality of these two tours could be compared, and the better one selected by the heuristic. Clearly, if the length of the two edges added is less than the two removed, then the new tour is an improvement. This simple method was introduced by Lin and Kernighan (1973), and extended as a k-opt method. Remove any k edges and replace them with (the best possible) crossing edges. It is easy to implement, and usually executes in a very reasonable and affordable amount of computation time. The 2-opt requires O(n2) operations each iteration, and 3-opt requires O(n3). Solutions for k = 3 are typically very good for practical applications.
The fleet size and mix vehicle routing problem with synchronized visits
Published in Transportation Letters, 2022
Mohamed Amine Masmoudi, Manar Hosny, Çağrı Koç
During the search of the TA algorithm, four well-known local search operators adopted from the literature (Potvin and Rousseau 1995) are developed as described below. Similar to the moves of the insertion operators described in Subsection 4.2, only the feasible move that respects the FSM-VRPS constraints at each use of a local search operator is accepted during the construction of the (new) improved solution. 2-opt (L1): This operator consists of deleting two edges from only one randomly selected route, and then reconnecting the two tours obtained.2-opt*(L2): This operator is similar to L1. The difference is that it is applied on two different routes but with the same two vehicle types (passenger cars or bikes).Relocate (L3): This operator consists of removing one or two (consecutive) patient(s) from a route and then inserting them in the best positions, either in the same route or other different routes, in order to obtain a better solution.Exchange (L4): Unlike the above mentioned operators related to the position of patients, this operator consists of changing an assigned vehicle of a randomly selected route without changing the route.
Memetic algorithm-based path generation for multiple Dubins vehicles performing remote tasks
Published in International Journal of Systems Science, 2020
Doo-Hyun Cho, Dae-Sung Jang, Han-Lim Choi
Local improvement heuristics play a major role in enhancing the quality of the solution in the general GA. In the proposed algorithm, the improvement heuristic is applied to the initial population or to the chromosome newly generated in the crossover or immigration phase. Improvement heuristics consists of 2-opt and swap methods, each of which is summarised as follows. The 2-opt method consists of a global 2-opt, which applies 2-opt for the entire chromosome, and a local 2-opt applying 2-opt for each tour assigned to the vehicle. The swap consists of a task swap that changes the order of two genes across the chromosome and a sample swap that optimises the sample node information for each gene. The main idea of 2-opt, one of the simplest local search algorithms to solve the TSP problem, is that the tour can be re-arranged by tweaking a part of the tour, thereby improving costs. For the ETSP (the cost from node a to node b is the same as the cost from b to a), the cost of the entire tour can be updated using only the cost variation between new edges caused by exchanging selected edges and destinations of two different edges. However, for the asymmetric TSP, the cost changes according to the direction of edges. Therefore, the cost of all the changed paths must be calculated to update the cost of the entire tour. To cope with this problem, Freisleben and Merz (1996) used 3-opt instead of 2-opt to preserve the direction of the path. However, we used 2-opt since the number of task clusters to visit is not very large in the instance handled in this study. In addition, the algorithm is constructed to guarantee the quality of the chromosome through the swap operators. The 2-opt and swap operations are not integrated as used in Renaud and Boctor (1998), but are made to work as separate operators. As in Snyder and Daskin (2006), Level-I improvement is applied when the cost of the chromosome does not belong to the upper rank with in our implementation, and Level-II improvement is applied when it belongs to it. We applied the global 2-opt, local 2-opt, and sample swap operators to the chromosome once through Level-I improvement, and we applied the task swap operator five times. Level-II improvement is applied to the chromosome until the global 2-opt, local 2-opt, task swap operator fail to improve the cost 10 times in succession, and the sample swap operator 3 times. The algorithm is designed to make the calculation more efficient by applying the improvement operator intensively to the high-quality chromosome.