首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  算法

解决这样一个需求。有三个时间段,每个时间段有很多订单。现在需要将订单进行组合 A->B->C, ABC 分别是三组订单中的某个。ABC 都有地理位置信息。要求是 A_>B_>C 路程时间最短,并且两者之间的路程时间小于所在时间段的时间间隔。

  •  
  •   xiatong · 350 天前 · 725 次点击
    这是一个创建于 350 天前的主题,其中的信息可能已经有所发展或是发生改变。

    解决这样一个需求。有三个时间段,每个时间段有很多订单。现在需要将订单进行组合 A->B->C,ABC 分别是三组订单中的某个。ABC 都有地理位置信息。要求是 A_>B_>C 路程时间最短,并且两者之间的路程时间小于所在时间段的时间间隔。

    5 回复  |  直到 2018-12-24 17:38:17 +08:00
        1
    xupefei   350 天前 via Android   ♥ 1
    就是个 Nearest neighbour 问题吧。如果当前的点是类型 A 那么下一步只能走类型 B 或 C 的点,如此往复,不保证最优。
    算最优的话可能是 NP HARD,感觉可以用动态规划解决。
        2
    xiatong   350 天前
    @xupefei 其实是一个环形的,有很多个起点,起点->A_>B_>C_>起点。订单只能走一次。找到每个起点的最优路线。
        3
    xupefei   350 天前 via Android   ♥ 1
    带回程的话,感觉更是 np hard,但我一时半会想不出算是什么问题了。但我知道,branch and bound 算法一定可用,能拿到最优。
        4
    xupefei   350 天前 via Android
    哦,找图中最短的环,如果 ABC 访问顺序固定的话,这好像是个 BFS 能简单解决的问题。
        5
    xiatong   350 天前
    @xupefei 谢谢你,我去看一下相关资料。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   945 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 23ms · UTC 21:33 · PVG 05:33 · LAX 13:33 · JFK 16:33
    ♥ Do have faith in what you're doing.