【作者】 张志杰；

【导师】 胡劲松； 邓健爽；

【作者基本信息】 华南理工大学 ， 计算机技术（专业学位）， 2020， 硕士

【摘要】 近年来,随着网购的兴起,电子商务和快递物流产业得到了迅猛的发展,而“最后一公里”作为物流配送末端环节,是一个通过快递员将快递件从配送站派送到客户手中的过程,其效率的瓶颈关键在于快递员调度的合理性。在实际场景中,庞大快递量的配送往往需要多名快递员协助完成,对快递员们的不合理调度会造成快递员之间配送路程的不均衡现象,这种现象直接导致客户之间等待时间和快递员之间工作量的差距过大,既影响了客户对企业服务的好感度,又造成了人力资源的不充分利用。基于上述场景分析,本文在研究如何合理调度快递员去提高物流配送效率这一实际工程问题上,要求在最小化快递员们配送总路程的基础上,也要考虑快递员之间配送路程的均衡性。本文将上述快递员调度问题抽象成基于多目标优化的多旅行商问题进行解决,其难点主要在于:其一,旅行商问题是典型的NP-hard问题,作为其扩展问题,多旅行商问题的研究难度又有所增加,在此基础上,与多目标优化问题的结合更是让问题难度提升了一个层次;其二,目前解决上述问题模型的相关研究极少,常用的启发式搜索算法由于其启发式信息不涉及路程的均衡性,无法很好地解决问题模型。本文通过蚁群算法的大量实验对上述难点进行验证分析,并为蚁群算法更好地解决问题模型提供改进方向。本文提出一种新颖的蚁群算法——回跳重组蚁群算法,去更好地解决快递员调度问题。该算法的改进点主要在于:对蚂蚁搜索实施回跳约束策略,根据假设性的子路径长度大小对蚂蚁移动方向进行约束,从而限制了子路径的长度;应用栈式可行解重组策略,对最长子路径和最短子路径进行中和重组,保证快递员之间配送路程的均衡性;利用阶段式信息素更新策略,在蚂蚁搜索的不同阶段采用针对性的信息素更新规则,提高蚂蚁的搜索质量。通过实验数据得出,三种改进策略有效地提升了蚁群算法在两个优化目标上的表现。根据小区的分布特点,本文模拟了电商物流“最后一公里”的配送点位置分布情况,并产生若干组测试样本。通过本文提出的回跳重组蚁群算法与遗传算法、差分进化算法、局部搜索算法以及模拟退火算法进行对比实验,结果显示回跳重组蚁群算法能够搜索出更优的解决方案去满足电商物流“最后一公里”中快递员调度问题的工程需求。更多还原

【Abstract】 In recent years,with the rise of online shopping,e-commerce and express logistics industry have developed rapidly."First-last Mile" as the end of logistics distribution is a process in which the couriers deliver items from distribution station to the customers,and the key to its efficiency lies in the rationality of courier scheduling.In actual scenarios,the delivery of many items often requires the assistance of multiple couriers.Unreasonable scheduling of couriers will cause an imbalance in the delivery distance between couriers.This imbalance will lead to the great gap between the waiting time of customers and the work load of couriers,which not only affects the preference for the enterprise service of customers,but also makes rest use of human cost.According to the above analysis,this paper requires to consider the balance of delivery distance between couriers based on minimizing the total delivery distance of couriers on the practical engineering problem of how to reasonably manage couriers to improve logistics distribution efficiency.This paper abstracts the above courier scheduling problem into a multiple traveling salesman problem based on multiple objective optimization.The main difficulties are as follows: Firstly,the traveling salesman problem is a typical NP-hard problem.The multiple traveling salesman problem is its expansion problem,the research difficulty of which has increased.On this basis,the combination with the multiple objective optimization problem has raised the difficulty of the problem to a higher level.Secondly,there are very few related studies to solve the above problem model,and the common algorithms based on heuristic search perform not well,because its heuristic information does not include the balance of delivery distance between couriers.In this paper,through a large number of experiments using ant colony algorithm,the above difficulties are verified and analyzed,and the improvement direction is provided for the ant colony algorithm to better solve the problem model.This paper proposes a novel ant colony algorithm—ant system with back-to-depot and path-reform behavior to better solve the courier scheduling problem.The improvement points of this algorithm are as follows: Firstly,the back-to-depot constraint strategy is applied to ant search,which limits the sub-path length by constraining the direction of ant movement according to the hypothetical sub-path length.Secondly,the stacked path-reform strategy is used to ensure the balance of the delivery distance between the couriers by neutralizing the longest sub-path and the shortest sub-path.Thirdly,the staged pheromone-update strategy is used to improve the quality of ant search by using the targeted pheromone update rules at different stages of ant search.According to the experimental data,the three improvedstrategies have effectively improved the performance of the ant colony algorithm on the two optimization objectives.According to the distribution characteristics of the community,the distribution position of the "First-last Mile" of e-commerce logistics was simulated,and several test samples were generated.The ant system with back-to-depot and path-reform behavior proposed in this paper,genetic algorithm,differential evolution algorithm,local search algorithm and simulated annealing algorithm were used in comparative experiments and the results show that the ant system with back-to-depot and path-reform behavior can search for a better solution to meet the engineering needs of courier scheduling problems in the "First-last Mile" of e-commerce logistics.更多还原