现实中遇到的业务状况记录

外卖平台,订单的自动派发.

　　　业务背景: 外卖平台,订单的自动派发.

　　　流程:

　　　　　　1,顾客下单

　　　　　　2,平台收到订单,分配订单给配送员,

　　　　　　3,商家出餐

　　　　　　4,配送员取货

　　　　　　5,配送员配送

　　　　　　6,用户收货,反馈评价

　　　　　　ps: 2,3,4同步进行

　　讨论的问题: 如何做到订单的自动派发(订单自动分配给最合适的配送员)?

　　　理想化的前提:

　　　　　　1,配送员速度恒定

　　　　　　2,不考虑路况,天气等外部原因

　　　　　　3,任何已知坐标的两点距离可以计算(使用直线)

　　　已知条件:

　　　　　　1,配送员速度v,坐标点point_配

　　　　　　2,配送员已有订单列表order₁,order₂...,order_n-1,order_n,订单列表可以为空

　　　　　　3,每个订单order包含两个重要部分,该订单提供货物的商家坐标point_n商,该订单需要配送到的用户坐标 point_n用,

　　　　　　4,新来订单的商家坐标 point_新商,用户坐标point_新用.

　　　　　　5,所有订单的商家统一的出餐时间是 t_出, 所有的订单的配送时长不允许超过 t_配

　　　要求算法结果:

　　　　　　1:匹配出最短路径(时间或者长度作为衡量标准,或者两者掺杂作为衡量标准都可以),

　　　　　　　　最佳路径:

　　　　　　　　　　最佳路径不一定是最短路径,例如A路径是最短的路径但是先送订单3再送2再送1,B路径不是最短路径,但是先送订单2,再送1,再送3

　　　　　　　　　　在不超时,A,B路径相差不大的情况下 B路径算作是比A路径友善,因为考虑了 用户体验.

　　　　　　2:尽量避免来回跑(真的非常难定义)

　　　　　　　ps:1是硬性要求,2是尽量满足.

　　　可能涉及的方面

　　　　　　1,最短路径dijkstra算法

　　　　　　2,floyd最短路径算法

　　　　　　3,路径的动态规划,因为不可能一个订单先去用户所在的点再去商家所在的位置

　　　　　　4,带权的无向图的遍历

　　　　　　5,树的遍历