+612 9045 4394
$7.95 Delivery per order to Australia and New Zealand
100% Australian owned
Over a hundred thousand in-stock titles ready to ship
ARC Routing : Theory, Solutions and Applications - Moshe Dror

ARC Routing

Theory, Solutions and Applications

By: Moshe Dror (Editor)

Hardcover Published: 31st August 2000
ISBN: 9780792378983
Number Of Pages: 483

Share This Book:


or 4 easy payments of $126.65 with Learn more
Ships in 10 to 15 business days

Earn 1013 Qantas Points
on this Book

Other Available Editions (Hide)

  • Paperback View Product Published: 4th October 2012
    Ships in 10 to 15 business days

Arc Routing: Theory, Solutions and Applications is about arc traversal and the wide variety of arc routing problems, which has had its foundations in the modern graph theory work of Leonhard Euler. Arc routing methods and computation has become a fundamental optimization concept in operations research and has numerous applications in transportation, telecommunications, manufacturing, the Internet, and many other areas of modern life. The book draws from a variety of sources including the traveling salesman problem (TSP) and graph theory, which are used and studied by operations research, engineers, computer scientists, and mathematicians. In the last ten years or so, there has been extensive coverage of arc routing problems in the research literature, especially from a graph theory perspective; however, the field has not had the benefit of a uniform, systematic treatment. With this book, there is now a single volume that focuses on state-of-the-art exposition of arc routing problems, that explores its graph theoretical foundations, and that presents a number of solution methodologies in a variety of application settings. Moshe Dror has succeeded in working with an elite group of ARC routing scholars to develop the highest quality treatment of the current state-of-the-art in arc routing.

Prefacep. xvii
Contributing Authorsp. xiii
A Historical Perspective on Arc Routingp. 1
Introductionp. 1
The Chinese Postman Problemp. 2
The Undirected CPPp. 3
The Directed CPPp. 6
The Mixed CPPp. 7
The Windy CPPp. 8
The Hierarchical CPPp. 9
The Rural Postman Problemp. 9
The Undirected RPPp. 10
The Directed RPPp. 10
The Mixed RPPp. 11
The Capacitated Arc Routing Problemp. 11
Research Outlooksp. 12
Traversing Graphs: The Eulerian and Hamiltonian Themep. 19
Introductory Remarksp. 19
Basics of Graph Theoryp. 20
Graphs and Their Partsp. 20
Walks, Trails, Paths, Cycles; Connectednessp. 23
Bipartite Graphs, Trees, Blocks, Mappingsp. 27
Connectivity, Menger's Theorem, the Splitting Lemma, and Factorsp. 32
Eulerian Graphs and Covering Walks, Cycle Decompositions and Cycle Coversp. 40
Algorithms for Constructing Eulerian Trailsp. 47
Mazesp. 48
Hamiltonian Cycles and Vertex-Covering Walksp. 50
Elements of Matching Theoryp. 58
The Chinese Postman Problem, The Traveling Salesman Problem, and Related Problemsp. 69
Elements of Network Theoryp. 77
Matching: Arc Routing and the Solution Connectionp. 89
Introductionp. 89
Matching: Applicationsp. 91
Team Selectionp. 91
Task Schedulingp. 92
Processor Schedulingp. 93
Route Connectionp. 94
Arc Routingp. 95
Node Routingp. 98
General Routingp. 101
Set Partitioningp. 104
Matching: Combinatorial Aspectsp. 107
Matching: Polyhedral Aspectsp. 112
Matching Algorithms: Linking Combinatorial and Polyhedral Resultsp. 116
Matching Algorithms: Implementation Issuesp. 119
Start Procedures: Constructing the Initial Extreme Matchingp. 120
Organization of Dual Updatesp. 122
Price and Reoptimizep. 123
Arc Routing: Complexity and Approximabilityp. 133
Introduction: Easy and Hard Problemsp. 133
CPP as a Problem in Pp. 141
NP-Hard Generalizations of the CPPp. 143
The Mixed CPPp. 143
The MCPP NP-Completenessp. 144
The Rural Postman Problemp. 147
The Windy Postman Problemp. 148
Non-intersecting Eulerian Circuits and A-trails in Eulerian Graphsp. 149
Dominating Trailsp. 151
Precedence in Arc Routingp. 152
Capacitated Arc Routingp. 154
Approximation Algorithmsp. 156
Approximation Results for Arc Routingp. 159
The Mixed CPPp. 159
The Windy CPPp. 161
The RPP and Other Variantsp. 161
The CARPp. 162
Conclusionsp. 164
Chinese Postman and Euler Tour Problems in Bi-directed Graphsp. 171
Bi-directed Graphs, Euler Tours, and Postman Toursp. 171
Aircraft Routing in a Space-time Networkp. 176
The Chinese Postman Problem in an Undirected Graphp. 181
Binary Group Problems and Blocking Problemsp. 189
Ideal Binary Matricesp. 192
Four Problems on Planar Graphsp. 193
Polyhedral Theory for Arc Routing Problemsp. 199
Introductionp. 199
The Basics of Polyhedral Theoryp. 200
The Routing Problems Definedp. 203
Variants of the Chinese Postman Problemp. 205
The CPPp. 205
The DCPPp. 205
The MCPPp. 206
The WPPp. 208
Variants of the Rural Postman Problemp. 209
The RPPp. 209
The GRPp. 212
The DRPPp. 216
The MRPPp. 217
The Capacitated Arc Routing Problemp. 219
Preliminariesp. 219
Sparse Formulations of the CARPp. 220
The Dense and Supersparse Formulations of the CARPp. 224
Conclusionsp. 226
Linear Programming Based Methods for Solving Arc Routing Problemsp. 231
Introductionp. 232
Chinese Postman Problemsp. 236
The Undirected CPPp. 236
Odd-Cut Separationp. 237
The Directed CPPp. 238
The Mixed CPPp. 239
A Cutting Plane Algorithm for the MCPPp. 240
Odd-Cut Separationp. 241
Balanced Set Separationp. 242
The Windy Postman Problemp. 243
Rural Postman Problemsp. 244
The Undirected RPPp. 244
Connectivity Separationp. 246
R-odd cut Separationp. 246
K-C Inequalities Separationp. 247
Cutting Plane and Branch and Cut Algorithms for the RPPp. 249
The General Routing Problemp. 250
Honeycomb Separationp. 251
Path-Bridge Separationp. 253
Cutting Plane and Branch and Cut Algorithms for the GRPp. 255
The Directed RPPp. 256
The Mixed RPPp. 257
Connectivity Separationp. 258
R-odd Cut and Balanced Set Separationp. 259
K-C and Path-Bridge Separationp. 259
The Capacitated Arc Routing Problemp. 259
Sparse Formulationsp. 260
Connectivity Separationp. 261
Parity Separationp. 262
Obligatory Cutset Separationp. 263
Separation of Constraints from the Knapsack Problemp. 263
Supersparse Formulation for the CARPp. 264
Capacity Constraints Separationp. 267
Disjoint Path Inequalities Separationp. 267
Exact Methods Based on the Sparse Formulationp. 268
A Cutting Plane Algorithm for the CARP Based on the Supersparse Formulationp. 269
Other Problemsp. 269
Conclusionsp. 270
Transformations and Exact Node Routing Solutions by Column Generationp. 277
Introductionp. 278
Transformations to Node Routing: Why?p. 279
The Capacitated Rural Postman Problemp. 279
Mathematical Formulation of the CARPp. 280
Time Window Constraints for Arc Routingp. 281
When to Transform to Node Routingp. 282
Arc Routing Transformations: Howp. 283
Transformations of Uncapacitated Arc Routing Problemsp. 284
Transformations of Capacitated Arc Routing Problemsp. 285
Transformation of CARP with Time Windows to VRPTWp. 287
Split Delivery Arc Routing with Time Windowsp. 289
Column Generation for Routing Problems with Non-split Deliveryp. 290
Revised Simplex: Chvatal's Introduction to Column Generationp. 290
Set Covering, Vehicle Routing, and Column Generationp. 292
The Shortest Path Subproblemp. 294
An Algorithm for the Shortest Path with Resource Constraintsp. 295
Solving SPRCP with only Elementary Pathsp. 297
Overlooking an Optimal Elementary Pathp. 299
An SPRCP--Improved Elementary Path Algorithmp. 300
Description of the Algorithmp. 302
Column Generation for Routing Problems with Split Deliveryp. 305
Properties of Split Deliveries with Triangle Inequalityp. 306
Formulationp. 308
Set Covering Approach for Split Deliveriesp. 309
The Subproblem for Generating Feasible Columns for Split Deliveryp. 311
Formulating the Subproblemp. 312
Alternating between the Master Problem and the Subproblemp. 313
The Computational Phase: A Mixed Integer Solver and a Dynamic Programming Algorithmp. 314
Discretizing the Split Deliveries in the SPPRC Subproblemp. 315
Discussion of Computational Experiments for the SDVRPTWp. 316
Another Set Covering Formulation for SDVRPTWp. 317
The (MP[subscript 3]) Model and Column Generation Approachp. 318
The Branching Scheme for the SDVRPTWp. 321
Conclusionp. 322
Heuristic Algorithmsp. 327
Introductionp. 327
Heuristics for Uncapacitated Arc Routing Problemsp. 329
The Chinese Postman Problemp. 329
The undirected chinese postman problemp. 329
The directed chinese postman problemp. 331
The mixed chinese postman problemp. 332
The windy postman problemp. 336
The Rural Postman Problemp. 338
The undirected rural postman problemp. 338
The directed rural postman problemp. 340
The mixed rural postman problemp. 344
The stacker crane problemp. 349
Additional algorithmic toolsp. 355
Heuristics for Capacitated Arc Routing Problemsp. 361
Simple Constructive Methods for the CARPp. 361
Two-Phase Constructive Methods for the CARPp. 373
Route first-cluster second algorithmsp. 373
Cluster first-route second algorithmsp. 377
Meta-Heuristics for the CARPp. 379
Conclusionp. 383
Roadway Snow and Ice Controlp. 389
Introductionp. 389
Brief History of RSICp. 390
Characteristics of Arc Routing for RSICp. 392
Solution Approachesp. 395
Early Workp. 396
Recent Workp. 400
CASPERp. 400
GeoRoutep. 406
Ottawa, Canadap. 408
Suffolk County, UKp. 410
Other Recent Workp. 411
Futurep. 413
Scheduling of Local Delivery Carrier Routes for the United States Postal Servicep. 419
Introductionp. 420
The Route Adjustment Processp. 422
Inspectionp. 422
Route Adjustmentp. 423
Auxiliary (or Remnant) Routesp. 424
Types of Delivery Routesp. 424
Park and Loop Routesp. 425
Curbline/ Dismount Routesp. 426
Combined Park and Loop and Curbline/ Dismount Routesp. 426
Relay Box Routesp. 427
Lines of Travel for the Four Types of Postal Delivery Routesp. 427
Walking Line of Travelp. 428
Driving Line of Travelp. 428
Examples of the Lines of Travel for the Four Types of Postal Delivery Routesp. 429
Park and Loop Routesp. 430
Curbline/ Dismount Routesp. 431
Combined Park and Loop and Curbline/ Dismount Routesp. 432
Relay Box Routesp. 433
Discussionp. 434
Algorithm for Route Adjustmentp. 435
Estimate the Number of Routes to Formp. 436
Partition the AOIp. 437
Form the Line of Travel for each Partitionp. 438
Is the Solution Balanced?p. 439
Manual Interventionp. 440
Conclusionsp. 440
Livestock Feed Distribution and Arc Traversal Problemsp. 443
Introductionp. 444
The Cattle Industryp. 444
The Cattle Yard Operationsp. 444
Livestock Feed Distribution as Arc Traversalsp. 447
Arc-Routing Models for Pen Inspection and Feed Deliveryp. 448
Mathematical Formulation of the Capacitated Rural Postman Problem (CRPP)p. 448
Split Deliveriesp. 450
Time Windowsp. 451
A Heuristic Approach for Trip Generationp. 452
Generating a Non-split Feasible Solutionp. 452
Extended Path Scanning Algorithm for Feeding-Time Feasibilityp. 453
Modified Augment-Merge Algorithmp. 454
Arc Swappingp. 455
Generating Split Delivery Routesp. 456
Route Additionp. 456
Route-First Cluster-Second Generalized TSP Heuristicp. 457
The Generalized Traveling Salesman Problemp. 457
Transforming the CRPP to an Equivalent GTSPp. 457
Solving the Equivalent GTSPp. 458
Computational Resultsp. 458
Epiloguep. 461
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9780792378983
ISBN-10: 0792378989
Audience: General
Format: Hardcover
Language: English
Number Of Pages: 483
Published: 31st August 2000
Publisher: Springer
Country of Publication: US
Dimensions (cm): 23.39 x 15.6  x 2.87
Weight (kg): 0.89

Earn 1013 Qantas Points
on this Book