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

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

  •  
  •   xiatong · 2018-12-24 16:58:40 +08:00 · 2608 次点击
    这是一个创建于 1920 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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