阿里云
服务器地域选择
发表主题 回复主题
  • 15035阅读
  • 6回复

[最后一公里极速配送]赛题攻略+评测代码开放+无效解解析,且不在排行榜展示

发帖
54
云币
97
— 本帖被 岱月 执行加亮操作(2016-08-29) —
一、赛题攻略


天池大多数的比赛都是ml类问题,但菜鸟最后一公里配送却是OR(Operation Research 运筹学)类问题,甚至是规模不小的OR问题,这可能对目前多数游走在天池的ML选手入门产生一定的困难,极有可能让多数选手无从下手。楼主在此作为一个非专业的入门(可能都算不上)级选手,给无从下手的亲们贡献点idea,起码做到可以下手,可以挤进排行榜哈~

·解题思路


首先,需要定位这是什么问题?显然是典型的VRP(Vehicle Routing Problem)问题,维基上关于VRP问题的介绍,https://en.wikipedia.org/wiki/Vehicle_routing_problem,在网上还可以搜到很多比较成熟的参考资料以及常用求解工具。

下一步,就需要对实际问题进行建模,搞清楚决策函数及约束条件。题目要求快递员总体配送时间最短,即为决策函数。对于约束条件,VRP中常见的约束无外乎最大容量约束(CVRP)、时间窗口约束(VRPTW)、先pickup后delivery约束(VRPPD),该题目全包含了。题目中描述所有电商单的配送需要到网点取后才能送,所有的O2O单要到店铺取后才能送,这是先pickup后delivery约束;题目中要求O2O单的取送货时间要满足要求的最早取货时间和最晚配送时间,这是时间窗口约束;题目中要求快递员任意时刻携带的包裹量不能超过140,这是最大容量约束。至此,该问题就建模完成,宝宝就可以很开心的调用求解工具或者己coding采用贪婪的方式去求解问题了。

但是,比较popular的工具对问题规模都是有限制的,超过限制性能就会出现问题,比如求解时间会成倍增加。楼主了解到,目前上百个点的规划基本是不成问题的,速度很快,但最大规模也仅限于几百个点,像最后一公里中上万点的规模是相当大的,一般的工具应该是hold不住。我们只能退而求其次,由最优转为次优,将问题规模缩小,分治求解,采用什么样的分治方法,大家可以多尝试,比如配送点聚类后分给各小件员,问题规模可以一下缩很小,可行解很快就可以出来。但有时分配不合理就会出现找不到可行解的情况,仔细阅读一下题目,时间窗口约束较弹性,可以不满足,加惩罚就ok了,所以,加上松弛变量就大致ok了,甚至可以将约束去掉~,大不了cost大点,也是有效的解。

至此,一个还过得去的解就出炉啦~

·提交成绩


根据目前为止楼主较长一段时间的测评发现,大家提交的无效解存在的问题都很类似,楼主在此总结下,还望大家在发现成绩无的时候不至于惊慌失措。存在问题:

一,快递员到同一地点取/送多笔订单时,未分开计算到达时间与离开时间。大家往往会忽视一点,快递员到达配送点,取/送多笔订单时,不同的订单还是要分开处理的。举例说明,快递员D0001在11点到达点B0001,配送2笔订单F0001,F0002,包裹量分别是10,20,则配送计划需要写成:
D0001,B0001,180,194,-10,F0001
D0001,B0001,194,212,-20,F0002
或者
D0001,B0001,180,198,-20,F0002
D0001,B0001,198,212,-10,F0001

二,两点间行驶时间(当前点到达时间-上一点离开时间)计算不正确。奇怪的是,出现这种情况往往不是整体出现,而是局部,所以,楼主也百思不得其解,为什么一些算对了,一些又不对,还望亲们好好检查下,不行就写个代码,将时间整体调整下。记得一定要采用四舍五入的方式哦~,是round不是int!突然想起来了,可能大家的行驶时间中还加入了等待时间,请大家谨记,等待时间只有可能发生在店铺取订单时,其他任何时候的等待都是非法等待,是要计入作弊次数的哈(累计10次以上就无效成绩了哈!)

三,订单的服务时间(离开时间-到达时间)计算不正确。对于网点来说,服务时间一定是0的哈,电商单的取货点是没有服务时间的,否则成绩直接无效哈;对于店铺来说,服务时间的有无决定于到达店铺的时间与商家要求的最早时间,如果早于要求的最早时间到达,是需要等待至最早取货时间才可以出发的哈,否则成绩直接无效,而不是惩罚哈;对于配送点,服务时间是严格遵守公式(2)的哈,记得同样是四舍五入(任何时候精确方式都采用四舍五入),计算方式应该是round(3*sqrt(x)+5)。

四,其他直接判定无效的条件还请大家仔细阅读赛题底部说明哈,实在不行就自己coding下评测程序,不过后续我们评测程序会开发出来,大家稍安勿躁哈~

结语:大家可以在群里或论坛里多交流下解题思路,是骡是马都拿出来溜溜,谁跑的快还不一定哈~,毕竟这样排行榜的迭代速度会快点,高出不胜寒啊,前三甲坐久了也是会寂寞的哈~


二、评测代码开放(第二赛季线上评测代码同步)

亲们,日思夜想的评测代码来了!猛戳附件!官方赛题页后续也会添加!由于线上评测程序涉及到代码安全问题,我们复现了一版python版本的线下评测代码,已经测试通过,与线上评测结果一致,请亲们放心的用起来,如有疑问,欢迎拍砖~

注意:如果该评测过了,线上还有问题,那尝试将你的结果文件最后一列空列(第7列)删除下,再测下

最新版评测程序较之前一版做了两处改动:
一,对解文件的列做了判断,防止再出现空列情况;
二,对cost的计算做了更新,以前的cost计算存在漏洞,该漏洞会导致作弊情况出现。该离线版本code已经与线上code保持同步,请大家放心使用。

最新版离线评测代码 evaluateOfflineTianChi.py.zip (3 K) 下载次数:559



三、【有更新】无效解解析,且不在排行榜展示

参赛选手提交的结果需要校验的所有逻辑如下,只要满足任一条件,即被判定为无效解,无效解将不在排行榜展示:
1. 解文件读写异常(正常保存为csv文件即可)。
2. 每个节点的到达时间早于上一节点的离开时间。
3. 每个节点的离开时间早于该节点的到达时间。
4. 同一笔订单,被取/送货多次(必须一次性取/送完)。
5. 任一笔订单取/送货数量、地点与给定数据集不一致。
6. 快递员达到取/送货点的离开时间早于订单要求的最早取货时间。
7. 取货订单数量、订单编号与送货订单数量、订单编号不匹配(有取必有送,有送必有取)。
8. 配送的订单集合必须与给定数据集中要配送的订单不完全匹配,遗漏订单。
9. 作弊次数超过10次。作弊的判定:服务时间(排除O2O订单取货节点,因为需要等待至最早取货时间)和行驶时间不满足假设7、8。
10. 快递员任意时刻携带包裹量>140。
11. 任一笔订单取货时间晚于送货时间。注:对于首单为O2O单的快递员,其到达首单店铺时间应>=距离该店铺最近的网点距离/快递员速度,否则,差异时间会计入10倍惩罚



[ 此帖被岱月在2016-08-29 10:44重新编辑 ]
级别: 新人
发帖
4
云币
5
只看该作者 沙发  发表于: 2016-07-20
Re赛题攻略
不错
级别: 新人
发帖
3
云币
4
只看该作者 板凳  发表于: 2016-07-20
Re赛题攻略
楼主详细讲一下什么是OR问题,
级别: 新人
发帖
2
云币
3
只看该作者 地板  发表于: 2016-07-20
Re赛题攻略
按照 快递员到同一地点取/送多笔订单时,需要分开计算到达时间与离开时间的规则,停留时间固定是所有订单的停留时间总和?
级别: 小白
发帖
45
云币
56
只看该作者 4楼 发表于: 2016-08-09
Re赛题攻略
路上行驶时间有偏差,可能是float精度不够导致的,供大家参考
级别: 新人
发帖
2
云币
2
只看该作者 5楼 发表于: 2016-10-11
Re赛题攻略+评测代码开放+无效解解析,且不在排行榜展示
您好,我是物流专业的学生,想下载最后一公里的数据,可是网页不支持下载了,可以麻烦您发给我一份吗?邮箱839157652@qq.com,谢谢
级别: 新人
发帖
2
云币
2
只看该作者 6楼 发表于: 2016-10-11
Re赛题攻略+评测代码开放+无效解解析,且不在排行榜展示
您好,我是物流专业的学生,想下载最后一公里的数据,可是网页不支持下载了,可以麻烦您发给我一份吗?邮箱839157652@qq.com,谢谢
发表主题 回复主题
« 返回列表上一主题下一主题

限100 字节
如果您在写长篇帖子又不马上发表,建议存为草稿
 
验证问题: 49 + 27 = ?
上一个 下一个