Multilevel refinement strategies for the capacity vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL algorithm, which uses a combination of standard VRP heuristics, is developed first to solve instances of the VRP. A ML version, which extends the global view of these heuristics, is then created, using variants of the construction and improvement heuristics at each level. Finally some multilevel enhancements are developed. Experimentation is used to find suitable parameter settings and the final version is tested on two well-known VRP benchmark suites. Results comparing both SL and ML algorithms are presented.

The application of multilevel refinement to the vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL heuristic, termed the combined node-exchange composite heuristic (CNCH), is developed first to solve instances of the VRP. A ML version (the ML-CNCH) is then created, using the construction and improvement heuristics of the CNCH at each level. Experimentation is used to find a suitable combination, which extends the global view of these heuristics. Results comparing both SL and ML are presented.

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

Multilevel approaches applied to the capacitated clustering problem

This paper presents two multilevel refinement algorithms for the capacitated clustering problem. Multilevel refinement is a collaborative technique capable of significantly aiding the solution process for optimisation problems. The central methodologies of the technique are filtering solutions from the search space and reducing the level of problem detail to be considered at each level of the solution process. The first multilevel algorithm uses a simple tabu search while the other executes a standard local search procedure. Both algorithms demonstrate that the multilevel technique is capable of aiding the solution process for this combinatorial optimisation problem.

Postcolonial futures: postcolonial literature and the Obama moment

In an analysis of President Obama's Acceptance Speech, this article argues that postcolonial theory is now being re-formulated for a global, transnational sensibility.

Postcolonial futures: postcolonial literature and the Obama moment

Since the late 1970s the western academy has encouraged the development of postcolonial literary theory and the formulation of a postcolonial literary canon existing outside the prescriptive narratives of the ‘mother’ country and empire. Having lost faith in the binary oppositions underpinning such narratives, we turned to alternative fictions that contested the construction of the ‘other’, the world divided between the ‘West and the Rest’. The publication of Edward Said’s Orientalism in 1978 marked the beginning of the discipline now known as postcolonial studies with its new ways of understanding ‘the west’s’ relationship with ‘the east’ and, by extension, all the former colonies of empire. Despite these radical origins, however, postcolonialism’s more recent emphasis on the psychological and its affirmation of the hybrid text and self has, for many, served to obscure real economic social realities that have very little to do with the magical or wondrous textual expression of a postcolonial identity. This paper considers problems associated with defining the postcolonial and proposes that, in a literary context, we broaden its meaning to include texts traditionally outside the category of postcolonial literature. To extend the meaning of postcolonial is timely as we are now witnessing its relocation from ‘margin’ to ‘centre’ with the election of Barack Obama. This moment may be seen as a disruption of conventional understandings of what constitutes postcolonial literature, essentially as oppositional discourse that could only define itself as peripheral to, or ‘post’, metropolitan and economic concerns. [From the Author]

Recovery from TBT pollution in English Channel environments: A problem solved?

Following recognition of effects in the 1980s, tributyltin (TBT) has been monitored at sites in the English Channel to evaluate the prognosis for biota – spanning the introduction of restrictions on TBT use on small boats and the recent phase-out on the global fleet. We describe how persistence and impact of TBT in clams Scrobicularia plana has changed during this period in Southampton Water and Poole Harbour. TBT contamination (and loss) in water, sediment and clams reflects the abundance and type of vessel activity: half-times in sediment (up to 8y in Poole, 33y in Southampton) are longest near commercial shipping. Recovery of clam populations – slowest in TBT-contaminated deposits – provides a useful biological measure of legislative efficacy in estuaries. On rocky shores, recovery from imposex in Nucella lapillus is evident at many sites but, near ports, is prolonged by shipping impacts, including sediment legacy, for example, in the Fal.