Я пытаюсь найти среднюю точку с длительным трафиком (исходя из трафика по отношению к времени отправления)

Ответ 1

Вы можете попробовать один, который более тонкий, чем то, что предложил Джеймс, но моя точка зрения просто находит путь между A и D, затем найдите точку "p" (которая является avg/n [maxN] * 100) в декодированном пути.

ex: если p равно 73, то найдите путь между декодированием A и D, например, он имеет 235 точек (Math.round((235/100) * 73) = 172). Выберите ширину и долготу позиции 178 на декодированном пути A, D) и повторный процесс.

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)
        }
    })
}

Ответ 2

Ниже я создал алгоритм (в псевдокоде), который минимизирует самое длинное время в пути:

Задача: заданные начальные точки A, B и C: Найдите центральное местоположение D так, чтобы продолжительность проезда от каждой точки до D была аналогичной. (где "аналогичный" определяется как "в пределах определенного допуска"... например, это может быть установлено на 1 минуту.)

Приготовление:

    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.

Исполнение:

    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

Приложенный рисунок иллюстрирует пример итерации.

Edit: Я реализовал доказательство демонстрации концепции на CodePen. Ниже приведен пример кода:

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);
}

См. DEMO