How to cluster trips, i.e. directed lines on a plain

I need to cluster transports/trips based on their start point and end point in longitude/latitude.

I have about 5000 trips. Each has a starting point (lon/lat) and an end point (lon/lat). I computed the haversine distance between those points. Bases on these five criteria (start lon, start lat, end lon, end lat, distance) I want to find clusters.

I tried kmeans and DBSCAN, but the results are not intuitive. Are there any established clustering algorithms for this problem?

• What do you want to find with your clusters? – user3644640 Oct 18 '16 at 10:36
• Similar trips. Similar by start region and end region – mondano Oct 18 '16 at 10:49

One trick could be that, for each pair of flights you calculate a distance between start $d_s$ and end points $d_e$, and sum them. You can try to use other metrics for distance like $d_s^2+d_e^2$ or $(d_s+d_e)^2$. Then you get $flights\times flights$ distance matrix, which you then may cluster.