配送过程中提货送货问题的静态动态方法的应用效果研究

发布时间：2018-04-03 00:28

  本文选题：物流　切入点：路由　出处：《哈尔滨工业大学》2016年硕士论文

【摘要】：随着互联网的快速发展,我们步入了一个快速消费的时代。现在互联网越来越普及,更多的消费者通过网络在全球动态市场中购买商品,这就给物流配送公司提出了迫切要求,必须以顾客为中心,及时完成配送。调度问题是许多物流系统面临的重大难题。大量研究一直致力于找到好的方案,进行调度优化。其中最有挑战性的组合优化研究课题之一就是车辆路径问题。车辆路径问题是指有一定数量的、地理位置分散的客户,各自有不同的货物需求,由一个车队负责从配送中心分送货物,组织适当的行车安排,目标是使得顾客的需求得到满足,并保证路程最短。车辆路径问题是配送管理的主要内容之一。尽管大量研究已经对几种类型的车辆路径问题提出了解决方案,但是都是针对一些相对简单的问题采用用精准算法解决。然而,一些近似算法在解决车辆路径问题上显示出了良好的效果。本文是针对动态的取送货路径优化问题进行研究,该问题由于其承诺的可能性,值得更多的关注。物流和快递公司为了使服务更加高效,对取送货路径优化的需求会不断增加。如今,配送系统需要运输要求实时到达,所以需要对如何更好地安排动态需求进行更多研究。动态取送货的例子有:货币收藏、食品饮料配送、银行与自动存款机之间的交付、医疗样本的运输以及最常见的基于互联网的交付等。取送货问题是车辆路径问题的扩展,每一个取送货请求包含两个位置:一个是取货的地点,一个是送货的地点。无论哪一个地点,应该只被访问一次,而且应该先取货后送达各自的货物交付地点。同时也需要考虑车的容量以及可以装载的货物数量。最后的限制条件就是复杂的优化过程。本研究的主要目标之一就是提供一个完整的关于带时间窗的动静态取送货问题的文献综述。第二个目标是对带时间窗取送货问题的解决方法进行大量分析,从而建立模型。本文共包括六个章节。第一章为绪论,概述了研究背景、研究意义、研究问题以及研究目标。第二章分析了不同国家的电子商务现状,电子商务与送货到家服务的现状以及送货到家服务存在的主要问题。本文讨论了物流服务中的配送问题,并提出了前瞻性的解决方案,可以更好地提高配送能力。第三章对车辆路径问题以及分类、带时间窗的取送货问题的相关文献进行了全面深入的回顾分析。第四章是动静态取送货问题的模型的发展。首先,对动静态取送货问题的解决方法进行了分析;然后,提供了方法、模型的选取、模型的描述和计算。第五章提供了实验结果,说明数据收集及分析过程并给出设计以及仿真结果分析。第六章为结论。虽然带时间窗的取送货问题在实际生活中可以被广泛运用,但是对该问题的研究还是相对较少。在运筹学领域,带时间窗的取送货问题给出了正在发展的各种情况。改善目前的算法,对这样复杂的优化问题进行更多的研究是很重要的。在动态车辆路径问题中,当配送车辆已经开始服务后,还会不断接收到新的服务请求。如今,在世界各地的大大小小的城市中,有很多快递公司提供服务,每天完成数百个取送货请求。这些服务请求只有一小部分是提前知道的,大部分是在服务的过程中动态接收到的。之前的研究主要是针对静态车辆问题,即在路径优化之前,知道所有的服务请求。动态取送货问题的布线方法需要对动态显示的信息作出反应。最近几年,很多现代的实时技术被研制出来,例如全球定位系统(gps)、先进的车队管理系统(afms)和智能转换系统(its)。这使得动态车辆路径问题成为一个比较热门的研究领域,虽然这方面的文献还是较少。车辆路径问题是np难题,取送货问题是比车辆路径问题更复杂的np难题。一些研究人员已经研究出了精确的算法,但它们通常只能解决简单的问题。一方面由于取送货问题的复杂性,另一方面由于该问题大量的计算需求,使得这些精确算法不适用。通过分析不同的可以应用于取送货问题的相关方法,本文决定选用元启发式方法。在解决取送货问题上,元启发式算法相对于传统算法更加有效。它是一个结合不同的程序对解空间进行探索以至于找到更好的解。本文提出了在带时间窗的取送货问题上应用元启发式算法的优势。本文将取送货问题转化为整数线性规划模型。整数线性规划模型是一个数学优化方法,它要求变量必须是整数型,目标函数和约束条件是线性的。该模型被应用在不同的情境中,包括时间调度问题。目标函数就是使总的运行距离最小化。为了对提出的模型进行仿真,必须先产生数据集。六种问题分别有不同长度的调度地平线,不同数据类型对地理位置的请求是不同的。为了对取送货的问题进行仿真,本文将位置与解决方案的路线进行随机配对。该模型是以弹射链邻域(ecn)和迭代搜索为框架。具体方法如下:1)一个请求(包括取货和送货两个位置)需要从一个路线移动到另一个路线。2)这导致另一个请求从一个路线移动到另一个路线,等等。3)外链可能包含任何数量的请求,可能是循环的,也可能不是。在这个过程中有一些遵循的基本规则:1)首先,确定取货的最佳插入位置;然后,当取货位置移动后,再确定送货的最佳插入位置。2)在插入取货或送货位置之后,使用目标函数的近似值来预估该位置的调整对成本函数的影响。3)将寻找最佳的插入移动链以超过当前设定的路线的任务,建模为一个最短路径问题,试探性地解决问题。4)在某些情况下,当送货位置不能改变时,新的请求只是简单地被安排在相同的路线上。这是因为对应的取货位置已经被服务过。应该使用适当的更新机制对计划路线进行跟踪,处理动态环境的响应时间必须足够快,而且可以根据新的请求对当前路线进行优化。本文提供了三个实验:场景1,场景2,场景3。场景1的模拟时间是8.5小时,使用20辆车辆,请求到达率不太频繁(平均每小时24次请求)。在场景1中,每辆车平均每小时服务1.2个服务请求。考虑到其中有5分钟的服务时间与每个服务点联系,12分钟用于此目的,所以行程时间是48分钟。在场景1的参数设置的比较宽松,为优化留下空间。相比静态解的问题,旅行时间和距离不会受到影响的附表。场景2将模拟时间设置为4.5小时,车辆从20辆减少到10辆,服务请求到达率保持在每小时28次。模拟结果为每辆车平均每小时服务2.4个服务请求。在更现实的环境中,在应用动态解决方案后,减少了21%的距离和18%的旅行时间。这提供了一个积极的结果。场景3比场景2更加动态,模拟时间是7小时,使用10辆车辆,请求到达率由平均每小时28次上升到平均每小时33次。在场景3中,每辆车平均每小时服务3.3个服务请求。所以一旦服务时间被减掉,每个小时只剩下27分钟可以行使。请求数量的增加对方案质量有显著的影响。几乎总成本的33%都是由于在顾客的位置超时或者迟到。一开始,看起来是每条路线上请求越多,优化机会就越多;然而,我们忽略了在事件发生之间缺乏计算时间。当获得更多的计算时间时,本文的算法是有效的。本文已证明禁忌搜索启发式算法可以应对复杂的动态环境,例如同城的取送货服务。当有足够的计算能力时,该算法优化了简单启发式算法的结果(即使是对已知请求的优化)。本文的主要结论是:1)静态取送货问题可以用动态的方法来解决,即静动态取送货问题的推广。2)禁忌搜索的启发式算法可以应付复杂的动态环境,例如,在本地的取货和送货服务。3)取得的结果,20%大于通过静态算法实现。因此,通过应用适于动态问题的方法,可以实现大规模静态问题的合理解决方案。本文的算法还存在以下不足:1)不能将车辆从当前位置转移到附近位置来服务一个新的请求,这是因为派遣中心与司机的沟通只在服务地点进行。所以,可以考虑对该方法进行改进,使得车辆在行驶过程中也可与派遣中心进行联系。2)该算法没有考虑意外事故的情况(例如,车辆发生故障)。
[Abstract]:With the rapid development of Internet , we have entered a era of rapid consumption . Now the Internet is becoming more and more popular , more consumers buy goods in the global dynamic market through the network . In recent years , many modern real - time technologies have been developed , such as global positioning system ( gps ) , advanced fleet management system ( afms ) and intelligent conversion system . The new request is simply arranged on the same route . This is because the corresponding pick - up location has been serviced . The response time for the dynamic environment must be fast enough to track the planned route using an appropriate update mechanism . This provides a positive result . In Scenario 1 , the travel time and distance will not be affected . In Scenario 3 , the algorithm optimizes the results of a simple heuristic algorithm ( even for known requests ) . In scenario 3 , the algorithm optimizes the results of simple heuristic algorithms ( even for known requests ) . The vehicle has failed ) .

【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：F724.6;F252
，

本文编号：1702825