阿里天池大赛：最后一公里急速配送
前言
最近公司组织了一场大咖秀，有位讲师建议我们没事多参加阿里的天池大赛，说是对提高自己很有帮助。于是想起自己几天前看到的FinanceR专栏的天池最后一公里，便紧随偶像步伐，注册并下载了一份数据，凑个热闹。详情请点击赛题介绍
简单分析
数据有三种类型的节点。第一类是Site，电商订单发货节点。第二类是Shop，O2O订单发货节点。第三类是Spot，消费者收获节点。电商订单的要求比较送，只需在当天晚上8点前配送完毕即可。O2O订单比较着急，必须在指定的时刻前去Shop取货，并在指定的时刻去Spot送货。
首先，我们将电商订单的情况打到地图上看一下。
library(readr)library(plyr)library(dplyr)library(tidyr)library(ggplot2)library(plotly)library(lubridate)library(leaflet)library(sp)library(RColorBrewer)library(jsonlite)library(splitstackshape)library(stringr)library(rlist)# 辅助函数points2spline % inner_join(df.site, by=c("Site_id")) %>% inner_join(df.spot, by=c("Spot_id")) %>% unite(Point_x, ends_with("x")) %>% unite(Point_y, ends_with("y")) %>% gather(point, location, Point_x, Point_y) %>% separate(location, c("Lng", "Lat"), sep="_", convert=TRUE) %>% unite(Line_id, Site_id, Spot_id, remove=FALSE)df.site % inner_join(df.site.spot %>% group_by(Site_id) %>% dplyr::summarise(order_cnt=sum(Num)), by=c("Site_id"))ls.site.spot % addTiles( 'http://webrd02.is.autonavi.com/appmaptile?lang=zh_cn&size=1&scale=1&style=8&x={x}&y={y}&z={z}', tileOptions(tileSize=256, minZoom=9, maxZoom=17) ) %>% addPolylines(data=sl.site.spot, weight=2, color="# 377EB8") %>% addCircleMarkers(lng=~Lng, lat=~Lat, radius=~order_cnt/1000, data=df.site, stroke=FALSE, fill=TRUE, fillColor="# E41A1C", fillOpacity=0.5, popup=~paste0("Order Num: ", order_cnt)) %>% fitBounds(sl.site.spot@bbox["x", "min"],sl.site.spot@bbox["y", "min"], sl.site.spot@bbox["x", "max"], sl.site.spot@bbox["y", "max"])m图中红色的圆圈就是每个Site，半径越长表明出货量越大。蓝色的线表示这个Site与它负责的电商订单的Spot的连线。可以看出Site和Spot之间是一一对应的关系，不存在交叉，所以如果只考虑电商订单，这就是一个比较简单的VRP问题，可以分而治之，每个Site单独规划。
但是呢，我们还有一堆O2O订单要一起配送，这就让问题的复杂度骤然提升了难度。我们先来看一下O2O订单的空间分布。
df.shop % inner_join(df.shop, by=c("Shop_id")) %>% inner_join(df.spot, by=c("Spot_id")) %>% unite(Point_x, ends_with("x")) %>% unite(Point_y, ends_with("y")) %>% gather(point, location, Point_x, Point_y) %>% separate(location, c("Lng", "Lat"), sep="_", convert=TRUE) %>% unite(Line_id, Shop_id, Spot_id, remove=FALSE)ls.shop.spot % inner_join(df.shop.spot %>% group_by(Shop_id) %>% dplyr::summarise(order_cnt=sum(Num)), by=c("Shop_id"))m % addTiles( 'http://webrd02.is.autonavi.com/appmaptile?lang=zh_cn&size=1&scale=1&style=8&x={x}&y={y}&z={z}', tileOptions(tileSize=256, minZoom=9, maxZoom=17) ) %>% addPolylines(data=sl.shop.spot, weight=2, color="# 4DAF4A") %>% addCircleMarkers(lng=~Lng, lat=~Lat, radius=~5, data=df.shop, stroke=FALSE, fill=TRUE, fillColor="# 984EA3", fillOpacity=0.5, popup=~paste0("Order Num: ", order_cnt)) %>% fitBounds(sl.shop.spot@bbox["x", "min"],sl.shop.spot@bbox["y", "min"], sl.shop.spot@bbox["x", "max"], sl.shop.spot@bbox["y", "max"])m途中紫色的点为每个shop，绿线为O2O订单的spot与shop的连线。从空间上看，O2O的订单分布就比较散乱了。我们将O2O订单和电商订单的分布叠到一起看一下效果：
叠在一起后，我们能够很明显地看到O2O订单范围比电商范围小，集中在市区。
下面，我们模仿下FinanceR的思路，看一下O2O提单与配送时间的分布。
fake_dt % mutate(pickup_hour=round_date(ymd_hm(paste0(fake_dt, Pickup_time)), "hour"), delivery_hour=round_date(ymd_hm(paste0(fake_dt, Delivery_time)), "hour")) %>% gather(time_type, tm, pickup_hour, delivery_hour) %>% group_by(time_type, tm) %>% summarise(order_cnt=n())ggplot(o2o.hour) + geom_point(aes(x=tm, y=order_cnt, colour=time_type)) + geom_line(aes(x=tm, y=order_cnt, colour=time_type)) + theme_bw(base_size=16)O2O订单有一个特点，就是比较碎。从数据中我们可以看到存在同一个spot在不同时刻向同一个shop下的订单。如果把这些碎订单拼凑在一起统一配送的话，能够节约很大成本。那么这种拼单思路的操作空间有多大呢？
df.o2o.order.batch % mutate(batch_pickup_time = round_minute(ymd_hm(paste0(fake_dt, Pickup_time)), 30), batch_delivery_time = round_minute(ymd_hm(paste0(fake_dt, Delivery_time)), 30)) %>% group_by(Spot_id, Shop_id, batch_pickup_time, batch_delivery_time) %>% summarise(total_order_size=sum(Num), total_order_num=n())table(df.o2o.order.batch$total_order_num)在拼单的时候，考虑到用户体验，将pickup和delivery时刻取整为最近的30分钟时刻，再分组统计并单数量。结论是2975单无法拼单，143个订单能2单合并，4个订单能3单合并。所以，仿佛拼单预处理的优化空间不是很大，关键还是在这个配送问题本身。
VRP入门
最后一公里急速配送这个比赛，是一道十分困难的VRP问题。学术上，这种问题称为VRPPDPTW，添加的后缀PDP表示Pickup Delivery Problem，即允许沿途取货送货；TW表示Time Window，即配送存在时间窗口约束。这么复杂的问题，我这种菜鸟肯定是搞不定的。
所以本文暂且把O2O订单抛开，来解一解单纯的电商订单问题。前文已经提到，电商的最后一公里配送网规划得比较整齐，一个site对一个spot，order之间没有交集，因此可以逐个site求解。本文采用的方法是Saving Method。
# 辅助函数## 赛题规定的两点距离计算公式p2pdist % inner_join(df.e.order %>% group_by(Site_id) %>% dplyr::summarise(Num=sum(Num)), by=c("Site_id")) %>% filter(Site_id==target.site) target.spot.geo % filter(Site_id==target.site) %>% inner_join(df.spot, by=c("Spot_id")) %>% arrange(Spot_id) target.site.geo$Index % select(Index, Site_id, Lng, Lat, Num) %>% dplyr::rename(ID=Site_id), target.spot.geo %>% select(Index, Spot_id, Lng, Lat, Num) %>% dplyr::rename(ID=Spot_id) ) return(points)}get_cost_matrix % list.remove(c(p1.idx, p2.idx)) %>% list.append(list(route_node=new_route_node, load=total_load, processing_time=total_processing_time, distance=total_distance, distance_time=distance_time_cost(total_distance))) } } } return(route)}## 绘制结果plot_vrp_route % list.map(list(spot_idx=str_c(route_node, collapse=","), load=load)) %>% list.stack() %>% mutate(id=1:length(route), Index=paste0("0,", spot_idx, ",0")) %>% cSplit(c("Index"), direction="long") %>% inner_join(points, by="Index") target.site.geo % filter(Index == 0) ls.route % addTiles( 'http://webrd02.is.autonavi.com/appmaptile?lang=zh_cn&size=1&scale=1&style=8&x={x}&y={y}&z={z}', tileOptions(tileSize=256, minZoom=9, maxZoom=17), group="高德地图" ) %>% addCircleMarkers(data=target.site.geo, radius=15, stroke=FALSE, fill=TRUE, fillColor="# E41A1C", fillOpacity=0.8, group="Site") %>% addCircleMarkers(lng=~Lng, lat=~Lat, radius=3, data=df.route, color=~factpal(id), group="Spot") %>% addPolylines(data=sldf.route, weight=3, color=~factpal(id), group="配送路线") %>% fitBounds(sldf.route@bbox["x", "min"], sldf.route@bbox["y", "min"], sldf.route@bbox["x", "max"], sldf.route@bbox["y", "max"]) %>% addLayersControl( baseGroups = c("配送路线"), overlayGroups = c("Site", "Spot", "高德地图"), options = layersControlOptions(collapsed = FALSE) ) return(m)}## 普通VRP主函数vrp_saving_method % select(Lng, Lat)) cost.matrix % filter(Index != 0) %>% select(ID, Num) init_route Saving Method规划的结果总体来看质量还是很不错的。简单说一下实现Saving Method的思路：构造cost矩阵和demand向量；构造初始解，即从site派专车送货到spot然后返回site；算saving matrix；将saving从大到小排序，逐个取出，判断这个saving对应的两个路线合并后车辆Capacity或时间窗等约束是否被满足，若满足则合并路径。其他常见的构造性的启发式算法还有Insert和Sweep；然后有一些听过大名的模拟退火、禁忌搜索等算法，不甚了解。由于学艺不精，时间有限，此题只能做到这里打住了。#r、leaflet#本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！