有必要对路线进行随机排序

这看起来像是对旅行推销员问题的不寻常表述。“公共汽车”定义了有向边，城市定义了顶点。如果你忽略了使用所有“公共汽车”的要求，那么这就是旅行推销员的问题。

因此，算法将是：

• 生成有向图（总线定义边，城市是顶点 ）
• 应用旅行推销员算法
• LOOP over edges in solution
  • 覆盖边缘的 SELECT 总线，如果可能，以前未使用过的总线。

这是您示例中的图表

这是使用公共汽车的路线

MAPLEWOOD ->(MegaBus)-> CRYSTALVILLE ->(MegaBus)-> WILLOWBROOK ->(TransLink)-> HARMONYVILLE ->(GoBus)-> SILVERLAKE ->(SwiftRide)-> OCEANVIEW ->(MetroTrans)-> MOONSTONE ->(CityHopper)-> CRYSTALVILLE ->(RouteMasters)-> RIVERDALE ->(MetroTrans)-> CEDARVILLE ->(MetroTrans)-> MAPLEWOOD

下面是实现此目的的 C++ 代码

main()
{
    std::string buses =
    "TransLink:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW\n"
    "GoBus:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW\n"
    "SwiftRide:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW\n"
    "SpeedyBus:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE\n"
    "CityHopper:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW@MOONSTONE\n"
    "RouteMasters:MOONSTONE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW\n"
    "MetroTrans:CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,RIVERDALE,CEDARVILLE@CRYSTALVILLE,WILLOWBROOK,HARMONYVILLE,SILVERLAKE,OCEANVIEW,RIVERDALE,CEDARVILLE\n"
    "MegaBus:MAPLEWOOD,CRYSTALVILLE@MAPLEWOOD,CRYSTALVILLE\n";

    raven::graph::cGraph g;
    g.directed();
    std::map<std::pair<std::string, std::string>, std::vector<std::string>> mpBus;
    std::stringstream ss(buses);
    std::string line;
    while (getline(ss, line))
    {
        // std::cout << line << "\n";
        int p1 = line.find(":");
        int p2 = line.find("@", p1);
        std::string busName = line.substr(0, p1);
        std::string srcs = line.substr(p1 + 1, p2 - p1 - 1);
        std::string dsts;
        dsts = line.substr(p2 + 1);
        auto vs = ParseCSV(srcs);
        auto vd = ParseCSV(dsts);
        for (auto &s : vs)
            for (auto &d : vd)
            {
                // std::cout << s << " -> " << d  << "\n";
                g.add(s, d);
                auto it = mpBus.find(std::make_pair(s, d));
                if (it == mpBus.end())
                {
                    std::vector<std::string> vb{busName};
                    mpBus.insert(
                        std::make_pair(
                            std::make_pair(s, d),
                            vb));
                }
                else
                    it->second.push_back(busName);
            }
    }

    // for( auto& s : g.edgeList() )
    //     std::cout <<"l " << g.userName(s.first) <<" "<< g.userName(s.second) << " 1\n";

    raven::graph::cTourNodes T;
    T.calculate(g);

    std::set<std::string> setUsed;

    std::string src, dst;
    std::string tourText;
    bool first = true;
    for (int v : T.getTour())
    {
        if (first)
        {
            first = false;
            src = g.userName(v);
            continue;
        }
        dst = g.userName(v);
        auto vBus = mpBus.find(std::make_pair(src, dst))->second;
        std::string busUsed;
        for (auto &b : vBus)
        {
            auto itUsed = setUsed.find(b);
            if (itUsed == setUsed.end())
            {
                busUsed = b;
                setUsed.insert(b);
                break;
            }
        }
        if( busUsed.empty() )
            busUsed = vBus[0];

        tourText += g.userName(v) + " ->(" + busUsed + ")-> ";
        src = dst;
    }
    std::cout << tourText << "\n";

    return 0;
}

在 https://github.com/JamesBremner/so76373906 完成应用程序代码