Trip Reconstruction by Mathematical Optimization Algorithms
“What ticket do I have to buy to get from Zurich Airport to Zurich main station and from there to ETH Zurich? Going back the same day, can I save money by not buying single tickets? Maybe I do some sightseeing, is it worthwhile purchasing a day ticket?”
With XIXO Siemens Next Generation Ticketing, there is no need to answer these questions before starting a journey. Check in at the start stop using a ticketing app running on your phone, get on board, and, possibly after changing trains, get off at the destination stop. The rest is left to the system: your trips are reconstructed, and, after a day of traveling, the guaranteed best price is calculated for all your trips together.
Explained above is a Check-In/Be-Out system where no user interaction is required at the destination. Siemens also developed the variants Check-In/Check-Out and Be-In/Be-Out, where a user interaction is required at the start and end stop of a journey or at neither of the two, respectively. The term XIXO resembles all possible variants.
Collection of positioning and motion data
To reconstruct the trips a user made, data have to be collected along the way.
Most importantly, GPS (Geographical Positioning System) coordinates are collected to track the position of the passenger over time, starting with onboarding. The coordinates are subject to uncertainties, depending on the visibility of GPS-satellites, the phone, the presence of subway lines or tunnels, the type of vehicle, buildings in the near, or weather conditions. To get extra information, Bluetooth Low Energy beacons can be installed at stations (especially subway or roofed stations) or in vehicles. The phones receive beacon signals containing the beacon Id, from which conclusions can be drawn about the visited vehicle or station. In addition, smartphone sensors are used to get probabilities for different means of transport (“activities”), for example walking, cycling, or riding in a vehicle.
Embedded into the trip detection engine of a distributed real-time backend system, the trip reconstruction algorithms use the collected data together with infrastructure information (location of stations, timetables) to derive the sequence of trips the user made (i.e., the sequence of trip IDs as given in the schedules). This task is challenging for several reasons: first, as mentioned above, data are uncertain, secondly, the amount of data is huge. Moreover, if several vehicles serve the same road sections at about the same time, how can we decide? The sequence of stops might help, but which of the stops passed are really stops served by the vehicle and not just driven by? Speed does not always help, just think of traffic lights, where vehicles might have to stop. Real-time schedules are not always available or reliable, so also delays come into the play. Passengers checking-in way too late or too early add some extra difficulty.
Despite all these obstacles, combinatorial optimization algorithms together with stochastic analysis are capable of matching the passenger trips to the scheduled timetable trips with a reliability fulfilling the requirements for real-life operation.
The appeal of these modern ticketing systems lies in their simplicity for the user (“just go”) and the promise of being charged the lowest price afterwards, even if the journeys invoke several fare systems. Often, journeys can be covered with different combinations of tickets (single tickets, day tickets, zone tickets, short distance tickets, special offers on certain partial routes etc.). The number of possibilities quickly becomes very large, and one cannot afford to try out all the variants. Thanks to mathematical theory, combinatorial algorithms find a provably optimal solution without explicitly trying out everything.
My Travel Day in Switzerland
By traveling with the real-life implementation of our, throughout Switzerland publicly available, Check-In/Check-Out system, I could experience the convenience and reliability of our ticketing solution myself. Travelling from Zürich to Wallisellen one morning, not sure, if I would visit a friend and colleague in Dachsen in the evening before returning to my hotel in Zürich, didn’t cost me a split-second of thinking about tariffs or how likely it is that I go for the visit.
“Swiping-In” with the app, getting on board, and following the trip on the app, showing the currently identified partial trip, was fun. Logging in into the developers’ backend GUI (graphical interface), and at the same time watching data coming in and being processed, was even more exciting.
On the next image, you can see that I decided for the evening visit, thus doing three journeys composed of five different trips in total. If I had bought single tickets only (not knowing in advance that I would visit my colleague), I would have spent 41,20 CHF. Luckily, I traveled with XIXO and was charged 28,70 CHF the next day.
From Proof-of-Concept to a Productive System
Trip reconstruction, as highlighted above, was done by optimization experts of #SiemensAI, at the Siemens Technology Department, in a long-term cooperation with Siemens Mobility Switzerland. An international team comprised of Siemens Business Units, Siemens Technology, our external partners Noser Engineering and intesso, our partner and customer Schweizerische Südostbahn (SOB), and later the Siemens subsidiaries eos.uptrade and HaCon, built the system from scratch through all phases from the proof-of-concept till the installation of ticketing systems open for the public.
The real-life test deployments, pilots, and publicly available XIXO implementations proofed that the Siemens solution fulfills all requirements for a productive system and is fit to compete in a highly competitive market.
In the end of 2019, the project was transferred to the Siemens subsidiaries HaCon and eos.uptrade which since then operate and further develop the system.
In 2020, Germany’s first Check-In/Be-Out system went life for the public with the Osnabrück public transport company (VOS). With this digital public transport initiative, the Stadtwerke Osnabrück AG, the city’s public utilities, won the first place in the STADTWERKE AWARD 2020.
Smart ticketing soon in your city?
More and more transport companies are opting to offer their customers the convenience of a next generation ticketing system. Chances are good, that you too will be able to enjoy the benefits of a Check-In/Be-Out system in your city in the near future. Check your local transport company’s website to find out if a launch is upcoming.
Within #SiemensAI, we have spent over 30 years leveraging artificial intelligence in the arts of engineering to create safe and sustainable solutions for real-world applications such as XIXO.
If you would like to find out more about our research or our AI services, please be invited to get in touch, directly, or via the Siemens AI Lab.