using geolocation on google map to group students home by nearest locations to each other?

Question

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??

Answer 1

I'm not quite sure if I completly understood your question (especially as you mention from your comment 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).