Heuristic search

Since scope economies are especially hard to quantify, a separate class of optimization models solely dealing with plant loading decisions can be found. For example, Mazzola and Schantz (1997) propose a non-linear mixed integer program that combines a fixed cost charge for each plant-product allocation, a fixed capacity consumption to reflect plant setup and a non-linear capacity-consumption function of the total product portfolio allocated to the plant. To develop the capacity consumption function the authors build product families with similar processing requirements and consider effects from intra- and inter-product family interactions. Based on a linear relaxation the authors explore both tabu-search heuristics and branch-and-bound algorithms to obtain solutions. 

To arrive at a true optimal subset of variables (wavelengths) for a given data set, consideration of all possible combinations should in principle be used but it is computationally prohibitive. Since each variable can either appear, or not, in the equation and since this is true with every variable, there are 2"-possible equations (subsets) altogether. For spectral data containing 500 variables, this means 2 possibilities. For this type of problems, i.e. for search of an optimal solution out of the millions possible, the stochastic search heuristics, such as Genetic Algorithms or Simulated Annealing, are the most powerful tools [14,15]. 

TaiUard, E., Badeau, P., Gendreau, M., Guertin, R, and Potvin, J. (1997), A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows, Transportation Science, Vol. 31, pp. 170-186. 

Wagner, B. and Davis, D. A search heuristic for the sequence-dependent economic lot scheduling problem. European Journal of Operational Research, 141(1) 133-146, 2002. 

For the last few decades, research on VRP has attracted a lot of attention along with traveling salesman problem which is similar to VRP in many ways. However, the research on TTRP is relatively scarce. Most people treat TTRP as a variant of VRP and had not given it a name until 2002 when Chao (2002) first named such a problem as TTRP and used a tabu search heuristic to solve 21 TTRPs adapted firom the classical 7 VRPs of Christofides et al. (1979). Since then, this topic draws increasing notice and many more heuristics and metaheuristics were developed to solve this problem. 

Chao (2002) developed a sophisticated tabu search method consisting of an initial constmction heuristic and a tabu search improvement heuristic to search the neighborhood of an initial solution and hence refine them. The method contains standard VRP moves as well as a new TTRP-specific root-defining move where the roots of sub-tours are changed to new customers. Four years later, Scheuerer (2006) extended Chao s work to develop a better tabu search heuristic that outperforms the Chao s method. Scheurer made use of two new construction heuristics called the T-Cluster and T-Sweep. The new construction heuristics proved to successfiilly find good initial solutions for TTRP. He was able to obtain better results in each of the 21 instances Chao (2002) adapted. 

A top-level design is illustrated in Fig. 3. Note that local search is applied to many steps including constmction heuristics, crossover, mutation, and selection. This is to prevent any unexploited space missed in each of the global search heuristic steps. 

Scheuerer S (2006) A tabu search heuristic for the truck and trailer routing poblem. Comput Oper Res 33 894-909... 

Renaud J, Laporte G, Boctor EF (1996) A tabu search heuristics for the multi-depot vehicle routing problem. Comput Oper Res 23(3) 229-235... 

Franca P., Gendreau M., Laporte G., Muller F. (1996). A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times. International Journal of Production Economics, 43, pp. 79-89... 

The GA is a parallel search heuristic that works on the process of natural biological evolution. GA is a widely used tool for optimisation and fast search applications. 

The evolutionary process is repeated until a stop criteria has been met. Here such a criteria is an impossibility to improve solutions with any of the presented local search heuristics. 

Keywords local search, stochastic local search, heuristic information,... 

While we portray the structure of matter in an hierarchical scheme, we also recognise that searching the structures is done at various levels of precision exact match, non-exact match with false positives allowed, non-exact match with false negatives allowed, fuzzy searches, heuristic searches, and similarity searches. Similarity searches themselves can be done at many adjustable levels, and similarity itself is multidimensional. 

Droste, S., Jansen, T., Wegener, I. (2002). Optimization with randomized search heuristics the (a)nfl theorem, realistic scenarios, and difficult functions. Theoretical Computer Science, 287, 131-144. 

---