I need to group waypoints based on their proximity to each other. We have resources that are assigned appointments (patients). For each patient, we see them 2x per week. I need to calculate the schedule for each day and then the route. The route part is easy with a call to the Bing Maps API. But, I'm struggling with how to generate a schedule.
For instance, if Resource1 sees 8 patients per week and each of them 2x - that's 16 appointments. Let's also assume I will see them on Mon & Wed or Tues & Thur. How would I assign which of the 8 patients should be seen on Mon/Wed & which ones are Tues/Thur. It should be based on their proximity to each other. So, give me a calculation which calculates which 4 should be seen on Mon/Wed & which 4 should be seen on Tues/Thur (assuming it's split 4/4 and not 5/3, etc)
There are a lot of ways to do this.
Looking at your scenario it looks like it would be fair to say that you would want half the patients to be visited on Mon/Wed, and the other half on Tues/Thurs. Furthermore, you would want a single resource works 4 days, and would be assigned half their patients per combination of days. With the above in mind, if we cluster the data into groups of no more than 4 patients per cluster, a single cluster would be the schedule for a single resource for a single day combo (e.g. Mon/Wed). Once you have these clusters, you can then slip them in half and assign to your resources. For a fairly accurate approach, I would want to use travel time for the clustering and would tackle this like so:
A cheaper, but less spatially accurate version of the above (less time efficient), would be to calculate straight line distances rather than travel time. Straight line distances are a simple calculation (Haversine formula).
If you want to go a step further, calculate the distance from the cluster or one of the patients in the cluster to each resource, and assign the resource who is closest (assuming the resources are not all located at the same location).
Here is proof of concept:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<title></title>
<style>
table, td, th {
border: 1px solid;
}
table {
width: 100%;
border-collapse: collapse;
}
</style>
</head>
<body>
<input type="button" onclick="schedulePatients()" value="Schedule patients"/>
<br/><br />
<div id="output"></div>
<script>
var resources = {
"type": "FeatureCollection",
"features": [
{ "type": "Feature", "id": 248, "properties": { "assignedMonWed": false, "assignedTuesThurs": false, "MonWebSchedule": [], "TuesThursSchedule": [] }, "geometry": { "type": "Point", "coordinates": [-122.050234696603, 47.6808627484536] } },
{ "type": "Feature", "id": 467, "properties": { "assignedMonWed": false, "assignedTuesThurs": false, "MonWebSchedule": [], "TuesThursSchedule": [] }, "geometry": { "type": "Point", "coordinates": [-122.003917771292, 47.697428787792] } },
{ "type": "Feature", "id": 415, "properties": { "assignedMonWed": false, "assignedTuesThurs": false, "MonWebSchedule": [], "TuesThursSchedule": [] }, "geometry": { "type": "Point", "coordinates": [-122.023083481977, 47.6673715172954] } },
{ "type": "Feature", "id": 564, "properties": { "assignedMonWed": false, "assignedTuesThurs": false, "MonWebSchedule": [], "TuesThursSchedule": [] }, "geometry": { "type": "Point", "coordinates": [-121.985338674036, 47.7022520412864] } },
{ "type": "Feature", "id": 533, "properties": { "assignedMonWed": false, "assignedTuesThurs": false, "MonWebSchedule": [], "TuesThursSchedule": [] }, "geometry": { "type": "Point", "coordinates": [-122.006075987628, 47.7046529915799] } }
]
};
var patients = {
"type": "FeatureCollection",
"features": [
{ "type": "Feature", "id": 1, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.997913065484, 47.7195839450159] } },
{ "type": "Feature", "id": 2, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.040368485372, 47.6869829619951] } },
{ "type": "Feature", "id": 3, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.048824870578, 47.7013191572943] } },
{ "type": "Feature", "id": 4, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.071031688833, 47.7449665072182] } },
{ "type": "Feature", "id": 5, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.015643772116, 47.7570578745646] } },
{ "type": "Feature", "id": 6, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.034052201107, 47.7451844538795] } },
{ "type": "Feature", "id": 7, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.032132503429, 47.714347009898] } },
{ "type": "Feature", "id": 8, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.04547396506, 47.6893615399414] } },
{ "type": "Feature", "id": 9, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.068392436109, 47.6832920975517] } },
{ "type": "Feature", "id": 10, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.984992007383, 47.6735499724146] } },
{ "type": "Feature", "id": 11, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.036957923548, 47.7530782996456] } },
{ "type": "Feature", "id": 12, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.066388808463, 47.7044949126107] } },
{ "type": "Feature", "id": 13, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.065430673396, 47.6936482443828] } },
{ "type": "Feature", "id": 14, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.005818300822, 47.6841991471929] } },
{ "type": "Feature", "id": 15, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.013423871487, 47.7267318710591] } },
{ "type": "Feature", "id": 16, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.991867919251, 47.6730825754312] } },
{ "type": "Feature", "id": 17, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.075035596741, 47.6825165944555] } },
{ "type": "Feature", "id": 18, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.02704005476, 47.7359799244539] } },
{ "type": "Feature", "id": 19, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.069711259786, 47.7582015474685] } },
{ "type": "Feature", "id": 20, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.00363876449, 47.696504598779] } },
{ "type": "Feature", "id": 21, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.027230559197, 47.7463213935986] } },
{ "type": "Feature", "id": 22, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.020278138182, 47.7565298732157] } },
{ "type": "Feature", "id": 23, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.041675234009, 47.7605001277431] } },
{ "type": "Feature", "id": 24, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.059226260036, 47.6842719244522] } },
{ "type": "Feature", "id": 25, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.99079261183, 47.6745521677151] } },
{ "type": "Feature", "id": 26, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.998635617356, 47.741838009627] } },
{ "type": "Feature", "id": 27, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.983315341491, 47.7529779792852] } },
{ "type": "Feature", "id": 28, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.996663951226, 47.6982171986915] } },
{ "type": "Feature", "id": 29, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.069967005873, 47.7499047491259] } },
{ "type": "Feature", "id": 30, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.032190749586, 47.757600296338] } },
{ "type": "Feature", "id": 31, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.992400954596, 47.6827035465803] } },
{ "type": "Feature", "id": 32, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.063594482899, 47.7247082989927] } },
{ "type": "Feature", "id": 33, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.075535378044, 47.6772273648534] } },
{ "type": "Feature", "id": 34, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.994743747063, 47.7387867524387] } },
{ "type": "Feature", "id": 35, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.041914349392, 47.6784018054591] } },
{ "type": "Feature", "id": 36, "properties": {}, "geometry": { "type": "Point", "coordinates": [-121.985731516363, 47.7173223782956] } },
{ "type": "Feature", "id": 37, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.066638385437, 47.7276733135571] } },
{ "type": "Feature", "id": 38, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.004119609955, 47.6871862520471] } },
{ "type": "Feature", "id": 39, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.042819720217, 47.699794194686] } },
{ "type": "Feature", "id": 40, "properties": {}, "geometry": { "type": "Point", "coordinates": [-122.029705426136, 47.72521276633] } }
]
};
//Check to see if there is enough resources for the number of patients (Half the patients assigned per day combo, with a resource having no more than 4 patients per day.
if (Math.ceil(patients.features.length) / 2 / 4 > resources.features.length) {
console.log('Not enough resources to see all patients');
}
function schedulePatients() {
var currentDayCombo = 'MonWeb';
var midPoint = Math.ceil(patients.features.length / 2);
var assigned = 0;
for (var i = 0; i < patients.features.length; i++) {
var p = patients.features[i];
var cluster = getThreeClosest(i);
//Add patient to the cluster.
cluster.push(p);
if (assigned >= midPoint) {
currentDayCombo = 'TuesThurs';
}
//Loop through resources and assign clusters.
var resource = getClosestUnassignedResource(cluster, currentDayCombo);
if (resource === null) {
//No available resource left. Handle this some how. Possibly throw an alert or log to console.
cluster.forEach(c => {
console.log(`No resources left, patient ${c.id} unassigned.`)
});
} else {
assigned += cluster.length;
}
}
//Scheduling complete. Recommend using route optimizate for the patients of each resource to get the most efficient order to visit those patients.
//Creating a table of the schedule.
var html = ['<table><tr><td>Resource ID</td><td>Mon/Wed Patient IDs</td><td>Tues/Thurs Patient IDs</td></tr>'];
resources.features.forEach(r => {
html.push(`<tr><td>${r.id}</td><td>${r.properties.MonWebSchedule.join(',')}</td><td>${r.properties.TuesThursSchedule.join(',') }</td></tr>`);
});
html.push('</table>');
document.getElementById('output').innerHTML = html.join('');
}
function getThreeClosest(patientIdx) {
//Create an array of distances and indices for each patient.
var distances = [];
var p = patients.features[patientIdx];
//Look at remaining unassigned patients and calculate distances.
for (var k = patientIdx + 1; k < patients.features.length; k++) {
var p2 = patients.features[k];
if (!p2.properties.assigned) {
distances.push({
distance: haversine(p.geometry.coordinates, p2.geometry.coordinates),
idx: k //Capture the index of the patient to do a quick lookup later.
});
}
}
//Sort the distances in ascending order.
distances.sort((a, b) => { return a.distance - b.distance });
//Possible there are less than 3 patients remaining.
var grab = Math.min(3, distances.length);
var closest = [];
for (var i = 0; i < grab; i++) {
closest.push(patients.features[distances[i].idx]);
}
return closest;
}
function getClosestUnassignedResource(cluster, dayCombo) {
//Calculate the average position of the cluster.
var sumLon = cluster.reduce((acc, curr) => acc + curr.geometry.coordinates[0], 0);
var sumLat = cluster.reduce((acc, curr) => acc + curr.geometry.coordinates[1], 0);
var origin = [sumLon / cluster.length, sumLat / cluster.length];
var currentDayProp = (dayCombo === 'MonWeb') ? 'assignedMonWed' : 'assignedTuesThurs';
//Create an array of distances and indices for each resource.
var closest = null;
var minDist = Infinity;
//Loop through resources and assign clusters.
for (var j = 0; j < resources.features.length; j++) {
var r = resources.features[j];
//Check that resource is not assigned.
if (!r.properties[currentDayProp]) {
var d = haversine(origin, r.geometry.coordinates);
if (d < minDist) {
minDist = d;
closest = r;
}
}
}
//Assign resource.
if (closest) {
closest.properties[currentDayProp] = true;
cluster.forEach(c => {
c.properties.dayCombo = dayCombo;
c.properties.resource = closest.id;
closest.properties[dayCombo + 'Schedule'].push(c.id);
});
}
return closest;
}
function haversine(p1, p2) {
var lat1 = p1[1] / 180.0 * Math.PI;
var lon1 = p1[0] / 180.0 * Math.PI;
var lat2 = p2[1] / 180.0 * Math.PI;
var lon2 = p2[0] / 180.0 * Math.PI;
var R = 6372.8; // km
var dLat = lat2 - lat1;
var dLon = lon2 - lon1;
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.asin(Math.sqrt(a));
return R * c;
}
</script>
</body>
</html>