车辆路径问题(英文影印版)

.p. toth, d. vigo
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
d. naddef, g. rinami
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
j. bramel, d. simchi-levi
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
g. laporte, f. semet
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
m. gendreau, g. laporte, j y. potvin
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
j.-f. cordeau, g. desaulniers, j. desrosiers, m. m. solomon, e soumis
7. i 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
p. toth, d. vigo
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
g. desaulniers, j. desrosiers, a. erdmann, m. m. solomon, f. soumis
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,
beverage, food, dairy, and newspaper industries
b. l. golden, a. a. assad, e. a. wasil
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
j. sniezek, l. bodin, l. levy, m. ball
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
ann m. campbell, lloyd w. clarke, martin w.p. savelsbergh
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
e. hadjiconstantinou, d. roberts
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
e. k. baker
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