英语原文共 20 页，剩余内容已隐藏，支付完成后下载完整资料
附录1 译文
现代物流末端快递中心任务分配方案设计与分析
摘要：随着人工智能技术的兴起与发展，快递行业也呈现出智能化发展的趋势。在现代物流的末端，每个快递中心每天都有数百件快递在等待派送，但是快递员的数量却远远少于待派送快件的数量。本文的主要研究目标是如何科学有效的为派送员分配每天的派送任务，能够让各个快递员之间的派送任务在每个周期内大致相同，从而使快递员之间的收入更加平衡。在仿真实验中，首先根据平衡k-means聚类算法对派送地址进行聚类，其次使用蚁群算法来计划每个类别中快递物品的交货顺序，然后根据各类快递商品的配送距离和配送方式建立时间成本模型，计算配送时间成本。通过对大量实验数据的分析发现，各快递公司交货时间成本的标准偏差逐渐减小并趋于稳定，这表明本方法对快递中心的任务分配具有良好的影响。本方法能够为快递员之间安排大致相同的工作量，能有效的提高快递员送货效率、节约能源、促进可持续发展。
关键词：快递中心；任务分配；调度；时间成本；
1.引言
随着在线购物的兴起和发展，人们的消费方式发生了很大变化。越来越多的人选择在线购物，这种消费方式极大地促进了快递行业的发展。作者经过调查以后了解到，在快递到达收货地址之前，它会被运送到社区快递中心，然后被分配给特定的快递员进行送货。快递中心每天需要派送的快递要比快递员多得多，如何将这些派送任务分配给快递员，以使快递员之间的工作量更加平衡已成为一个问题。工作量的多少将会直接影响快递员的薪水，如果快递员的工作量不同，他们的薪水也会不同。另外，实际上，如果工作量较多的员工获得的薪水较低，而工作量更少的员工获得的薪水较高的话，就会很不利于快递公司的发展。因此，如何合理分配快递员的工作量已成为非常重要和现实的目标。
目前，快递中心将需要在同一天派送的快递分配给每个快递员，通常是根据他们的经验进行分配，这就容易导致分配的任务不平衡，而任务分配的不平衡通常会影响快递员的工资分配。本文的目的就是研究一套针对快递中心关于快递员的工作任务分配方法，帮助快递中心恰当地分配每个快递员的工作，以解决快递中心之前不均衡分配快递员派送任务的问题。
首先，采用平衡k-means聚类算法[1]对交货地址进行聚类[2]，然后采用蚁群算法确定各类货物的交货顺序，最后得到每个类别的交货路线和交货方式。在第一天，根据每个类别的时间成本，将其从低到高分配给快递员，并对快递员的累计时间成本从高到低进行排序；在第二天，再将每个类别的时间成本从低到高分配给了快递员，该累计器累积了时间从高到低的累计成本。大量的实验数据表明，该方法对快递中心分配快递员工作量有很好的效果[3-5]，可以有效的解决快递中心对快递员任务分配不平衡的问题，帮助快递中心更合理地分配派送任务。因此，有效分配每个快递员的工作量，不仅能增加快递员工作收入，还可以提高快递中心的交付效率，促进快递公司的发展[6,7]。
本文的其余部分安排如下：第二部分介绍了本文的研究进展，阐述了蚁群算法和遗传算法在路径规划中的应用，介绍了快递行业的驱动因素和未来前景，分析了各种任务分配方法并进行比较，同时也介绍了各种聚类算法；第三部分首先介绍了k-means聚类算法和平衡k-means聚类算法的原理及在本文中的应用，然后介绍了蚁群算法的原理和步骤，最后，基于本文的研究背景，建立了快递的时间成本模型；第四部分进行了模拟实验，通过使用平衡k-means聚类算法、蚁群算法和时间成本模型，得出各快递员在一段时间内的累计交货时间成本的标准差，分析证明本文构造的任务分配方法的可行性。
2.相关文章
Russell G. Thompson[8,9]在研究最佳配送路线时考虑了驾驶和步行的成本，基于此提出了一个两层优化模型。该模型通过遗传算法搜索最优解，同时生成行驶调度路线和行人配送路线，为快递配送提出了一种简单、可行的方法。
Tsung-Sheng Chang[10]提出了一种创新的路线调度策略，以帮助城市快递中心降低运营成本并提高服务水平。这种调度策略通过分析城市街道网络的特征，将城市路线调度视为一个静态问题，来专门研究固定服务位置和时间。
Raphaeuml;lle Ducret[11-13]以法国为例，研究了欧洲快递业的变化和挑战，分析了快递业的驱动因素，并强调了快递业这一新领域的未来前景。
A.V. Hill[14]研究了用于快速调度车辆的决策支持系统，该系统有助于正确确定车辆数量，收集适当的路线和路线行驶时间。该系统已在一些公司实施，证明了其实际应用价值。
Felipe Balmaceda[15,16]研究了一种具有避免损失因子的最佳任务分配方法。该方法通过避免损失因子将一项任务的边际成本与其他任务中选择的工作量的增加相结合，以确定补偿成本。
赖奇明[18]使用熵简化组优化算法研究任务分配问题，该算法使用熵来描述分配任务的不确定性水平，使不确定性较高的任务有更多的机会可以重新分配。
G. Melendez-Melendez[19]提出了一种改进的部分聚类算法，研究发现离群值检测对于改善聚类结果非常重要，例如异常值的过度检测会导致信息丢失。
张庚[21]提出了一种基于密度冠层的改进的k-means聚类算法，提高了k-means聚类算法的准确性和稳定性，解决了确定最合适的簇数K和最优初始种子的问题。
Keivan Bamdad[22]提出了一种使用蚁群算法的连续域蚁群优化方案，以解决能源优化问题。
Mohamed MS Abdulkader[23]使用混合蚁群算法研究了多车辆的路径问题，并根据实验数值评估了算法的性能。作者将本地搜索与现有的蚁群算法结合起来，用其与现有的蚁群算法进行了比较。实验结果表明，混合蚁群算法可以提高算法的性能。
李永波[24]提出了一种多目标线性数学模型，该模型通过使用蚁群算法，研究基于收益最大化和成本最小化的多目标车辆路径问题，从而解决目标冲突问题。
Saeed Rubaiee[25]提出了一种能量感知的多目标蚁群算法，以最大程度地减少调度的完成时间和成本。
Raka Jovanovic[26]提出了一种针对起重块定位问题的蚁群优化算法，这种新的启发式方法，被其定义为贪婪算法。该算法既不受限制，又能适用于不同的期限约束。
Nikolaos D. Doulamis[27]提出了一种将任务分配给资源的算法，该算法可最大程度地减少违反任务时间要求的情况，同时最大程度地提高给定数量资源的资源利用率。经过实验结果表明，在不同的粒度值和任务请求负载下，该算法的调度性能优于其他算法。
通过参考以上的文献，作者了解到平衡k-means聚类算法在聚类中很容易实现，并且聚类效果非常好。因此，本文采用平衡k-means聚类算法对需要发送的快递物品按照收货地址进行聚类，其中K值是快递员的数量。
当快递员递送快递时，必须遍历所有的递送地址，从本质上讲，这可以看作是旅行社的问题。在阅读相关参考文献之后，作者了解到蚁群算法在解决TSP（旅行商问题）方面具有很强的全局搜索能力，因此本文采用蚁群算法来解决快递交货单问题。
3.算法介绍
3.1.k-means聚类算法和平衡k-means聚类算法简介
k-means聚类算法[28-31]在数据聚类中具有很高的效率[32]，因此，该算法可以对快递中心的待派送快件地址进行聚类。
k-means聚类算法是一种非常常见的聚类方法[33,34]。在其聚类时，时间复杂度仅为O（tkn），其中t是算法的迭代次数，k是算法中所需的簇数，n是算法中的数据总量。在后面的仿真实验中，t是算法操作的迭代次数，直到计算出最优解为止。这个实验的价值是1000，k是可以在同一天派送快递的快递员数量，n是交货中心当天需要发送的货物的数量[35]。
k-means聚类算法首先需要随机选择K个对象作为初始聚类中心，然后计算每个对象与每个种子群集中心之间的距离，并将每个对象分配给最接近它的群集中心，而群集中心和分配给它们的对象就代表一个聚类。分配完所有对象后，将根据群集中现有的对象重新计算每个群集的群集中心。该过程将继续重复，直到满足终止条件时停止，终止条件可能是没有（或最少数量的）对象被重新分配给不同的群集，没有（或最少数量的）群集中心被重新改变。
k-means聚类算法的目标是将n个数据点划分为k个聚类，然后找到每个聚类的中心，并使聚类中的点尽可能地聚集在一起。假设将群集分为C1, C2,, ..., Ck，算法的目标是使平方误差E最小化，平方误差E的数学表达式为：
其中micro;i是簇Ci的均值矢量，也称为簇Ci的质心，其数学表达式为：
根据以上公式，可以知道k-means聚类算法是要解决NP-hard（非确定性多项式）问题，但是直接解决这种问题是不可能的，因为这种问题只能通过启发式迭代方法解决。
在平面上对坐标点进行聚类时，最常用的优化标准是均方误差（MSE）：
其中Xi是数据点位置，Cj是质心位置。
k-means聚类算法具有两个基本操作：分配和更新。
分配是将要处理的数据点放入最近的质心相关簇，表达式如下：
更新操作是计算并更新每个聚类的平均值，表达式为：
平衡k-means聚类算法[36]的分配操作是基于k-means聚类算法构造了权重函数，目的是使成本函数最小化[37]，其数学表达式为：
平衡k-means聚类算法的更新操作与k-means聚类算法的更新操作相似，表达式为：
边缘的权重构造公式为：
算法收敛后，Xi点的分区标准为：
3.2求解TSP问题的蚁群算法
蚁群算法[38-43]用于求解每个群集中的装运顺序并得到调度最短路径。
蚁群算法求解最优路径的步骤如下：
步骤1：初始化相关参数，包括蚁群大小、信息素因子、启发式功能因子、信息素挥发性因子、信息素常数、最大迭代次数等，并将参数读入程序进行预处理。
步骤2：将蚂蚁随机放置在不同的起点，并为每只蚂蚁计算下一个要访问的城市，直到所有城市都有蚂蚁进入。
步骤3：设每只蚂蚁的路径长度为Lk，记录当前迭代次数的最优解，并更新路径上的信息素浓度。
步骤4：确定是否达到最大迭代次数。如果不是，返回步骤2，否则结束该过程。
步骤5：输出结果，并根据需要输出优化过程中的相关指标，例如运行时间、收敛迭代和最短距离。
在解决旅行推销员问题（TSP）[44,45]时，蚁群算法应给出两个不同城市之间的距离，并最终找到通过每个城市的最短路径。以下为实验过程：
第一步：初始化。蚂蚁被随机安置在n个城市中，每个蚂蚁的禁忌都是该蚂蚁当前所在的城市，并且每条边信息都初始化为c。实验通过禁忌表反映蚂蚁的记忆，确保蚂蚁不会走重复的道路。
第二步：构造路径。在时间t内，蚂蚁k从城市i移至城市j的概率为：
其中Tabuk是每个蚂蚁k曾经去过的城市的集合，Jk ={N-Tabuk}；alpha;，beta;为系统参数，分别代表信息素和距离对蚂蚁路径选择的影响程度；tau;(i，j)表示边缘L(i，j)上的信息素浓度；phi;(i，j）表示可以根据城市i对城市j的预期程度来确定。
信息启发因子alpha;越大，蚂蚁选择的可能性就越大，搜索路径的随机性越小；alpha;越小，蚁群的搜索范围将越小，容易使算法陷入局部优化。当alpha;=0时，该算法演变为传统的随机贪婪算法，并且最近的城市被选中的可能性最高，预期启发式因子越大，蚁群算法就越容易选择局部较短的路径，这时，算法的收敛速度加快，但随机性减弱，容易获得局部相对最优。当beta;=0时，蚂蚁根据信息素的浓度完全确定路径，该算法将快速收敛，因此所构建的路径与实际目标相距甚远。大量实验表明，将alpha;=1~2和beta;=2~5设置更为合适。
第三步：更新信息素。在所有蚂蚁都找到合法路径之后，信息素就会更新（蚂蚁周模型）：
其中rho;是信息素的挥发性因子，其值通常小于1个正数0.5，一方面是为了防止信息素的无限积累，另一方面是为了寻求更可行的求解方法来改进系统搜索能力，以避免早期发现新路径的能力丧失。由于信息素的挥发性因子太小，每条路径上留下的信息素过多，容易导致搜索无效路径，并且影响算法的收敛速度。但是，如果信息素的波动因子太大，则可以从搜索中排除无效路径，但不能保证不会从搜索中遗弃有效路径，因此，这会影响对最佳值的搜索。此外，m表示
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[409983]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
