第一图书网

车辆路径问题

(美)托夫 等著 清华大学出版社
出版时间:

2011-2  

出版社:

清华大学出版社  

作者:

(美)托夫 等著  

页数:

367  

Tag标签:

无  

内容概要

  in the field of combinatorial optimization problems, the
vehicle routing problem (vrp) is one of the most challenging.
defined more than 40 years ago, the problem involves designing the
optimal set of routes for fleets of vehicles for the purpose of
serving a given set of customers . interest in vrp is motivated by
its practical relevance as well as its considerable
difficulty.
   the vehicle routing problem covers both exact and heuristic
methods developed for the vrp and some of its main variants,
emphasizing the practical issues common to vrp. the book is
composed of three parts containing contributions from well-known
experts. the first part covers basic vrp, known more commonly as
capacitated vrp. the second part covers three main variants of vrp:
with time windows, backhauls, and pickup and delivery. the third
part covers issues arising in real-world vrp applications and
includes both case studies and references to software
packages.
   this book will be of interest to both researchers and
graduate-level students in the communities of operations research
and mathematical sciences. it focuses on a specific family of
problems while offering a complete overview of the effective use of
the most important techniques proposed for the solution of hard
combinatorial problems. practitioners will find this book
particularly useful.
   reader need a basic knowledge of the main methods for the
solution of combinatorial optimization problems.

作者简介

作者:(美国)托夫(Paolo Toth) (美国)Daniele VigoPaolo Toth is a Professor of Combinatorial Optimization at the Faculty of Engineering of the University of Bologna. His current research interests concern the design of algorithms for combinatorial optimization and graph theory problems and their application in real-world transportation, crew management and routing and loading problems. In July 1998, he was awarded the Euro Gold Medal. He has published more than 90 papers internationally,has co-authored and edited several books, and serves as editor for several journals. He is president of the International Federation of the Operational Research Societies (IFORS} for the period 2001-2003.Daniele Vigo is an Associate Professor of Operations Research at the Faculty of Engineering of the University of Bologna. His main research activities are in the field of combinatorial optimization, with particular interest in the design of algorithms for routing, cutting, packing, and crew management problems. He has published more than 30 papers internationally and serves as Associate Editor for the journal Operations Research.

书籍目录

list of contributors
preface
1 an overview of vehicle routing problems
 1.1 introduction
 1.2 problem definition and basic notation
  1.2.1 capacitated and distance-constrained vrp
  1.2.2 vrp with time windows
  1.2.3 vrp with backhauls
  1.2.4 vrp with pickup and delivery
 1.3 basic models for the vrp
  1.3.1 vehicle flow models
  1.3.2 extensions of vehicle flow models
  1.3.3 commodity flow models
  1.3.4 set-partitioning models
 1.4 test instances for the cvrp and other vrps
 bibliography
ⅰ capacitated vehicle routing problem
 2 branch-and-bound algorithms for the capacitated vrp
  2.1 introduction
  2.2 basic relaxations
   2.2.1 bounds based on assignment and matching
   2.2.2 bounds based on arborescences and trees
   2.2.3 comparison of the basic relaxations
  2.3 better relaxations
   2.3.1 additive bounds for acvrp
   2.3.2 further lower bounds for acvrp
   2.3.3 lagrangian lower bounds for scvrp
   2.3.4 lower bounds from a set-partitioning formulation
   2.3.5 comparison of the improved lower bounds
  2.4 structure of the branch-and-bound algorithms for cvrp
   2.4.1 branching schemes and search strategies
   2.4.2 reduction, dominance rules, and other features
   2.4.3 performance of the branch-and-bound algorithms
  2.5 distance-constrained vrp
  bibliography
 3 branch-and-cut algorithms for the capacitated vrp
  3.1 introduction and two-index flow model
  3.2 branch-and-cut
  3.3 polyhedral studies
   3.3.1 capacity constraints
   3.3.2 generalized capacity constraints
   3.3.3 framed capacity constraints
   3.3.4 valid inequalities from stsp
?  3.3.5 valid inequalities combining bin packing and stsp
   3.3.6 valid inequalities from the stable set problem
  3.4 separation procedures
   3.4.1 exact separation of capacity constraints
   3.4.2 heuristics for capacity and related constraints
   3.4.3 stsp constraints
  3.5 branching strategies
  3.6 computational results
  3.7 conclusions
  bibliography
 4 set-covering-based algorithms for the capacitated vrp
  4.1 introduction
  4.2 solving the linear programming relaxation of p
  4.3 set-covering-based solution methods
   4.3.1 branch-and-bound algorithm for problem cg
   4.3.2 polyhedral branch-and-bound algorithm
   4.3.3 pseudo-polynomial lower bound on cmin
   4.3.4 solving pa via dual-ascent and branch-and-bound
  4.4 solving the set-covering integer program
   4.4.1 a cutting plane method
   4.4.2 branch-and-price
   4.4.3 additional comments on computational approaches
  4.5 computational results
  4.6 effectiveness of the set-covering formulation
   4.6.1 worst-case analysis
   4.6.2 average-case analysis
  bibliography
 5 classical heuristics for the capacitated vrp
  5.1 introduction
  5.2 constructive methods
   5.2.1 clarke and wright savings algorithm
   5.2.2 enhancements of the clarke and wright algorithm
   5.2.3 matching-based savings algorithms
   5.2.4 sequential insertion heuristics
  5.3 two-phase methods
   5.3.1 elementary clustering methods
   5.3.2 truncated branch-and-bound
   5.3.3 petal algorithms
   5.3.4 route-first, cluster-second methods
  5.4 improvement heuristics
   5.4.1 single-route improvements
   5.4.2 multiroute improvements
  5.5 conclusions
  bibliography
 6 metaheuristics for the capacitated vrp
  6.1 introduction
  6.2 simulated annealing
   6.2.1 two early simulated annealing algorithms
   6.2.2 osman's simulated annealing algorithms
   6.2.3 van breedam's experiments
  6.3 deterministic annealing
  6.4 tabu search
   6.4.1 two early tabu search algorithms
   6.4.2 osman's tabu search algorithm
   6.4.3 taburoute
   6.4.4 taillard's algorithm
   6.4.5 xu and kelly's algorithm
   6.4.6 rego and roucairol's algorithms
   6.4.7 barbarosoglu and ozgur's algorithm
   6.4.8 adaptive memory procedure of rochat and taillard
   6.4.9 granular tabu search of toth and vigo
   6.4.10 computational comparison
  6.5 genetic algorithms
   6.5.1 simple genetic algorithm
   6.5.2 application to sequencing problems
   6.5.3 application to the vrp
  6.6 ant algorithms
  6.7 neural networks
  6.8 conclusions
  bibliography
ⅱ important variants of the vehicle routing problem
 7 vrp with time windows
  7.1 introduction
  7.2 problem formulation
   7.2.1 formulation
   7.2.2 network lower bound
   7.2.3 linear programming lower bound
   7.2.4 algorithms
  7.3 upper bounds: heuristic approaches
   7.3.1 route construction
   7.3.2 route improvement
 ? 7.3.3 composite heuristics
   7.3.4 metaheuristics
   7.3.5 parallel implementations
   7.3.6 optimization-based heuristics
   7.3.7 asymptotically optimal heuristics
  7.4 lower bounds from decomposition approaches
   7.4.1 lagrangian relaxation
   7.4.2 capacity and time-constrained shortest-path problem.
   7.4.3 variable splitting
   7.4.4 column generation
   7.4.5 set-partitioning formulation
   7.4.6 lower bound
   7.4.7 commodity aggregation
   7.4.8 hybrid approach
  7.5 integer solutions
   7.5.1 binary decisions on arc flow variables
   7.5.2 integer decisions on arc flow variables
   7.5.3 binary decisions on path flow variables
   7.5.4 subtour elimination and 2-path cuts
   7.5.5 k-path cuts and parallelism
   7.5.6 integer decisions on (fractional and integer) time
variables
  7.6 special cases
   7.6.1 multiple tsp with time windows
   7.6.2 vrp with backhauls and time windows
  7.7 extensions
   7.7.1 heterogeneous fleet, multiple-depot, and initial
conditions
   7.7.2 fleet size
   7.7.3 multiple time windows
   7.7.4 soft time windows
   7.7.5 time- and load-dependent costs
   7.7.6 driver considerations
  7.8 computational results for vrptw.
  7.9 conclusions
  bibliography
 8 vrp with backhauls
  8.1 introduction
   8.1.1 benchmark instances
  8.2 integer linear programming models
   8.2.1 formulation of toth and vigo
   8.2.2 formulation of mingozzi, giorgi, and baldacci
  8.3 relaxations
   8.3.1 relaxation obtained by dropping the cccs
   8.3.2 relaxation based on projection
   8.3.3 lagrangian relaxation
   8.3.4 overall additive lower bound
   8.3.5 relaxation based on the set-partitioning model
  8.4 exact algorithms
   8.4. i algorithm of toth and vigo
   8.4.2 algorithm of mingozzi, giorgi, and baldacci
   8.4.3 computational results for the exact algorithms
  8.5 heuristic algorithms
   8.5.1 algorithm of deif and bodin
   8.5.2 algorithms of goetschalckx and jacobs-blecha
   8.5.3 algorithm of toth and vigo
   8.5.4 computational results for the heuristics
  bibliography
 9 vrp with pickup and delivery
  9.1 introduction
  9.2 mathematical formulation
   9.2.1 construction of the networks
   9.2.2 formulation
   9.2.3 service quality
   9.2.4 reduction of the network size
  9.3 heuristics
   9.3.1 construction and improvement
   9.3.2 clustering algorithms
   9.3.3 metaheuristics
   9.3.4 neural network heuristics
   9.3.5 theoretical analysis of algorithms
  9.4 optimization-based approaches
   9.4.1 single vehicle cases
   9.4.2 multiple vehicle cases
  9.5 applications
  9.6 computational results
  9.7 conclusions
  bibliography
ⅲ applications and case studies
 10 routing vehicles in the real world: applications in the solid
waste,
  10.1 introduction
  10.2 computerized vehicle routing in the solid waste
industry
   10.2.1 history
   10.2.2 background
   10.2.3 commercial collection
   10.2.4 residential collection
   10.2.5 case studies
   10.2.6 roll-on-roll-off
   10.2.7 further remarks
  10.3 vehicle routing in the beverage, food, and dairy
industries
   10.3.1 introduction
   10.3.2 beverage industry
   10.3.3 food industry
   10.3.4 dairy industry
  10.4 distribution and routing in the newspaper industry
   10.4.1 industry background
   10.4.2 newspaper distribution problem
   10.4.3 vehicle routing algorithms for ndp
   10.4.4 three case studies
   10.4.5 further remarks
  10.5 conclusions
  bibliography
 11 capacitated arc routing problem with vehicle-site dependencies:
the philadelphia experience
  11.1 introduction
  11.2 networks, assumptions, and goals of the carp-vsd
   11.2.1 travel network
   11.2.2 service network
   11.2.3 vehicle classes
   11.2.4 travel network and service network for a vehicle
class
   11.2.5 vehicle preference list
   11.2.6 other assumptions
   11.2.7 goals and constraints of the carp-vsd
  11.3 vehicle decomposition algorithm (vda)
   11.3.1 step a. create and verify vehicle class networks
   11.3.2 step b. estimate total work and determine initial fleet
mix
   11.3.3 step c. partition the service network
   11.3.4 step d. determine travel path and balance the
partitions
   11.3.5 step e. revise estimate of total work and adjust fleet
mix
  11.4 implementation of the vda in philadelphia
  11.5 enhancements and extensions
  bibliography
 12 inventory routing in practice
  12.1 introduction
  12.2 problem definition
  12.3 literature review
  12.4 solution approach
   12.4.1 phase i: integer programming model
   12.4.2 phase i: solving the integer programming model
   12.4.3 phase ii: scheduling
  12.5 computational experience
   12.5.1 instances
   12.5.2 solution quality
   12.5.3 alternate heuristic
   12.5.4 computational experiments
  12.6 conclusion
  bibliography
 13 routing under uncertainty: an application in the scheduling of
field service engineers
  13.1 introduction
  13.2 vrpsst with variable costs of recourse
  13.3 literature review
   13.3.1 vrpst
   13.3.2 vrpsd
  13.4 stochastic integer vrpsst formulation
   13.4.1 first-stage problem
   13.4.2 second-stage problem
  13.5 paired tree search algorithm (ptsa)
   13.5.1 linked trees
   13.5.2 lower bounds
   13.5.3 computational implementation
  13.6 applied maintenance scheduling problem
   13.6.1 maintenance scheduling system in practice
   13.6.2 stochastic problem setting
  13.7 modeling the applied problem as a vrpsst
  13.8 model input
   13.8.1 job locations and the road network
   13.8.2 service times
  13.9 model output: computational considerations
   13.9.1 framework for the analysis of results
   13.9.2 reoptimization
  13.10 example scenario
  13.11 overall computational results
  13.12 conclusion
  bibliography
 14 evolution of microcomputer-based vehicle routing software: case
studies in the united states
  14.1 introduction
  14.2 definition of the vrp
   14.2.1 customer specification
   14.2.2 product specification
   14.2.3 vehicle specification
  14.3 algorithms
  14.4 future trends in vehicle routing software
  14.5 summary and conclusions
  bibliography
index

章节摘录

版权页:插图:In this section we give a formal definition, as graph theoretic models, of the basic problems of the vehicle routing class. These problems, which have received the greatest attention in the scientific literature, are examined in detail in the first two parts of the book. We first describe the Capacitated VRP, which is the simplest and most studied member of the family, then we introduce the Distance-Constrained VRP, the VRP with Time Windows, the VRP with Backhauls, and the VRP with Pickup and Delivery.For each of these problems, several minor variants have been proposed and examined in the literature, and often different problems are given the same name. Although in many cases the solution methods, particularly the heuristic ones, may be adapted to incorporate additional features, this indeterminacy in problem definition generally causes much confusion. Therefore, for each problem we first describe the basic version, i.e., the one that in this book is denoted by the corresponding acronym, and then we discuss the variants. In addition, we make an explicit distinction between the symmetric and asymmetric versions of a problem only if models and solution approaches proposed in the literature make use of this distinction.Also in this section, we introduce all the relevant notation and terminology used throughout the book. Additional notation and definitions required to describe particular variants and practical VRP problems are given in the appropriate chapters. Figure 1.1 summarizes the main problems described in this section and illustrates their connections. In the figure, an arrow moving from problem A to problem B means that B is an extension of A.


编辑推荐

《车辆路径问题(影印版)》:国际著名数学图书

图书封面

图书标签Tags

广告

下载页面


车辆路径问题 PDF格式下载



值得细细研究,毕竟是车辆路径领域为数不多的好教材。


好书,比较好理解。


书不错,纸张不太好。


总是在找这本书,这次终于找着了。


送货速度真快,但是书的纸张好薄啊


不错的读本,建议再附上源代码更好


印刷质量差,纸有皱的


物流给力,书本还是因人而异吧,有这方面基础的可以考虑,专业性方面还是比较权威的。


全英文版的 比较难懂啊


相关图书