英语原文共 15 页
为提高“最后一公里”配送效率：一个有效的具有可伸缩性解决方案的群体任务模型
作者：Yuan Wang , Dongxiang Zhang , Qing Liu , Fumin Shen , Loo Hay Lee
摘要
随着电子商务的不断发展，城市物流中从仓库到消费者家中的最后一英里的配送变得越来越具有挑战性。它需要周密的计划和日程安排，以最大限度地降低全球配送成本，但往往因为大多数消费者不在家而导致配送无法完成。本文提出了一种有效的大规模移动群体任务模型，该模型使用大量的市民配送员进行最后一英里的配送。为了有效地求解这个模型，我们将其描述为一个网络最小成本流问题，并提出了各种可以显著地减小网络规模的剪枝策略。针对新加坡和北京的数据进行了综合实验。结果表明，我们的解决方案能够使大规模移动众包问题中的实时配送优化。
- 序言
通过铁路网和集装箱运货船进行货物运输被认为是城市物流中最具成本效益的方式。然而，当货物的仓库容量过高时，必须及时将货物运往最终的目的地。供应链的最后一个环节效率比较低，而且占总成本的28%。更糟糕的是，大多数消费者在送货时都不在场。未完成签收的包裹可能需要进行多次配送，已经成为了物流公司的一个重要问题。
为了缓解这种状况，新加坡邮政等一些物流公司提出了包裹自提的概念。这个概念指的就是直接将包裹送到自提站。然后，消费者将收到通知，并通过移动应用程序收取他们自己的包裹。如果包裹在5天后仍未签收，将视为交货失败。为了确保这种模式的正常应用，需要投入很高的基础设施成本建设大量的自提站。以便照顾到城市不同地区的居民，并尽量缩短他们收取包裹的距离。但是，该模式还没有很好地解决缩短快递中的包裹周转时间的问题，例如许多包裹可能会在自提柜里放好几天。
本文研究了如何利用群众配送员的力量来提高最后一公里配送的效率。特别的是，我们将每个包裹从自提柜送到消费者手里的配送工作视为一个群体任务。根据配送员的历史轨迹模式产生的行程费用，会给予他们一定数量的金钱奖励。我们会把包裹分配给最合适的配送员，以尽量减少物流公司支付的总报酬。基本原则与其他共享经济应用程序类似，都是要最大限度地利用资源（此应用程序中的群众配送员）。由于大量的市民群众配送员可以参与到这个工作中，而且群众交付模式比自提模式需要的自提站数量少得多，因此可以减少基础设施建设的费用。此外，包裹的周转时间和故障率都可以大大降低，因为人群工作人员更积极地收集包裹并将它们送到消费者手中。除此之外，群众配送员更加积极地收集包裹并将其交付给消费者，使得包裹的周转时间和交付失败率都可以显著地减少。
在城市生活中会有大量的包裹和工人，因此我们的群体配送模型本质上是一个大规模的任务优化问题。我们的解决方案是将其建模为网络最小成本流问题，并将其用作绩效评估的基准。然后，我们提出了各种有效的剪枝策略，可以显著地减小网络规模。对比新加坡和北京的数据进行了综合实验。结果表明，在网络规模缩减后，性能提高了2-3个数量级。在不到10秒的时间内，就可以找到2000个包裹的最佳分配方案，将其分配给50万名群众配送员。
综上所述，本文的贡献主要包括：
我们提出了一个有趣的人群物流优化问题，它利用大量的公民工人来完成最后一英里的传递。我们正式地证明了所提出的模型是等价的。针对网络最小成本流问题.我们提出了三种类型的剪枝规则，可以显着地减少网络规模，从而提高性能。我们进行全面的经验利用新加坡和北京的数据集验证了我们提出的方法的有效性。
论文的剩下部分的内容如下。在第二章我们主要描述了问题的定义，并在第三章呈现了相关的文献。在第四节中，这个问题被正式地归结为一个最小的成本流问题。在第四章我们正式开始将这个问题简化为最小成本流问题。在第五章中我们提出了各种修剪技术，以有效减小网络规模。我们在第六章中进行了广泛的性能研究，以评估我们提出的解决方案的性能。 第七章主要是论文的总结和展望。
-
问题定义
- 研究背景
针对群体配送模型，在城市和许多愿意接受从自提站到顾客家中的配送任务的工人周围分布着大量的自提站。如图1所示，根据自提站的位置我们可以将城市划分成沃罗诺伊区域。物流公司只需把重点放在配送包裹的调度优化上。直观的说，每个包裹都将根据消费者的地址被发送到离他最近的自提站。换句话说，最终交货地址和相关的自提站将位于同一个Voronoi区域内。此后，自提站的包裹将分配给群众配送员，并最终到达消费者手中。
当配送员通过移动应用程序接受任务时（类似于Uber司机接受骑乘请求），他/她可以使用一次性密码从自提站取出包裹。然后，系统会通知消费者包裹已被取走，并开始跟踪配送员的实时位置。当包裹安全签收时，消费者将会发送确认消息以完成此收货。为了提高系统的可靠性和服务质量，会验证配送员的身份，这种操作在Uber和GrabTaxi等应用程序中是很常见的。
我们还了解到，Uberrush也提供包裹递送服务，他们的司机作为配送员。主要区别在于，Uberrush处理按需配送请求并将其发送给附近的司机。它这个属于一次性的流程，没有复杂的优化问题。相反的，我们更关注最后一英里的配送，以提高整个供应链的效率。我们的方法是利用群众配送员，以任何可能的运输方式完成最后一段交货。换句话说，我们把交通工具视为一个黑匣子，这些群众配送员可以步行、乘公共汽车/火车或开车来完成运送任务。
如图2所示，与传统的协作或同步方法相比，我们的系统从以下角度展示了其优越性。
- 平行性。很明显，群体配送模型中可用的工人数量远远高于同步配送模型中的配送车辆的数量，从而在作业执行中产生更高的并行性。尽管协作模型可以提高资源利用率，但每辆车每天仍要处理大量包裹，这需要精心的规划。
- 交流。在我们的模型中，每个工作人员只处理少量的包裹，配送员和收件人之间的交流将会更为有效。即使在收件人不在时包裹无人接收，这种情况对后续交付的影响也会最小化。相反，当这种情况发生在同步配送中时，同一车辆的所有后续配送都可能会延迟。
-
生态友好。生态友好。我们的群体配送模型被认为是更环保的，因为它可以帮助降低运营成本和碳排放。对城市传统物流的影响可能类似于Uber对传统出租车行业的影响。
- 模型与目标函数
直观地说，包裹应该通过将额外配送量最小化的方式分配给配送员。例如，假设Alice是一家购物中心的职员，她住在安徒生街。如果在同一个购物中心的一个自提站有一个包裹要送到住在安徒生街街，那么Alice就是一个很好的人选来承担这项任务。基于这一标准，我们采用以下简化假设建立了群体配送模型：
- 每个配送员都与一个以A→B形式展现的移动模型相关联。以爱丽丝为例，她的移动模型是“购物中心→安徒生街”。
- 配送包裹的报酬取决于对配送员的额外配送量。为了简单起见，我们通过使用额外的行程距离作为估计。例如，当一个包裹由配送员以移动模型A→B的方式从自提站送到目的地时，，她的成本是通过额外的行程距离来衡量的：
（1）
其中这里两个地点之间的距离指的是欧氏距离，是在配送中产生的距离，d(A,B)指的是配送员未接受任务时的行程距离。
- 为了简单起见，我们假设不同包裹的配送是独立的。然后，配送员的总报酬额是每次配送成本的总和。
- 我们假设每个配送员都有一个送货能力C，以确定他/她可以运送的最大包裹数量。
- 模型中没有考虑到消费者的时间约束。我们简单地假设配送时间是消费者和指定的工作人员协商好了的。
通过这些简化的假设，我们可以建立一个大规模的群体配送模型，该模型可以用可行的计算量来求解。我们的目标是用最低的费用将所有包裹分配给最合适的配送人员。
设表示包裹被分配给了配送员，则表示相反的情况。因此，我们的目标函数为：
（2）
约束条件是：
约束条件(3)限制分配给配送员的包裹数量不得大于C。约束条件(4)意味着每个包裹必须分配给一名配送员。
在现实中，群体配送系统往往要复杂得多。例如，当一个配送员拒绝接收指定的任务时，系统需要找到另一个替代者或提供更高的价格。在任务被最终分配之前，此过程可能需要与配送员进行多轮沟通。其他具有挑战性问题还包括更好的定价策略和系统服务得可靠性。针对基于人群的最后一英里配送，这些问题都是值得被关注的。本文我们主要做的工作可以看作是用简化假设来建立模型的初步工作。通过求解模型，每个包裹都能得到一个很好的分配。这些任务可以通过后续的优化步骤进一步细化，这些工作我们将在未来进行进一步研究。
- 相关研究
在本章中，我们对最后一英里配送和移动众包的相关文献进行了回顾。
-
- 最后一英里配送
近年来，为了提高最后一英里运输的效率，已经做出了一些努力。我们将应用策略归纳为两大类。在第一类中，采用了类似于自提站的概念。它能有效地解决在送货过程中消费者不在家时无人签收包裹的头疼问题。这些包裹存放在有各种大小储物柜的自提站。然后通知消费者使用一次性密码自行收取包裹。例如，在Dellamico和Hadjidimitriou（2012）中，模块化BentoBox系统（M-BBX）建议将货物存放在BentoBox，在客户提货之前将货物存放在那里。DHL和奥地利邮政等物流运营商也采用了这一理念，并分别介绍了PackStation系统和Post.24包装机。
在第二类中，通过更好地整合和同步现有资源来提高效率。其主要思想是通过多家物流公司共享配送工具和员工来提高资源利用率。这类似于不同航空公司之间为减少运营费用而采用的代码分享协议。在DeSouza(2014年)等人的研究中，作者提出了协同城市物流的概念，从新加坡物流的角度强调了多方协作。他们的目标是扩大和优化各方的资源整合，并通过更好的资源协调和数据协调来加强自身的市场地位。在Liakos和Delis（2015年）的研究中，作者提出了一种互动式货运联营服务模式，可以减少城市地区的不良影响和货运成本。所应用的优化模型类似于车辆路径问题(Dantzig和Ramser，1959年)，其目标是使多个托运人的供应链同步，并使用更少的资源运送相同数量的货物。在Petrovic(2013年)等人的文章中，作者研究了如何通过允许接受者使用智能手机向物流供应商开放通信渠道来克服通信障碍。在Handoko(2014)等人的研究中。最后一英里的交付任务外包给城市整合中心，并提出了一个利润最大化拍卖机制，以确定哪些需求将得到满足。
-
- 移动众包
近年来，由于智能手机的起源和区域的服务的蓬勃发展，移动众包已成为各个任务领域的热门研究课题。当将众包与移动设备相结合时，出现了许多有趣的应用程序。例如，GeoCrowd(Kazemi和Shahabi，2012年)为每个工人分配了附近的任务。目标是最大限度地增加已分配任务的总数，因为每个任务都作为一个工作被分配，所有的约束条件都必须得到满足。提出了三种贪婪启发式方法来解决优化问题。
在Su（2014）和Zhang等人（2014年）的研究中，提出了建议出行路径采用人群工作方式。研究的挑战在于如何有效地总结全体员工的反馈意见，并提出建设性的建议。提出了一种基于熵的度量方法来获取路径选择的难易程度，并将其转化为基于新度量的优化问题。在Cheng等人（2015年）的文章中，研究了一个有趣的问题，他们将来自不同人群的片段拼凑成一个完整的故事。像Crowdsc（Benouaret等人，2013年）和gmension（Chen等人，2014b）等系统的开发旨在建设具有大规模公民参与的智能城市。Ilarri等人（2014）综述了城市交通协同传感领域（如停车位、交通和轨道）的研究现状。Pournajaf(2014年)等人讨论了如何保护员工隐私的问题。与我们的群体配送模型最相关的工作是Chen（2014年）等人研究的Traccs系统。群体任务平台为每个工人分配一系列任务，同时会考虑到他们的轨迹路线。它将任务分配定义为一个优化问题，目的是最大化所有分配任务的总回报。提出了一种整数线性规划模型，该模型能很好地处理小尺度问题。为了提高效率，提出了无理论保证的贪婪启发式方法。它的实验研究只评估1000种左右的药剂。相比之下，我们的群体配送平台需要一个能够处理百万规模员工的解决方案，以实现盈利，因为更多的群组员工可以帮助降低每个任务的价格。
- 最小成本流模型
在本章中，我们将所提出的群体任务模型的优化设计为最小成本流问题。表1列出了本文常用的符号，供参考。
-
- 背景
最小成本流模型是网络流领域的一个基本问题(Ahuja等人，1993年)。给出一个有向图，其中每个弧与容量Ue和单位运输成本Ce相关。此外，每个节点V都有一个表示其供应/需求的数字。如果gt; 0，则节点v为剩余节点；如果lt; 0，则节点v为需求值是的需求节点；如果= 0，则节点v称为转运节点。要求供需之间平衡，即。
设N （v）表示v的外邻域，N-（v）表示v的邻域，v表示v的内邻域。最小成本流问题考虑的是如何以最便宜的方式从供应节点中获取需求节点。该问题的决策变量为弧流，用fe表示。然后，将问题转化为具体目标的优化问题：
（5）
约束条件：
图3描述了一个玩具例子的最小成本流问题。图中有5个节点和8个弧。在节点中，V1是一个多余的节
资料编号：[5152]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
