Multilevel refinement for the vehicle routing problem

Multilevel approaches to computational problems are pervasive across many areas of applied mathematics and scientific computing. The multilevel paradigm uses recursive coarsening to create a hierarchy of approximations to the original problem, then an initial solution is found for the coarsest problem and iteratively refined and improved at each level, coarsest to finest. The solution process is aided by the global perspective (or `global view') imparted to the optimisation by the coarsening. This paper looks at their application to the Vehicle Routing Problem.

Multilevel refinement for combinatorial optimisation problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

Using set operations to deal with the frame problem

This paper presents a simple approach to the so-called frame problem based on some ordinary set operations, which does not require non-monotonic reasoning. Following the notion of the situation calculus, we shall represent a state of the world as a set of fluents, where a fluent is simply a Boolean-valued property whose truth-value is dependent on the time. High-level causal laws are characterised in terms of relationships between actions and the involved world states. An effect completion axiom is imposed on each causal law, which guarantees that all the fluents that can be affected by the performance of the corresponding action are always totally governed. It is shown that, compared with other techniques, such a set operation based approach provides a simpler and more effective treatment to the frame problem.

Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

Numerical optimisation techniques applied to evacuation analysis

A common problem faced by fire safety engineers in the field of evacuation analysis concerns the optimal design of an arbitrarily complex structure in order to minimise evacuation times. How does the engineer determine the best solution? In this study we introduce the concept of numerical optimisation techniques to address this problem. The study makes user of the buildingEXODUS evacuation model coupled with classical optimisation theory including Design of Experiments (DoE) and Response Surface Models (RSM). We demonstrate the technique using a relatively simple problem of determining the optimal location for a single exit in a square room.

The food multimix concept: new innovative approach to meeting nutritional challenges in Sub-Saharan Africa

Food insecurity, chronic hunger, starvation and malnutrition continue to affect millions of individuals throughout the developing world, especially Sub-Saharan Africa. Various initiatives by African governments and International Agencies such as the UN, the industrial nations, the International Monetary Fund, the World Bank and the World Trade Organisation to boost economic development, have failed to provide the much-needed solution to these challenges. The impact of these economic shifts and the failures of structural adjustment programmes on the nutritional well-being and health of the most vulnerable members of poor communities cannot be over-emphasised. The use of ad hoc measures as an adjunct to community-based rural integrated projects have provided little success and will be unsustainable unless they are linked to harnessing available local resources. The present paper therefore focuses on exploring alternative ways of harnessing the scant agricultural resources by employing a scientific approach to food-related problem-solving. The food multimix (FMM) concept offers a scientific contribution alongside other attempts currently in use by the World Food Programme, WHO and FAO to meet the food insecurity challenges that confront most of the developing world in the twenty-first century. It is an innovative approach that makes better use of traditional food sources as a tool for meeting community nutritional needs. The FMM concept employs a food-based approach using traditional methods of food preparation and locally-available, cheap and affordable staples (fruits, pulses, vegetables and legumes) in the formulation of nutrient-enriched multimixes. Developed recipes can provide >= 40% of the daily nutritional requirements of vulnerable groups, including patients with HIV/AIDS and children undergoing nutrition rehabilitation. The FMM approach can also be used as a medium- to long-term adjunct to community-based rural integration projects aimed at health improvement and economic empowerment in Sub-Saharan Africa.

Models of advertising standardisation and adaptation: it's time to move the debate forward

Advertising standardisation versus adaptation has been discussed in some detail in the marketing literature. Despite previous attempts, there is still no widely-used decision-making model available that has been accepted by marketing practitioners and academics. This paper examines the development of this important area by reviewing six prominent models in the advertising standardisation/adaptation literature. It shows why there has been a lack of development in the current literature and why it is crucial to address this problem. Important areas for future research are suggested in order to find a solution