Flows In Transportation Networks

FLOWS IN TRANSPORTATION NETWORKS This is Volume 90 in MATHEMATICS IN SCIENCE AND ENGINEERING A series of monographs and textbooks Edited by RICHARD BELLMAN, University of Southern California The complete listing of books in this series is available from the Publisher upon request. Flows in Transportation Networks RENFREY B. POTTS ROBERT M. OLIVER Department of Applied Mathematics University of Adelaide Adelaide, Australia Department of Industrial Engineering and Operations Research University of California Berkeley, California ACADEMIC PRESS New YorkandLondon COPYRIGHT 0 1972, BY ACADEMIC PRESS,INC. ALL RIGHTS RESERVED NO PART OF THIS BOOK MAY BE REPRODUCED IN ANY FORM, BY PHOTOSTAT, MICROFILM, RETRIEVAL SYSTEM, OR ANY OTHER MEANS, WITHOUT WRITTEN PERMISSION FROM THE PUBLISHERS. ACADEMIC PRESS, INC. 111 Fifth Avenue, New York, New York 10003 United Kingdom Edition published by ACADEMIC PRESS, INC. (LONDON) LTD. 24/28 Oval Road, London NWl LIBRARY OF CONGRESS CATALO~ CARDNUMBER: 70-182673 PRINTED IN THE UNITED STATES OF AMERICA CONTENTS ix xi Preface Acknowledgments Chapter I TRANSPORTATION NETWORKS 1. Introduction 2. Examples of Transportation Networks (a) City Street Network (b) Main Road Network (c) Traffic Desire Network (d) Spider Web Network 3. Transportation Planning Process 4. Conclusion 5. Notes and References 1 2 2 4 9 9 10 13 13 Chapter I1 ELEMENTS OF NETWORK THEORY 6. Introduction 7. Graphs: Definitions and Notations (a) Directed Graph (b) Chain and Cycle (c) Path and Mesh (d) Accessible and Connected Nodes (e) Cut-Set (f) Undirected and Mixed Graphs (g) Tree and Arborescence V 17 18 18 19 21 22 22 24 24 vi Contents 8. Flows and Conservation Laws 9. 10. 11. 12. (a) Link Flows and Kirchhoff’s Law (b) Single 0-D Network: Link Flows ( c ) Single 0-D Network: Chain Flows (d) Multiple 0-D Network (e) Compressibility and Separability Costs and Capacities (a) Link, Route, and Network Costs (b) Capacitated Network Conclusion Notes and References Problems 26 26 29 32 34 36 38 38 41 43 44 45 Chapter 111 EXTREMAL PRINCIPLES AND TRAFFIC ASSIGNMENT 13. Introduction 14. Cheapest Routes (a) Appraisal of Algorithms (b) Tree-Building Algorithms 15. 16. 17. 18. (c) Turn Penalties and Prohibitions (d) Cheapest Route Assignment Minimum Network Cost (a) Link Flows (b) Chain Flows (c) The Out-of-Kilter Algorithm Flow Dependent Costs (a) Multicommodity Formulation (b) Equilibrium Flow Patterns for Noncooperative Users (c) Minimum Network Cost Flow Patterns (d) Associated Traffic Assignment Problems (e) A Numerical Example with Four Commodities (f) Congested Assignment Notes and References Problems 49 51 51 52 56 63 65 66 71 75 86 87 88 91 95 96 100 102 109 Chapter IV TRIP DISTRIBUTION 19. 20. 21. 22. Introduction Model Formulation Hitchcock Model Entropy Models (a) Network Entropy (b) Proportional Model (c) Mean Trip Length Model (d) Gravity Model 115 116 118 121 121 123 130 133 Contents vii 23. Opportunity Models 136 137 138 141 142 142 143 143 144 149 24. 25. 26. 27. (a) Intervening Opportunities Model (b) Preferencing Model Combined Distribution and Assignment (a) TRC Program (b) LTS Program (c) Multicommodity Distribution-Assignment Conclusion Notes and References Problems Appendix A THEOREM FOR CHEAPEST ROUTE ALGORITHMS 153 Appendix B 157 DUALITY THEORY Appendix C INEQUALITIES FOR MARGINAL AND AVERAGE LINK AND CHAIN COSTS 159 Appendix D ANSWERS TO P