javascript - 我正在尝试找到持续时间流量的中点(基于相对于出发时间的流量)

Question

我试图使用指定出发时间(timeStamp)中的持续时间流量值(n1，n2，n3)找到中点，以便所有三人都有相同的旅行时间(时间中点)。我正在使用谷歌距离矩阵。

根据这三个位置的距离，我已经经过了所有三个位置(a、b、c)和中点(d)。

我尝试通过减法(全部三个)、平均值(其中三个)并减去(n1、n2、n3的最大值和最小值)来找到它们的中点，以便行驶时间等于或小于指定时间(其中三个的最大时间距离)。然后点变成中点但我找不到解决办法。非常感谢您的建议。

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

下面，我创建了一个算法(以伪代码形式)，可以最小化最长旅行时间:

问题:给定起点 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.

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

参见DEMO