计算给定领土的公交路线的估计移动性需求

Question

我的疑问比与编程相关的概念更为概念，但是我们开始了。

目的是为公交路线放置最佳的一组停车，但首先我们需要计算一个领土上的估计需求。

尚未定义输入，但假设我们有一个相关的加权点在一个领土上的共同关注点。

我们应该计算在该领土上所有道路上的每一点中的移动性需求，以便放置前面提到的停靠点。

我要解决这个问题的方法是：

• 对于道路上的每个点，计算R半径中n个元素的权重总和（例如KNN算法逻辑）。

• 之后，使用Kmeans（由于其基于距离），我们可以计算领土上最相关的K质剂，以获取第一个停止样本。之后，优化以适合给出的优化参数，例如涵盖的涵盖，路线时间等。

您对这种方法有何看法？您会使用其他算法吗？您会尝试以不同的方式解决问题吗？

最后，最大的数学挑战是：

• 在给定领土中定义移动性需求。
• 根据移动性需求放置站。

Answer 1

步骤1：定义每个潜在停止。

在城市中，这将是每个街区的中心。您很高兴有用户穿越道路吗？如果没有，则每个街区的中央有两个站，在道路的每一侧一个。在农村地区，也许每条道路每250米。郊区更加复杂。可能确定每250米的主要道路，并沿着这些路线停留。

步骤2：

计算每个潜在停止的需求。

步骤3：

使用K-均值来识别将成为实际停止的N站（请参见下面的示例实现）。 n是一个输入。您可能必须迭代n个值，计算到最近的实际停止的最差需求距离，直到找到可接受的最差服务距离的N为止。

步骤3：

构建顶点（实际停止）和边缘（道路）的图表

4：

使用旅行推销员（Euclidean）算法来计算公交路线。

---

使用K-Means来识别将成为实际停止的N停止的示例实现，

这是使用KMeans库中的C ++实现，来自 https://github.com/jamesbremner/kmeans

void cSolution::selectStops()
{
    // Construct the KMeans class
    KMeans KM;

    // loop over potential bus stops
    for (auto &ps : myPotentialStops)
    {
        //Each unit of need at the potential bus stop
        // is represented by "a need" at the location
        for (int k = 0; k < ps.myNeed; k++)
        {
            cDataPoint l(2);
            l.d[0] = ps.myLoc.first;
            l.d[1] = ps.myLoc.second;
            KM.Add(l);
        }
    }

    // initialize KMeans with the number of actual bus stops reuired
    KM.Init( myCountActualStops, false );

    // run KMeans algorithm to find clusters of need
    for( int kiter=0; kiter < 10; kiter++ )
    {
        KM.Assign();
        KM.MoveClustersToMean();
    }

    // Select bus stops nearest to cluster centers
    for( auto& c : KM.clusters() )
    {
        float min = 1e10;
        int nearest;
        int ks = -1;
        for (auto &ps : myPotentialStops)
        {
            ks++;
            float td = dist2( 
                ps.myLoc,
                { c.center().d[0],  c.center().d[1]});
            if( td < min )
            {
                min = td;
                nearest = ks;
            }
        }
        // convert nearest potential bus stop to an actual bus stop.
        myPotentialStops[nearest].myfActual = true;
    }

}

为了对其进行测试，我在块中间建造了一条带有潜在停靠点（绿色点）的道路。我已经为每个潜在停止（停止旁边的数字）分配了半随机需求。运行上面的代码产生此结果（红点分配了实际停止）

此应用程序的完整代码位于 https：/ /Github.com/jamesbremner/bussttop