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 Gloria L. Rodriguez-Verjan Ecole Nationale Supérieure des Mines de Saint-Étienne, France Senior Editorial Director: Kristin Klinger Director of Book Publications: Julia Mosemann Editorial Director: Lindsay Johnston Acquisitions Editor: Erika Carter Development Editor: Michael Killian Production Editor: Sean Woznicki Typesetters: Milan Vracarich, Jr. Print Coordinator: Jamie Snavely Cover Design: Nick Newcomer Published in the United States of America by Information Science Reference (an imprint of IGI Global) 701 E. Chocolate Avenue Hershey PA 17033 Tel: 717-533-8845 Fax: 717-533-8661 E-mail: [email protected] Web site: http://www.igi-global.com Copyright © 2012 by IGI Global. All rights reserved. No part of this publication may be reproduced, stored or distributed in any form or by any means, electronic or mechanical, including photocopying, without written permission from the publisher. Product or company names used in this set are for identification purposes only. Inclusion of the names of the products or companies does not indicate a claim of ownership by IGI Global of the trademark or registered trademark. Library of Congress Cataloging-in-Publication Data Hybrid algorithms for service, computing and manufacturing systems: routing and scheduling solutions / Jairo R. Montoya- Torres ... [et al.] p. cm. Includes bibliographical references and index. Summary: “This book explores research developments and applications from an interdisciplinary perspective that combines approaches from operations research, computer science, artificial intelligence, and applied computational mathematics”-- Provided by publisher. ISBN 978-1-61350-086-6 (hardcover) -- ISBN 978-1-61350-087-3 (ebook) -- ISBN 978-1-61350-088-0 (print & perpetual access) 1. Operations research. 2. Artificial intelligence. 3. Computer science--Mathematics. I. Montoya-Torres, Jairo R., 1977- T57.6.H93 2012 658.5’3--dc23 2011023571 British Cataloguing in Publication Data A Cataloguing in Publication record for this book is available from the British Library. All work contributed to this book is new, previously-unpublished material. The views expressed in this book are those of the authors, but not necessarily of the publisher. Editorial Advisory 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, University of 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, University of Oxford, UK Andres Weintraub, Universidad de Chile, Chile List of Reviewers Edgar H. Alfonso, Ecole Nationale Supérieure des Mines de Saint-Étienne, France Burcin Bozkaya, Sabanci University, Turkey Tom Burgess, University of Leeds, UK Juan Pablo Caballero, Pontificia Universidad Javeriana, Colombia Ani Calinescu, University of Oxford, UK Linda Castro, École Polytechnique de Montréal, Canada Gaston Cedillo, COMIMSA, Mexico Julio Mario Daza, Universidad Autónoma del Caribe, Colombia Javier Faulin, Public University of Navarre, Spain Andreas Fink, Helmut-Schmidt-University & UniBw Hamburg, Germany Jorge Freire de Sousa, Universidade do Porto, Portugal Alvaro Garcia, Universidad Politécnica de Madrid, Spain Marco Gavanelli, Università di Ferrara, Italy Alex Grasas, Universitat Pompeu Fabra, Spain Scott Grasman, Missouri University of Science and Technology, USA Edgar Gutierrez, Universidad de La Sabana, Colombia Patrick Hirsch, University of Natural Resources and Applied Life Sciences, Austria Luisa Huaccho Huatuco, University of Leeds, UK Antonia Huertas, Open University of Catalonia, Spain Angel Juan, Open University of Catalonia, Spain Fabian López, Universidad Autónoma de Nuevo León (CEDEEM), México Laura Lotero, Universidad Nacional de Colombia, Colombia Helena R. Lourenço, Universitat Pompeu Fabra, Spain Toni Mancini, Università di Roma La Sapienza, Italy Vanessa Manotas, Universidad de La Sabana, Colombia Alberto Márquez, University of Seville, Spain Carlos A. Méndez, INTEC, Argentina Jairo R. Montoya-Torres, Universidad de La Sabana, Colombia Miguel Ortega Mier, Universidad Politécnica de Madrid, Spain Pedro Palominos, University of Santiago of Chile, Chile Daniel Riera, Open University of Catalonia, Spain Gloria L. Rodríguez-Verjan, Ecole Nationale Supérieure des Mines de Saint-Étienne, France Janet Smart, University of Oxford, UK Elyn L. Solano-Charris, Universidad de La Sabana, Colombia M. Grazia Speranza, University of Brescia, Italy Gülfem Tuzkaya, Yildiz Technical University, Turkey Eva Vallada, Universidad Politénica de Valencia, Spain Mario Vélez, EAFIT University, Colombia Claude Yugma, Ecole Nationale Supérieure des Mines de Saint-Étienne, France Table of Contents Foreword .............................................................................................................................................viii Preface ...................................................................................................................................................xi Acknowledgment ................................................................................................................................xvi Section 1 Hybrid Algorithms for Routing Problems Chapter 1 Matheuristics for Inventory Routing Problems .......................................................................................1 Luca Bertazzi, University of Brescia, Italy M. Grazia Speranza, University of Brescia, Italy Chapter 2 Vehicle Routing Models and Algorithms for Winter Road Spreading Operations ...............................15 Nathalie Perrier, École Polytechnique de Montréal, Canada James F. Campbell, University of Missouri-St. Louis, USA Michel Gendreau, École Polytechnique de Montréal, Canada André Langevin, École Polytechnique de Montréal, Canada Chapter 3 Routing Solutions for the Service Industry ...........................................................................................46 Burcin Bozkaya, Sabanci University, Turkey Buyang Cao, Tongji University, China Kaan Aktolug, Aktolug Consultancy Ltd., Turkey Chapter 4 A Hybrid Genetic Algorithm-Simulated Annealing Approach for the Multi-Objective Vehicle Routing Problem with Time Windows .....................................................................................79 Gülfem Tuzkaya, Yildiz Technical University, Turkey Bahadır Gülsün, Yildiz Technical University, Turkey Ender Bildik, Yildiz Technical University, Turkey E. Gözde Çağlar, Yildiz Technical University, Turkey Chapter 5 Strategies for an Integrated Distribution Problem ................................................................................98 Helena R. Lourenço, Universitat Pompeu Fabra, Spain Rita Ribeiro, Catholic University of Portugal (Porto), Portugal Chapter 6 A Hybrid Algorithm Based on Monte-Carlo Simulation for the Vehicle Routing Problem with Route Length Restrictions ...................................................................................................................122 Angel A. Juan, Open University of Catalonia, Spain Javier Faulin, Public University of Navarre, Spain Tolga Bektaş, University of Southampton, UK Scott E. Grasman, Missouri University of Science and Technology, USA Section 2 Hybrid Algorithms for Scheduling Problems Chapter 7 A Hybrid Particle Swarm Algorithm for Resource-Constrained Project Scheduling .........................137 Jens Czogalla, Helmut-Schmidt-University Hamburg, Germany Andreas Fink, Helmut-Schmidt-University Hamburg, Germany Chapter 8 Marriage in Honeybee Optimization to Scheduling Problems ...........................................................158 Pedro Palominos, University of Santiago of Chile, Chile Victor Parada, University of Santiago of Chile, Chile Gustavo Gatica, University of Santiago of Chile, Chile Andrés Véjar, Université de Nancy, France Chapter 9 Global Bacteria Optimization Meta-Heuristic: Performance Analysis and Application to Shop Scheduling Problems .............................................................................................................178 Elyn L. Solano-Charris, Universidad de La Sabana, Colombia Libardo S. Gómez-Vizcaíno, Universidad Autónoma del Caribe, Colombia Jairo R. Montoya-Torres, Universidad de La Sabana, Colombia Carlos D. Paternina-Arboleda, Universidad del Norte, Colombia Chapter 10 Hybrid Algorithms for Manufacturing Rescheduling: Customised vs. Commodity Production ........195 Luisa Huaccho Huatuco, University of Leeds, UK Ani Calinescu, University of Oxford, UK Section 3 Other Applications of Hybrid Algorithms Chapter 11 HMIP Model for a Territory Design Problem with Capacity and Contiguity Constraints .................226 Fabian Lopez, Universidad Autónoma de Nuevo León (CEDEEM), México Chapter 12 Hybrid Heuristics for the Territory Alignment Problem .....................................................................258 Jorge Freire de Sousa, Universidade do Porto, Portugal José Barros-Basto, Universidade do Porto, Portugal Paulo Lima Júnior, Universidade do Vale do São Francisco, Brazil Chapter 13 A Hybrid Lagrangian Relaxation and Tabu Search Method for Interdependent-Choice Network Design Problems ..................................................................................................................294 Chi Xie, The University of Texas at Austin, USA Mark A. Turnquist, Cornell University, USA S. Travis Waller, The University of Texas at Austin, USA About the Contributors ....................................................................................................................325 Index ...................................................................................................................................................333 viii Foreword Most fundamental problems in combinatorial optimization field have been proven to be computation- ally hard to solve to optimality and are known as NP-hard problems in the literature. Knowing that a problem of interest is NP-hard implies, on the one hand, that the problem is unlikely to be solved within a reasonable amount of computation time and, on the other, that one has to be satisfied with solv- ing the problem approximately or near-optimally. An important class of algorithms that have shown their usefulness in solving many computationally hard optimization problems is that of meta-heuristics. This is by no chance –meta-heuristics methods possess many good features, among which we could distinguish: they are able to find high quality solu- tions in a reasonable amount of computation time, are robust, generic, flexible and easy to implement on sequential, parallel and networked computer systems. This, together with the fact that for most practical applications in industry and businesses high quality solution would suffice, have converted meta-heuristics into de facto approaches to cope in practice with the computationally hard optimization problems. In fact, even when a polynomial time algorithm is known for a certain problem, solving large-size/real-life instances (e.g. instances at enterprise scale) calls again for the application of meta-heuristics methods. Not less importantly, meta-heuristic approaches can tackle with efficacy both single and multi-objective optimization problems. Meta-heuristics methods have been applied for decades now. Besides using them as stand alone ap- proaches, during the last years, the attention of researchers has shifted to consider another type of high level algorithms, namely hybrid algorithms. These algorithms do not follow any concrete meta-heuristic, but rather combine meta-heuristics with meta-heuristics and/or other methods (e.g. divide-and-conquer, linear programming, dynamic programming, constraint programming or other AI techniques) yielding thus hybrid meta-heuristics. One fundamental question here is how can be achieved for hybrid approaches to outperform stand alone approaches? The hybridization aims at exploring the synergies among stand alone methods in order to achieve better results for the optimization problem under study. For instance, using hybrid approaches one can explore the synergies between exploration of solution space (through population based meta-heuristics, such as Genetic Algorithms—GAs) with the exploitation of the solu- tion space (through local search methods, such as Tabu Search –TS); the GA could them be used as a main search method while TS can improve locally the individuals of the population. The rationale behind the hybridization resides in the ``no free lunch theorem” stating that ``... all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions. In particular, if algorithm A outperforms algorithm B on some cost functions, then loosely speaking there must exist exactly as many other functions where B outperforms A.” Based ix on this theorem, existing algorithms can be used as components for designing new efficient search algorithms and expect improved performance of the newly obtained algorithm for some cost functions. Naturally, there are major issues in designing hybrid meta-heuristics for a given optimization problem, such as: (a) how to choose heuristic and/or meta-heuristic methods to be combined (within the same family or from different families of existing algorithms), and, (b) how to combine the chosen methods into new hybrid approaches. Unfortunately, there are no theoretical foundations for these issues, yet there are interesting evidences, experiences and reports on the literature. For the former, different classes of search algorithms can be considered for the purposes of hybridization, such as exact methods, simple deterministic or random heuristic methods and meta-heuristics. Moreover, meta-heuristics themselves are classified into local search based methods, population based methods and other classes of nature inspired meta-heuristics. Therefore, in principle, one could combine any methods from the same class or methods from different classes. Regarding the later, there are some attempts for taxonomies of hybrid meta-heuristics; in fact, the common approach is to try out in smart ways, based on domain knowledge of problem at hand and characteristics of heuristics methods, different hybrid approaches and shed light on the performance of the resulting hybrid approach. The level of hybridization here plays an important role, namely the degree of coupling between the meta-heuristics (e.g. coercive vs. cooperative). It should as well be noted that frameworks that facilitate fast prototyping have been also provided in the hybrid meta-heuristics literature. This book brings excellent contributions to the field of hybrid algorithms, their design, implemen- tation and experimental evaluation. The proposed hybrid approaches tackle fundamental problems in the domain of logistics, industry services, commercial distribution and manufacturing systems. The studied problems include routing, different forms of scheduling, such as permutation scheduling and shop scheduling problems, service allocation problems, etc. The proposed approaches include hybrid- ization of meta-heuristic methods with other meta-heuristic methods such as Genetic Algorithms (GA) and Simulated Annealing (SA) or the hybridization of meta-heuristics with the exact solution of one or several mathematical programming models. Besides advancing in the design of more sophisticated hybrid solution strategies for routing and scheduling problems, the contributions of the book have a practical focus for solving real life problems. The aim is to support decision processes in companies and thus to enable achieving better business ob- jectives by solving the problems at company scale. Also, the use of benchmarks and software packages are good examples of best practices in the field. The editors of this volume bring together experts and researchers from the field whose contributions explore new research findings, developments and future directions in the hybrid approaches for routing and scheduling problems arising in service, computing and manufacturing systems. Finally, although focused on the concrete field of the routing and scheduling for service, computing and manufacturing systems, most of the conclusions provided in the volume could be extended to routing and scheduling in other research fields. Fatos Xhafa Technical University of Catalonia, Spain