Efficient optimization of schedules in a public transportation system
View Patent ↗Methods and systems are disclosed for optimizing public transportation schedules. Shifts from current schedules associated with a public transportation system can be evaluated. The impact on waiting times can then be determined, based on evaluating the shifts from the current schedules. Schedules associated with the public transportation system are then optimized based on the impact on the waiting times. Public transport schedules can thus be optimized by minimizing the waiting time during, for example, transfers. Using ticket validation data to construct a realistic scenario-based model of the waiting times, a goal of this approach is to compute shifts of the current schedules that reduce the overall expected waiting time.
1. A method for improving a public transportation system by optimizing public transportation schedules, said method comprising:
evaluating shifts from current schedules associated with a public transportation system, wherein said shifts include offsets comprising time shifts and wherein said evaluating of said shifts involves an evaluation of said offsets, said evaluation including computing a series of minimums in a distributed fashion;
determining an impact of said shifts including said offsets on waiting times in said public transportation system based on said evaluating of said shifts from said current schedules associated with said public transportation system; and
optimizing schedules associated with said public transportation system based on said impact of said shifts including said offsets on said waiting times, wherein said evaluating said shifts, said determining said impact of said shifts, and said optimizing said schedules improve the public transportation system and wherein said evaluating said shifts from said current schedules further comprises exploring random shifts from said current schedules utilizing a parallel local search with parallel iterations.
2. The method of claim 1 wherein said parallel heuristic search produces parallel heuristic search results.
3. The method of claim 1 wherein said evaluating shifts from said current schedules associated with said public transportation system, further comprises:
finding a shift of each transit trip among a plurality of transit trips associated with said current schedules so as to minimize an expected transfer waiting time among said waiting times.
4. The method of claim 1 wherein evaluating shifts from current schedules associated with a public transportation system, further comprises:
randomly selecting a subset of trips among a plurality of transit trips associated with said current schedules to offset;
randomly selecting a perturbation of said offset within an adequate boundary; and
evaluating an impact of said offset.
5. The method of claim 4 wherein optimizing said schedules further comprises updating a best schedule among said schedules.
6. The method of claim 4 further comprising running parallel instances with different seeds.
7. A system for improving a public transportation system by optimizing public transportation schedules, said system comprising:
at least one processor; and
a non-transitory computer-usable medium embodying computer program code, said computer-usable medium capable of communicating with said at least one processor, said computer program code comprising instructions executable by said at least one processor and configured for:
evaluating shifts from current schedules associated with a public transportation system, wherein said shifts include offsets comprising time shifts and wherein said evaluating of said shifts involves an evaluation of said offsets, said evaluation including computing a series of minimums in a distributed fashion;
determining an impact of said shifts including said offsets on waiting times in said public transportation system based on said evaluating of said shifts from said current schedules associated with said public transportation system; and
optimizing schedules associated with said public transportation system based on said impact of said shifts including said offsets on said waiting times, wherein said evaluating said shifts, said determining said impact of said shifts, and said optimizing said schedules improve the public transportation system and wherein said evaluating said shifts from said current schedules further comprises exploring random shifts from said current schedules utilizing a parallel local search with parallel iterations.
8. The system of claim 7 wherein said parallel heuristic search produces parallel heuristic search results.
9. The system of claim 7 wherein said instructions for evaluating shifts from said current schedules associated with said public transportation system further comprise instructions configured for finding a shift of each transit trip among a plurality of transit trips associated with said current schedules so as to minimize an expected transfer waiting time among said waiting times.
10. The system of claim 8 wherein said instructions for evaluating shifts from current schedules associated with a public transportation system, further comprises instructions configured for:
randomly selecting a subset of trips among a plurality of transit trips associated with said current schedules to offset;
randomly selecting a perturbation of said offset within an adequate boundary; and
evaluating an impact of said offset.
11. The system of claim 10 wherein said instructions for optimizing said schedules further comprise instructions configured for updating a best schedule among said schedules.
12. The system of claim 10 further comprising instructions configured for running parallel instances with different seeds.
13. A non-transitory processor-readable medium storing computer code representing instructions to cause a process for improving a public transportation system by optimizing public transportation schedules, said computer code comprising code to:
evaluate shifts from current schedules associated with a public transportation system, wherein said shifts include offsets comprising time shifts and wherein said evaluate of said shifts involves an evaluation of said offsets, said evaluation including computing a series of minimums in a distributed fashion;
determine an impact of said shifts including said offsets on waiting times in said public transportation system based on said evaluating of said shifts from said current schedules associated with said public transportation system; and
optimize schedules associated with said public transportation system based on said impact of said shifts including said offsets on said waiting times, wherein said evaluate of said shifts, said determine of said impact of said shifts, and said optimize of said schedules improve the public transportation system and wherein said code to evaluate said shifts from said current schedules further comprises code for exploring random shifts from said current schedules utilizing a parallel local search with parallel iterations.
14. The non-transitory processor-readable medium of claim 13 wherein said parallel heuristic search produces parallel heuristic search results.
15. The non-transitory processor-readable medium of claim 13 wherein said code to evaluate shifts from said current schedules associated with said public transportation system further comprises code to find a shift of each transit trip among a plurality of transit trips associated with said current schedules so as to minimize an expected transfer waiting time among said waiting times.
16. The non-transitory processor-readable medium of claim 14 wherein said code to evaluate shifts from current schedules associated with a public transportation system, further comprises code to:
randomly select a subset of trips among a plurality of transit trips associated with said current schedules to offset;
randomly select a perturbation of said offset within an adequate boundary; and
evaluate an impact of said offset.
17. The non-transitory processor-readable medium of claim 16 wherein said code to optimize said schedules further comprises code for updating a best schedule among said schedules.