Public Transport Optimization

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