Xxxx Search Heuristics Sample Clauses

Xxxx Search Heuristics. ‌ A first algorithm used in research on the TTP is a xxxx search based heuristic. The xxxx search approach for TTP was introduced by Xx Xxxxxxx and Xxxxxxx (2007). This method dives deeper into the neighbourhood of certain moves and makes use of a xxxx list in order to search for new schedules in a more efficient way. The program is extended with a local search algorithm to improve the search for a (near) optimal solution. The xxxx search heuristic is equipped with its own cost function based on the total distance to be travelled and the number of violated constraints. Two constraints, C4 and C5 (Section 2.1), are defined as soft constraints. Violations against these create an infeasible schedule and are penalised in the cost function. To perform a local search, the algorithm uses the five move operators proposed by Xxxxxxxxxxxxxxx et al. (2006): 1. SwapHomes: swap venues for two teams in two different rounds 2. SwapTeams: swap two teams in all rounds 3. SwapRounds: swap two complete rounds 4. PartialSwapTeams: change the opponents for two teams in one round 5. PartialSwapRounds: swap the opponents of one team in two rounds Since the last two move operators might create a schedule that falls outside the search space, an ejection chain should be included (Xx Xxxxxxx & Xxxxxxx, 2007). An ejection chain for the TSP is defined by Xxxxxx (1992) as follows: “An ejection chain is initiated by selecting a set of elements to undergo a change of state (e.g. to occupy new positions or receive new values). The result of this change leads to identifying a collection of other sets, with the property that the elements of at least one must be “ejected from” their current states.” The translation to the TTP problem is the following. When a schedule undergoes a certain swap operation where several elements are changed, the newly created schedule might fall outside the search space, i.e. violations against constraints C1, C2 or C3 (Section 2.1) can occur. This calls for an ejection chain that will change critical elements in the schedule in order to make it part of the search space again. However, it is not guaranteed that the new schedule will be part of the solution space, i.e. the new schedule might violate constraints C4 and C5. To improve efficiency and to avoid not detecting a move on the xxxx list, Xx Xxxxxxx and Xxxxxxx (2007) execute a neighbourhood analysis to determine move operators that have the same end result. The cardinality of both move operator 3 & 5, and 4...