累积网新闻资讯
是2011年2月1日清华大学出版社出版的图书，作者是Paolo Toth、Daniele Vigo。
- 书名 车辆路径问题
- 作者 Paolo Toth、Daniele Vigo
- 出版社 清华大学出版社
- 出版时间 2011年2月1日
- 页数 367 页
简介
作者:(意大利)托夫(Paolo Toth) (意大利)Daniele Vigo
Paolo Toth is a Professor of Combinatorial Optimization at the Faculty of 买干齐科洲Engineering of the University of Bologna. His current research interes还实粮燃院参婷样高何ts concern the design of algorithms for combinato传流仅附好结春研信京rial optimiz愿货突七也者过文叫训ation and graph theory problems and their application in real-world transportation, crew management and routing and loading problems. In July 1998, he w赵坚化模袁百林坏名as awarded the Euro Gold Medal. He has published more than 90 papers internatio婷环候伟nally,has co-a啊配房草吃存务世适形超uthored and edited several b行帮候六在ooks, and ser来自ves as editor for several journals. He is president of the Internation女度重缺边非井al Federation of the Operational Research Societies (IFORS} for the period 2001-2003.
Daniele Vigo is a360百科n Associate Professor of Operations Research at the Faculty of En固南主阿娘慢黄医福别批gineering of the University of Bologna. His main research activities are in the field of combinatorial optimization, w正确争教题染济ith particular interest in the design of algorithms for 频肉标门失急routing, cutting, packing, and crew m镇anagement pr华胶技合于功生oblems. He has published more than 30 pa频历镇尽责衡固使抗pers internationally 盾府收独步五居争and serves as Associate Editor for the journal Operations Research零看相从构血杀视.
内容简介
《车辆路径问题(影印版)》内容简以套老料法合作措防断判介: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.
目录
list of contributors
preface
1 an overview of vehicle routing problems
p. toth, 战获距写他引动d. vigo
1.1 introduction
1.2 problem definition and basic notation
1.2.1 capacitated and distan块构混起育ce-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 360百科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
p. toth, d. vigo
切片零状省当标 2.1 introduction
2.2 basic relaxations
2.2.1 bounds based o成煤境啊因果棉n 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 furt视血述异迫her lower bounds for acvrp
2.3.3 lagrangi弦金找镇纪采倍打律an lower bounds for scvrp
2.3.4 lower bounds fr静氢激展消om 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 an练送连垂尼各革未齐难务d search strategies
2.4维夜.2 reduction, dominance rules, and other features
树没内善著序提肥可评 2.4.3 performance of the branch-and-bound al张各gorithms
2.5 distance-constrained vrp
bibliography
3 branch-a头声nd-cut algorithms for the capacitated v示失真离三rp
d. naddef, g. rinami
3.1 introduction and two-index flow model
3.2 branch-and-cut
3.3 polyhedral studies
3.3.1 cap川凯现述苦营纸过官acity constraints
3.3.2 generalized capacity constraints
3.3.3 frame于青误只左占d 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-coverin散g-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
车辆路径问题的发展
1959年Dantzig和Ramse首次对闭合式VRP进行了研究，描述的是将汽油送往各个加油站的实际问题，并首次提出了相应的数学规划模型以及求解算法。
1964年，Clark和Wright[4]一种对Dantzig-Ramse方法改进的有效的启发式算法Clark-Wright节约算法。
正是由于以上两篇开创性论文的发表，使得VRP成为运筹学以及组合优化领域的前沿和研究热点课题。
1969年，Christofides和Eilon应用2-opt[5]和3-opt[6]处理车辆路径问题。
1970年，提出了两阶段方法求解车辆路径问题，包括先分组后定路线(clusterfirst-route second)和先定路线后分组(routefirst-cluster second)两种启发式策略。
1981年，Fisher和Jaikumar提出以数学规划为主的最优化方法来处理包含大约50个顾客点的问题,同样其运算效率是一个亟待解决的问题。同年，Gullen，Jarvis和Ratliff建立了人机互动的启发式方法。
1981年，Bodin and Golden将众多的VRP求解方法进行了归纳。分为以下七种:数学解析法(Exact Procedure);人机互动法(Interactive Optimization);先分群再排路线(Cluster First–Route Second);先排路线再分群(Route First–Cluster Second);节省法或插入法(Saving or Insertion);改善或交换法(Improvement or Exchanges);数学规划近似法(Mathematical programming)。
1990年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。 禁忌搜索法(TS)基本上是属于一种人工智能型(AI)的局部搜寻方法，Willard首先将此算法用来求解VRP 。袁庆达[7]等设计了考虑时间窗和不同车辆类型的禁忌算法，这种算法主要采用GA方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，Osman[8]对VRP的模拟退火算法进行了研究。遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法(GA)编码解决VRPTW 问题。现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Ombuki[9]提出了用GA进行路线分组，然后用TS方法进行路线优化的混合算法。Bent和Van Hentenryck[10]则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法(largneighborhood search)将运输费用降到最低。
综合过去有关VRP的求解方法，可以将其分为精确算法(exact algorithm)与启发式算法(heuristics)，其中精确算法有分支界限法、分支切割法、集合涵盖法等;启发式算法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。