Efficient tool path computation using multi-core GPUs

Tool path generation is one of the most complex problems in Computer Aided Manufacturing. Although some efficient strategies have been developed, most of them are only useful for standard machining. However, the algorithms used for tool path computation demand a higher computation performance, which makes the implementation on many existing systems very slow or even impractical. Hardware acceleration is an incremental solution that can be cleanly added to these systems while keeping everything else intact. It is completely transparent to the user. The cost is much lower and the development time is much shorter than replacing the computers by faster ones. This paper presents an optimisation that uses a specific graphic hardware approach using the power of multi-core Graphic Processing Units (GPUs) in order to improve the tool path computation. This improvement is applied on a highly accurate and robust tool path generation algorithm. The paper presents, as a case of study, a fully implemented algorithm used for turning lathe machining of shoe lasts. A comparative study will show the gain achieved in terms of total computing time. The execution time is almost two orders of magnitude faster than modern PCs.

Improving kNN multi-label classification in Prototype Selection scenarios using class proposals

Prototype Selection (PS) algorithms allow a faster Nearest Neighbor classification by keeping only the most profitable prototypes of the training set. In turn, these schemes typically lower the performance accuracy. In this work a new strategy for multi-label classifications tasks is proposed to solve this accuracy drop without the need of using all the training set. For that, given a new instance, the PS algorithm is used as a fast recommender system which retrieves the most likely classes. Then, the actual classification is performed only considering the prototypes from the initial training set belonging to the suggested classes. Results show that this strategy provides a large set of trade-off solutions which fills the gap between PS-based classification efficiency and conventional kNN accuracy. Furthermore, this scheme is not only able to, at best, reach the performance of conventional kNN with barely a third of distances computed, but it does also outperform the latter in noisy scenarios, proving to be a much more robust approach.

Software for video-based multi-point frequency measuring and mapping

Complementary programs

Aid decision algorithms to estimate the risk in congenital heart surgery

Background and objective: In this paper, we have tested the suitability of using different artificial intelligence-based algorithms for decision support when classifying the risk of congenital heart surgery. In this sense, classification of those surgical risks provides enormous benefits as the a priori estimation of surgical outcomes depending on either the type of disease or the type of repair, and other elements that influence the final result. This preventive estimation may help to avoid future complications, or even death. Methods: We have evaluated four machine learning algorithms to achieve our objective: multilayer perceptron, self-organizing map, radial basis function networks and decision trees. The architectures implemented have the aim of classifying among three types of surgical risk: low complexity, medium complexity and high complexity. Results: Accuracy outcomes achieved range between 80% and 99%, being the multilayer perceptron method the one that offered a higher hit ratio. Conclusions: According to the results, it is feasible to develop a clinical decision support system using the evaluated algorithms. Such system would help cardiology specialists, paediatricians and surgeons to forecast the level of risk related to a congenital heart disease surgery.

Plasticité du cortex visuel: «homéodynamie» des connexions neuronales et modèle d’effets d’antidépresseurs

Les informations sensorielles sont traitées dans le cortex par des réseaux de neurones co-activés qui forment des assemblées neuronales fonctionnelles. Le traitement visuel dans le cortex est régit par différents aspects des caractéristiques neuronales tels que l’aspect anatomique, électrophysiologique et moléculaire. Au sein du cortex visuel primaire, les neurones sont sélectifs à divers attributs des stimuli tels que l’orientation, la direction, le mouvement et la fréquence spatiale. Chacun de ces attributs conduit à une activité de décharge maximale pour une population neuronale spécifique. Les neurones du cortex visuel ont cependant la capacité de changer leur sélectivité en réponse à une exposition prolongée d’un stimulus approprié appelée apprentissage visuel ou adaptation visuelle à un stimulus non préférentiel. De ce fait, l’objectif principal de cette thèse est d’investiguer les mécanismes neuronaux qui régissent le traitement visuel durant une plasticité induite par adaptation chez des animaux adultes. Ces mécanismes sont traités sous différents aspects : la connectivité neuronale, la sélectivité neuronale, les propriétés électrophysiologiques des neurones et les effets des drogues (sérotonine et fluoxétine). Le modèle testé se base sur les colonnes d’orientation du cortex visuel primaire. La présente thèse est subdivisée en quatre principaux chapitres. Le premier chapitre (A) traite de la réorganisation du cortex visuel primaire suite à une plasticité induite par adaptation visuelle. Le second chapitre (B) examine la connectivité neuronale fonctionnelle en se basant sur des corrélations croisées entre paires neuronales ainsi que sur des corrélations d’activités de populations neuronales. Le troisième chapitre (C) met en liaison les aspects cités précédemment (les effets de l’adaptation visuelle et la connectivité fonctionnelle) aux propriétés électrophysiologiques des neurones (deux classes de neurones sont traitées : les neurones à décharge régulière et les neurones à décharge rapide ou burst). Enfin, le dernier chapitre (D) a pour objectif l’étude de l’effet du couplage de l’adaptation visuelle à l’administration de certaines drogues, notamment la sérotonine et la fluoxétine (inhibiteur sélectif de recapture de la sérotonine). Méthodes En utilisant des enregistrements extracellulaires d’activités neuronales dans le cortex visuel primaire (V1) combinés à un processus d’imagerie cérébrale optique intrinsèque, nous enregistrons l’activité de décharge de populations neuronales et nous examinons l’activité de neurones individuels extraite des signaux multi-unitaires. L’analyse de l’activité cérébrale se base sur différents algorithmes : la distinction des propriétés électrophysiologiques des neurones se fait par calcul de l’intervalle de temps entre la vallée et le pic maximal du potentiel d’action (largeur du potentiel d’action), la sélectivité des neurones est basée sur leur taux de décharge à différents stimuli, et la connectivité fonctionnelle utilise des calculs de corrélations croisées. L’utilisation des drogues se fait par administration locale sur la surface du cortex (après une craniotomie et une durotomie). Résultats et conclusions Dans le premier chapitre, nous démontrons la capacité des neurones à modifier leur sélectivité après une période d’adaptation visuelle à un stimulus particulier, ces changements aboutissent à une réorganisation des cartes corticales suivant un patron spécifique. Nous attribuons ce résultat à la flexibilité de groupes fonctionnels de neurones qui étaient longtemps considérés comme des unités anatomiques rigides. En effet, nous observons une restructuration extensive des domaines d’orientation dans le but de remodeler les colonnes d’orientation où chaque stimulus est représenté de façon égale. Ceci est d’autant plus confirmé dans le second chapitre où dans ce cas, les cartes de connectivité fonctionnelle sont investiguées. En accord avec les résultats énumérés précédemment, les cartes de connectivité montrent également une restructuration massive mais de façon intéressante, les neurones utilisent une stratégie de sommation afin de stabiliser leurs poids de connectivité totaux. Ces dynamiques de connectivité sont examinées dans le troisième chapitre en relation avec les propriétés électrophysiologiques des neurones. En effet, deux modes de décharge neuronale permettent la distinction entre deux classes neuronales. Leurs dynamiques de corrélations distinctes suggèrent que ces deux classes jouent des rôles clés différents dans l’encodage et l’intégration des stimuli visuels au sein d’une population neuronale. Enfin, dans le dernier chapitre, l’adaptation visuelle est combinée avec l’administration de certaines substances, notamment la sérotonine (neurotransmetteur) et la fluoxétine (inhibiteur sélectif de recapture de la sérotonine). Ces deux substances produisent un effet similaire en facilitant l’acquisition des stimuli imposés par adaptation. Lorsqu’un stimulus non optimal est présenté en présence de l’une des deux substances, nous observons une augmentation du taux de décharge des neurones en présentant ce stimulus. Nous présentons un modèle neuronal basé sur cette recherche afin d’expliquer les fluctuations du taux de décharge neuronale en présence ou en absence des drogues. Cette thèse présente de nouvelles perspectives quant à la compréhension de l’adaptation des neurones du cortex visuel primaire adulte dans le but de changer leur sélectivité dans un environnement d’apprentissage. Nous montrons qu’il y a un parfait équilibre entre leurs habiletés plastiques et leur dynamique d’homéostasie.

Plasticité du cortex visuel: «homéodynamie» des connexions neuronales et modèle d’effets d’antidépresseurs

Les informations sensorielles sont traitées dans le cortex par des réseaux de neurones co-activés qui forment des assemblées neuronales fonctionnelles. Le traitement visuel dans le cortex est régit par différents aspects des caractéristiques neuronales tels que l’aspect anatomique, électrophysiologique et moléculaire. Au sein du cortex visuel primaire, les neurones sont sélectifs à divers attributs des stimuli tels que l’orientation, la direction, le mouvement et la fréquence spatiale. Chacun de ces attributs conduit à une activité de décharge maximale pour une population neuronale spécifique. Les neurones du cortex visuel ont cependant la capacité de changer leur sélectivité en réponse à une exposition prolongée d’un stimulus approprié appelée apprentissage visuel ou adaptation visuelle à un stimulus non préférentiel. De ce fait, l’objectif principal de cette thèse est d’investiguer les mécanismes neuronaux qui régissent le traitement visuel durant une plasticité induite par adaptation chez des animaux adultes. Ces mécanismes sont traités sous différents aspects : la connectivité neuronale, la sélectivité neuronale, les propriétés électrophysiologiques des neurones et les effets des drogues (sérotonine et fluoxétine). Le modèle testé se base sur les colonnes d’orientation du cortex visuel primaire. La présente thèse est subdivisée en quatre principaux chapitres. Le premier chapitre (A) traite de la réorganisation du cortex visuel primaire suite à une plasticité induite par adaptation visuelle. Le second chapitre (B) examine la connectivité neuronale fonctionnelle en se basant sur des corrélations croisées entre paires neuronales ainsi que sur des corrélations d’activités de populations neuronales. Le troisième chapitre (C) met en liaison les aspects cités précédemment (les effets de l’adaptation visuelle et la connectivité fonctionnelle) aux propriétés électrophysiologiques des neurones (deux classes de neurones sont traitées : les neurones à décharge régulière et les neurones à décharge rapide ou burst). Enfin, le dernier chapitre (D) a pour objectif l’étude de l’effet du couplage de l’adaptation visuelle à l’administration de certaines drogues, notamment la sérotonine et la fluoxétine (inhibiteur sélectif de recapture de la sérotonine). Méthodes En utilisant des enregistrements extracellulaires d’activités neuronales dans le cortex visuel primaire (V1) combinés à un processus d’imagerie cérébrale optique intrinsèque, nous enregistrons l’activité de décharge de populations neuronales et nous examinons l’activité de neurones individuels extraite des signaux multi-unitaires. L’analyse de l’activité cérébrale se base sur différents algorithmes : la distinction des propriétés électrophysiologiques des neurones se fait par calcul de l’intervalle de temps entre la vallée et le pic maximal du potentiel d’action (largeur du potentiel d’action), la sélectivité des neurones est basée sur leur taux de décharge à différents stimuli, et la connectivité fonctionnelle utilise des calculs de corrélations croisées. L’utilisation des drogues se fait par administration locale sur la surface du cortex (après une craniotomie et une durotomie). Résultats et conclusions Dans le premier chapitre, nous démontrons la capacité des neurones à modifier leur sélectivité après une période d’adaptation visuelle à un stimulus particulier, ces changements aboutissent à une réorganisation des cartes corticales suivant un patron spécifique. Nous attribuons ce résultat à la flexibilité de groupes fonctionnels de neurones qui étaient longtemps considérés comme des unités anatomiques rigides. En effet, nous observons une restructuration extensive des domaines d’orientation dans le but de remodeler les colonnes d’orientation où chaque stimulus est représenté de façon égale. Ceci est d’autant plus confirmé dans le second chapitre où dans ce cas, les cartes de connectivité fonctionnelle sont investiguées. En accord avec les résultats énumérés précédemment, les cartes de connectivité montrent également une restructuration massive mais de façon intéressante, les neurones utilisent une stratégie de sommation afin de stabiliser leurs poids de connectivité totaux. Ces dynamiques de connectivité sont examinées dans le troisième chapitre en relation avec les propriétés électrophysiologiques des neurones. En effet, deux modes de décharge neuronale permettent la distinction entre deux classes neuronales. Leurs dynamiques de corrélations distinctes suggèrent que ces deux classes jouent des rôles clés différents dans l’encodage et l’intégration des stimuli visuels au sein d’une population neuronale. Enfin, dans le dernier chapitre, l’adaptation visuelle est combinée avec l’administration de certaines substances, notamment la sérotonine (neurotransmetteur) et la fluoxétine (inhibiteur sélectif de recapture de la sérotonine). Ces deux substances produisent un effet similaire en facilitant l’acquisition des stimuli imposés par adaptation. Lorsqu’un stimulus non optimal est présenté en présence de l’une des deux substances, nous observons une augmentation du taux de décharge des neurones en présentant ce stimulus. Nous présentons un modèle neuronal basé sur cette recherche afin d’expliquer les fluctuations du taux de décharge neuronale en présence ou en absence des drogues. Cette thèse présente de nouvelles perspectives quant à la compréhension de l’adaptation des neurones du cortex visuel primaire adulte dans le but de changer leur sélectivité dans un environnement d’apprentissage. Nous montrons qu’il y a un parfait équilibre entre leurs habiletés plastiques et leur dynamique d’homéostasie.

Long-term persistence of multi-drug-resistant Salmonella enterica serovar Newport in two dairy herds

Objective - To evaluate the association between maintaining joint hospital and maternity pens;and persistence of multi-drug-resistant (MDR) Salmonella enterica serovar Newport on 2 dairy farms. Design - Observational study. Sample Population - Feces and environmental samples from 2 dairy herds. Procedure - Herds were monitored for fecal shedding of S enterica Newport after outbreaks of clinical disease. Fecal and environmental samples were collected approximately monthly from pens housing sick cows and calving cows and from pens containing lactating cows. Cattle shedding the organism were tested serially on subsequent visits to determine carrier status. One farm was resampled after initiation of interventional procedures, including separation of hospital and maternity pens. Isolates were characterized via serotyping, determination of antimicrobial resistance phenotype, detection of the CMY-2 gene, and DNA fingerprinting. Results - The prevalence (32.4% and 33.3% on farms A and B, respectively) of isolating Salmonella from samples from joint hospital-maternity pens was significantly higher than the prevalence in samples from pens housing preparturient cows (0.8%, both farms) and postparturient cows on Farm B (8.8%). Multi-drug-resistant Salmonella Newport was isolated in high numbers from bedding material, feed refusals, lagoon slurry, and milk filters. One cow excreted the organism for 190 days. Interventional procedures yielded significant reductions in the prevalences of isolating the organism from fecal and environmental samples. Most isolates were of the C2 serogroup and were resistant to third-generation cephalosporins. Conclusions and Clinical Relevance - Management practices may be effective at reducing the persistence of MDR Salmonella spp in dairy herds, thus mitigating animal and public health risk.

Seizure detection algorithm for neonates based on wave-sequence analysis

Objective: The description and evaluation of the performance of a new real-time seizure detection algorithm in the newborn infant. Methods: The algorithm includes parallel fragmentation of EEG signal into waves; wave-feature extraction and averaging; elementary, preliminary and final detection. The algorithm detects EEG waves with heightened regularity, using wave intervals, amplitudes and shapes. The performance of the algorithm was assessed with the use of event-based and liberal and conservative time-based approaches and compared with the performance of Gotman's and Liu's algorithms. Results: The algorithm was assessed on multi-channel EEG records of 55 neonates including 17 with seizures. The algorithm showed sensitivities ranging 83-95% with positive predictive values (PPV) 48-77%. There were 2.0 false positive detections per hour. In comparison, Gotman's algorithm (with 30 s gap-closing procedure) displayed sensitivities of 45-88% and PPV 29-56%; with 7.4 false positives per hour and Liu's algorithm displayed sensitivities of 96-99%, and PPV 10-25%; with 15.7 false positives per hour. Conclusions: The wave-sequence analysis based algorithm displayed higher sensitivity, higher PPV and a substantially lower level of false positives than two previously published algorithms. Significance: The proposed algorithm provides a basis for major improvements in neonatal seizure detection and monitoring. Published by Elsevier Ireland Ltd. on behalf of International Federation of Clinical Neurophysiology.

The cross-entropy method for continuous multi-extremal optimization

In recent years, the cross-entropy method has been successfully applied to a wide range of discrete optimization tasks. In this paper we consider the cross-entropy method in the context of continuous optimization. We demonstrate the effectiveness of the cross-entropy method for solving difficult continuous multi-extremal optimization problems, including those with non-linear constraints.

Monitoring Infants By Automatic Video Processing

This work has, as its objective, the development of non-invasive and low-cost systems for monitoring and automatic diagnosing specific neonatal diseases by means of the analysis of suitable video signals. We focus on monitoring infants potentially at risk of diseases characterized by the presence or absence of rhythmic movements of one or more body parts. Seizures and respiratory diseases are specifically considered, but the approach is general. Seizures are defined as sudden neurological and behavioural alterations. They are age-dependent phenomena and the most common sign of central nervous system dysfunction. Neonatal seizures have onset within the 28th day of life in newborns at term and within the 44th week of conceptional age in preterm infants. Their main causes are hypoxic-ischaemic encephalopathy, intracranial haemorrhage, and sepsis. Studies indicate an incidence rate of neonatal seizures of 0.2% live births, 1.1% for preterm neonates, and 1.3% for infants weighing less than 2500 g at birth. Neonatal seizures can be classified into four main categories: clonic, tonic, myoclonic, and subtle. Seizures in newborns have to be promptly and accurately recognized in order to establish timely treatments that could avoid an increase of the underlying brain damage. Respiratory diseases related to the occurrence of apnoea episodes may be caused by cerebrovascular events. Among the wide range of causes of apnoea, besides seizures, a relevant one is Congenital Central Hypoventilation Syndrome (CCHS) \cite{Healy}. With a reported prevalence of 1 in 200,000 live births, CCHS, formerly known as Ondine's curse, is a rare life-threatening disorder characterized by a failure of the automatic control of breathing, caused by mutations in a gene classified as PHOX2B. CCHS manifests itself, in the neonatal period, with episodes of cyanosis or apnoea, especially during quiet sleep. The reported mortality rates range from 8% to 38% of newborn with genetically confirmed CCHS. Nowadays, CCHS is considered a disorder of autonomic regulation, with related risk of sudden infant death syndrome (SIDS). Currently, the standard method of diagnosis, for both diseases, is based on polysomnography, a set of sensors such as ElectroEncephaloGram (EEG) sensors, ElectroMyoGraphy (EMG) sensors, ElectroCardioGraphy (ECG) sensors, elastic belt sensors, pulse-oximeter and nasal flow-meters. This monitoring system is very expensive, time-consuming, moderately invasive and requires particularly skilled medical personnel, not always available in a Neonatal Intensive Care Unit (NICU). Therefore, automatic, real-time and non-invasive monitoring equipments able to reliably recognize these diseases would be of significant value in the NICU. A very appealing monitoring tool to automatically detect neonatal seizures or breathing disorders may be based on acquiring, through a network of sensors, e.g., a set of video cameras, the movements of the newborn's body (e.g., limbs, chest) and properly processing the relevant signals. An automatic multi-sensor system could be used to permanently monitor every patient in the NICU or specific patients at home. Furthermore, a wire-free technique may be more user-friendly and highly desirable when used with infants, in particular with newborns. This work has focused on a reliable method to estimate the periodicity in pathological movements based on the use of the Maximum Likelihood (ML) criterion. In particular, average differential luminance signals from multiple Red, Green and Blue (RGB) cameras or depth-sensor devices are extracted and the presence or absence of a significant periodicity is analysed in order to detect possible pathological conditions. The efficacy of this monitoring system has been measured on the basis of video recordings provided by the Department of Neurosciences of the University of Parma. Concerning clonic seizures, a kinematic analysis was performed to establish a relationship between neonatal seizures and human inborn pattern of quadrupedal locomotion. Moreover, we have decided to realize simulators able to replicate the symptomatic movements characteristic of the diseases under consideration. The reasons is, essentially, the opportunity to have, at any time, a 'subject' on which to test the continuously evolving detection algorithms. Finally, we have developed a smartphone App, called 'Smartphone based contactless epilepsy detector' (SmartCED), able to detect neonatal clonic seizures and warn the user about the occurrence in real-time.

Multi-scale approaches to Food Sciences: computational QM and MM explorations at the microscopic level

L'obiettivo principale della politica di sicurezza alimentare è quello di garantire la salute dei consumatori attraverso regole e protocolli di sicurezza specifici. Al fine di rispondere ai requisiti di sicurezza alimentare e standardizzazione della qualità, nel 2002 il Parlamento Europeo e il Consiglio dell'UE (Regolamento (CE) 178/2002 (CE, 2002)), hanno cercato di uniformare concetti, principi e procedure in modo da fornire una base comune in materia di disciplina degli alimenti e mangimi provenienti da Stati membri a livello comunitario. La formalizzazione di regole e protocolli di standardizzazione dovrebbe però passare attraverso una più dettagliata e accurata comprensione ed armonizzazione delle proprietà globali (macroscopiche), pseudo-locali (mesoscopiche), ed eventualmente, locali (microscopiche) dei prodotti alimentari. L'obiettivo principale di questa tesi di dottorato è di illustrare come le tecniche computazionali possano rappresentare un valido supporto per l'analisi e ciò tramite (i) l’applicazione di protocolli e (ii) miglioramento delle tecniche ampiamente applicate. Una dimostrazione diretta delle potenzialità già offerte dagli approcci computazionali viene offerta nel primo lavoro in cui un virtual screening basato su docking è stato applicato al fine di valutare la preliminare xeno-androgenicità di alcuni contaminanti alimentari. Il secondo e terzo lavoro riguardano lo sviluppo e la convalida di nuovi descrittori chimico-fisici in un contesto 3D-QSAR. Denominata HyPhar (Hydrophobic Pharmacophore), la nuova metodologia così messa a punto è stata usata per esplorare il tema della selettività tra bersagli molecolari strutturalmente correlati e ha così dimostrato di possedere i necessari requisiti di applicabilità e adattabilità in un contesto alimentare. Nel complesso, i risultati ci permettono di essere fiduciosi nel potenziale impatto che le tecniche in silico potranno avere nella identificazione e chiarificazione di eventi molecolari implicati negli aspetti tossicologici e nutrizionali degli alimenti.

A comparative evaluation of term recognition algorithms

Automatic Term Recognition (ATR) is a fundamental processing step preceding more complex tasks such as semantic search and ontology learning. From a large number of methodologies available in the literature only a few are able to handle both single and multi-word terms. In this paper we present a comparison of five such algorithms and propose a combined approach using a voting mechanism. We evaluated the six approaches using two different corpora and show how the voting algorithm performs best on one corpus (a collection of texts from Wikipedia) and less well using the Genia corpus (a standard life science corpus). This indicates that choice and design of corpus has a major impact on the evaluation of term recognition algorithms. Our experiments also showed that single-word terms can be equally important and occupy a fairly large proportion in certain domains. As a result, algorithms that ignore single-word terms may cause problems to tasks built on top of ATR. Effective ATR systems also need to take into account both the unstructured text and the structured aspects and this means information extraction techniques need to be integrated into the term recognition process.

A Bayesian formulation of search, control and the exploration/exploitation trade-off

A new approach to optimisation is introduced based on a precise probabilistic statement of what is ideally required of an optimisation method. It is convenient to express the formalism in terms of the control of a stationary environment. This leads to an objective function for the controller which unifies the objectives of exploration and exploitation, thereby providing a quantitative principle for managing this trade-off. This is demonstrated using a variant of the multi-armed bandit problem. This approach opens new possibilities for optimisation algorithms, particularly by using neural network or other adaptive methods for the adaptive controller. It also opens possibilities for deepening understanding of existing methods. The realisation of these possibilities requires research into practical approximations of the exact formalism.

Multi-party risk management helps manage cement plant construction in Thailand

Several parties (stakeholders) are involved in a construction project. The conventional Risk Management Process (RMP) manages risks from a single party perspective, which does not give adequate consideration to the needs of others. The objective of multi-party risk management is to assist decision-makers in managing risk systematically and most efficiently in a multi-party environment. Multi-party Risk Management Processes (MRMP) consist of risk identification, structuring, analysis and developing responses from all party perspectives. The MRMP has been applied to a cement plant construction project in Thailand to demonstrate its effectiveness.

A hybrid genetic algorithm for the multi-depot vehicle routing problem

The distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP). The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, two hybrid genetic algorithms (HGAs) are developed in this paper. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method and the nearest neighbor heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different problem sizes. It is proved that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time.