Public Transport Optimization

Description

This textbook provides a comprehensive step-by-step guide for new public transport modelers. It includes an introduction to mathematical modeling, continuous and discrete optimization, numerical optimization, computational complexity analysis, metaheuristics, and multi-objective optimization. These tools help engineers and modelers to use better existing public transport models and also develop new models that can address future challenges. By reading this book, the reader will gain the ability to translate a future problem description into a mathematical model and solve it using an appropriate solution method. The textbook provides the knowledge needed to develop highly accurate mathematical models that can serve as decision support tools at the strategic, tactical, and operational planning levels of public transport services. Its detailed description of exact optimization methods, metaheuristics, bi-level, and multi-objective optimization approaches together with the detailed description of implementing these approaches in classic public transport problems with the use of open source tools is unique and will be highly useful to students and transport professionals. Preface Acknowledgements Contents Acronyms Part I Mathematical Programming of Public Transport Problems 1 Introduction to Mathematical Programming 1.1 Mathematical Modeling 1.1.1 Introductory Definitions 1.1.2 Basics of Linear Algebra 1.1.3 Basics of Differentiation 1.1.4 Basics of Propositional Logic 1.2 General Representation of an Optimization Problem 1.2.1 Sets, Parameters and Variables 1.2.2 Objectives 1.2.3 Constraints 1.2.4 Modeling Example of a Public Transport Problem 1.3 Continuous Optimization 1.3.1 Introduction 1.3.2 Example of a Continuous Public Transport Optimization Problem 1.4 Discrete Optimization 1.4.1 Introduction 1.4.2 Combinatorial Optimization 1.4.3 Mixed-Integer Problems 1.5 Global and Local Optimum 1.5.1 Local Optimum 1.5.2 Global Optimum 1.5.3 Convexity 1.5.4 Example of a Convex Transport Problem 1.6 Linear Programming Reformulations 1.6.1 Linearizations of Max and Absolute Terms 1.6.2 Linearization of a Fractional Program 1.6.3 Product Function to a Separable Function 1.6.4 Linearization of Conditional Expressions 1.6.5 Linearization of Constraints on a Collection of Variables 1.6.6 Linearizations of Nonlinear Functions with Piecewise Linear Functions Exercises References 2 Introduction to Computational Complexity 2.1 Big O Notation 2.2 Big Omega (Ω) and Big Theta (Θ) Notations 2.3 P vs NP 2.4 NP-complete, NP-Hard and Other Classes 2.5 Decision vs Optimization Problems 2.6 Reductions 2.6.1 Reduction Example I: SAT leqp 3SAT 2.6.2 Reduction Example II: Vertex Cover leqp Independent Set 2.6.3 Reduction Example III: Vertex Cover leqp Set Cover 2.6.4 2SAT and Problems in P Exercises References 3 Continuous Unconstrained Optimization 3.1 Single-Dimensional Problems 3.1.1 Necessary Conditions for Local Optimality 3.1.2 Sufficient Conditions for Local Optimality 3.1.3 Global Optimality 3.2 Multivariate Problems 3.2.1 Necessary Conditions for Local Optimality 3.2.2 Sufficient Conditions for Local Optimality 3.2.3 Global Optimality 3.3 Optimization Algorithms 3.3.1 Order of Convergence 3.3.2 Line Search Strategy 3.3.3 Exact and Inexact Methods for Determining the Step Length 3.3.4 Steepest/Gradient Descent Line Search Method 3.3.5 Newton Line Search Method 3.3.6 Quasi-Newton Line Search Methods (DFP, BFGS, SR1, Broyden) 3.3.7 Conjugate Gradient Line Search Method 3.3.8 Trust-Region Strategy Exercises References 4 Continuous Constrained Optimization 4.1 Necessary Conditions for Local Optimality 4.1.1 Duality 4.1.2 Necessary Conditions for Opimization Problems with Equality Constraints (Lagrange Multipliers) 4.1.3 Necessary Conditions for Opimization Problems with Equality and Inequality Constraints (Karush-Kuhn-Tucker) 4.2 Second-order Sufficient Conditions for Local Optimality 4.3 Global Optimality 4.4 More Advanced Topics in Linear Algebra 4.5 Linear Programming 4.5.1 Simplex 4.5.2 Two-phase Simplex 4.5.3 Revised Simplex 4.5.4 Dual Simplex 4.5.5 Karmarkar's Interior Point Method 4.6 Quadratic Programming 4.6.1 Equality-Constrained Convex Quadratic Programs 4.6.2 Convex Quadratic Programs with Equality and Inequality Constraints 4.7 Sequential Quadratic Programming 4.8 Interior Point Method in Nonlinear Programming 4.8.1 Step Direction 4.8.2 Step Length 4.8.3 Termination Criterion 4.8.4 Updating the Barrier Parameter 4.8.5 Dealing with Nonconvexity and Practical Implementation 4.9 Penalty and Augmented Lagrangian Methods 4.9.1 Penalty Methods 4.9.2 Augmented Lagrangian Methods References 5 Discrete Optimization 5.1 Introduction 5.2 Branch and Bound 5.2.1 Mixed-integer Problems with Binary Variables 5.2.2 Problems with Continuous and Discrete Variables 5.3 Branch and Bound Decisions 5.3.1 Leaf Node Selection 5.3.2 Selection of Branching Variable 5.4 Branch and Cut for Integer Linear Programming 5.4.1 Intuition of Cutting Planes 5.4.2 Gomory Cutting Planes 5.4.3 Branch & Cut and Cut & Branch 5.5 Integer and Mixed-integer Formulations of Common Combinatorial Problems Exercises References Part II Solution Approximation with Artificial Intelligence: The Case of Metaheuristics 6 Metaheuristics 6.1 Heuristics vs Metaheuristics 6.2 Genetic Algorithms 6.2.1 Encoding 6.2.2 Fitness Function 6.2.3 Selection for Reproduction 6.2.4 Crossover 6.2.5 Mutation 6.2.6 Population Evolution 6.2.7 Termination Criteria 6.3 Simulated Annealing 6.3.1 Temperature Update 6.3.2 Replacing Probability 6.4 Tabu Search 6.5 Differential Evolution 6.6 Particle Swarm Optimization Exercises References 7 Multi-objective Optimization 7.1 Multi-objective Optimization 7.2 Classic a Priori MOOP Methods 7.2.1 Weighted Sum Method 7.2.2 Lexicographic Method 7.3 A Posteriori MOOP Methods: Mathematical Programming and Metaheuristics 7.3.1 Weighted Sum Method 7.3.2 ε-Constraint Method 7.3.3 Multi-objective Evolutionary Algorithms (MOEAs) Exercises References Part III Public Transport Optimization: From Network Design to Operations 8 Strategic Planning of Public Transport Services 8.1 Trip Distribution 8.1.1 Entropy Maximization 8.1.2 Growth Factor Method 8.1.3 Gravity Method 8.2 Design of Stops 8.2.1 Location Set Covering Problem 8.2.2 The Maximal Covering Location Problem 8.2.3 The m-center Problem 8.3 Shortest Paths 8.3.1 Dijkstra's Algorithm 8.3.2 Dijkstra's Algorithm with Binary Heap 8.3.3 Shortest Path Problem as an Integer Linear Program 8.3.4 All-pairs Shortest Path Problem 8.3.5 K-shortest Paths Problem 8.4 Line Planning 8.4.1 General Outline 8.4.2 Line Planning Problem with a Multi-commodity Flow Formulation 8.4.3 Skeleton Heuristic 8.4.4 Further Reading 8.5 Network Complexity and Connectivity Exercises References 9 Tactical Planning of Public Transport Services: Frequencies and Timetables 9.1 Frequency Settings 9.1.1 Closed-form Methods 9.1.2 Model-based Frequency Setting 9.1.3 Passenger Assignment based on Line Frequencies 9.1.4 Subline Frequency Setting 9.2 Transit Network Timetabling 9.2.1 Closed-form Methods 9.2.2 Model-based Timetabling Exercises References 10 Tactical Planning of Public Transport Services: Multi-modal Synchronization 10.1 Multi-modal Synchronization Without Hierarchy 10.1.1 Maximal Multi-modal Synchronization Without Hierarchy 10.1.2 Multi-modal Synchronization Without Hierarchy and Time Windows at Transfers 10.2 Multi-modal Synchronization with Hierarchy: Feeder and Collector Lines Exercises References 11 Tactical Planning of Public Transport Services: Vehicle and Crew Schedules 11.1 Vehicle Scheduling 11.1.1 Single-Depot Vehicle Scheduling Problem (SD-VSP) 11.1.2 Multiple-Depot Vehicle Scheduling Problem 11.2 Crew Scheduling 11.2.1 Crew Scheduling as a Fixed Job Scheduling Problem with Spread-Time Constraints 11.2.2 Crew Scheduling as a Set Partitioning Problem Exercises References 12 Tactical Planning of On-Demand and Shared Mobility Services 12.1 Introduction 12.2 Planning the Route of a Single Vehicle: Traveling Salesman Problem 12.3 Planning the Routes of Multiple Vehicles: Capacitated Vehicle Routing Problem 12.4 Dial-a-Ride Problem 12.4.1 Classic DARP 12.4.2 Dial-a-Ride with Interchange Point Exercises References 13 Operational Planning and Control 13.1 General Overview of Operational Planning 13.2 Rescheduling Approaches 13.2.1 Rescheduling Vehicles 13.2.2 Rescheduling the Dispatching Times of High-frequency Services 13.3 Vehicle Holding 13.3.1 Single-variable Vehicle Holding Problems 13.3.2 Multi-variable Vehicle Holding Problems 13.4 Stop-skipping 13.4.1 Single-trip Stop-skipping 13.4.2 Stop-skipping of Multiple Trips in Rolling Horizons Exercises References Appendix A Solutions Index