A parameter-free approach for solving combinatorial optimization problems through biased randomization of efficient heuristics

This paper discusses the use of probabilistic or randomized algorithms for solving combinatorial optimization problems. Our approach employs non-uniform probability distributions to add a biased random behavior to classical heuristics so a large set of alternative good solutions can be quickly obtained in a natural way and without complex conguration processes. This procedure is especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods, both of exact and approximate nature, may fail to reach their full potential. The results obtained are promising enough to suggest that randomizing classical heuristics is a powerful method that can be successfully applied in a variety of cases.

Incorporating waiting time in competitive location models: formulations and heuristics

In this paper we propose a metaheuristic to solve a new version of the Maximum Capture Problem. In the original MCP, market capture is obtained by lower traveling distances or lower traveling time, in this new version not only the traveling time but also the waiting time will affect the market share. This problem is hard to solve using standard optimization techniques. Metaheuristics are shown to offer accurate results within acceptable computing times.

Adaptive approach heuristics for the generalized assignment problem

The Generalized Assignment Problem consists in assigning a setof tasks to a set of agents with minimum cost. Each agent hasa limited amount of a single resource and each task must beassigned to one and only one agent, requiring a certain amountof the resource of the agent. We present new metaheuristics forthe generalized assignment problem based on hybrid approaches.One metaheuristic is a MAX-MIN Ant System (MMAS), an improvedversion of the Ant System, which was recently proposed byStutzle and Hoos to combinatorial optimization problems, and itcan be seen has an adaptive sampling algorithm that takes inconsideration the experience gathered in earlier iterations ofthe algorithm. Moreover, the latter heuristic is combined withlocal search and tabu search heuristics to improve the search.A greedy randomized adaptive search heuristic (GRASP) is alsoproposed. Several neighborhoods are studied, including one basedon ejection chains that produces good moves withoutincreasing the computational effort. We present computationalresults of the comparative performance, followed by concludingremarks and ideas on future research in generalized assignmentrelated problems.

Consumer choice in competitive location models: Formulations and heuristics

A new direction of research in Competitive Location theory incorporatestheories of Consumer Choice Behavior in its models. Following thisdirection, this paper studies the importance of consumer behavior withrespect to distance or transportation costs in the optimality oflocations obtained by traditional Competitive Location models. To dothis, it considers different ways of defining a key parameter in thebasic Maximum Capture model (MAXCAP). This parameter will reflectvarious ways of taking into account distance based on several ConsumerChoice Behavior theories. The optimal locations and the deviation indemand captured when the optimal locations of the other models are usedinstead of the true ones, are computed for each model. A metaheuristicbased on GRASP and Tabu search procedure is presented to solve all themodels. Computational experience and an application to 55-node networkare also presented.

Incorporating waiting time in competitive location models: Formulations and heuristics

In this paper we propose a metaheuristic to solve a new version of the Maximum CaptureProblem. In the original MCP, market capture is obtained by lower traveling distances or lowertraveling time, in this new version not only the traveling time but also the waiting time willaffect the market share. This problem is hard to solve using standard optimization techniques.Metaheuristics are shown to offer accurate results within acceptable computing times.

Scheduling forest road maintenance using the analytic hierarchy process and heuristics

Abstract

Simple Heuristics in a Social Game

Simple Heuristics in a Social World invites readers to discover the simple heuristics that people use to navigate the complexities and surprises of environments populated with others. The social world is a terrain where humans and other animals compete with conspecifics for myriad resources, including food, mates, and status, and where rivals grant the decision maker little time for deep thought, protracted information search, or complex calculations. Yet, the social world also encompasses domains where social animals such as humans can learn from one another and can forge alliances with one another to boost their chances of success. According to the book's thesis, the undeniable complexity of the social world does not dictate cognitive complexity as many scholars of rationality argue. Rather, it entails circumstances that render optimization impossible or computationally arduous: intractability, the existence of incommensurable considerations, and competing goals. With optimization beyond reach, less can be more. That is, heuristics--simple strategies for making decisions when time is pressing and careful deliberation an unaffordable luxury--become indispensible mental tools. As accurate as or even more accurate than complex methods when used in the appropriate social environments, these heuristics are good descriptive models of how people make many decisions and inferences, but their impressive performance also poses a normative challenge for optimization models. In short, the Homo socialis may prove to be a Homo heuristicus whose intelligence reflects ecological rather than logical rationality.