一种在众包快递系统中匹配寄送人和寄送请求的算法外文翻译资料

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

一种在众包快递系统中匹配寄送人和寄送请求的算法

摘要

随着电子商务销量的快速增产，传统的包裹递送方式正在受到众包快递等创新方法的挑战。让个人（如上班族）来顺路寄送快递可以带来一些经济、环境上的好处。本文阐述了一种算法，该算法基于运输路线和时间限制来自动匹配并优化寄送人寄送快递的路径。 我们通过使用基于德国主要城市记录的移动性数据的模拟环境来评估我们的算法。 本文为众包快递系统的匹配算法的后续研究提供了指导，并提出了一个既能用于现在的众包平台又具有适应未来众包平台能力的算法。

关键词

众包快递，匹配算法，共享经济，动态匹配，流网络

引言

众包快递，即使用群众中的某个个体（而不是专业信使）来寄送物品的概念，在过去几年中越来越引起人们的兴趣（Hodson 2013;Rougegrave;sand Montreuil 2014; Sadilek et al。2013）。众包快递，与大多数众包活动一样，是通过一个可供组织或个人用来发布运输请求的在线平台实现。 其他用户可以在平台上注册，接受和执行请求，并从发件人或平台运营商处获得补贴。 在美国，为众包快递服务提供平台的创业公司（如Postmates和Deliv）已分别获得了2200万美元和1400万美元的投资（Rougegrave;s和Montreuil 2014）。 这一概念还吸引了诸如亚马逊和沃尔玛等成熟实体公司的兴趣，这些公司正在美国的某些地区（亚马逊网站2017;本德2016）实施众包快递服务。

但是，现有的平台都主要针对能有固定或准确的配送时间的寄送人。在大多数情况下，驾驶员会得到一份预先选定的与当前位置相匹配的寄送请求列表以及可用时间，以便他们选择希望执行的寄送请求。 在Rougegrave;s和Montreuil（2014）的研究中提出，使用匹配算法来优化给寄送人的请求分配。 这种算法可以通过优化潜在的匹配并进一步自动化匹配过程来提高众包快递平台的效率。 然而，很少有人研究基于运输路径来匹配寄送人的算法。

在本文里，我们提出了一个可扩展的算法模型，该模型将运输请求与预先知道自己行程路线的寄送人相匹配。为了建立一个好的模型，我们使用了一个设计科学研究方法（Peffers et al。2007）。我们用大量的运输请求和部分随机生成部分来自德国城市真实数据的行程路线在测试模型的有效性。我们借鉴了Agatz等人的研究（2011），他们在动态拼车系统的环境下为相关匹配问题构建了解决方案。我们的算法能用于现在的众包平，也具有适应未来众包平台能力，用于将寄送人的路线和寄送请求的匹配自动化，从而充分利用潜在的寄送人。通过将寄送请求和已知形成路线的个体相匹配，我们可以把寄送过程融入寄送人的日常生活和路径中，即实现顺路寄送。由于是基于个体的原有路线来实现寄送，我们将拥有更多的寄送人，而寄送人也可因此花费最少的时间来完成指定的寄送任务。

本文的其余部分的结构如下。 首先，我们介绍众包快递概念的理论背景。 其次，我们介绍我们的算法模型，并通过一个简化的例子来说明它。 第三，我们讨论将我们的算法模型应用于更大更真实的问题后的结果，以阐述我们算法的有效性。 第四，我们讨论我们目前研究的局限性并为未来的研究提供建议。 最后，我们用一个讨论和小结来结束论文。

理论背景

在Schouml;der等人 （2016）的研究中表明，从2013年到2018年，全球范围内的B2C电子商务销售额预计将翻一番，如图1所示。这种增长意味着快递量的增加以及随之而来的负面环境影响，如污染和交通噪音的增长。 因此，人们开展了几项与快递的最后一英里的替代概念有关的研究（Huuml;bneret al。2016; Joerss et al。2016; Slabinac 2015）。

蓝色表示电商交易值 红色表示全球GDP

图1: 2013-2018年的全球电商交易值和GDP百分比（单位：十亿美元）（Schouml;der等人，2016）

其中一个概念是众包快递，即将众包概念应用于快递寄送过程。根据Estelleacute;s-Arolas和Gonzaacute;lez-Ladroacute;n-de-Guevara（2012）的观点，众包是“一种个体，机构，非营利组织或公司自愿向一群人承担一项任务的在线参与式活动”。根据McKinnon（2016）的说法，众包快递会带来了许多好处，如交通量、能源排放的缩减，以及零售商在快递速度和成本方面的差异化竞争优势。尤其对于那些缺乏能建立或加入现有快递网络的资源的传统实体店来说，众包快递提供了一种保持竞争力的手段（Douml;rrzapfet al。2016）。群众工人（Estelleacute;s-Arolas和Gonzaacute;lez-Ladroacute;n-de-Guevara 2012）的短期可用性使得中小型零售商能够提供更高级的服务，例如目前主要由Amazon.com等大型零售公司提供（MacKenzie et al。2013）的当日寄送服务。此外，众包快递也可以被那些希望避免寄送包裹的潜在高成本和交付时间的个人使用（Mladenow et al。2015）。

正如McKinnon（2016）指出的那样，众包快递服务的市场相对还很年轻，大多数平台都是在过去6 - 7年内出现。 诸如Deliv，Zipments和Postmates的初创公司正在成长和获得更多的投资，已经建立完善运输体系的的Uber和DHL等公司也正在扩大他们的平台和服务，他们将结合了众包快递运输的uberRUSH和DHL MyWays服务投入特定领域进行测试。根据McKinnon（2016）的报告，随着亚马逊Amazon Flex服务在美国29个城市的推广，各个众包快递平台的竞争将进一步加剧。

Rougegrave;s和Montreuil（2014）表明，通过使用算法可以自动匹配运输请求和潜在寄送人。 Amazon Flex或uberRUSH之类的服务提供了一些匹配标准，如物件大小，可用时间和配送位置，以便找到可能的匹配项。 根据这些标准，潜在寄送人可以接受或拒绝接收到的请求或从列表中选择它们。 请注意，在大多数情况下，寄送物品的任务被认为是当前时间点寄送人的主要活动。 另一种匹配标准是寻找正在前往其他目的地（例如工作场所）的司机。在这种情况下，我们可以评估可能存在的寄送路线和这个司机的路线的匹配程度。众包快递服务Hitch便是这样一个以上班族为潜在寄送人的平台。 然而，它不是根据工作路线来找到最佳的匹配，而是在地图上显示所有投递路线，并要求潜在的寄送人自行选择匹配（Caluzo 2014）。如果我们能根据这些投递路线建议最佳匹配，我们就可以提高众包快递任务的效率，因为这有助于快递员将这些任务整合到他们的日常生活活动中，而不需要额外分配时间给那些随机出现的寄送路线。

到目前为止，关于根据路线来匹配寄送人和寄送物品的研究还很少。拼车系统的概念，即“一种便于司机和乘客共同完成一次出行的自动化系统”（Agatz et al。2012），是一个类似的问题，且已被更广泛地研究（ Masoud和Jayakrishnan 2015）。在拼车系统中，驾驶员的请求和乘坐者的乘车请求需要根据乘车路线和时间限制（即最早出发和最晚到达时间）来匹配。在Agatz等人（2011）的论文里提出，使用最大权二分匹配模型来解决动态拼车问题。虽然他们研究的问题看起来与众包快递问题类似，但他们的解决方案不能直接转移到众包快递问题领域，因为其中对驾驶员的行为的假设在某些方面与物品有所不同。例如，在Agatz等人（2011）的案例中，假定所有乘客都拥有一辆自己的车，这样如果没有合适的拼车对象，这个乘客可以自己完成行程并接送其他乘客。此外，乘车请求被假定为针对工作的乘车，这样的路线的时间可变性小。而物品的寄送与之不同，即使是在当天交货的情况下，物品的时间灵活性也往往要大得多。

在下面的章节中，我们构建了一个匹配寄送人和物品的算法，在这个算法里考虑了众包快递系统中物品不同于乘客的诸多特殊属性。

问题描述和匹配算法

在下文中，我们提出了一个正式的问题描述和一个算法模型，它解决了将寄送请求与寄送人匹配的任务。 此外，我们通过计算一个典型问题实例来说明所提出的算法的有效性。 我们通过解释现有算法可以如何扩展并适应不同的需求来结束本节内容。

问题描述

我们的模型考虑了一组寄送人路线和一组寄送要求。 每次路线始于出发点并结束于目的地，而与请求相对应的每个物品都具有一个取货点和送货点。 路线有最早的出发时间和最晚的到达时间，物品有最早取件时间和最晚的送打时间。 我们在几分钟内测量出两个地点之间的运送距离。 由于寄送者和接收者的分配基于旅行路线，我们需要知道形成和请求的距离和时间来完成匹配过程。 但是，只要行程和请求尚未匹配，这些信息便可以改变。 表1列出了本文其余部分我们将要使用的符号。

表1 符号，定义和描述

考虑到这些信息，我们正在寻找最适合的运输请求分配，也就是寻找一个成本最小的匹配，这个最小成本将在后面用一个由代表行程的nodes和运输需求组成的二分图进一步解释。

算法模型

为了计算我们的二分图的最优匹配，我们构造并求解了最小成本最大流问题。 在一个流网络中，一定流量从一个源顶点s沿着几条边流到一个汇点顶点t。 每条边都有成本，最大容量和流量值。 在最小成本最大流量问题中，我们旨在以最小成本找到最大流量。 我们构造一个有向图?=（?，?），其中：

? = ? cup;R cup; {?, ?}

?={(?,?)isin;?times;?|????_????????(?,?)}cup; {(?,?)|?isin;?}cup;{(?,?)|?isin;?}

我们插入了一个新引入的源顶点?和一个汇点顶点?。 我们将所有旅程和请求都设为节点中，确保任何潜在匹配都是可行的。 然后，我们从源顶点?向所有行程，从所有请求向汇点顶点?引入了边。 为了量化匹配度并为每条边确定一个成本，我们引入一个成本函数Gamma;：?(?) → R:

Gamma;(?,?){???,?? ???,?? ???,?? minus;???,?? , (?,?)isin;?times;?

0, ????

该成本函数计算了寄送人i为执行寄送请求j而需要花费的额外时间。 对于任意从源点或汇点顶点的边，我们将其成本设置为0。我们的目标是找到一组权值低的匹配，即我们认为额外时间少的匹配比额外时间多的匹配更好。该成本函数还可以调整以适用于基于其他因素的匹配，对此我们将在本节结束时给出更详细地解释。 此外，我们给每条边（?，?）isin;?（?）分配一个容量和流量值1。 现在我们可以使用这个模型来发送从源顶点?沿着边到汇点顶点t的流。 由于我们正在寻找最大匹配，我们希望最大化发送到汇点顶点的流量。 统一流量为1可以确保对于每个行程最多只有一个输出边，对于任何请求最多只有一个输入边。

图2展现了我们构建的网络。 边标注指示其对应的成本值，即该特定匹配所需的额外时间。 我们忽略了容量和流量值，以及所有连接到源点或汇点顶点的边的成本值，因为这些值在任何问题中都将保持不变。

图2 最小代价最大流问题

计算样例

接下来我们用一个实例来演示算法的执行。 表2和表3分别列出了在一天开始时已知的虚构的形成和寄送请求。 每个行程和请求都和计算潜在匹配代价所需的信息一起显示，包括：出发/取件时间，到达/交付时间以及开始/目的地位置。 请注意，在现实情况中，形成和寄送请求的列表预计会更长。

您可能感兴趣的文章

• 使用金属伪影减少算法从 CT 数据生成的数字模型的准确性外文翻译资料
• 彩色光流外文翻译资料
• 云环境下基于虚拟机配置文件针对DDOS攻击的最优网络攻击探测方法外文翻译资料
• 监控大视频数据分析中的模糊逻辑: 综述、挑战和研究方向外文翻译资料
• PeopleSoft人力资源管理系统实施外文翻译资料
• 图像绗缝的纹理合成与转移外文翻译资料
• 管理云中的资源:Chrome扩展到OpenStack外文翻译资料
• 一种基于凸显区域检测和SPBVM的美学QR码新算法外文翻译资料
• 微信小程序-所有你需要知道外文翻译资料
• Java核心技术卷II高级特性外文翻译资料