Bus Stops Problem: Solving for 4000 Addresses in a City

[acertijo4ever]

Hi all, I have the following problem I need to solve, and I hope you can point me to the right direction.

I have a bunch (4000) of people addresses in a city that are mapped to coordinates (longitude and latitude). I also have different bus routes (up to 17), that go through the city picking up these people, that I could draw to google maps for example. This routes were designed based on human experience, and the buses that travel on them practically have to stop every time a person raises one's hand (sometimes on every block), which is pretty inefficient.

What I would like to do is to define a number of Bus Stops, along all of the routes, that comply with the following restrictions:

- Each bus stop groups the most people near that point according to their addresses.
- The number of Bus Stops doesn't have to be the minimun available, but the best in order for people not to walk too far from their houses.
- The routes should not be modified.

I know there's a lot of work to be done so I'd appreciate any help.

Regards.
Joel

 

[mfb]

Where do the people go to?

Those problems rarely have exact optimal answers that you could find with reasonable computing effort, so algorithms that start with some solution and improve this step by step are the typical approach.

 

[acertijo4ever]

People go all to the same place, its a transportation system for a company that collects people from the city and takes them to work.

Thanks for your answer, I think the same, maybe I' ll have to use some AI approach, like a Genetic Algorithm that improves a specified function at each iteraction.

 

[Pepper Mint]

Based on your current criteria, I think you can go with clustering methods to look up the centroid of each cluster which is where the bus stop should be located. Genetic Algorithm used to look up optimums seems like an overkill to the problem and its required mating and fitness functions to generate new population also are not always easy to design.

 

[mfb]

We have multiple bus routes, so just making bus stops based on clusters is not sufficient for an optimal solution - the stops should also produce up to 17 aligned paths for the buses.

 

[acertijo4ever]

I could be a little more specific, the bus stop needs to be X meters away from people's addresses (in practice 300 meters) and this should be fulfilled for at least Y% of people (in practice 80% of them), if I find such bus stops then I can declare victory.

The question is what method to use, and if it has been done before, so I can check out other alternative solutions. Thanks for your help.

 

[mfb]

I would guess that manual tuning is not too bad. There are so many things that are hard to consider in algorithms - convenient locations where the bus can stop, connections between stops, and so on. Anyway, a clustering algorithm can be a good start.

 

[rootone]

I suppose that the optimum delivery of passengers must involve an equation which minimizes the total of distances that passengers have to walk to get to their intended destination.

(assuming that there is no delays, like their having a drink or some fast food, or whatever)

 

[Dominik Tugend]

Sorry for being picky, but you probably want to give an criteria for minimizing the number of bus stops.

Otherwise the optimal solution could be computed as follows:

1) For each address determine shortest distance to a route and thus the point for a stop
2) Remove any duplicate points (not too likely)

That way you probably won't end up with much less stops than addresses you have :-(

 

[Dominik Tugend]

Just want do add that step 2) can become an complicated problem too (i.e. if 1 address has multiple possible points due to equal distances).

 

[Tom.G]

Perhaps something on the order of K-MEANS clustering. https://en.wikipedia.org/wiki/K-means_clustering
Its advantage is you don't have to define the cluster characteristics, ' just' the number of clusters.

NOTES: Well, plus figure out how to constrain to the existing bus routes. This in itself might rule out K-MEANS. Maybe do some preprocessing to include riders only within a certain distance of a route, then run the algorithm for each route. (Just 'string-of-consciousness' here without any mental debugging.)

 

[Dominik Tugend]

Those problems rarely have exact optimal answers that you could find with reasonable computing effort, so algorithms that start with some solution and improve this step by step are the typical approach.

I would guess that manual tuning is not too bad. There are so many things that are hard to consider in algorithms - convenient locations where the bus can stop, connections between stops, and so on. Anyway, a clustering algorithm can be a good start.

Let's assume you want to minimize the average number of stops per kilometre (as said above currently you forgot to gave a minimization criteria and thus an optimal solution can be found easily).

Then basically mfb is right, while your problem isn't technically NP-hard, it even is in P, simply because the input is limited, it probably would be NP-hard if for example the number of addresses could be arbitrary.

This doesn't have to be a good solution, but this is what I'd try (this won't be very efficient though, might have at least N^2 run-time where N is the number of initial points):

Initialization:

If you had already data about the stops (i.e. locations + number of people that get in or out), that would be a great initialization for an greedy approximation algorithm.

If not you could start with let's say by approximating the routes with points of no more than 50 metres distance (or 10 metres if 50 metres isn't too slow already).
Then you could for each address you find a nearest point and assign the passenger to that point. If there are multiple nearest points I'd suggest using some simple strategy (because otherwise you run into hard problems again), for example assign the passenger to the point that has the most passengers already (and if there are multiple then randomize the selection). Of course everyone should be assigned to the company stop point (nearest point to the company of a route) too, since they want to get there (hopefully).

Point reduction (loop):

- Calculate the average number of bus stops per kilometre, if it's good enough for you, then the algorithm stops
- Mark points that can be removed without violating your criteria (pretend to remove it, then test your criteria), if there are no such points the algorithm stops
- Select the point with the fewest number of passengers getting in or out for removal
- Find the nearest point for each passenger address again and assign passengers to the remaining points accordingly

Life-time Evaluation:
Find some criteria that indicate where to insert new bus-stops (since things change all the time).
A simple approach here might be to start with the bus stops you already have by then, insert a single point between each stop and run the reduction algorithm again.
A better approach might be to limit the number of points inserted and to make them real test bus-stops and use real passenger data gathered to decide if to keep them and which others to remove.

PS:
Of course this approach would suffer from all sorts of statistical problems that Choropleth Maps have, for example Modifiable Areal Unit Problem.

I am not sure if the home addresses of the passengers is a good approach, since it doesn't reflect their actual behaviour maybe. Maybe each passenger should be give the opportunity to give 2 to 3 points where he would want to ideally get in-or out (not including the company). However be aware that this system would be probably abused for non-company related rides most likely, not sure if you want to allow that.

Maybe s.o. here has a better idea, but that would come to my mind.

Edit: Don't forget some maximum distance criteria, meaning a point cannot be removed if the minimum distance of an address to the remaining points increases above a certain threshold. Otherwise a few people going to be really mad.