文档章节

如何送货最省钱?菜鸟自研核心引擎架构首次曝光!

 时光承诺
发布于 2017/07/14 15:11
字数 1922
阅读 3
收藏 0
点赞 0
评论 0

原文地址

随着中国物流运输行业的蓬勃发展, 物流成本已经占据了18%的国民生产总值, 其中, 车辆运输作为配送成本的核心要素, 成为了一个必须面对的问题。而车辆路径规划问题的目标就是减少配送的车辆数目和距离, 进而降低物流成本, 同时也是物流成本透明化的重要手段。

菜鸟网络人工智能部从自身业务出发, 联合集团IDST、阿里巴巴云计算的力量, 打造一款适合中国复杂的业务需求, 又在效果上接近国际水准的分布式车辆路径规划求解引擎 -- STARK VRP, 以此向财富自由还继续追求黑科技的钢铁侠致敬。

菜鸟业务总览

image


由上图可见, 车辆路径规划在整个链路中起到了举足轻重的作用。

运筹优化 机器学习 人工智能

Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear.
--Leonhard Euler

作为优化领域历史悠久的问题, 车辆路径规划问题已经被研究了数十年,我们从菜鸟自身的技术背景出发, 充分利用自身庞大的计算资源为优势,探索一条结合运筹优化、分布式计算、机器学习、人工智能结合的技术路线。

问题定义

VRP问题目标, 是给出一个确定的最优解,包含车辆以及他们的运输路径, 来服务一个客户集合的订单。 这也是组合优化中研究最广, 最重要的问题之一。


image


如大家所知, 中国的物流情况尤为复杂, 有自己很多独特的场景, 也衍生出了对应的VRP求解类型和分支。以下是STARK VRP现阶段支持以及开发中的VRP类型和对应的业务类型。

  • CVRP: Capacitated VRP, 限制车的体积、重量、客户数、最长距离等
  • VRPTW: VRP with Time Windows, 针对客户有要求送达时间的场景, 时间窗可以是多个
  • VRPPD: VRP with Pickup and Delivery,外卖O2O,快递员从不同的商店取货,送到不同的客户
  • MDVRP: Multi-Depot VRP,同样的货物在多个仓库都可以获取, 每个客户选择最佳的仓库
  • OVRP:Open VRP,外包的私家车,在完成配送任务后,不需要返回仓库
  • VRPB: VRP with backhaul,回程取货,回收返修的电子元器件
  • Heterogeneous Fleet: 支持多车型,尤其适合中国目前配送资源是外包的情况
  • T + n 时效:针对时效要求不高的, 可以动态决定哪天送达,合并多日订单,减少车辆数
  • Milk Run:同一辆车会循环取货
  • Skilled VRP:某些客户只能由指定的车辆来服务,在中国司机会和客户之前形成一定的默契关系
  • Same Route VRP:某些订单必须在一条路径上
  • Generalized VRP:某个订单,有若干个location,可从任一个取货,均可满足要求
  • Split Delivery:某个客户的需求(当超过一辆车的容量时),可以由多辆车来分别送达
  • Generalized VRP:某个订单,有若干个location,可从任一个取货,均可满足要求
  • VRP with intermediate facilities:针对新能源车的场景,考虑沿途的充电点以及载重量和耗电的关系
  • 2E VRP:多级VRP,适用于需要在不同的运输环节更换运输工具的场景, 例如使用重卡运输到镇点之后, 使用面包车或者无人机运输到村点


image

 

技术选型 - 丰富多样的求解方式

image

 

传统用于求解VRP的精确解法无法应对大规模数据集

image

 

利用元启发式构建求解的基础框架

image


在整个VRP算法迭代的过程中, 我们顺势建立了一整套元启发式的框架, 目前可以调用的包括:

  • Large Neighborhood Search
  • Adapative Large Neighborhood Search
  • Variable Neighborhood Search
  • Metaheuristic Hybrids
  • Iterated Local Search
  • Memetic Algorithm
  • Tabu Search
  • Simulated Annealing
  • Guided Local Search
  • Fast Local Search

ALNS - Adapative Large Neighborhood Search

使用大规模领域搜索使得在每次迭代寻找一个更好的候选解集成为可能, 并且能够指向一个更为有前途的搜索方向。

在实际过程中, 不同的问题, 甚至问题的不同阶段,每个operator的适用性和效果都是不同的,大家可以想象成在作战过程中, 骑兵和坦克适用于大规模冲锋,但是在山路崎岖的地方就会行进艰难, 而面对河流就直接无法通行。

属于Hyper heuristics的ALNS就是为了解决这一问题, 它使用使用了BANDIT算法, 根据每一次迭代的效果差异来确定下一次迭代各个算子的选择概率。

image

 

利用并行化提升效果

在效果的提升上, 并行化是我们的重点方向之一, 如果充分利用阿里在云计算和并行化的优势, 是我们效果提升的关键。

ISLAND

基于ISLAND的并行化思路, 在于island之间以一定的机制动态发送和接受结果, 保障搜索方向的有效性和利用多样性避免陷入Local Minima。

image


EE Pool

EE Pool的思路是有一个核心的控制环节, 在island之间通信的时候平衡solution pool的exploration和exploitation, 在不同的阶段调整追求intensification和diversity的平衡。整个控制过程采用SSP, 即不会在任何环节同步。

灵活的分布式架构

image


利用深度增强学习提升效果

这个方向是我们目前重点探索的方向之一, 通过以某种embedding的方式表达Problem, 根据Reinforcement Learning的反馈, 更新算子选择的概率,以期望在效率和效果获得提升, 走向data-driven。

image

 

业务效果的提升

村淘业务减少了28%的行驶距离


image
image
image


零售通业务减少10%的车辆


image


持平6项Best Know Solution

Gehring & Homberger benchmark 保存了全球范围内有史以来已知的最好结果(Best Known Solution)

STARK VRP在400 Job上持平了4项BKS, 在1000 Job上持平了2项BKS。


image

 

总结

我们希望通过以上几个实例让大家感受到车辆路径规划技术的重要性,这是有别于传统的基于机器学习的搜索、推荐、广告的AI赋能的另一种表达,它在日益快速发展的物流领域占据了不可或缺的一席之地, 在无人驾驶大行其道的未来, 它也是处于核心位置的调度中心。

STARK VRP不仅仅在菜鸟内部的村淘、零售通、跨境、新能源车、仓内路径规划已经开始落地, 而且更为广泛的开始服务于像日日顺、云鸟这样的外部公司, 为降低中国的物流成本, 提升时效尽一份算法人员的能力。

原文地址

 

本文转载自:http://click.aliyun.com/m/25951/

共有 人打赏支持
粉丝 0
博文 225
码字总数 0
作品 0
云计算史上的第一次开箱直播 阿里云神龙技术架构首次全方位曝光

5月16日,阿里云目前最先进的自研弹性计算技术架构“神龙(X-Dragon)”首次全方位曝光,这种新型的计算架构打破了过去物理机和虚拟机的隔阂,既保留了物理机的性能优势和硬件级隔离,又具备...

阿里云头条
05/17
0
0
600页阿里技术全景图曝光,程序员看完都沸腾了!

如果你不甘心一直在写增删改查,希望看到更广的技术世界,阿里技术团队重磅发布的《阿里技术参考图册》,总计600余页,现已开放下载,将为你呈现阿里技术全景,走进各个技术领域的世界。 此书...

vhwfr2u02q
04/17
0
0
速度收藏!600页阿里技术全景图曝光,程序员看完都沸腾了

如果你不甘心一直在写增删改查,希望看到更广的技术世界,阿里技术团队重磅发布的《阿里技术参考图册》,总计 600 余页,现已开放下载,将为你呈现阿里技术全景,走进各个技术领域的世界。 ...

c9yv2cf9i06k2a9e
04/18
0
0
600页阿里技术全景图《阿里技术参考图册》开放下载

如果你不甘心一直在写增删改查,希望看到更广的技术世界,阿里技术团队重磅发布的《阿里技术参考图册》,总计600余页,现已开放下载,将为你呈现阿里技术全景,走进各个技术领域的世界。 此书...

程序师
04/22
0
0
亚马逊无人机专利再曝光,可根据地形自动调整脚架高度

这一可节约运送成本的送货方式,有很大可能会在解决技术和安全问题后成为我们的主流“快递员”。 近日,亚马逊无人机专利再次被曝光,据曝光信息显示,亚马逊正在致力于让无人机可以根据对地...

行者武松
03/01
0
0
搞技术的必看!600页阿里技术图册,30位资深大牛解读!(免费下载)

如果你不甘心一直在写增删改查,希望看到更广的技术世界,阿里技术团队重磅发布的《阿里技术参考图册》,总计600余页,现已开放下载,将为你呈现阿里技术全景,走进各个技术领域的世界。 此书...

egefcxzo3ha1x4
04/18
0
0
刚刚,阿里开源600页技术全景图,看完少走10年弯路!

如果你不甘心一直在写增删改查,希望看到更广的技术世界,阿里技术团队重磅发布的《阿里技术参考图册》,总计600余页,现已开放下载,将为你呈现阿里技术全景,走进各个技术领域的世界。 此书...

tw6cy6ukydea86z
04/18
0
0
速度收藏!《阿里技术参考图册》发布,公开600页技术全景图

如果你不甘心一直在写增删改查,希望看到更广的技术世界,阿里技术团队重磅发布的《阿里技术参考图册》,总计600余页,现已开放下载,将为你呈现阿里技术全景,走进各个技术领域的世界。 此书...

技术小能手
04/18
0
0
数据库厂商都怕低价竞争?阿里云说并不可惧

  【IT168 评论】2017年Gartner发布的数据库厂商推荐报告中首次收录了来自中国的数据库厂商,分别是阿里云、巨杉数据库SequoiaDB以及南大通用GBase。在这三家厂商中,巨杉数据库和南大通用...

it168网站
05/07
0
0
新物流迈入“分钟级”配送时代 你生活的城市有此服务吗?

昨天(3月15日),菜鸟宣布全新的“门店发货”物流模式开始升级,从早期的国内一线城市扩展到了全国30多个大小城市,已接入近400家门店作为发货前置仓。以屈臣氏为例,消费者网购下单后,可以...

技术小能手
03/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

一款成功的全球服游戏该如何进行架构选型与设计?

全球服游戏如今正在成为出海游戏的主要考虑模式,跨国对战、全球通服打破国界的限制,将不同地区不同语言的玩家放在一起合作/竞技,成功吸引了大量玩家的关注,并逐渐成为主流的游戏玩法。 ...

UCloudTech
6分钟前
0
0
StringUtils类中isEmpty与isBlank的区别

org.apache.commons.lang.StringUtils类提供了String的常用操作,最为常用的判空有如下两种isEmpty(String str)和isBlank(String str)。 StringUtils.isEmpty(String str) 判断某字符串是否为...

说回答
19分钟前
0
0
react native使用redux快速上手

看例图 要求点击组件一中的按钮,改版组件二的背景色。 利用state和props和容易实现。 //app.jsimport React, {Component} from 'react';import {StyleSheet, Button, View, Text} from ...

燕归南
21分钟前
0
0
页面输出JSON格式数据

package com.sysware.utils;import java.io.IOException;import javax.servlet.ServletResponse;import org.apache.log4j.Logger;import com.sysware.SyswareConstant;pub......

AK灬
42分钟前
0
0
springCloud-2.搭建Eureka Client的使用

1.使用IDEA,Spring Initializr创建 2.填写项目资料 3.选择spring boot版本,插件选择Cloud Discovery→Eureka Discovery 4.选择保存地址 5.修改application.yml eureka: client: s...

贺小康
45分钟前
0
0
CenOS 6.5 RPM 安装 elasticsearch 6.3.1

下载 wget --no-check-certificate https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-6.3.1.rpm...

阿白
48分钟前
0
0
1.4 创建虚拟机&1.5 安装CentOS7&1.6 配置ip(上)&1.7 配置ip(下)

1.4 创建虚拟机 知识点 虚拟机网络链接模式 桥连 直接将虚拟网卡桥接到一个物理网卡上面。需要手工为虚拟系统配置IP地址、子网掩码,而且还要和宿主机器处于同一网段,这样虚拟系统才能和宿主...

小丑鱼00
54分钟前
0
0
TrustAsia(亚洲诚信)助力看雪2018安全开发者峰会

2018年7月21日,看雪2018安全开发者峰会在北京国家会议中心圆满落下帷幕。拥有18年悠久历史的老牌安全技术社区——看雪学院联手国内最大开发者社区CSDN,汇聚业内顶尖的安全开发者和技术专家...

亚洲诚信
56分钟前
0
0
Spring注解介绍

@Resource、@AutoWired、@Qualifier 都用来注入对象。其中@Resource可以以 name 或 type 方式注入,@AutoWired只能以 type 方式注入,@Qualifier 只能以 name 方式注入。 但它们有一些细微区...

lqlm
今天
0
0
32位汇编在64位Ubuntu上的汇编和连接

本教程使用的操作系统是Ubuntu Linux 18.04 LTS版本,汇编器是GNU AS(简称as),连接器是GNU LD(简称ld)。 以下是一段用于检测CPU品牌的汇编小程序(cpuid2.s): .section .dataoutput...

ryanliue
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部