【内容简介】
　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.
【目次】
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 pa……