Vehicle and personnel routing optimization in the service sector: application to water distribution and treatment

We present an overview of the author’s Ph.D. thesis, supervised by P. Dejax and N. Bostel, which was defended in February 2006 at école des Mines de Nantes, France. The thesis is written in French, and is available at . It was conducted in the context of a research contract with a water distribution company. In a first section, we define multiperiod routing problems for service technicians. In a second section, we present some heuristics and a memetic algorithm used to solve these problems. The third section introduces optimal and near-optimal approaches based on column generation. Finally, we present some applications to the real-life case. The methods presented in Sects. 2, 3 and 4 were tested over several sets of problems, based on real-life statistics provided by the company.      

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

The k-means range algorithm for personalized data clustering in e-commerce

This paper describes the k-means range algorithm, a combination of the partitional k-means clustering algorithm with a well known spatial data structure, namely the range tree, which allows fast range searches. It offers a real-time solution for the development of distributed interactive decision aids in e-commerce since it allows the consumer to model his preferences along multiple dimensions, search for product information, and then produce the data clusters of the products retrieved to enhance his purchase decisions. This paper also discusses the implications and advantages of this approach in the development of on-line shopping environments and consumer decision aids in traditional and mobile e-commerce applications.     

COSEARCH: A Parallel Cooperative Metaheuristic

In order to design a well-balanced metaheuristic for robustness, we propose the COSEARCH approach which manages the cooperation of complementary heuristic methods via an adaptive memory which contains a history of the search already done. In this paper, we present the idiosyncrasies of the COSEARCH approach and its application for solving large scale instances of the quadratic assignment problem (QAP). We propose an original design of the adaptive memory in order to focus on high quality regions of the search and avoid attractive but deceptive areas. For the QAP, we have hybridized three heuristic agents of complementary behaviours: a Tabu Search is used as the main search algorithm, a Genetic Algorithm is in charge of the diversification and a Kick Operator is applied to intensify the search. The evaluations have been executed on large scale network of workstations via a parallel environment which supports fault tolerance and adaptive dynamic scheduling of tasks.     

Tree-edges deletion problems with bounded diameter obstruction sets

We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems.     

Fast computation of a rational point of a variety over a finite field

We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bézout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.

     

关于Fuzzy聚类分析及其在脊髓灰质炎中的应用

本文用Fuzzy数学的观点探讨了Fuzzy聚类分析，并通过对脊髓灰质炎病毒抗体水平的Fuzzy聚类分析，获得了良好的聚类效果，为该项问题的研究提供了科学依据。     

Hereditary optimal control problems: Numerical method based upon a padé approximation

In this paper, we consider a particular approximation scheme which can be used to solve hereditary optimal control problems. These problems are characterized by variables with a time-delayed argumentx(t – ). In our approximation scheme, we first replace the variable with an augmented statey(t) x(t - ). The two-sided Laplace transform ofy(t) is a product of the Laplace transform ofx(t) and an exponential factor. This factor is approximated by a first-order Padé approximation, and a differential relation fory(t) can be found. The transformed problem, without any time-delayed argument, can then be solved using a gradient algorithm in the usual way. Four problems are solved to illustrate the validity and usefulness of this technique.This research was supported in part by the National Aeronautics and Space Administration under NASA Grant NCC-2-106.     

遗传算法在构象搜寻中的应用

遗传算法是一种模仿自然进化进程的新颖的启发式优化方法。通过它，人们可以在计算机上对所需的各种问题实施进化操作，最终产生理想的结果。遗传算法现已被广泛于计算机辅助设计、工程设计、系统模拟等领域并取得了极大的成功。本文拟对遗传算法在对大、中、小分子的构象搜寻中的应用作一较全面的综述。     

Multivariate calibration of near infrared spectra by orthogonal WAVElet correction using a genetic algorithm

Orthogonal WAVElet correction (OWAVEC) is a pre-processing method aimed at simultaneously accomplishing two essential needs in multivariate calibration, signal correction and data compression, by combining the application of an orthogonal signal correction algorithm to remove information unrelated to a certain response with the great potential that wavelet analysis has shown for signal processing. In the previous version of the OWAVEC method, once the wavelet coefficients matrix had been computed from NIR spectra and deflated from irrelevant information in the orthogonalization step, effective data compression was achieved by selecting those largest correlation/variance wavelet coefficients serving as the basis for the development of a reliable regression model. This paper presents an evolution of the OWAVEC method, maintaining the first two stages in its application procedure (wavelet signal decomposition and direct orthogonalization) intact but incorporating genetic algorithms as a wavelet coefficients selection method to perform data compression and to improve the quality of the regression models developed later. Several specific applications dealing with diverse NIR regression problems are analyzed to evaluate the actual performance of the new OWAVEC method. Results provided by OWAVEC are also compared with those obtained with original data and with other orthogonal signal correction methods.