China
Africa
Explore chapters and articles related to this topic
Advanced Algorithms for the Layout Problem
Published in Sunderesh S. Heragu, Facilities Design, 2022
To explain simulated annealing, we examine how it differs from simple improvement algorithms such as the 2-opt, 3-opt, or CRAFT algorithms discussed in Chapter 9. A primary distinction is that local optimization algorithms often restrict their search for the optimal solution in a downhill direction. In other words, the initial solution is changed only if it results in a decrease in the OFV for minimization problems; similarly, for maximization problems, a new solution is accepted only if it results in an increase in the OFV. Although this may help us find a local optimum solution, in many cases, that solution may be inferior to the global optimum solution. Moreover, the local optimum solution for 2-opt (or 3-opt) is dependent upon the local region in which the search takes place, which itself is determined by the initial solution provided to it. To overcome this entrapment in local optima, the local search algorithm is modified to allow it to back out of poor local optimal regions and explore other regions, so the chances of finding a better solution are greatly increased. This is the essence of the simulated annealing algorithm.
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
After a cycle is implemented and the solution is updated, 3 -opt is applied to maintain within route optimality. Now, the improvement graph needs to be regenerated based on the updated solution. The practice of only updating the improvement graph rather than reconstructing it all over again is evaluated. Although it would save some time, it was insignificant comparing with the implementation complications it would invoke. Since our graph is quite big and many routes are involved in a single iteration, updating instead of reconstructing it is not very beneficial. Furthermore, since the computational time spent on constructing the improvement graph is of the same order as the time spent on finding a negative cycle, it would probably not help much even if the time on generating the improvement graph can be cut down, unless a better algorithm is also used for negative cycle detection. For problems of smaller sizes, where the number of routes that are affected in any particular iteration are much smaller than the total number of routes, updating the improvement graph rather than reconstructing it can save significant amount of time.
Introduction to Extremal Optimization
Published in Yong-Zai Lu, Yu-Wang Chen, Min-Rong Chen, Peng Chen, Guo-Qiang Zeng, Extremal Optimization, 2018
Yong-Zai Lu, Yu-Wang Chen, Min-Rong Chen, Peng Chen, Guo-Qiang Chen
Then, 3-opt move is used to update the states of selected cities. In 3-opt, the rearrangement process breaks the tour into three segments C1, C2, and C3 by deleting three edges, and then reorders the segments as C2, C1, and C3 and relinks them to form a new tour (Cirasella et al., 2001), as illustrated in Figure 2.5. Each 3-opt move simultaneously updates the states of three cities: p, q, and r.
An effective heuristic based on 3-opt strategy for seru scheduling problems with learning effect
Published in International Journal of Production Research, 2023
Zhe Zhang, Xiaoling Song, Xue Gong, Yong Yin, Benjamin Lev, Xiaoyang Zhou
According to 3-opt strategy, the tour is broken into three paths by deleting three edges, and then reconnected in the other possible ways and the best one will be selected. Repeat this breaking and reconnecting process until no improvement can be found (Bellmore and Nemhauser 1968; Gülcü et al. 2018; Tuani, Keedwell, and Collett 2020). Accordingly, given a sequence of jobs circled along with the assignment in serus, the 3-opt strategy breaks down the job sequence by edges to three blocks, denoted as , respectively. Without loss of generality, let , , , then there will be eight cases for the reconnection in 3-opt, see Figure 4. (V), (VI), (VII) and (VIII) in Figure 4 are special cases of 3-opt, in which (V) is 1-opt (original sequence), and (VI), (VII) and (VIII) are 2-opt, respectively. For three blocks , there are six orders for them as 1, 2, 3; 1, 3, 2; 2, 1, 3; 3, 1, 2; 2, 3, 1; 3, 2, 1. Let right arrow represent jobs in this block performed in clockwise and left arrow represent those in counterclockwise, then there are eight scenarios in each order. Hence, there are 48 moves in total for choosing a new order in each step, see Figure 4.
Electric vehicle routing problem with flexible deliveries
Published in International Journal of Production Research, 2022
Mir Ehsan Hesam Sadati, Vahid Akbari, Bülent Çatay
To reduce the computational effort, we employ GTS that evaluates promising moves only and omits a significant number of unpromising ones. This approach considers an arc or a node in a move if its cost does not exceed the granularity threshold defined as , where represents the objective function value of the initial solution, and are the numbers of customers and routes in the solution, respectively. The granularity threshold is updated after every iteration by setting the threshold to , where , and denote the objective function value, number of routes, and number of customers of the best solution obtained by GVNS/GTS, respectively. GTS is supported by an intensification strategy to improve the new incumbent solution (Hirsch and Gronalt 2007; Aras, Aksen, and Tekin 2011). When we find a new incumbent solution, we apply 3-Opt as a local post-optimisation procedure in an attempt to further improve it. 3-Opt breaks three arcs and replaces them with the other three within a route.