小程序3分钟跑最后一公里极速配送
贴子的排版可能不是很优美，所以可以去我的博客
博客地址：
blog.csdn.net/three_fish/article/details/52518682
得分：586581
未计算时间复杂度：运行时间 < 3min（i5,8GB）
赛题描述：
tianchi.shuju.aliyun.com/competition/information.htm?spm=5176.100067.5678.2.t7Bjn1&raceId=231581
较简单的解题思路：
由于不同订单同时到达同一配送点，订单服务时间依旧是分开算的，所以服务时间是固定的。可减少的时间有：路程消耗、惩罚时间、等待时间和回程时间。
从实际意义出发，网点与对应配送点间的距离应最小化（不会傻到将目标配送点的货物放在最远的网点吧），所以可认为：
每一个电商订单中，有网点a->配送点b，满足离配送点a最近的网点是网点b（事实上，数据基本满足此条件）。
并且网点数量少于快递员数量（少很多），所以电商配送问题可以转化为单个取货点CVRP问题。即快递员在配送完成后，回出发网点重新取货。
对于单个取货点CVRP问题，采用C-W节约法（三角形中，两边之和大于第三边，比较简单的方法，临时学起来容易）先建立路径。（就是路径已经固定，较不灵活）
先解决电商订单（网点快递员分配）：
初始化每个网点site消耗时间为0xffff（大数）
1.遍历每个网点site；
2.计算向site增加一个快递员可节省的时间；
a.按回程时间增序遍历网点site的路径path（让快递员最后停留在远离网点的配送点，减少回程消耗），选出属于该网点的，目前使用时间最短的快递员，配送该路径上的包裹。计算出总消耗时间cost，节省时间为（当前site消耗时间 - cost）
b.如果节省时间大于最大节省时间，更新最大节省时间，并记录最优选择网点best_site
3.向网点best_site 增加快递员，按2的过程更新快递员路径。
解决O2O订单：
1.按取货时间遍历O2O订单oid；
2.选出处理订单oid消耗最少的快递员；
a.遍历每个快递员man
b.计算当前快递员所在位置与oid商家位置距离（cost1）
c.计算是否将取货超时，若超时则增加惩罚（cost2=超出时间*5（官方处罚）*W）。W为自己设置的参数，加大惩罚，防止部分快递员长时处于等待时间（闲着没事做），部分快递员一直处理忙碌（累死了），另外可以让更多的快递员集中在商家集中的地方。（加上W减少了10W消耗）
d.计算是否将送货超时，若超时则增加惩罚（cost3=超出时间*5（官方处罚）*W2）。W2类似过程c，复赛时发现W2设为0更高分（即去掉d）
e. 如果消耗小于最小消耗时间，更新最小消耗时间，并记录最优选择快递员best_man
3.让best_man处理订单oid，并分析是否取多个订单（这里只分析同一个商点到同一个配送点的订单）
取订单的条件：
a.满足两订单间取货时间间隔小于t，或者t满足设定的数值
b.快递员当前工作时间大于（下一个订单取货时间- T）
最后根据快递员所走路径生成结果
具体还是得看源码：
github.com/3ZY/Tian_chi/tree/master/Last_mile
展开
收起
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
相关课程
更多
推荐问答
