出现此文本是由于Yandex中的随机咖啡乐趣-如果两名随机员工表示希望参加此类会议，则系统会对其进行约会。我的对话者发现了有关我正在做的事情的故事的趣味，现在我开始将其提供给更多的听众。在Habr之前，我曾在HSE和Yandex的计算机科学学院做过客座演讲-我告诉FCS的学生完全一样的事情，我现在将告诉您（帖子末尾有一个视频）即，如何与司机一起从在线商店交付订单，使我们的团队说服了有关物流的新服务。我希望能向您传达我在这方面的感受：我去了加兹勒斯和拉格斯，听取了员工对来自诺金斯克的挑剔阿姨的抱怨，目睹了三个孩子的三个踏板车如何变成一部戏剧。 。最后，让我们谈谈技术。第1部分。一切如何开始
几年前，我在办公室里走来走去，思考是否该改变我的生活了，所以我几乎不小心碰到了一位同事，在我过去的一个项目中，我非常尊重他。原来，他切换到内部创业公司，而他们只是在寻找分析师。所以我最终进入了一个名为B2BGeo的部门。当时，这个小团体应该为基于Yandex地理服务的公司做某种事情-只有没人知道哪个。从历史上看，地理服务员工一直在使用台式机Yandex.Maps，Maps，Navigator和Metro移动应用程序。此外，该部门还拥有令人印象深刻的基础设施：路由引擎的开发，地图服务，道路标志的识别，从卫星图像中提取数据等等。网络地图和Yandex.Navigator都是应用程序，适用于大众用户。在为公司提供的服务中，我们只有一组映射API：用于站点的JS地图小部件，用于应用程序的MapKit和REST路由构建API。因此，B2BGeo团队在开始为公司销售产品之前，必须提出这些产品。我们花了一些时间进行市场研究和原型制作。原型很有趣，例如，建筑物内蜂窝信号质量的地图。然后，蜂窝运营商没有使用他们拥有的大量数据，而是主要在街道上以一种相当原始的方式来测量质量。原型的另一个示例是具有机器学习功能的通用可定制路由器。顺便说一下，以下称为路由器，路由器不是网络设备，而是路由构建程序。一些原型没有起飞，其他原型对足够多的公司不感兴趣。需要更大的东西。将来，它将改变世界，开辟新的视野，并且从一开始，它将通过地理技术带来巨大的收益。我们进行了一次战略性会议：我们离开办公室，集思广益了两天。根据会议的结果，我们确定了一个有足够前景的行业。我们的选择取决于物流。在俄罗斯，很多商用车，许多运输和快递公司都在某处运送东西。而且所有这些都极有可能是通过手动方式或在可能效果不佳的程序的帮助下进行路由的，因为它们没有考虑到交通拥堵。在我们身后，有一个完整的Yandex，其中包含许多硬件，只有少数公司（只有一个罕见的例子-Google）拥有示例数据，并且拥有优秀的程序员。这方面的能力是稀有且有价值的：Uber在某个时候买断了整个制图团队。在这种前景的鼓舞下，我们同意了一家交付聚合商（一家从各种在线商店交付订单的公司），以便他们让我们从内而外地看待他们的工作，“使自己沉浸于行业中”。我们的小团队成员与快递员一起运送订单，并与计划路线的物流员坐在一起。第2部分。沉浸在行业中
上午8点，是三环线后面的工业区之一，聚集器的仓库和办公室位于该工业区。一间小房间，让人想起邮局：角落里用桌子围起来，里面是后勤计算机，电话，打印机。油腻的椅子和开裂的真皮的电脑椅。一个装有廉价中国手机的盒子，每个盒子上都贴有一个数字纸，然后分发给驾驶员。墙壁上有简单的沙发宴会，出口处有一个打印输出的架子：运输规则，某种内部说明，罚款表-例如，司机将收取200-300卢布的未交付订单。聚合器还有一个普通的办公室，主管，经理和簿记员坐在漂亮的桌子旁，但对我们来说，关键事件却发生在这个小房间里。
司机在外面抽烟，但那里很凉，大部分在里面，所以房间里很拥挤。 Mat-remat在三层楼中，早晨很多时候令人沮丧，有人想要拿起他的发票并离开去装货，有人遇到麻烦了，他不高兴。局势很紧张，有两名物流师，他们都在肥皂水里。我们被告知，这是正常的一天，只是在早上，去旅行时，总会有一个公园。晚上，当计划继续进行时，也溺水了，一个小时内某个地方的紧张局势将减轻，后勤人员将能够休息。几个司机被告知Yandex将与您同在。他们感到惊讶，并不特别满意-不清楚为什么他们如此高兴，以及是否让我们跟随他们。我们，办公室工作人员，背着背包的IT工人与这些阴郁的男人形成了鲜明的对比。我得到了瞪羚，它有一个驾驶员和一个货运代理，我坐在我的怀里，背着背包坐在第三位，并尽量不占用太多空间。订单已经加载到主体中，我们开始。
后来我了解到，通常是在路线上的汽车出发之前。假设今天是星期三，您在Yandex.Market上的一个小站点上订购了冰箱，这家商店的价格最优惠而且评论也很合理。适合您的周五才可以送货。该站点实际上只是一个展示；对于很小的站点，确认订单的经理通常可以是唯一的雇员。您的冰箱和同一家公司的其他冰箱一起位于波多利斯克附近的仓库中的某个地方（一家小商店没有自己的仓库-实际上，销售来自制造商的仓库）。经理保留了这台冰箱，并将订单发送到交货聚合器。在星期三期间，汇总员收集订单，并在星期四将大型卡车发送到Podolsk，以在其他商店订购您的和其他冰箱。所有这些都归集合商在莫斯科工业区租用的仓库。在星期四晚上，当所有要在星期五交货的货物都收集在仓库中时，物流人员坐下来工作。到了凌晨4-5时，他们应该按机器分配订单，仓库工作人员会将货物堆放起来，每台机器都有自己的堆-您需要留一些时间进行此项工作。一堆将被装载到汽车上，它将取悦顾客。
为了通过机器分配订单，后勤人员使用专门购买的程序。它与1C集成：企业，将有关机器的数据（允许的重量和货物数量，一天的工作成本）和有关货物的数据（重量，体积，地址和交货间隔，客户联系方式，评论）加载到其中。其中一些汽车属于聚合器，其中有高跟鞋（拉达·拉格斯）和瞪羚（瞪羚/福特全顺/现代波特）。也有私人汽车上的快递员，通常是旅行车上的卡车（我们见过福特福克斯，三菱帕杰罗，甚至还有一些老雷克萨斯）。该程序是由优秀的程序员编写的，它知道如何给汽车分配负载并建立最佳（按时间或行驶里程）路线来避免订单（给定一系列参数）。但是后勤人员不会以任何方式使用此功能。但是他积极使用地图上订单的可视化。该程序允许您在地图上绘制多边形区域，并显示这些区域内货物和路线的统计数据。后勤人员将整个莫斯科和莫斯科地区，直至大混凝土（A108号高速公路）划分为以下类型的区域：
在中心，有一些小区域，然后放射状部分开始沿着主要公路运行并围绕该区域。在每个这样的区域中，通常熟悉该区域的某些驾驶员会知道道路，交通特征，交通警察在哪里，卡车的限制和标志是什么。物流师又知道机组人员可以携带多少订单。他给30位以下订单提供了更多经验，而对于最近开始工作的人员，则提供20-25位订单。他查看某个区域中的订单数量，如果数量过多，则将其扔给下一个订单。或从邻居那里添加：比如说，物流师是一些驾驶员的朋友，并向他们发出“轻便”的命令，而这些命令很可能即将到来。而这位无人驾驶的司机可能会讨厌。例如，向一位事先挑剔的客户扔一个订单，他将严格要求在指定的时间交货，将所有货物打印，将对其进行长时间检查。除了，后勤人员可以简单地给驾驶员更少的订单：驾驶员每收到200卢布，他就会有更多的兴趣。在程序中规划路线的功能被完全忽略。在这样的系统中，这种可能性没有意义：如果后勤人员告诉驾驶员他需要如何下达命令，驾驶员会回答他：“你坐在那儿的办公室里，我在这方面就像我的手背一样。”因此，后勤人员只为汽车分配订单，将驾驶员的任务表述为仓库中的一堆和一堆印刷的发票。所以，回到瞪羚。我们的地区是发烧友高速公路，再往Noginsk方向行驶，前往莫斯科环城路的订单大约有15条，我会去那里。驾驶员离开前往第三运输环，此时，货运代理取了一包发票并按照正确的顺序进行转移。正确的顺序是这样的：-首先，我们将沿着发烧友的高速公路驶向莫斯科环城公路，并接受右边的所有订单。我们并不总是将其驶向左侧，过马路时可能会出现交通拥堵的情况，最好在晚上乘车。然后，我们将前往该地区，并将其带到那里。晚上，我们将回去携带其余的东西。-但是，例如，第一笔订单-希望“在14小时后”吗？晚上留吗？-可能在傍晚，但最好还是同意现在就给。谈判过程立即得到证明。 9点30分，货运代理在14小时后拨打了电话订单：-您好，送货，我们已经在您的地区了，您可以接受订单吗？..我们将在您的地区之后去该地区，晚上不回来。也许我们会在9点之后返回，或者我们会完全留在该地区，这是一个无法预测的业务，我们可能不得不推迟第二天的交货……好吧，然后我们会在15分钟内到达。那时我才意识到快递员来自哪里，他们说：“你好，我已经和你在一起了！” -并完全忽略我的评论和交货间隔！开车开过其他汽车的同事告诉我，有人在送货前一个小时诚实地叫了司机或货运代理。我的社交不太好，他们打电话约十五分钟，大声说出顾客的意见。考虑了简单的愿望（“不打对讲机，孩子正在睡觉”），但是影响路线的所有因素通常都被忽略。转移发票后，货运代理人拿出一份订单，该订单必须送到离诺金斯克几公里的一个村庄。-再来一次还记得她下令，然后结婚吗？现在有新订单。-是的，再次抬起洗衣机。另一个有趣的是：“请从12交付到16”。她如何想象？-是的，总的来说，他们不明白自己在写什么。我想是这样的：如果您在Noginsk订购洗衣机，请坐在那里，静静等待，直到它被带上为止。要么以某种方式与邻居达成协议，要么辞掉工作。我们不能每天都去诺金斯克找她。我在莫斯科环城公路附近下车，司机沿着高尔基公路沿着瞪羚走得更远。实际上，他们并不是坏人，尽管受到客户的热烈欢迎（至少占所有对话的三分之二），但他们很可能会设法将洗衣机交付给16名顾客。如果没有，他们甚至都不会打扰。我的第二次旅行是在一辆较小的汽车中进行的：拉格斯（Largus）的货物绕着西北行政区行驶。货物很小，没有冰箱，所以司机一个人。叔叔很友善，我们谈论了很多他。他说，总的来说，他是摔跤运动的大师，是一名教练，但现在一切都是聋子，所以他当快递员了。钱虽然少，但增长却是令人愉悦的：每天可获得约2000笔。交付订单很容易，可以在需要时使用。当然，有一些细微差别：您遇到不愉快的顾客，您必须在车上吃储存的三明治，您很着急，甚至不去洗手间，都必须询问顾客。但总的来说，他很富裕，对他来说更可能是娱乐。这很有趣：同事，特别是女孩，送货服务人员也讲过这样的故事：“快递员不是主要工作，而纯粹是为了灵魂”，“总的来说，我通常会走在behhe”等等。我记得在Rublevka 或Krylatsky地区这样的对话：-到了城市，他下达了命令，在那里他们在摩天大楼中有公寓，走廊全是大理石，我走进了公寓-地毯，金色框架的画作，一些皮大衣悬挂着，而这些都不在那里。一份5800的订单，所以他要求找200卢布的零钱，算吗？！-所以，也许他有皮草大衣和油画正是因为他节省了200卢布。听完我的话，司机苦思冥想。一个小时后，我们到达了舒基诺，我“了解了一切”关于这项业务的信息。在下一根高架笔上，记下了一切都不符合命令的顺序：在购买的三辆总价值为两万卢布的儿童滑板车中，只有两辆在车上。司机叫物流师。原来，那名女子在星期一下令订购三辆踏板车，但昨天，星期三，第三辆踏板车被错误地放错车上。那是一辆私家车，由于某种原因，他没有像“普通”司机那样晚上在晚上回到仓库，而踏板车仍然骑着它。我们可以尝试拦截他，但今天他开始从事他的生意，不可能越过。下次他明天（星期五）工作，但这不准确。保证重新组合所有三个踏板车，并且只有在星期六才能将它们全部收起。有了这些信息，驱动程序调用了客户端。有一个非常不高兴的女人。她说：在星期六的上午10点，他们有一个家庭假期，他们想给她的三个孩子送踏板车。因此，她严格按三件的数量要求他们，她不同意部分赎回并且完全不知道怎么可能-她在星期一下了订单，现在我们的踏板车商店正在替她订购。周六在不确定的时间分娩并不适合她。明天她将在晚餐前在家中，如果您今天或明天早上不能这样做，她将取消订单并将商店诅咒至第三膝（您可以理解）。第3部分。局部最小值
商店从快递公司购买了订单递送服务。对于未送达的踏板车，他将对一家快递公司处以500卢布的罚款。该公司将对未按时带回踏板车的店主和司机处以200-300卢布的罚款。一个不高兴的女人会把她的2万卖给一个更敏捷的商店，而Yandex上的一颗星就会被市场打耳光。这家商店可以提供最好的服务，但“最后一英里”是由瞪羚和拉格斯的忧郁男子进行的。如果他们在顾客方面表现不好，那么商店将无法影响这一点。同时，商店通常会寻找成本最低的送货方式-从某种意义上说，如果您付给司机的钱更少，他们将成为出租车司机或其他地方的工作。司机优化了他们的每日收入-您需要承担更多的订单，而不会被罚款。如果我们组成一个描述整个系统的全局成本函数，那么函数的这种状态肯定会与其局部最小值（“势阱”）相对应。
在这个坑中显然存在着大的系统性问题。首先，最困难的工作移交给了最不熟练的员工：驾驶员控制机器并计划路线并与客户沟通。他也有钱。他还具有其他技能和专长-例如，每天能够在某个区域内交付30个订单。事实证明，公司必须培训经验不足的驾驶员，而经验丰富的驾驶员也不要失去，因为他们（对于公司而言是不幸的）很难替代。其次，交付过程是完全不可预测的。客户不知道他们什么时候会来找他。通常向客户提供宽阔的交货期-四小时，六小时或更长时间。这给他带来了极大的不便：并非总是可以在一个地方坐六个小时。甚至驱动程序也无法始终进入这些窗口。只有对于能够更努力地推动并跳出潜在漏洞进入更优化状态的大型公司，才有可能为客户提供方便的狭窄窗口（两个小时或一个小时更好）的机会。我们正在谈论拥有自己的送货和快递公司的公司。 “自己的”快递员对所有公司都将是有用的：这样，您可以控制他们的工作质量，甚至可以进行某种形式的销售（当快递员向某人提供要订购的东西时）。但是聘请快递员的费用非常昂贵-只有WildBerries或Lamoda这样的大公司才能负担得起。第三，后勤人员不断作弊。诸如汽车超载和驾驶员换档中断等技巧被认为是司空见惯的（而不是8个小时，而是10到12个小时）。 “没关系-如果它不适合体积，那么他会把多余的东西放进驾驶室”-即使发生这种情况。为此，将处以罚款，尤其是对超载货车：罚款本身（每家公司十万卢布起）将附加对路基损坏的赔偿。它被认为是过载系数乘以一个距离的乘积，很容易达到数十万卢布。车队拥有者希望驾驶不间断。但是，假设后勤人员可以选择：-“增加多余的托盘，稍微超过”-“增加额外的汽车，增加成本，但又不中断”-“再坐半小时并制定一个适当的计划”，他通常会选择第一个。如此令人沮丧的画面激发了我们极大的乐观情绪。我们对物流其他分支机构的公司进行了几次采访，例如大型货物的交付，单据的交付。我们所有关于这个地方不是完美世界的假设都得到了证实。因此，在我们面前打开了一个很大的机会之窗。我们热切希望开始工作。第4部分。MVRP和交通堵塞
以下是我们产品的技术细节，因此让我们从定义开始。MVRP是一个多车辆路线选择问题，也就是说，您需要在一个拥有多个车辆的车队的情况下最佳地绕过多个位置。我们使用的术语中，将一台计算机的相似任务称为SVRP（单个VRP）。它与传统的旅行推销员问题（TSP，旅行推销员问题）的不同之处在于交货窗口的存在。似乎没有统一的术语：在Wikipedia的文章中，我们解决的任务称为复杂缩写VRPPDTW（具有取货和送货方式以及送货窗口的VRP）。解决此类问题的程序传统上称为“求解器”。为了实现多功能性，您需要在求解器中添加许多选项和限制：附加选项的示例— , .
— (, ), .
— ( , ).
— . , : , .
— .
— .
— (, -), : . , * .
— «» , . , , - .
— : , .
求解器中可以使用几种算法。例如，有很多通用的开源和付费约束求解器（Google OR-Tools，OptaPlanner，Choco-solver）。在每个组件中，构建了一个功能，并考虑了所需的限制进行了优化。这样的求解器通常能够解决很多任务：VRP任务，调度，在云中优化资源分配。还有许多专门针对MVRP任务量身定制的商业解决方案，可以与企业管理系统集成。 VeeRoute，Maxoptra和Antor在俄罗斯闻名。Solver Yandex.Routing使用退火模拟算法的组合和遗传算法。我们不知道竞争对手在使用什么，但很可能类似。根据我们的测量，在VRP任务约束求解器中，商业求解器会损失很多。
解决美国各州回旋处的TSP问题，我将立即提出保留：解决MVRP问题的主题如此之大，以至于在本文中我们将不进行详细讨论，而将撰写另一篇文章。求解器的主要输入是计划中涉及的点之间的距离矩阵（定单点和一个或多个仓库）。实际上，这不是一个矩阵，而是两个矩阵：按里程数和行驶时间。通过这些矩阵可以完成优化。如上所述，与其他商业解决方案的开发人员不同，Yandex具有交通信息。也就是说，对我们来说，矩阵不是恒定的，而是随时间变化的，我们在求解器中将其考虑在内。据我们所知，世界上没有人这样做：即使了解有关交通拥堵的所有信息，也很难建立具有合理离散度的距离矩阵（足以确保生成的路线良好）。事实是，矩阵单元的数量从阶数开始呈平方增长。假设我们正在解决VRP任务，即使用500辆车组成的车队交付10,000个订单。然后我们得到两个随时间变化的巨大矩阵。仅在网络上下载它们会花费很多时间，但是必须首先计算它们的内容。如果执行效率不够高，我们将需要等待几个小时，直到建立和下载矩阵，然后才能启动求解器。 Dijkstra算法在这里为我们提供了帮助：大距离矩阵的计算可以在几乎线性的时间内（根据矩阵大小）实现。但是我们的团队还将在未来几周的另一篇文章中讨论这一点。因此，我们构建了一个智能求解器，将其并行化为一堆汽车，制造了具有超快速距离矩阵的路由器，该矩阵考虑了交通拥堵，并且还弄清楚了如何将这些矩阵放入求解器。结果，他们有机会在15分钟内解决在3,000个地点附近行驶的问题。在地图上的结果：
第5部分。执行的结果和困难
您可以将我们的路线与由后勤人员通过竞争对手程序手动或（有时）以半自动方式计划行程的后勤人员进行比较。在典型情况下，我们的解决方案可让您以最优的小路线击败物流专家，平均减少20％。同时，完成路线的时间要少得多-15分钟而不是几个小时。在美好的未来中，物流师应该从一个半夜紧张而精疲力尽的人驱散汽车的订单，成为一个受人尊敬的社会成员。他将使用我们的自动计划功能，并偶尔用手纠正单个边缘情况。当客户在交付服务时购买了我们的解决方案时，实施最为顺利。但是我们的大多数客户都不是新客户。他们已经有一个已实施的物流解决方案，并且客户越多，它对这个特定公司流程的各种功能（甚至只是拐杖）的过度需求就越强大。他们的开发和支持由他们自己或雇用的IT服务来完成。可以相信，大公司（即使我们的产品优势显而易见）也只能与IT基础结构的重大更新一起实施路由。这通常每隔几年就会发生一次。 2018年5月，我们与IKEA合作在YaC 2018大会上宣布了我们的新生儿服务。六个月后，实施开始了，我们开始交换数据，一年后，在物流行业会议上，宜家的项目经理谈到了结果。结果是积极的，但对我们来说有点意外。例如，通知客户增加了他们的满意度，并大大减少了呼叫中心的电话数量（之前，在不了解所购买沙发的命运的情况下，人们开始紧张并开始打电话）。另一个例子-与石油行业的工人一起。, . , . , « » — . , , , «» ( , YouTube , ). , ( , ), , . : — , , , . . .
也就是说，事实证明我们的初始安装并不完全正确。我们以为我们可以卖出有效的弯路点，但事实证明，公司需要的产品会影响不同的指标，而不仅是效率方面，而且不是那么重要。幸运的是，我们还提供了更多核心技术产品。较小的公司更擅长克服集成难题，但可能会面临人为因素。要说服驾驶员遵循计划的路线并保持跟踪应用程序处于打开状态，这是非常困难的。这在某种程度上让人联想到19世纪农民打破机械割草机和犁的故事。一切当然都不是那么难过，但是进步是有阻力的。结论
在短时间内，我们设法制造出一种产品，我们希望该产品能够改变该国的所有物流（或至少会对其产生重大影响）。我们目前的客户和Yandex都相信我们。后者也很重要：是的，内部启动要比公司外部的启动要平静，但我们还需要证明结果。我们在未来的计划中着重于大公司，以降低进入服务的门槛。您可以直接在Yandex.Maps上解决SVRP问题：在路线上添加第四个点时，将出现“优化”按钮，该按钮将调用我们的求解器。
针对HSE的FCS学生的相同故事的视频：所有最好的路线！