I have many points on google map that represents students's homes

I also have many buses .

I have to group students according to their locations by grouping the nearest students to each other with the same bus .

so the bus driver will get them to the school.

any ideas about the algorithm about that? any ideas??

I have many points on google map that represents students's homes

I also have many buses .

I have to group students according to their locations by grouping the nearest students to each other with the same bus .

so the bus driver will get them to the school.

any ideas about the algorithm about that? any ideas??

• javascript
• google-maps
• google-maps-api-3

• 2 Do you have mapped routes for the buses? And/or lat/lng locations for each stop the bus makes along its route? – duncan Commented Jun 17, 2013 at 13:31
• actually , the route of the bus is the lat/lng of students's home and that's what I need algorithm to determine > I want to determine the route of each bus from school location to the group of students locations that are near each others – Feras Taleb Commented Jun 17, 2013 at 16:51
• did you ever find a solution for your problem? I have to achieve EXACTLY the same... – swalkner Commented Oct 8, 2013 at 7:38
• movable-type.co.uk/scripts/latlong.html This website can help calculate the distance between two points using lat/long – Dawood Awan Commented Oct 15, 2013 at 7:48

6 Answers 6

I'm not quite sure if I pletly understood your question (especially as you mention from your ment that "the route of the bus is the lat/lng of students's home"). So I assume then that you don't have predefined bus routes but want to find the best possible routes.

Now to clarify we should split the task into sub-tasks, after my assumptions we can say that:

1. You need an algorithm to assign student-homes to the closest bus-stop. The bus-stops might be predefined, or not - you need to clarify if the bus-stops are defined or not.

2. Since you have multiple buses, each bus needs to be assigned to a group of bus-stops (lets call it a bus-zone) that they are responsible for stopping at.

3. Then you need to solve the TSP (Traveling salesman problem) for each bus-zone ( group of bus-stops).

Possible solutions

1 - What you want to look into is how to group points (meaning in this case - student-homes) defined by (lat,lon). To do that you need to be able to calculate the distance between two points on earth, the Haversine formula is widely used for this. You can find alot of existing implementations if you search for this - here is a simple JS implementation:

var R = 6371; // km
var dLat = (lat2-lat1).toRad();
var dLon = (lon2-lon1).toRad();
var lat1 = lat1.toRad();
var lat2 = lat2.toRad();

var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

There is also a function implemented in the Google Maps API v3, you can find more information at this SO question.

So if you have pre-defined bus-stops it would simply be a matter of calculating the distance of each student-home to each bus-stop and then grouping each student to it's closest bus-stop (meaning the lowest calculated distance)

Depending on the amount of data/calculations needed for your project, you might want to consider moving that to a backend solution instead of doing it in the client.

2 - Again this depends on the requirements for your project, if you have predefined bus-zones (polygons) you then simply determine which bus-stops belongs to each bus-zone. This is simply the problem of solving Point in polygon for a sphere. If you need your own implementation search SO, there is alot of existing solutions available. Othwerise Google maps API v3 has a function containsLocation() which you can use:

google.maps.geometry.poly.containsLocation(google.maps.LatLng(latitude, longitude),polygons);

3 - There is a lot of information on solving the TSP. A good solution for getting the fastest route in google maps is OptiMap. The source-code is also available. You should be able to run it for each bus-zone (group of bus-stops).

I don't know if this helps: Genetic Algorithm Traveling Salesman Problem with Javascript

Love the project..... should be fun

I would properly split the map up and make a bus responsible for each area and than have some fail safe procedures (in case 1 region ends up with 99% of the students, in which the case the regions would dynamically change to make it more even). You could also make it so that if one bus's route ends up being more than 20% other busses, than reduce students for that bus.

From there each bus will have a students from which you can calculate a route. It will however be a lot of work to create an algorithm that calculates the best route for multiple busses.

You may wish to consider services which already do this, such as MapBox. This would make your life a lot easier however It would also incur an ongoing cost.

Hope that helps

You can try a hierarchical cluster to group the students. Then you can use an open tsp algorithm to find a route. Optimap from Gebweb is a free solver. To group the students you can look for clusterfck JavaScript. You can also try a heuristic like the saving algorithm.

The brute force approach

If you know where the busses are and you have all the students locations then you should calculate the distance of all students in relation to all bus stops. For each student sort their distances to each bus stop and assign them to the closest bus stop.

Optimization 1

Rule out bus stops for some students. There are some bus stops that don't need distance calculated and you may know this right off the bat. You can say that if some student belongs to some quadrant. Then you would only need to calculate distance for a subset of busses (only 1/4th instead of all). This might result in interesting situations at the borders, but you could account for that.

Optimization 2

Based on the previous optimization you can do this further, up until the point where you are basically guaranteed to not pute any distances. If a user falls within some node then they will end up going to some bus stop. You essentially overlay a grid onto your map if a student falls within some grid node they will go to that bus stop. The previous problem is basically solved as well. It shouldn't matter if the distance to a bus stop is slightly longer since it is relatively trivial. You can however guarantee maximum distance traveled for any student.

Solution

Each bus has a serviceable area (a hit box). For each student within some quadrant/node determine if they fall within a bus' service area. If not bubble them up to a higher level quadrant/node.

yes i used that with more then 500 markers at a time i can send you some links for your help : first link second link

Read it and apply with the help of array.