I am trying to find mid point with duration traffic (based on traffic with respect to departure time)

Question

I am trying to find the midpoint using duration traffic values(n1,n2,n3) in specified departure time(timeStamp) so that all the three-person have the same travel time (midpoint by Time). I'm using Google distance matrix.

I have been passing all three locations (a,b,c) & midpoint(d) based on the distance of the three locations.

I tried finding their midpoint by subtraction(all three), average(three of them) and subtracting with (Max and Min Values of n1,n2,n3) so that there traveling time becomes equal or less than the specified time(maxTime distance b/w three of them). Then point becomes the Midpoint But I couldn't find a solution. Suggestions are much appreciated.

const maxTime = 5000; var i = 0; z = 0; j = 0  //Distance Matrix Api function getDistanceMatrix(a, b, c, d, timeStamp, googleWarnings, copyRights) {   clientMap.post(config_KEYS.DISTANCE_MATRIX_API + a + "|" + b + "|" + c + "&destinations=" + d.lat + "," + d.lng + "+&key=" + config_KEYS.GOOGLE_API_KEY + "&departure_time=" + timeStamp + "", function(gotDistanceResp, err) {     if (err) {       res.status(400).json(gotDistanceResp)     } else {       let n1 = gotDistanceResp.rows[0].elements[0].duration_in_traffic.value       let n2 = gotDistanceResp.rows[1].elements[0].duration_in_traffic.value       let n3 = gotDistanceResp.rows[2].elements[0].duration_in_traffic.value       // let minTime = Math.abs(n2 - n1)       let minTime = Math.round((n3 + n2 + n1) / 3)       if (n1 >= n2 && n1 >= n3) {         if (minTime <= maxTime) {           res.send(gotDistanceResp)         } else {           i++;           let arrayPoints = getDirectionApi(a, d, timeStamp, i)         }       } else {         if (n2 >= n1 && n2 >= n3) {           if (minTime <= maxTime) {             res.send(gotDistanceResp)           } else {             j++;             let arrayPoints = getDirectionApi(b, d, timeStamp, j)           }         } else {           if (n3 >= n1 && n3 >= n1) {             if (minTime <= maxTime) {               res.send(gotDistanceResp)             } else {               z++;               let arrayPoints = getDirectionApi(c, d, timeStamp, z)             }           } else {             res.send(gotDistanceResp)           }         }       }     }   }) } //Get Direction Api function getDirectionApi(a, b, timeStamp, r) {   clientMap.post(config_KEYS.DIRECTION_API + a + "&destination=" + b.lat + "," + b.lng + "&key=" + config_KEYS.GOOGLE_API_KEY + "&departure_time=" + timeStamp + "", function(route, error) {     if (route.geocoder_status == "ZERO_RESULTS" | route.status == "INVALID_REQUEST") {       res.status(400).send(route)     } else {       let googleWarnings = route.routes[0].warnings       let copyRights = route.routes[0].copyrights       let polyline = route.routes[0].overview_polyline.points       let decoded = decode(polyline)       let midPointCha = getDistanceMatrix(Location1, Location2, Location3, reversedMidArra[r])     }   }) } 

Answer 1

Below, I have created an algorithm (in pseudocode) that minimizes the longest travel time:

Problem: Given starting points A, B, and C: Find a central location D such that the travel duration from each point to D is similar. (where "similar" is defined as "within a specified tolerance"...for example, this could be set to 1 minute.)

Preparation:

     Determine a candidate location for D:     the "center of gravity" or geographic midpoint.     (Average the x coordinates and the y coordinates.)     Set _Converged_ to false. 

Execution:

     While (not _Converged_) {       Query the travel time from each start location to point D.        If all three travel times are within the specified tolerance:         Then            _Converged_ = true // current point D is returned as acceptable          Else           Average the three travel times: avg           Identify the starting point with the longest travel time:              where Q is A, B, or C and t is the travel time.           Divide the average by t:             where p is avg/t           Compute a new point E between Q and D based on percentage p             (for example, if p is .66, then new point is 66% along             the vector from Q to D)             E = p(D - Q) + Q           Set D to this new point E             D = E     }     return D 

The attached figure illustrates an example iteration.

Edit: I have implemented a proof of concept demonstration on CodePen. Below is a sample of the code:

else { // Minimize the longest duration   // First, find the average duration   let avg = (n[0]+n[1]+n[2])/3;   // Divide the average by longest travel time   let p = avg / n[maxN];   // Compute a new point E between Q and D based on percentage p   // E = p(D - Q) + Q   // D = E   destination[0].lat = lerp(origins[maxN].lat,destination[0].lat,p);   destination[0].lng = lerp(origins[maxN].lng,destination[0].lng,p);   // Cycle again, waiting a bit to prevent server overload   setTimeout(calculateDistances, 500+Math.random()*100); } 

See DEMO

Answer 2

You can try below one, Which is more slimier like What James suggested but my point of view just find the path between A and D then find "p" point(Which is avg / n[maxN] *100) in the decoded path.

ex: if p is 73 then find the path between A and D decode for example it has 235 points then (Math.round((235/100)*73)=172) Pick 172 position latitude and longitude in the decoded path of A,D) and repeat process.

let arrOfMid = []; //Distance Matrix Api function getDistanceMatrix(a, b, c, d, timeStamp, i) {     clientMap.post(config_KEYS.DISTANCE_MATRIX_API + a + "|" + b + "|" + c + "&destinations=" + d.lat + "," + d.lng + "+&key=" + config_KEYS.GOOGLE_API_KEY + "&departure_time=" + timeStamp + "", function (gotDistanceResp, err) {         if (gotDistanceResp.status == "OVER_QUERY_LIMIT" | gotDistanceResp.status == "REQUEST_DENIED") {             res.status(400).json(gotDistanceResp)         }         else {             let n1 = gotDistanceResp.rows[0].elements[0].duration_in_traffic.value             let n2 = gotDistanceResp.rows[1].elements[0].duration_in_traffic.value             let n3 = gotDistanceResp.rows[2].elements[0].duration_in_traffic.value             let maxValue = Math.max(n1, n2, n3)             let minTime = Math.abs(n2 - n1)             let avg = Math.round((n3 + n2 + n1) / 3)             let value = (avg / maxValue) * 100             if (n1 >= n2 && n1 >= n3) {                 if (arrOfMid.includes(gotDistanceResp.destination_addresses[0]) == true) {                     res.send(gotDistanceResp)                 }                 else {                     arrOfMid.push(d)                     i++;                     let arrayForTenPerc = getDirectionApi(a, d, timeStamp, value, i)                 }              }             else {                 if (n2 >= n1 && n2 >= n3) {                      if (arrOfMid.includes(gotDistanceResp.destination_addresses[0]) == true) {                         res.send(gotDistanceResp)                     }                     else {                         arrOfMid.push(gotDistanceResp.destination_addresses[0])                         j++;                         let arrayPoints = getDirectionApi(b, d, timeStamp, value, j)                     }                  }                 else {                     if (n3 >= n1 && n3 >= n1) {                         if (arrOfMid.includes(gotDistanceResp.destination_addresses[0]) === true) {                              res.send(gotDistanceResp)                         }                         else {                             arrOfMid.push(gotDistanceResp.destination_addresses[0])                              z++;                             let arrayPoints = getDirectionApi(c, d, timeStamp, value, z)                         }                     }                     else {                         res.send(gotDistanceResp)                     }                 }             }         }     }) }   //Get Direction Api function getDirectionApi(a, b, timeStamp, r, i) {     clientMap.post(config_KEYS.DIRECTION_API + a + "&destination=" + b.lat + "," + b.lng + "&key=" + config_KEYS.GOOGLE_API_KEY + "&departure_time=" + timeStamp + "", function (route, error) {         if (route.geocoder_status == "ZERO_RESULTS" | route.status == "INVALID_REQUEST") {             res.status(400).send(route)         }         else {             let polyline = route.routes[0].overview_polyline.points             let decoded = decode(polyline)             let x = Math.round(decoded.length / 100 * r)             let midPointCha = getDistanceMatrix(Location1, Location2, Location3, decoded[x], timeStamp, i)         }     }) }