Arc Routing

Theory, Solutions and Applications

By: Moshe Dror (Editor)

Write A Review

Hardcover | 31 August 2000

At a Glance

Hardcover
516 Pages

Dimensions(cm)
23.5 x 15.88 x 3.18

Hardcover

$729.00

or 4 interest-free payments of $182.25 with

Ships in 5 to 7 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.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Mathematics Combinatorics & Graph Theory Business & Management Operational Research Applied Mathematics Engineering & Technology Mechanical Engineering & Materials Production & Industrial Engineering Computing & I.T.Computer Programming & Software Development Software Engineering

Other Editions and Formats

Paperback

Published: 4th October 2012

View Product

Preface	p. xvii
Contributing Authors	p. xiii
A Historical Perspective on Arc Routing	p. 1
Introduction	p. 1
The Chinese Postman Problem	p. 2
The Undirected CPP	p. 3
The Directed CPP	p. 6
The Mixed CPP	p. 7
The Windy CPP	p. 8
The Hierarchical CPP	p. 9
The Rural Postman Problem	p. 9
The Undirected RPP	p. 10
The Directed RPP	p. 10
The Mixed RPP	p. 11
The Capacitated Arc Routing Problem	p. 11
Research Outlooks	p. 12
Theory
Traversing Graphs: The Eulerian and Hamiltonian Theme	p. 19
Introductory Remarks	p. 19
Basics of Graph Theory	p. 20
Graphs and Their Parts	p. 20
Walks, Trails, Paths, Cycles; Connectedness	p. 23
Bipartite Graphs, Trees, Blocks, Mappings	p. 27
Connectivity, Menger's Theorem, the Splitting Lemma, and Factors	p. 32
Eulerian Graphs and Covering Walks, Cycle Decompositions and Cycle Covers	p. 40
Algorithms for Constructing Eulerian Trails	p. 47
Mazes	p. 48
Hamiltonian Cycles and Vertex-Covering Walks	p. 50
Elements of Matching Theory	p. 58
The Chinese Postman Problem, The Traveling Salesman Problem, and Related Problems	p. 69
Elements of Network Theory	p. 77
Matching: Arc Routing and the Solution Connection	p. 89
Introduction	p. 89
Matching: Applications	p. 91
Team Selection	p. 91
Task Scheduling	p. 92
Processor Scheduling	p. 93
Route Connection	p. 94
Arc Routing	p. 95
Node Routing	p. 98
General Routing	p. 101
Set Partitioning	p. 104
Matching: Combinatorial Aspects	p. 107
Matching: Polyhedral Aspects	p. 112
Matching Algorithms: Linking Combinatorial and Polyhedral Results	p. 116
Matching Algorithms: Implementation Issues	p. 119
Start Procedures: Constructing the Initial Extreme Matching	p. 120
Organization of Dual Updates	p. 122
Price and Reoptimize	p. 123
Arc Routing: Complexity and Approximability	p. 133
Introduction: Easy and Hard Problems	p. 133
CPP as a Problem in P	p. 141
NP-Hard Generalizations of the CPP	p. 143
The Mixed CPP	p. 143
The MCPP NP-Completeness	p. 144
The Rural Postman Problem	p. 147
The Windy Postman Problem	p. 148
Non-intersecting Eulerian Circuits and A-trails in Eulerian Graphs	p. 149
Dominating Trails	p. 151
Precedence in Arc Routing	p. 152
Capacitated Arc Routing	p. 154
Approximation Algorithms	p. 156
Approximation Results for Arc Routing	p. 159
The Mixed CPP	p. 159
The Windy CPP	p. 161
The RPP and Other Variants	p. 161
The CARP	p. 162
Conclusions	p. 164
Chinese Postman and Euler Tour Problems in Bi-directed Graphs	p. 171
Bi-directed Graphs, Euler Tours, and Postman Tours	p. 171
Aircraft Routing in a Space-time Network	p. 176
The Chinese Postman Problem in an Undirected Graph	p. 181
Binary Group Problems and Blocking Problems	p. 189
Ideal Binary Matrices	p. 192
Four Problems on Planar Graphs	p. 193
Solutions
Polyhedral Theory for Arc Routing Problems	p. 199
Introduction	p. 199
The Basics of Polyhedral Theory	p. 200
The Routing Problems Defined	p. 203
Variants of the Chinese Postman Problem	p. 205
The CPP	p. 205
The DCPP	p. 205
The MCPP	p. 206
The WPP	p. 208
Variants of the Rural Postman Problem	p. 209
The RPP	p. 209
The GRP	p. 212
The DRPP	p. 216
The MRPP	p. 217
The Capacitated Arc Routing Problem	p. 219
Preliminaries	p. 219
Sparse Formulations of the CARP	p. 220
The Dense and Supersparse Formulations of the CARP	p. 224
Conclusions	p. 226
Linear Programming Based Methods for Solving Arc Routing Problems	p. 231
Introduction	p. 232
Chinese Postman Problems	p. 236
The Undirected CPP	p. 236
Odd-Cut Separation	p. 237
The Directed CPP	p. 238
The Mixed CPP	p. 239
A Cutting Plane Algorithm for the MCPP	p. 240
Odd-Cut Separation	p. 241
Balanced Set Separation	p. 242
The Windy Postman Problem	p. 243
Rural Postman Problems	p. 244
The Undirected RPP	p. 244
Connectivity Separation	p. 246
R-odd cut Separation	p. 246
K-C Inequalities Separation	p. 247
Cutting Plane and Branch and Cut Algorithms for the RPP	p. 249
The General Routing Problem	p. 250
Honeycomb Separation	p. 251
Path-Bridge Separation	p. 253
Cutting Plane and Branch and Cut Algorithms for the GRP	p. 255
The Directed RPP	p. 256
The Mixed RPP	p. 257
Connectivity Separation	p. 258
R-odd Cut and Balanced Set Separation	p. 259
K-C and Path-Bridge Separation	p. 259
The Capacitated Arc Routing Problem	p. 259
Sparse Formulations	p. 260
Connectivity Separation	p. 261
Parity Separation	p. 262
Obligatory Cutset Separation	p. 263
Separation of Constraints from the Knapsack Problem	p. 263
Supersparse Formulation for the CARP	p. 264
Capacity Constraints Separation	p. 267
Disjoint Path Inequalities Separation	p. 267
Exact Methods Based on the Sparse Formulation	p. 268
A Cutting Plane Algorithm for the CARP Based on the Supersparse Formulation	p. 269
Other Problems	p. 269
Conclusions	p. 270
Transformations and Exact Node Routing Solutions by Column Generation	p. 277
Introduction	p. 278
Transformations to Node Routing: Why?	p. 279
The Capacitated Rural Postman Problem	p. 279
Mathematical Formulation of the CARP	p. 280
Time Window Constraints for Arc Routing	p. 281
When to Transform to Node Routing	p. 282
Arc Routing Transformations: How	p. 283
Transformations of Uncapacitated Arc Routing Problems	p. 284
Transformations of Capacitated Arc Routing Problems	p. 285
Transformation of CARP with Time Windows to VRPTW	p. 287
Split Delivery Arc Routing with Time Windows	p. 289
Column Generation for Routing Problems with Non-split Delivery	p. 290
Revised Simplex: Chvatal's Introduction to Column Generation	p. 290
Set Covering, Vehicle Routing, and Column Generation	p. 292
The Shortest Path Subproblem	p. 294
An Algorithm for the Shortest Path with Resource Constraints	p. 295
Solving SPRCP with only Elementary Paths	p. 297
Overlooking an Optimal Elementary Path	p. 299
An SPRCP--Improved Elementary Path Algorithm	p. 300
Description of the Algorithm	p. 302
Column Generation for Routing Problems with Split Delivery	p. 305
Properties of Split Deliveries with Triangle Inequality	p. 306
Formulation	p. 308
Set Covering Approach for Split Deliveries	p. 309
The Subproblem for Generating Feasible Columns for Split Delivery	p. 311
Formulating the Subproblem	p. 312
Alternating between the Master Problem and the Subproblem	p. 313
The Computational Phase: A Mixed Integer Solver and a Dynamic Programming Algorithm	p. 314
Discretizing the Split Deliveries in the SPPRC Subproblem	p. 315
Discussion of Computational Experiments for the SDVRPTW	p. 316
Another Set Covering Formulation for SDVRPTW	p. 317
The (MP[subscript 3]) Model and Column Generation Approach	p. 318
The Branching Scheme for the SDVRPTW	p. 321
Conclusion	p. 322
Heuristic Algorithms	p. 327
Introduction	p. 327
Heuristics for Uncapacitated Arc Routing Problems	p. 329
The Chinese Postman Problem	p. 329
The undirected chinese postman problem	p. 329
The directed chinese postman problem	p. 331
The mixed chinese postman problem	p. 332
The windy postman problem	p. 336
The Rural Postman Problem	p. 338
The undirected rural postman problem	p. 338
The directed rural postman problem	p. 340
The mixed rural postman problem	p. 344
The stacker crane problem	p. 349
Additional algorithmic tools	p. 355
Heuristics for Capacitated Arc Routing Problems	p. 361
Simple Constructive Methods for the CARP	p. 361
Two-Phase Constructive Methods for the CARP	p. 373
Route first-cluster second algorithms	p. 373
Cluster first-route second algorithms	p. 377
Meta-Heuristics for the CARP	p. 379
Conclusion	p. 383
Applications
Roadway Snow and Ice Control	p. 389
Introduction	p. 389
Brief History of RSIC	p. 390
Characteristics of Arc Routing for RSIC	p. 392
Solution Approaches	p. 395
Early Work	p. 396
Recent Work	p. 400
CASPER	p. 400
GeoRoute	p. 406
Ottawa, Canada	p. 408
Suffolk County, UK	p. 410
Other Recent Work	p. 411
Future	p. 413
Scheduling of Local Delivery Carrier Routes for the United States Postal Service	p. 419
Introduction	p. 420
The Route Adjustment Process	p. 422
Inspection	p. 422
Route Adjustment	p. 423
Auxiliary (or Remnant) Routes	p. 424
Types of Delivery Routes	p. 424
Park and Loop Routes	p. 425
Curbline/ Dismount Routes	p. 426
Combined Park and Loop and Curbline/ Dismount Routes	p. 426
Relay Box Routes	p. 427
Lines of Travel for the Four Types of Postal Delivery Routes	p. 427
Walking Line of Travel	p. 428
Driving Line of Travel	p. 428
Examples of the Lines of Travel for the Four Types of Postal Delivery Routes	p. 429
Park and Loop Routes	p. 430
Curbline/ Dismount Routes	p. 431
Combined Park and Loop and Curbline/ Dismount Routes	p. 432
Relay Box Routes	p. 433
Discussion	p. 434
Algorithm for Route Adjustment	p. 435
Estimate the Number of Routes to Form	p. 436
Partition the AOI	p. 437
Form the Line of Travel for each Partition	p. 438
Is the Solution Balanced?	p. 439
Manual Intervention	p. 440
Conclusions	p. 440
Livestock Feed Distribution and Arc Traversal Problems	p. 443
Introduction	p. 444
The Cattle Industry	p. 444
The Cattle Yard Operations	p. 444
Livestock Feed Distribution as Arc Traversals	p. 447
Arc-Routing Models for Pen Inspection and Feed Delivery	p. 448
Mathematical Formulation of the Capacitated Rural Postman Problem (CRPP)	p. 448
Split Deliveries	p. 450
Time Windows	p. 451
A Heuristic Approach for Trip Generation	p. 452
Generating a Non-split Feasible Solution	p. 452
Extended Path Scanning Algorithm for Feeding-Time Feasibility	p. 453
Modified Augment-Merge Algorithm	p. 454
Arc Swapping	p. 455
Generating Split Delivery Routes	p. 456
Route Addition	p. 456
Route-First Cluster-Second Generalized TSP Heuristic	p. 457
The Generalized Traveling Salesman Problem	p. 457
Transforming the CRPP to an Equivalent GTSP	p. 457
Solving the Equivalent GTSP	p. 458
Computational Results	p. 458
Epilogue	p. 461
Table of Contents provided by Syndetics. All Rights Reserved.

Arc Routing

Theory, Solutions and Applications

At a Glance

Hardcover

Shipping

How to return your order

Defective items

You Can Find This Book In

Other Editions and Formats

Paperback

More in Production & Industrial Engineering

Deep Learning Applications in Operations Research

The Site Reliability Workbook

Practical ways to implement SRE

Manufacturing Engineering and Technology in SI Units

8th Edition

The Origins of Efficiency

Safety Metrics

Tools and Techniques for Measuring Safety Performance

Reliability Engineering and Risk Analysis

A Practical Guide, Third Edition

Particle-fluid and Multiphase Flows

Particle-fluid and Multiphase Flows

Rules of Thumb for Maintenance and Reliability Engineers

Machinery Failure Analysis and Troubleshooting, Fourth Edition

Practical Machinery Management for Process Plants

Systems Engineering

Design Principles and Models

Assessing Innovation

Metrics, Rubrics, and Standards

Living Interaction Design

The Transition Towards Designed Interactive Living Systems for Regenerative Ecologies

Living Interaction Design

The Transition Towards Designed Interactive Living Systems for Regenerative Ecologies

Scheduling Variable Capacity Resources for Sustainability

Industry 4.0 in Composite Manufacturing Industry for Sustainable Development

Automotive Product Development

A Systems Engineering Implementation

Designing for Kids

Creating for Playing, Learning and Growing

Designing for Kids

Creating for Playing, Learning and Growing

Logistics for Engineers

Automatic Control, Network Science, and Industry 4.0

Sustainable Surface Engineering Approaches for Industrial Applications

Sustainable Coating Solutions

Fuzzy-Model-Based Mode Control of Complex Nonlinear Systems

Engineering Mathematics and Operations Research

Diversity in Women's Entrepreneurship

Global Sustainability in African Countries

Gas Turbine Combined Cycle Power Plants

Nanomaterials for Smart Manufacturing

Fundamental Principles, Theory, Case Studies, and Advanced Applications

This product is categorised by