【導(dǎo)讀】objectiveisto?clanes,intersections,andvehicle?likelyto?conveyorsetc.)converge.candvehicle-?Commonly-foundconstraintsa?

　　

【正文】 egies using penalties, modifying underlying decision criterion and selecting the next move among those neighborhood moves with di?erent probabilities which are based on di?erent evaluation values . In this section, we describe how it can be employed for the crane scheduling problem. Neighborhood Structure From an initial feasible solution obtained by a greedy method or a random cranejob assign－ ment, the graph representation bees almost edge ―saturated‖, . we can hardly add an edge without violating the Noncrossing, Neighborhood and Jobseparation constraints. We can however delete an edge from the current solution and try to add other edges until it is ―saturated‖ again. Deleting the edge which connects crane c and job j allows some cranes and jobs to bee assignable. Obviously, these 11 can only e from cranes and jobs which are neighbors to c and j, respectively, which do not violate the Noncrossing constraint . all current assignments (discounting the c to j assignment). Jobs selected must also satisfy the Neighborhood and Jobseparation constraints. After deleting the edge connecting c to j, we consider each neighbor of c from these feasible neighbors together with c, one by one. For each crane, we assign a probability p1for it to be selected for a job. For each selected crane, we have two types of assignments: one is a greedy assignment which selects a patible job with the largest weight。 the other is a random assignment which randomly picks one job from all the patible jobs. Which scheme is chosen depends on yet another probability, p2. Tabu Search Memory TS memory structures guide the search process. There are two kinds of memory structures. One is ―shortterm memory‖, which can prevent the search from being trapped in a local optimum and the other is ―longterm memory‖, which provides diversi?cation and inten－ si?cation. Shortterm memory restricts the position of new solutions generated. If an edge is deleted in a move, we forbid its addition in the next few moves。 similarly, if an edge is added in a move, we forbid its deletion in the next few moves. Such a mechanism prevents the search from revisiting local optima in the short term and reduces the chance of cycling in the long term. How long a restriction is in e?ect depends on a tabu tenure parameter, which identi?es the number of iterations a particular restriction remains in force . We implemented short term memory using a recencybased memory structure as follows. Let iter denote the current iteration number, tabu add(x, y) and tabu delete(x, y) denote future iteration values that forbid a reversal of the moves on adding edge (x, y) or deleting edge (x, y). Furthermore, let tabu add tenure and tabu delete tenure be the values of tabu tenure for these two moves. When the TS restriction is imposed, we update the recency memory by: tabu add(x, y) = iter + tabu add tenure tabu delete(x, y) = iter + tabu delete tenure We assign positive penalties to edges in tabu status, which means they are forbidden by the recency memory. A TS restriction is overridden by aspiration if the oute of the move under consideration is su?ciently desirable. This can be achieved by deducting a large number 12 from the total penalty. Move Evaluation After ?nding all neighborhood candidate moves, we evaluate these moves so that they are ready for selection. The resulting evaluation value is in two parts: the total pro?t and the penalties. For our crane scheduling problem, the penalties prise: (1) Shortterm memory penalties which include tabu status penalties as well as aspiration satisfaction ―penalties‖ (2) Longterm memory penalties which include transition measure and residence measure penalties and (3) Penalties for other biases. Probabilistic Move Selection After evaluating all candidate moves, we select one move to proceed. The fundamental idea of move selection is to choose the best move, ., choose the move with the highest evaluation. However, we found that this greedy selection strategy is strongly biased. We therefore made adjustments using probabilities. The strategy for a probabilistic move selection is given as follows: 1. Generate the candidate list and evaluate candidate moves which have described above 2. Select the move from the candidate list with the highest evaluation value 3. Accept the move with probability p and exit。 otherwise, go to (4). Here, p is a param eter and is set to in the algorithm 4. Remove the move from the candidate list. If the list is empty, accept the ?rst move of the original candidate list and exit. Otherwise, go to (2). It is easily shown that the probability of choosing one of the best k moves is 1 ? (1 ? p)k, which is large even if p is not large. For example, if p is , the probability of choosing the best 5 moves is , the best 10 moves is . We can therefore choose relatively high evaluation moves while avoiding favoring those with highest evaluations always. SWO with Local Search Approach ―Squeaky Wheel‖ Optimization (SWO) is a general approach to optimization and consists of a ConstructAnalyzePrioritize cycle at its core. The Analyzer will assign a numerical ‖blame‖ value to the problem elements that contribute to shortings in the current solution. The Prioritizer will modify sequences of problem elements and 13 elements that received blame are moved to the front of the sequence. The higher the blame, the further the element is moved. The Constructor deals with problem elements according to the modi?ed sequence in the next iteration. The cycle repeats until a termination condition is satis?ed. The SWO algorithm has been e?ective in job scheduling and graph coloring problems and outperforms TS and integer programming in some applications. Although SWO strives to avoid getting trapped in local op