Timetabling with flexible frequencies to synchronise groups of bus lines at common stops

ABSTRACT

In this study, we present a bi-objective partially-integrated optimisation approach for frequency setting and timetabling problems, assuming that buses' speed depends on the departure time of trips. Our goal is to synchronise groups of bus lines at common stops, minimising the average waiting time at synchronisation points and operational costs in terms of lines' frequencies. Our optimisation problem is formulated as a mixed-integer linear programme, which uses time-indexed variables to define a linear approximation of the average waiting time. Moreover, we present an experimental stage using the commercial solver CPLEX, a weighted sum method implementing a Biased Random-Key Genetic Algorithm (BRKGA) to solve the problem, and a BRKGA combined with the Hierarchical Non-dominated Sorting Algorithm to obtain an approximation of the Pareto front for bi-objective version. Numerical results show that our proposed metaheuristics are handy tools to obtain better solutions in short computational times than the solver of CPLEX.

KEYWORDS:

• Timetabling
• flexible frequencies
• synchronisation
• bus transportation systems
• bi-objective optimisation

Acknowledgments

This research was partially supported by the UANL-PAICYT, under Grant CE870-19.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 The relative gap is computed as $\left(\frac{SolutionCPLEX-DualBound}{SolutionCPLEX}\right)100\mathrm{\%}$

2 The relative improvement of BRKGA over CPLEX is computed as $\left(\frac{SolutionCPLEX-SolutionBRKGA}{SolutionCPLEX}\right)100\mathrm{\%}$

Additional information

Funding

This research was partially supported by the Universidad Autónoma de Nuevo León (UANL-PAICYT), under Grant CE870-19.