logo资料库

vehicle routing problems, methods, and applications, paolo toth.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：3.74M 资料格式：pdf 举报 版权申诉
第1页 / 共467页
第2页 / 共467页
第3页 / 共467页
第4页 / 共467页
第5页 / 共467页
第6页 / 共467页
第7页 / 共467页
第8页 / 共467页
资料共467页，剩余部分请下载后查看
    List of Figures
    List of Tables
    Preface to the Second Edition
    Preface to the First Edition
    The Family of Vehicle Routing Problems
    Introduction
    The Capacitated Vehicle Routing Problem
    The Family of VRP
    Bibliography
    I The Capacitated Vehicle Routing Problem
    Classical Exact Algorithms for the Capacitated Vehicle Routing Problem
    Introduction
    Branch-and-Bound Algorithms
    Early Set Partitioning Algorithms
    Branch-and-Cut Algorithms
    Conclusions and Future Research Directions
    Bibliography
    New Exact Algorithms for the Capacitated Vehicle Routing Problem
    Introduction
    Main Exact Approaches
    Formulations
    Valid Cuts
    Pricing
    Branching vs. Route Enumeration
    Overview of Computational Results
    Conclusions and Future Research Directions
    Bibliography
    Heuristics for the Vehicle Routing Problem
    Introduction
    Constructive Heuristics
    Classical Improvement Heuristics
    Metaheuristics
    Hybridizations
    Unified Algorithms
    Computational Comparison of Selected Metaheuristics
    Conclusions and Future Research Directions
    Bibliography
    II Important Variants of the Vehicle Routing Problem
    The Vehicle Routing Problem with Time Windows
    Introduction
    Mathematical Formulations
    Exact Solution Methods
    Heuristics
    Extensions
    Conclusions and Future Research Directions
    Bibliography
    Pickup-and-Delivery Problems for Goods Transportation
    Introduction
    Many-to-Many Problems
    One-to-Many-to-One Problems
    One-to-One Problems
    Problems with Loading Constraints
    Conclusions and Future Research Directions
    Bibliography
    Pickup-and-Delivery Problems for People Transportation
    Introduction
    Dial-a-Ride Problems
    Problem Formulation
    Solution Methods for Dial-a-Ride Problems
    Other Problems Concerning Pickup and Delivery of People
    Conclusions and Future Research Directions
    Bibliography
    Stochastic Vehicle Routing Problems
    Introduction
    A Priori Optimization
    The Reoptimization Model
    Probabilistic Formulation
    Stochastic Demands
    Stochastic Customers
    Stochastic Travel Times
    Conclusions and Future Research Directions
    Bibliography
    Four Variants of the Vehicle Routing Problem
    Introduction
    VRP with Backhauls
    Heterogeneous or Mixed Fleet VRP
    Periodic Routing Problems
    VRP with Split Deliveries
    Conclusions and Future Research Directions
    Bibliography
    Vehicle Routing Problems with Profits
    Introduction
    Single-Vehicle Case
    Multiple-Vehicle Case
    Conclusions and Future Research Directions
    Bibliography
    Dynamic Vehicle Routing Problems
    Introduction
    Definitions, Objectives, and Overview of Problem Variants
    Dynamic Requests
    Dynamic and Time-Dependent Travel Times
    Dynamic Vehicle Availability
    Performance Measurements and Evaluation of Solution Approaches
    Conclusions and Future Research Directions
    Bibliography
    III Applications of the Vehicle Routing Problem
    Software Tools and Emerging Technologies for Vehicle Routing and Intermodal Transportation
    Introduction
    Basic Functionalities of Vehicle Routing Software
    Input and Output
    Model Properties
    Algorithms
    Implementation, Performance, and Price
    VRP Technology Survey
    New and Emerging Technologies
    The Future of the Vehicle Routing Business
    Summary and Conclusions
    Bibliography
    Ship Routing and Scheduling in Industrial and Tramp Shipping
    Introduction
    Cargo Routing and Scheduling
    Maritime Inventory Routing
    Dynamic and Stochastic Ship Routing
    Conclusions and Future Research Directions
    Bibliography
    Vehicle Routing Applications in Disaster Relief
    Introduction
    Phases in Disaster Management
    Performance Metrics in Disaster Operations
    Commercial VRPs vs. Disaster Relief VRPs
    Conclusions and Future Research Directions
    Bibliography
    Green Vehicle Routing
    Environmentally Sustainable Routing
    Fuel Consumption and Emission Models for Road Transportation
    Minimizing Emissions in Vehicle Routing
    Speed Optimization on Fixed Routes
    Multicriteria Analysis
    Routing in Other Modes of Transport
    Alternative Fuel-Powered Vehicles
    Conclusions and Future Research Directions
    Bibliography
    Index
    Chapter 1: The Family of Vehicle Routing Problems
    Chapter 2: Classical Exact Algorithms for the Capacitated Vehicle Routing Problem
    Chapter 3: New Exact Algorithms for the Capacitated Vehicle Routing Problem
    Chapter 4: Heuristics for the Vehicle Routing Problem
    Chapter 5: The Vehicle Routing Problem with Time Windows
    Chapter 6: Pickup-and-Delivery Problems for Goods Transportation
    Chapter 7: Pickup-and-Delivery Problems for People Transportation
    Chapter 8: Stochastic Vehicle Routing Problems
    Chapter 9: Four Variants of the Vehicle Routing Problem
    Chapter 10: Vehicle Routing Problems with Profits
    Chapter 11: Dynamic Vehicle Routing Problems
    Chapter 12: Software Tools and Emerging Technologies for Vehicle Routing and Intermodal Transportation
    Chapter 13: Ship Routing and Scheduling in Industrial and Tramp Shipping
    Chapter 14: Vehicle Routing Applications in Disaster Relief
    Chapter 15: Green Vehicle Routing
    Back Matter
    Vehicle Routing MO18_Toth_VigoFM-10-20-14.indd 1 10/20/2014 9:46:05 AM
    MOS-SIAM Series on Optimization This series is published jointly by the Mathematical Optimization Society and the Society for Industrial and Applied Mathematics. It includes research monographs, books on applications, textbooks at all levels, and tutorials. Besides being of high scientific quality, books in the series must advance the understanding and practice of optimization. They must also be written clearly and at an appropriate level for the intended audience. Editor-in-Chief Katya Scheinberg Lehigh University Editorial Board Santanu S. Dey, Georgia Institute of Technology Maryam Fazel, University of Washington Andrea Lodi, University of Bologna Arkadi Nemirovski, Georgia Institute of Technology Stefan Ulbrich, Technische Universität Darmstadt Luis Nunes Vicente, University of Coimbra David Williamson, Cornell University Stephen J. Wright, University of Wisconsin Edition Theory of Discrete Optimization Convex Algebraic Geometry Problems in Function Spaces ´ ´ Applications to PDEs and Optimization, Second Edition Series Volumes Toth, Paolo and Vigo, Daniele, editors, Vehicle Routing: Problems, Methods, and Applications, Second Attouch, Hedy, Buttazzo, Giuseppe, and Michaille, Gérard, Variational Analysis in Sobolev and BV Spaces: Shapiro, Alexander, Dentcheva, Darinka, and Ruszczynski, Andrzej, Lectures on Stochastic Programming: Modeling and Theory, Second Edition Locatelli, Marco and Schoen, Fabio, Global Optimization: Theory, Algorithms, and Applications De Loera, Jesús A., Hemmecke, Raymond, and Köppe, Matthias, Algebraic and Geometric Ideas in the Blekherman, Grigoriy, Parrilo, Pablo A., and Thomas, Rekha R., editors, Semidefinite Optimization and Delfour, M. C., Introduction to Optimization and Semidifferential Calculus Ulbrich, Michael, Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Biegler, Lorenz T., Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes Shapiro, Alexander, Dentcheva, Darinka, and Ruszczynski, Andrzej, Lectures on Stochastic Programming: Modeling and Theory Conn, Andrew R., Scheinberg, Katya, and Vicente, Luis N., Introduction to Derivative-Free Optimization Ferris, Michael C., Mangasarian, Olvi L., and Wright, Stephen J., Linear Programming with MATLAB Attouch, Hedy, Buttazzo, Giuseppe, and Michaille, Gérard, Variational Analysis in Sobolev and BV Spaces: Wallace, Stein W. and Ziemba, William T., editors, Applications of Stochastic Programming Grötschel, Martin, editor, The Sharpest Cut: The Impact of Manfred Padberg and His Work Renegar, James, A Mathematical View of Interior-Point Methods in Convex Optimization Ben-Tal, Aharon and Nemirovski, Arkadi, Lectures on Modern Convex Optimization: Analysis, Algorithms, Conn, Andrew R., Gould, Nicholas I. M., and Toint, Phillippe L., Trust-Region Methods Applications to PDEs and Optimization and Engineering Applications MO18_Toth_VigoFM-10-20-14.indd 2 10/20/2014 9:46:05 AM
    Vehicle Routing Problems, Methods, and Applications Second Edition Edited by Paolo Toth DEI, University of Bologna Bologna, Italy Daniele Vigo DEI, University of Bologna Bologna, Italy Society for Industrial and Applied Mathematics Mathematical Optimization Society Philadelphia Philadelphia MO18_Toth_VigoFM-10-20-14.indd 3 10/20/2014 9:46:06 AM
    Copyright © 2014 by the Society for Industrial and Applied Mathematics and the Mathematical Optimization Society 10 9 8 7 6 5 4 3 2 1 All rights reserved. Printed in the United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Society for Industrial and Applied Mathematics, 3600 Market Street, 6th Floor, Philadelphia, PA 19104-2688 USA. Trademarked names may be used in this book without the inclusion of a trademark symbol. These names are used in an editorial context only; no infringement of trademark is intended. Access and Excel are trademarks of Microsoft Corporation in the United States and/or other countries. DISC and REACT are trademarks of MJC2 Limited. Fleetboard is a trademark of Pictorial, Inc. GeoRoute and GIRO/Acces are trademarks of GIRO, Inc. Google Maps™ mapping service, Google, and the Google logo are registered trademarks of Google Inc., used with permission. IBM ILOG CPLEX is developed and supported by IBM, Inc. IBM ILOG CPLEX is a registered trademark of IBM, Inc. www.ibm.com. Intel Core is a registered trademark of Intel Corporation or its subsidiaries in the United States and other countries. Linux is a registered trademark of Linus Torvalds. MapInfo, the MapInfo logo, MapBasic, and MapInfo Professional are trademarks of Pitney Bowes MapInfo Corporation and/or its affiliates. Microsoft and MS-DOS are registered trademarks and ODBC, Windows, Windows 95, and Windows Vista are trademarks of Microsoft Corporation. NAVTEQ Traffic is a trademark of NAVTEQ. Optrak is a trademark of Optrak Distribution Software, Ltd. R2 Optimointi is a trademark of Procomp Solutions Oy. SAP is a registered trademark of SAP AG in Germany and in several other countries. SmarTour is a trademark of PTV AG. Spider 5 is a trademark of Spider Solutions AS. TomTom and the “two hands” logo are registered trademarks of TomTom N.V. or one of its subsidiaries. TransIT is a trademark of GTS Systems and Consulting, GmbH. UNIX is a registered trademark of The Open Group in the United States and other countries. Figure 14.1 reprinted with permission from the United Nations Development Programme. Figures 14.3 and 14.12 reprinted with permission from Elsevier. Figures 14.6 and 14.9 reprinted with permission from John Wiley and Sons. Figure 14.14 reprinted with permission from INFORMS. Library of Congress Cataloging-in-Publication Data Vehicle routing problem. Vehicle routing : problems, methods, and applications / edited by Paolo Toth, University of Bologna, Bologna, Italy, Daniele Vigo, University of Bologna, Bologna, Italy. -- Second edition. pages cm. -- (MOS-SIAM series on optimization) Revision of: The vehicle routing problem. ©2002. Includes bibliographical references and index. ISBN 978-1-611973-58-7 1. Transportation problems (Programming) I. Toth, Paolo, editor. II. Vigo, Daniele, editor. III. Title. QA402.6.V44 2014 388.3’10285--dc23 2014029491 is a registered trademark. is a registered trademark. MO18_Toth_VigoFM-10-20-14.indd 4 10/20/2014 9:46:06 AM
    i i List of Contributors Claudia Archetti Dipartimento Metodi Quantitativi, Università di Brescia, Italy, archetti@eco.unibs.it Tolga Bekta¸s Southampton Management School, University of Southampton, UK, t.bektas@soton.ac.uk Olli Bräysy VU University of Amsterdam, The Netherlands, o.m.p.braysy@vu.nl Marielle Christiansen Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology of Trondheim, Norway, mc@iot.ntnu.no Jean-François Cordeau HEC Montréal, Québec, Canada, jean-francois.cordeau@hec.ca Guy Desaulniers Department of Mathematical and Industrial Engineering, École Polytechnique de Montréal, Québec, Canada, guy.desaulniers@polymtl.ca Karl F. Doerner Department of Business Administration, University of Vienna, Austria, karl.doerner@univie.ac.at Kjetil Fagerholt Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology of Trondheim, Norway, kjetil.fagerholt@iot.ntnu.no Michel Gendrau Department of Mathematical and Industrial Engineering, École Polytechnique de Montréal, Québec, Canada, michel.gendreau@polymtl.ca Bruce L. Golden Robert H. Smith School of Business, University of Maryland, MD, USA, bgolden@rhsmith.umd.edu Geir Hasle SINTEF ICT, Norway, geir.hasle@sintef.no Manuel Iori Dipartimento di Scienze e Metodi dell’Ingegneria, Università degli Studi di Modena e Reggio Emilia, Italy, manuel.iori@unimore.it Stefan Irnich Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Germany, irnich@uni-mainz.de Richard Eglese Department of Management Science, Lancaster University Management School, UK, R.Eglese@lancaster.ac.uk Ola Jabali Department of Logistics and Operations Management, HEC Montréal and CIRRELT, Québec, Canada, ola.jabali@hec.ca v
    i i vi List of Contributors Attila A. Kovacs Department of Business Administration, University of Vienna, Austria, attila.kovacs@univie.ac.at Frédéric Semet Ecole Centrale de Lille, Villeneuve d’Ascq Cedex, France, frederic.semet@ec-lille.fr Gilbert Laporte HEC Montréal, Québec, Canada, gilbert.laporte@cirrelt.ca Marcus Poggi Departamento de Informática, Pontifícia Universidade Católica de Rio de Janeiro, Brazil, poggi@inf.puc-rio.br Walter Rei D´rpartement de management et technologie, Université du Québec a Montréal, Québec, Canada, rei.walter@uqam.ca Panagiotis P. Repoussis Stevens Institute of Technology, Hoboken, NJ, USA, panagiotis.repoussis@stevens.edu Stefan Ropke Department of Management, Engineering, Technical University of Denmark, Kongens Lyngby, Denmark, ropke@dtu.dk Juan-José Salazar-González Departamento de Estadística, Investigación Operativa y Computación, Universidad de La Laguna, Tenerife, Spain, jjsalaza@ull.es M. Grazia Speranza Dipartimento di Economia e Management, Università degli Studi di Brescia, Italy, speranza@eco.unibs.it Christos D. Tarantilis Department of Management Science and Technology, Athens University of Economics and Business, Greece, tarantil@aueb.gr Paolo Toth Department of Electrical, Electronic, and Information Engineering “G. Marconi”, Università di Bologna, Italy, paolo.toth@unibo.it Eduardo Uchoa Departamento de Engenharia de Produção, Universidade Federal Fluminense, Niterói, Rio de Janeiro, Brazil, uchoa@producao.uff.br Thibaut Vidal Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, USA, vidalt@mit.edu Daniele Vigo Department of Electrical, Electronic, and Information Engineering “G. Marconi”, Università di Bologna, Italy, daniele.vigo@unibo.it Michael Schneider Logistikplanung und Informationssysteme, Technische Universität Darmstadt, Germany, schneider@bwl.tu-darmstadt.de Edward A. Wasil Kogod School of Business, American University, Washington, DC, USA, ewasil@american.edu
    i i Contents List of Figures List of Tables Preface to the Second Edition Preface to the First Edition 1 I 2 3 xi xiii xv xvii 1 1 3 8 23 35 The Family of Vehicle Routing Problems S. Irnich, P. Toth, D. Vigo Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 The Capacitated Vehicle Routing Problem . . . . . . . . . . . . . . . . . 1.2 1.3 The Family of VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Capacitated Vehicle Routing Problem Classical Exact Algorithms for the Capacitated Vehicle Routing Problem 37 F. Semet, P. Toth, D. Vigo 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Branch-and-Bound Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Early Set Partitioning Algorithms . . . . . . . . . . . . . . . . . . . . . . . 2.4 Branch-and-Cut Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Conclusions and Future Research Directions . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . New Exact Algorithms for the Capacitated Vehicle Routing Problem M. Poggi, E. Uchoa Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Main Exact Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Valid Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Branching vs. Route Enumeration . . . . . . . . . . . . . . . . . . . . . . . 3.6 Overview of Computational Results . . . . . . . . . . . . . . . . . . . . . 3.7 Conclusions and Future Research Directions . . . . . . . . . . . . . . . . 3.8 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 38 45 46 53 53 59 59 60 62 65 69 74 77 83 83 vii
    i i viii 4 II 5 6 7 8 Contents 87 Heuristics for the Vehicle Routing Problem G. Laporte, S. Ropke, T. Vidal 87 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 88 Constructive Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 89 Classical Improvement Heuristics . . . . . . . . . . . . . . . . . . . . . . . 4.3 90 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 94 Hybridizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 97 Unified Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Computational Comparison of Selected Metaheuristics . . . . . . . . . 99 4.7 4.8 Conclusions and Future Research Directions . . . . . . . . . . . . . . . . 109 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Important Variants of the Vehicle Routing Problem The Vehicle Routing Problem with Time Windows G. Desaulniers, O.B.G. Madsen, S. Ropke 117 119 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.1 Mathematical Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.2 Exact Solution Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.3 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 5.4 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 5.5 5.6 Conclusions and Future Research Directions . . . . . . . . . . . . . . . . 151 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 Pickup-and-Delivery Problems for Goods Transportation 161 M. Battarra, J-F. Cordeau, M. Iori Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6.1 Many-to-Many Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 6.2 One-to-Many-to-One Problems . . . . . . . . . . . . . . . . . . . . . . . . 165 6.3 One-to-One Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 6.4 Problems with Loading Constraints . . . . . . . . . . . . . . . . . . . . . 177 6.5 6.6 Conclusions and Future Research Directions . . . . . . . . . . . . . . . . 180 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 Pickup-and-Delivery Problems for People Transportation 193 K.F. Doerner, J.J. Salazar-González Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 7.1 Dial-a-Ride Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 7.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 7.3 Solution Methods for Dial-a-Ride Problems . . . . . . . . . . . . . . . . 199 7.4 Other Problems Concerning Pickup and Delivery of People . . . . . 203 7.5 7.6 Conclusions and Future Research Directions . . . . . . . . . . . . . . . . 207 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 Stochastic Vehicle Routing Problems M. Gendreau, O. Jabali, W. Rei 213 8.1 8.2 8.3 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 A Priori Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 The Reoptimization Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料