Introduction
People like travelling. Sometimes they need to reach some point in the world because they are going on vacations, sometimes this is a business case. People ride trains, use ships, use flying machines to reach their destination. Not always you can take a single transport vehicle and go to the destination point from your current location. Often you need to use multiple Transfers between intermediate Points to reach your destination Point.
The problem
The well known problem: finding a path between two points, where you have a set of transfers between some of the points in the set. But the problem is even harder when you must consider timings: when each transfer starts and when it ends, when you have to reach the destination point.
If you have lots for Points and Transfers, it is a large amount of data. The large amount of data needs databases to store them into. But if you use simple sqls to find a Path using multiple Transfers using intermediate Points to your destination Point, you are going to fail, because there is no good default solution to create such a SQL index to work your sql fast enough. The problem is that when you join Transfers using time intervals like (sourcePoint.arrivalTime < intermediatePoint.departureTime and sourcePoint.arrivalTime > DATE_ADD(destinationPoint.deparatureTime, INTERVAL 8 HOUR) ), there is no way to create a good table index to handle such a condition.
The solution
The solution is to use discrete time intervals, that I call clustering strategy in my example application.
I will not go into to details here, but I provide test results using clustering strategy and a simple sql join strategy to find travel Paths.
There are two databases with generated data to test strategies, mentioned above: test_normal and test_complete.
Each database contains about 1000 generated Points, and about 1000 000 generated transfers for a time period from 2027-01-01 to 2027-12-01.
Points are aligned to a 30×30 grid square, where distance between two neighbor Points is 6000 units. There are periodic transfers between each two neighbor points at 8 directions (up, down, left, right and 4 diagonal directions). This is how test_normal database data looks like.
In the test_complete database points of coordinate X=0, are treated as HUB points, and have additional travels with each other HUB point. Also, there are additional travels with each HUB point and remaining points, whose Y coordinate is the same as a HUB point’s Y coordinate.
This way you should always find a Path if you use 4 transfers between any two Points in the test_complete database.
In the test_normal database you will find a Path between two points A and B if the distance between them is equal to or lesser than Transfer amount multiplied by 6000.
Maximum connection hours should be considered between intermediate points, when you expect to find a Path. The longer is a connection period between transfers, the higher possibility to find a Path, but for the traveler it is less comfortable to wait longer in the intermediate Point to continue his travel.
Also, longer connection periods cause a bigger load on the database when the Path finding algorithm is running.
Summary experiment results
When you use 2 Transfers (one time of transport vehicle change) for finding a Path, simple algorithm does well running max 0.17 s ; but if you try to find a Path with 3 Transfers (two times of transport vehicle change), running sql always timeouts (longer than 15s).
Using clustering strategy Paths with transfers count 4, are found efficiently faster than by 1 second.
Paths with transfers count 5 and connection time 32 hours are found in 4 to 5 s in database test_normal. And in 3 to 7s in database test_complete.
The experimental code is deployed at http://darbelis.eu:7080, you may try to search Paths by yourself. The long running queries are interrupted by the DB statement configuration if they reach the running time of 30s (15s if the Transfers count <= 3 ).
The detailed experiments’ data are collected in the separate files.
- experiment_8clustered_normal
- experiment_8clustered_complete
- experiment_simple_normal
- experiment_simple_complete
Source code: https://github.com/kukulis/persedimai
2025-12-26