Hybrid Algorithms for Service, Computing and Manufacturing Systems: Routing and Scheduling Solutions

Hybrid Algorithms for Service, Computing and Manufacturing Systems: Routing and Scheduling Solutions

Jairo R. Montoya-Torres (Universidad de La Sabana, Colombia), Angel A. Juan (Open University of Catalonia, Spain), Luisa Huaccho Huatuco (University of Leeds, UK), Javier Faulin (Public University of Navarre, Spain) and Gloria L. Rodriguez-Verjan (Ecole des mines de Saint-Etienne, France)
Indexed In: SCOPUS
Release Date: August, 2011|Copyright: © 2012 |Pages: 354
ISBN13: 9781613500866|ISBN10: 1613500866|EISBN13: 9781613500873|DOI: 10.4018/978-1-61350-086-6

Description

In a global, highly competitive environment, organizations face increasing economic pressure and customer demands for more complex products and services. Hybrid algorithms have the potential to play an important role in helping organizations achieve cost reduction and increased product development.

Hybrid Algorithms for Service, Computing and Manufacturing Systems: Routing and Scheduling Solutions explores research developments and applications from an interdisciplinary perspective that combines approaches from operations research, computer science, artificial intelligence, and applied computational mathematics. Contributions cover a range of hybrid algorithm theory and practice as it relates to routing, scheduling, and real-life applications.

Topics Covered

The many academic areas covered in this publication include, but are not limited to:

  • Genetic algorithms
  • Global Bacteria Optimization (GBO)
  • Hybrid Algorithms for Manufacturing Rescheduling
  • Particle Swarm Optimization (PSO)
  • Routing Solutions for the Service Industry
  • Simulated Annealing (SA)
  • Tabu Search Procedure
  • Territory Alignment Problem
  • Vehicle Routing Models and Algorithms
  • Vehicle Routing Problem with Time Windows (VRPTW)

Reviews and Testimonials

This book brings excellent contributions to the field of hybrid algorithms, their design, implementation and experimental evaluation. The proposed hybrid approaches tackle fundamental problems in the domain of logistics, industry services, commercial distribution and manufacturing systems.

– Fatos Xhafa, Technical University of Catalonia, Spain

Table of Contents and List of Contributors

Search this Book:
Reset

Preface

PURPOSE OF THE BOOK

In a global and highly-competitive world, organizations face an increasingly difficult environment, with increasing economic pressure and customer demands for more complex products and services that are inexpensive and that can be provided at short notice. In relation to this, hybrid algorithms could play an important role in helping organizations achieve current imperative costs reduction and fast product development.

This book deals with the study of Hybrid Algorithms for Service, Computing and Manufacturing Systems. Solutions to current real-life problems, such as supply chain management require more than an individual algorithm. Hybrid algorithms take advantage of each individual algorithm and help find solutions which are stronger/faster or more efficient than those provided by individual algorithms. Recently, the use of hybrid algorithms has increased in popularity in different research areas and industries. One of the indicators of this situation is the number of sessions, workshops, and conferences dealing with the design and application of hybrid algorithms. In practice, hybrid algorithms have proved to be efficient in solving a wide range of complex real-life application problems in different domains, including: Logistics, Bioinformatics and Computational Biology, Engineering Design, Networking, Environmental Management, Transportation, Finance and Business.

This book aims at exploring state-of-the-art research developments and applications in these research areas from an interdisciplinary perspective that combines approaches from Operations Research, Computer Science, Artificial Intelligence and Applied Computational Mathematics.

The interest in hybrid algorithms has risen considerably among academics in order to improve both the behavior and the performance of meta-heuristics. Meta-heuristics are a branch of optimization in Computer Science, Operations Research and Applied Computational Mathematics that are related to algorithms and computational complexity theory. The past few years have witnessed the development of numerous meta-heuristics in various communities that sit at the intersection of several fields, including Artificial Intelligence, Computational Intelligence, Soft Computing, and Mathematical Programming. Most of the meta-heuristics mimic natural metaphors to solve complex optimization problems (e.g. evolution of species, annealing process, behavior of ant colonies, particle swarm, immune system, bee colony, wasp swarm, or bacterial behavior).

Some results of many real-life application problems are presented in this book. As reported in the literature, hybrid algorithms could result from one of the following, by:
  • Combining meta-heuristics with complementary meta-heuristics,
  • Combining meta-heuristics with exact methods from mathematical programming,
  • Combining meta-heuristics with constraint programming approaches developed in the artificial intelligence community,
  • Combining meta-heuristics with machine learning and data mining techniques,
  • Combining meta-heuristics or exact methods with simulation techniques (optimization through simulation).

TARGET AUDIENCE

This book is a valuable tool for Researchers, Practitioners and Managers, Master and PhD students, Consultants, Government officials and Policy makers, as explained below:
  1. Researchers: Since this book presents cutting-edge research on hybrid algorithms for routing, scheduling and other real-life application of hybrid algorithms. As shown by the chapters included in this book, researchers in Operations Research, Management Science, and Computer Science are developing new hybrid algorithms to solve problems in Logistics (to a large extend), Supply Chain Management and Design, Production and Operations Management, Applied Operations Research and Applied Combinatorial Optimization.
  2. Practitioners and Managers: Logistics and Operations Managers, Supply Chain Managers, Production Managers and Control Engineers are dealing with real-life problems on a daily basis. The hybrid algorithms presented in this book provide a valuable resource to draw upon to inform their daily practice.
  3. Master and PhD students: The book can be of interest for lecturers and students in Operations Research, Computer Science, Applied Computational Mathematics, Discrete Mathematics, Logistics and Operations Management, Industrial Engineering and Systems Engineering. Especially useful for the teaching and learning of the following topics: vehicle routing, scheduling, applied and discrete mathematics and artificial intelligence.
  4. Consultants: this book provides off-the-shelf hybrid algorithms that have been tried and tested which can be used by consultants and further applied to their clients.
  5. Government officials and Policy makers: In general, decision-makers in both private and public sectors could benefit from this book by tailoring and assessing the hybrid algorithms according to their decision-making criteria.
OVERVIEW OF THE BOOK

The chapters published in this book are authored by a total of 38 researchers affiliated to Higher Education Institutions based in 13 countries, as follows (in alphabetical order): Brazil, Canada, Chile, Colombia, France, Germany, Italy, Mexico, Portugal, Spain, Turkey, United Kingdom and United States of America. These manuscripts cover a range of hybrid algorithms theory and practice in three main areas: Routing, Scheduling, and Other real-life application problems. These areas correspond to the three sections of the book, as explained in detail below.

The first section contains six chapters and it is devoted to the application of hybrid algorithms for solving complex realistic Routing problems.

Chapter 1 is written by Bertazzi and Speranza. This invited chapter reviews the main heuristic approaches for the solution of Inventory Routing Problems (IRP) by presenting the most recent and novel ideas for the design of a new class of heuristics called matheuristics. This class of heuristic algorithms embeds, in a heuristic or meta-heuristic scheme, the exact solution of one or several mathematical programming models.

Chapter 2 is authored by Perrier, Campbell, Gendreau, and Langevin. It provides a survey of recent optimization models and solution methodologies for the vehicle routing problem for spreading operations. The chapter presents a detailed classification scheme of models developed over the past 40 years. It highlights some factors that may be limiting the application of Operations Research models in practice and discuss promising future research trends.

The Vehicle Routing Problem with Time Windows (VRPTW) is dealt with in chapters 3 and 4, respectively. VRPTW consists on finding routes for the vehicles to serve all the customers at a minimal cost without violating the capacity and travel time constraints of the vehicles and the time window constraints set by the customers. Chapter 3 is written by Bozkaya, Cao and Aktolug. It provides the reader with the background, mathematical models and various solution approaches for the Vehicle Routing Problem with Time Windows (VRPTW). Three case studies are presented as “success stories” of implementation of decision-aid tools for solving the VRPTW at an enterprise scale. Chapter 4 is authored by Tuzkaya, Gülsün, Bildik, and Çaglar. The chapter considers a multiple objective Vehicle Routing Problem subject to Time Windows deliveries. A hybrid meta-heuristic algorithm based on Genetic Algorithm (GA) and Simulated Annealing (SA) is proposed.

Chapter 5 is written by Lourenço and Ribeiro. It studies the problem of designing market-efficient and cost-effective product distribution routes. This chapter explores three different distribution routing strategies: (i) the classical vehicle routing problem where total distance or cost is minimized, responding to the classical objective functions of a Logistics Department in a company, (ii) a master route strategy with daily adaptations with maximization of customer’s loyalty, as intended by Marketing Departments, and (iii) a strategy that takes into account the cross-functional planning between the logistics (cost-based objective) and the marketing (customer-oriented objective) objectives through a multi-objective model. All strategies are analyzed in a multi-period scenario through a meta-heuristic algorithm based on the iterated local search scheme.

Chapter 6 is authored by Juan, Faulin, Bektas and Grasman, discusses how simulation can be efficiently integrated with a classical heuristic in order to solve Vehicle Routing Problems with route length constraints and customer service costs. The strategy behind the hybrid solution procedure is to combine Monte Carlo Simulation with the classical Clarke & Wright Savings (CWS) algorithm and a divide-and-conquer technique. Authors also discuss the advantages and disadvantages of the procedures in relation to other existing approaches from literature.

The second section of the book is composed of four chapters and it is devoted to the presentation of hybrid algorithms for the solution of various Scheduling problems.

Chapter 7 is authored by Czogalla and Fink, and proposes a Particle Swarm Optimization (PSO) approach for the Resource-Constrained Project Scheduling Problem (RCPSP). It incorporates well-known procedures such as the serial Schedule Generation Scheme (SGS) and is hybridized with forward-backward improvement. The proposed procedure is compared against state-of-the-art methods from the literature through an extensive computational experiment using a benchmark instances.

Chapter 8 is written by Palominos, Parada, Gatica, and Vejar. It provides an exploratory analysis of the marriage of honey-bees optimization (MBO) algorithm to solve scheduling problems. The chapter also evaluates the potential utility and adaptability of this method. Two scheduling problems are considered: minimization of earliness-tardiness penalties under single machine scheduling environment with a common due date constraint and the permutation flow shop problem.

Chapter 9 is written by Solano-Charris, Gómez-Vizcaíno, Montoya-Torres and Paternina-Arboleda. It proposes the use of a novel bio-inspired algorithm to solve hard combinatorial optimization problems. The procedure is called Global Bacteria Optimization (GBO) algorithm and emulates the movement of microscopic organisms (bacteria) in response to stimulus from light. Applications are considered to solve hard mono-objective and bi-objective jobshop scheduling problems, with makespan and due date-based objective functions.

Chapter 10 is authored by Huaccho Huatuco and Calinescu. In this chapter, manufacturing rescheduling of customized production versus commodity production is investigated. Five hybrid rescheduling algorithms are presented. These are obtained by combining two key rescheduling-related elements found in the literature: rescheduling criteria and level of disruption transmitted to the shop-floor due to rescheduling. The main advantage of the proposed hybrid rescheduling algorithm over individual rescheduling algorithms consists of their ability to combine the main features of two different algorithms in order to achieve enhanced performance, depending on the objective of the organization. The practical impact of the hybrid algorithms is analyzed in the context of three manufacturing companies.

The third section is composed of three chapters and it is devoted to the presentation of hybrid algorithms for solving Other real-life application problems.

The Territory Design and Alignment Problems are considered in chapters 11 and 12, respectively. The Territory Design Problem (TDP) consists on grouping small geographic Basic Units (BU) into larger geographic territories. Chapter 11 is written by López. It considers a real-life case study from a large soft drinks distribution company that operates in the city of Monterrey, Mexico. The chapter proposes a new strategy based on a hybrid-mixed integer programming method (HMIP). By taking advantage from territory centers obtained through a relaxation of the p-median model, the procedure requires a small number of iterations to find connected solutions. The chapter highlights that the model is currently being used by the large beverage bottler in Latin America.

Chapter 12 is authored by Freire de Sousa, Barros Basto and Lima Júnior. It briefly updates the review of the existing literature on the territory alignment problem, its applications and solution approaches. The chapter also illustrates the most recent tendencies by proposing a hybrid resolution approach based on the Greedy Randomized Adaptive Search Procedure (GRASP) and Tabu Search meta-heuristics that is integrated to an interactive and user-friendly Geographic Information System (GIS) application.

Chapter 13 is authored by Xie, Turnquist and Waller. It presents a hybrid Lagrangean relaxation and Tabu Search procedure for a class of discrete network design problems with complex interdependent-choice constraints. The algorithm is implemented on the solution of a network design problem with lane reversal and crossing elimination strategies, arising from urban evacuation planning.

In such a context, the reader will gain full exposure to some of the latest research models and frameworks with hybrid algorithms to solve practical real-life application problems. In addition, the literature is enriched by the discovery of current and future trends due to evolution of the research in the field.

The Editors

Jairo R. Montoya-Torres
Bogotá
Angel A. Juan
Barcelona
Luisa Huaccho Huatuco
Leeds
Javier Faulin
Pamplona
Gloria L. Rodriguez-Verjan
Gardanne

January, 2011

Author(s)/Editor(s) Biography

JAIRO R. MONTOYA-TORRES is an Associate Professor of Operations Research and Director of the Master program in Operations Management at the School of Economics and Management Sciences, Universidad de La Sabana, Colombia. He holds a Ph.D. degree from Ecole Nationale Supérieure des Mines de Saint-Étienne, France. He has been Invited Professor at Universidad Nacional Autónoma de Nuevo León, Mexico, in 2009, and Ecole Nationale Supérieure des Mines de Saint-Étienne, France, in 2011 within the Department OMSI. He has been Guest Editor for the Int. J. of Information Systems and Supply Chain Management (published by IGI Global), Annals of Operations Research, Journal of Intelligent Manufacturing and Int. J. of Industrial and Systems Engineering. Dr. Montoya is currently Associate Editor of the Journal of Modelling and Simulation Systems, and the Journal of Artificial Intelligence: Theory and Application. His research interests include scheduling, applied combinatorial optimization, reverse/sustainable logistics, supply chain management under collaborative and sustainable environments, and modeling and simulation of complex industrial and service systems. His webpage is http://jrmontoya.wordpress.com.
Angel A. Juan (ajuanp@gmail.com) is an associate professor of simulation and data analysis in the computer sciences department at the Open University of Catalonia (Spain). He is also a lecturer at the Technical University of Catalonia. He holds a PhD in industrial engineering (UNED), an MS in information technology (Open University of Catalonia), and an MS in applied computational mathematics (University of Valencia). His research interests include computer simulation, applied data analysis, and mathematical e-learning. He has published several papers in international journals, books, and proceedings regarding these fields. As a researcher, he has been involved in several international research projects.
Luisa Huaccho Huatuco is a Lecturer in Operations & Business Processes at Leeds University Business School. She obtained her doctorate degree from the Department of Engineering Science, University of Oxford. Before that, she completed a M.Sc. degree at the International Institute for Aerospace Survey and Earth Sciences (ITC), The Netherlands. Her research interests include complexity in manufacturing systems, supply chain management and operations management.
Javier Faulin (javier.faulin@unavarra.es) is an associate professor of operations research and statistics at the Public University of Navarre (Spain). He is also a lecturer at the UNED (Pamplona, Spain). He holds a PhD in economics from the University of Navarre (Pamplona, Spain), a MS in operations management, logistics and transportation from UNED (Madrid, Spain) and an MS in mathematics from the University of Zaragoza (Zaragoza, Spain). He has extended experience in distance and Web-based teaching at several European universities. His research interests include logistics and simulation modeling and analysis. He has published several papers in international journals, books, and proceedings.
Gloria L. Rodriguez-Verjan graduated with highest honors as industrial engineer from Pontificia Universidad Javeriana, Bogotá, Colombia, and obtained her MSc degree in industrial engineering from Ecole Nationale Supériere des Mines de Saint-Étienne, France. She currently working as Research Engineer at a Franco-Italian semiconductor manufacturer, and working towards a doctoral degree within the Microelectronics Division of Provence (CMP) of Ecole nationale Supérieure des Mines de Saint-Éteinne. She has worked as logistics analyst at P&A Renault, and Demand Manager at Symrise, both enterprises located in Bogotá, Colombia. She has also been part-time lecturer in simulation at Pontificia Universidad Javeriana. Her research work has been focused on coordination and collaboration issues within the supply chains, simulation of logistics operations in maritime ports, and most recently in optimization and statistical analysis of semiconductor manufacturing operations. Results of her researches have been published in various academic journals and presented in various international conferences.

Indices

Editorial Board

  • Ajith Abraham, Norwegian University of Science and Technology, Norway
  • Sana Belmokhtar, Research center for Automatic Control of Nancy (CRAN), France
  • Gaston Cedillo, COMIMSA, Mexico
  • Stéphane Dauzère-Pérès, École nationale supérieure des mines de Saint-Étienne, France
  • Scott Grasman, Missouri University of Science and Technology, USA
  • M. Grazia Speranza, Università degli Studi di Brescia, Italy
  • Patrick Hirsch, University of Natural Resources and Applied Life Sciences, Austria
  • Carlos A. Méndez, INTEC, Argentina
  • Helena Ramalhinho Lourenço, Universidad Pompeu Fabra, Spain
  • Janet Smart, Said Business School University of Oxford, United Kingdom
  • Andres Weintraub, Universidad de Chile, Chile