Implicit depot assignments and rotations in vehicle routing heuristics

Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.     

A hybrid generational genetic algorithm for the periodic vehicle routing problem with time windows

We propose a new population-based hybrid meta-heuristic for the periodic vehicle routing problem with time windows. This meta-heuristic is a generational genetic algorithm that uses two neighborhood-based meta-heuristics to optimize offspring. Local search methods have previously been proposed to enhance the fitness of offspring generated by crossover operators. In the proposed method, neighborhood-based meta-heuristics are used for their capacity to escape local optima, and deliver optimized and diversified solutions to the population of the next generation. Furthermore, the search performed by the neighborhood-based meta-heuristics repairs most of the constraint violations that naturally occur after the application of the crossover operators. The genetic algorithm we propose introduces two new crossover operators addressing the periodic vehicle routing problem with time windows. The two crossover operators are seeking the diversification of the exploration in the solution space from solution recombination, while simultaneously aiming not to destroy information about routes in the population as computing routes is NP-hard. Extensive numerical experiments and comparisons with all methods proposed in the literature show that the proposed methodology is highly competitive, providing new best solutions for a number of large instances.     

Symmetries of a generic coaction

If B is -algebra of dimension $4\leq n<\infty$ then the finite dimensional irreducible representations of the compact quantum automorphism group of B, say , have the same fusion rules as the ones of SO(3). As consequences, we get (1) a structure result for in the case where B is a matrix algebra (2) if then the dual is not amenable (3) if then the fixed point subfactor has index n and principal graph . Received: 3 December 1998 / in final form: 8 January 1999     

Heuristics for multi-attribute vehicle routing problems: A survey and synthesis

The attributes of vehicle routing problems are additional characteristics or constraints that aim to better take into account the specificities of real applications. The variants thus formed are supported by a well-developed literature, including a large variety of heuristics. This article first reviews the main classes of attributes, providing a survey of heuristics and meta-heuristics for Multi-Attribute Vehicle Routing Problems (MAVRP). It then takes a closer look at the concepts of 64 remarkable meta-heuristics, selected objectively for their outstanding performance on 15 classic MAVRP with different attributes. This cross-analysis leads to the identification of “winning strategies” in designing effective heuristics for MAVRP. This is an important step in the development of general and efficient solution methods for dealing with the large range of vehicle routing variants.     

Optimal shape of a strongest inverted column

By using Pontryagin's maximum principle we determine the shape of the strongest column positioned in a constant gravity field, simply supported at the lower end and clamped at upper end (with the possibility of axial sliding). It is shown that the cross-sectional area function is determined from the solution of a nonlinear boundary value problem. A variational principle for this boundary value problem is formulated and two first integrals are constructed. These integrals lead to an a priori estimate of the value of one the missing initial condition and to the reduction of the order of the system. The optimal shape of a column is determined by numerical integration.     

Exact controllability for the magnetohydrodynamic equations

We study the local exact controllability of the steady state solutions of the magnetohydrodynamic equations. The main result of the paper asserts that the steady state solutions of these equations are locally controllable if they are smooth enough. We reduce the local exact controllability of the steady state solutions of the magnetohydrodynamic equations to the global exact controllability of the null solution of the linearized magnetohydrodynamic system via a fixed‐point argument. The treatment of the reduced problem relies on two Carleman‐type inequalities for the backward adjoint system. © 2003 Wiley Periodicals, Inc.     

Path Relinking, Cycle-Based Neighbourhoods and Capacitated Multicommodity Network Design

In this paper, we propose a path relinking procedure for the fixed-charge capacitated multicommodity network design problem. Cycle-based neighbourhoods are used both to move along paths between elite solutions and to generate the elite candidate set by a tabu-like local search procedure. Several variants of the method are implemented and compared. Extensive computational experiments indicate that the path relinking procedure offers excellent results. It systematically outperforms the cycle-based tabu search method in both solution quality and computational effort and offers the best current meta-heuristic for this difficult class of problems.     

Quantum automorphism groups of vertex-transitive graphs of order ≤ 11

We study quantum automorphism groups of vertex-transitive graphs having less than 11 vertices. With one possible exception, these can be obtained from cyclic groups , symmetric groups S _n and quantum symmetric groups , by using various product operations. The exceptional case is that of the Petersen graph, and we present some questions about it.     

The Laplacian subalgebra of is a strongly singular masa

In this paper, we present a new class of strongly singular maximal abelian subalgebras living inside the -folded tensor product of the free group factor with itself (). The notions of strongly singular masas in type factors and that of asymptotic homomorphism were introduced by A. Sinclair and R. Smith. One of their first examples was the Laplacian subalgebra of the free group factor, generated by the sum of words of length 1 in . This subalgebra was known to be a singular masa. Using the results of A. Sinclair and R. Smith, we show that the unique trace-preserving conditional expectation onto the Laplacian subalgebra of is an asymptotic homomorphism, and hence the Laplacian subalgebra is a strongly singular masa for every .