tailieunhanh - Adaptive search techniques for problems in vehicle routing, part I: A survey

Research in the field of vehicle routing is often focused on finding new ideas and concepts in the development of fast and efficient algorithms for an improved solution process. In this first part of the survey, we present an overview of recent literature dealing with adaptive or guided search techniques for problems in vehicle routing. | Yugoslav Journal of Operations Research 25 (2015), Number 1, 3–31 DOI: Invited survey ADAPTIVE SEARCH TECHNIQUES FOR PROBLEMS IN VEHICLE ROUTING, PART I: A SURVEY Stefanie KRITZINGER Department of Production and Logistics, Johannes Kepler University Linz, Austria Karl F. DOERNER Christian Doppler Laboratory for Efficient Intermodal Transport Operations, Department of Business Administration, University of Vienna, Austria Fabien TRICOIRE, Richard F. HARTL Department of Business Administration, University of Vienna, Austria , Received: February 2014 / Accepted: May 2014 Abstract: Research in the field of vehicle routing is often focused on finding new ideas and concepts in the development of fast and efficient algorithms for an improved solution process. Early studies introduce static tailor-made strategies, but trends show that algorithms with generic adaptive policies - which emerged in the past years - are more efficient to solve complex vehicle routing problems. In this first part of the survey, we present an overview of recent literature dealing with adaptive or guided search techniques for problems in vehicle routing. Keywords: Adaptive Strategies, Local Search, Metaheuristics, Vehicle Routing. MSC: 90B06, 90C05, 90C08. 1. INTRODUCTION Metaheuristics and vehicle routing problems (VRPs) are on the one hand, solution procedures and on the other hand, problem types which are strongly 4 S. Kritzinger, F. Tricoire, K. F. Doerner, R. F. Hartl / Adaptive Search Techniques connected. Most of the VRPs are NP-hard and so efficient solution techniques do not exist, but as shown by Garey and Johnson [23], there are no adequate solution techniques for solving them. Therefore, these problem types are perfect applications where metaheuristic search techniques can provide substantial support in tackling them. In fact, with the invention