Public Transport Optimization

ISBN-13: 9783031124433 / Angielski / Twarda / 2023 / 626 str.

Konstantinos Gkiotsalitis

Opis

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.

Spis treści

Part I Mathematical Programming of Public Transport Problems

1 Introduction to Mathematical Programming

1.1 Mathematical Modeling

1.2 General Representation.

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 Public Transport Problem

1.4 Discrete Optimization.

1.4.1 Introduction

1.4.2 Combinatorial Optimization.

1.4.3 Integer and 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 Public Transport Problem

1.6 Linear and Nonlinear Programming.

1.7 Exercises

1.8 References

2 Introduction to Computational Complexity.

2.1 Big O Notation

2.2 Big _ Notation

2.3 P vs NP.

2.4 Exercises

2.5 References

3 Continuous Unconstrained Optimization

3.1 Single-dimensional Problems

3.1.1 Necessary Conditions

3.1.2 Sufficient Conditions

3.1.3 Global Optimality

3.2 Multivariate Problems

3.2.1 Necessary Conditions

3.2.2 Sufficient Conditions

3.2.3 Global Optimality

3.3 Optimization Algorithms

3.3.1 Line Search with Golden Section Search

3.3.2 Gradient Descent

3.3.3 Conjugate Gradient (CG).

3.3.4 Newton-CG

3.3.5 Trust Region

3.3.6 Quasi-Newton Methods.

3.3.7 Broyden-Fletcher-Goldfarb-Shanno (BFGS).

3.3.8 Limited-Memory BFGS.

3.4 Exercises

3.5 References

4 Continuous Constrained Optimization

4.1 First-order Necessary Conditions: Karush-Kuhn-Tucker.

4.1.1 Saddle point.

4.1.2 Stationarity

4.1.3 Primal feasibility

4.1.4 Dual feasibility.

4.1.5 Complementary slackness

4.1.6 Constraint Qualifications.

4.2 Second-order Sufficient Conditions

4.2.1 Global Optimality

4.2.2 Example in a Public Transport Problem.

4.3 Lagrange Multipliers

4.3.1 Duality

4.4 Optimization Algorithms

4.4.1 Interior Point Method

4.4.2 Sequential Quadratic Programming

4.4.3 Penalty Methods

4.5 The special case of Linear Programming.

4.5.1 Simplex

4.5.2 Interior Point Method

4.6 The special case of Quadratic Programming

4.6.1 Equality-Constrained QuadraticPrograms

4.6.2 Inequality-Constrained QuadraticPrograms.

4.7 Exercises

4.8 References

5 Discrete Optimization.

5.1 Branch and Bound.

5.2 Branch and Cut

5.3 Exercises

5.4 References

Part II Solution Approximation with Artificial Intelligence: The case of metaheuristics

6 Metaheuristics for Discrete Optimization Problems

6.1 Genetic Algorithms

6.2 Simulated Annealing

6.3 Ant Colony Optimization

6.4 Tabu search.

6.5 Further Reading

6.6 Exercises

6.7 References

7 Metaheuristics for Continuous Optimization Problems

7.1 Differential Evolution.

7.2 Particle Swarm Optimization

7.3 Further Reading

7.4 Exercises

7.5 References

8 Multi-objective Optimization Metaheuristics.

8.1 Pareto Optimality.

8.2 Vector-evaluated Genetic Algorithm (VEGA).

8.3 Non-dominated Sorting Genetic Algorithm II (NSGA-II)

8.4 The _-based Multi-objective Evolutionary Algorithm (_-MOEA).

8.5 Exercises

8.6 References

Part III Public Transport Optimization: from Network Design to Operations

9 Public Transport Network Design

9.1 Design of Stops

9.1.1 Optimal Stop Density

9.1.2 Network Coverage: the Optimal Stop Location Problem

9.1.3 Network Complexity and Connectivity.

9.2 Route Selection

9.2.1 Shortest Path Problem

9.2.2 All-pairs Shortest Path Problem

9.2.3 K-shortest Paths Problem.

9.3 Multi-objective Route Selection.

9.4 Exercises

9.5 References

10 Tactical Planning of Public Transport Services

10.1 Frequency Settings

10.2 Timetabling.

10.3 Vehicle Scheduling

10.4 Crew Scheduling.

10.5 Exercises

10.6 References

11 Multi-modal Synchronization at the Tactical Planning Stage

11.1 Synchronizing Feeder Lines with Collector Lines

11.2 Multi-modal Synchronization without Hierarchy.

11.3 Exercises

11.4 References

12 Operational Planning and Control.

12.1 Short-turning Approaches.

12.2 Interlining Approaches.

12.3 Vehicle Holding

12.4 Speed Control

12.5 Stop-skipping.

12.6 On-demand and Shared Mobility Services.

12.6.1 Planning the route of a single vehicle: Traveling Salesman Problem

12.6.2 Planning the routes of Multiple Vehicles: Capacitated Vehicle Routing Problem.

12.7 Exercises

12.8 References

13 Planning under Uncertainty

13.1 Uncertainty in Problem Parameters

13.2 Confidence interval-based Approaches

13.3 Stochastic Optimization

13.3.1 Formulation and Probability Distributions.

13.3.2 Sample Average Approximation with Monte Carlo Simulations

13.4 Robust Optimization

13.4.1 Wald’s maximin model: Performing well in worst-casescenarios.

13.4.2 Evolutionary Approaches

13.4.3 Problem Relaxation with Discretization.

13.5 Exercises

13.6 References

O autorze

Dr Konstantinos Gkiotsalitis is an Assistant Professor in data science in transportation engineering at the Transport Engineering and Management (TEM) group, Dept. of Civil Engineering, University of Twente. His research focuses on mathematical modeling and optimization in transport, with specific emphasis on public transport planning and operations. From 2012 until 2018, he was conducting industrial research related to public transport optimization at NEC Laboratories Europe (Heidelberg, Germany) with a specific focus on EU and APAC markets. 

He received his PhD from the National Technical University of Athens on unveiling the mobility patterns of individuals and matching the public transportation supply with the travel demand. He also received his bachelor's degree in Civil Engineering from the National Technical University of Athens (2010) and his MSc in Transport and Sustainable Development from Imperial College London and University College London (2012).

He has been involved in several EU and international projects on smart cities, urban mobility, public transport operations, MaaS, and logistics, and he holds several patents in the aforementioned areas. He is also Review Coordinator of the Transit Management and Performance committee (AP010) at the Transportation Research Board, and he has served as guest editor on public transport-related special issues in scientific journals. He has authored more than 45 peer-reviewed scientific articles in international scientific journals in the area of public transport optimization and he has received the 2022 Best Paper Award in the highly impactful Transport Reviews journal.