Exploiting Symmetries in Logistics Distribution Planning
L. Marsh a and D. Gossink a
Abstract:
Logistics distribution and movements planning involves developing an efficient plan to move all of the required supplies, equipment and personnel to desired locations in a timely manner. It is an inherently difficult problem to solve and given the complexity of the problem, scenarios of a realistic size can take a significant amount of time to compute.
A greedy distribution algorithm has been created for the task of developing transport schedules to satisfy the movement requirements. At each phase of the simulation the algorithm assigns the most capable transport to deliver the highest priority resources. Although it is observed that the distribution algorithm performs faster than exact algorithms based on integer programming or brute force, even greedy based approaches can have performance issues as the scenario size increases.
In this paper, a technique is examined which exploits redundancies garnered due to symmetries in the distribution model to improve performance of the distribution algorithm. A key redundancy in the model occurs when there are multiple similar transports at the same location. By performing one calculation for all transports of a similar type at the same location, it is suspected that computational savings could be made. Given that many of the distribution scenarios are complex, many of the transports are not always at the exact location as each other. One way to increase the effectiveness of the symmetry exploitation is to perform only one calculation for all transports of a similar type within a certain range. However, there is a side effect to increasing the range value, and that is it introduces an error in the planning calculation. Part of the analysis to be explored through simulation is what an effective range is, given that the larger the range the greater the computational savings but also the greater the error is introduced into the distribution plan.
Simulations were run testing the performance of the distribution algorithm with and without utilising the symmetries with varying range values to minimize the distribution model. It is shown empirically that by exploiting the symmetries in the distribution model, for the scenarios tested computation time could be reduced on average by approximately 24-45%, while the efficiency of the distribution plan is only reduced by approximately 0.3-18% due to introduced error.
Keywords: Logistics distribution, movements planning, model minimization
1 INTRODUCTION
Logistics distribution and movements planning involves developing an efficient plan to move all of the required supplies, equipment and personnel to desired locations in a timely manner (Perugini, 2006). It is an inherently difficult problem to solve, and is suspected to be NP-Hard (Cook, 1971). Given the complexity of the problem, scenarios of a realistic size can take a significant amount of time to compute.
A greedy distribution algorithm (Cormen et al., 1990) has been created which develops a schedule for each transport in the scenario, to satisfy all of the required movements and complete the distribution. It aims to complete all movements as quickly as possible by greedily assigning the most capable transports to the highest priority items to move. An overview of the algorithm is outlined in Section 3. For this distribution problem, even greedy based approaches can have performance issues as the scenario size increases. It is suspected that improvements to the greedy distribution algorithm developed could be made.
A technique that exploits redundancies (Ravindran and Barto, 2001) which occur due to symmetries in the distribution model to improve performance of the distribution algorithm is examined in Section 4. Finally, Section 5 outlines the simulations which were run in order to test the performance of the distribution algorithm with and without utilizing the symmetries to minimize the distribution model.
2. OVERVIEW OF THE DISTRIBUTION PROBLEM
The distribution and movements planning domain which is the focus of this paper incorporates many transport platforms covering land, sea, air and rail with a goal of delivering supplies to a destination from a source location. The supplies, equipment and people can be sourced from many locations, and similarly need to be transported to possibly many locations. Immediately it can be seen that the solution space can expand rapidly, as the number of transports, routes, base locations and requirements of supply increases. Additionally there are business rules, constraints and complexities inherent in this distribution domain, which need to be satisfied when developing a plan.
The set of complexities inherent to the distribution domain include: multiple source locations; multiple destination locations; multiple route types (land, sea, air, rail); directed routes; multiple routes to destination, intermediary locations to destination; known as “transshipment”; multiple transport trips via lsquo;drop and swaprsquo;; many types of transports, multiple supply types to be moved, transports can carry many types of supply at once; and many trips may be performed if needed to transport item from the source to destination.
The set of constraints inherent in this distribution problem include: The minimum runway length required for aircraft; minimum runway classification required for aircraft, known as “pavement classification number”; transport speed; transport range; transport personnel capacity; transport cargo capacity; and transport loading/unloading times. If in the scenario there is no route to the destination, or due to the constraints or specifications on the transports there are no possible options for distri
剩余内容已隐藏，支付完成后下载完整资料
将对称性利用到物流配送规划中
文章摘要：
物流配送和行动规划涉及到开发一个有效的计划将必需的所有用品,及时所需的区域设备及人员。本质上这是一个困难的问题解决,考虑到问题的复杂性,一个逼真的情景需要花费大量的时间来计算。
创建了一个贪婪的分布算法发展运输任务的时间表,以满足运动要求。在每个阶段的仿真算法分配最有能力的运输交付最高优先级的资源。虽然观察到分布算法执行速度比基于整数规划的精确算法或暴力,甚至基于贪婪的方法可以有性能问题随着场景的大小增加。
摘要技术是利用冗余检查获得由于对称分布模型来提高性能的分配算法。模型中一个关键的冗余时发生在同一位置有多个类似的传输。通过执行一个计算相似类型的所有传输在同一位置,计算储蓄可以怀疑。鉴于许多分布场景复杂,许多传输并不总是彼此的确切位置。增加对称剥削的有效性的一种方法是执行只有一个计算相似类型的所有传输在一定范围内。然而,有一个副作用增加范围的值,这就是在规划计算中引入了一个错误。部分的分析,探索通过模拟一个有效范围是什么,考虑到更大的范围越大计算储蓄也越大误差引入分销计划。
模拟运行测试分配算法的性能和不利用对称性不同范围值最小化分布模型。经验证明,利用对称性的分布模型,场景的测试计算时间可以平均减少了大约24 - 45%,而分销计划的效率仅减少了由于引入的误差约为0.3 -18%。
关键词:物流配送、运动规划、最小化模型
1简介
物流配送和行动规划涉及到开发一个有效的计划将必需的所有用品,及时所需的区域设备及人员(Perugini,2006)。它本质上是一个难于解决的问题,怀疑是非确定性多项式(Cook, 1971)。鉴于问题的复杂性,实际大小的场景可以花大量的时间来计算。
贪婪的分配算法(科尔曼等人,1990)创建开发每个运输的安排在该方案中,以满足所有需要的动作和完成分配。它的目标是尽快完成所有的动作,贪婪地分配最能够传输优先级最高的物品。第三节中概述的算法的概述。这分布问题,甚至基于贪婪的方法可以有性能问题随着场景的大小增加。贪婪的分布是怀疑改进算法可以开发的。
利用冗余的技术(ravindran和Bart,2001),导致对称分布模型来提高性能的分配算法研究在第四节。最后,第五节概述的模拟运行,以测试分配算法的性能,而不利用对称性最小化分布模型。
2分配问题的概述
分布和运动规划领域,是本文的重点包含许多运输平台覆盖土地、海洋、天空和铁路的目标交付供应从源到目的地的位置。物资、设备,人员可以来自很多地方,同样需要运送到可能很多地方。立马可以看出解决方案空间可以迅速扩张,传输的数量、路线,基地位置供应和需求增加。另外,还有业务规则、约束和复杂性的分销领域,需要满足在开发的一个计划。
对流通领域的内在复杂性设置包括：:多个源位置;多个目的地位置;多个路由类型(陆地、海洋、天空、铁路);指导路线;多个航线目的地,中间位置到目的地,被称为“转运”;多个交通旅行通过下降和交换,许多类型的传输,多个供应类型移动,传输可以携带许多类型的供应,和许多旅行可能如果需要执行运输项目从源到目的地。
在这个分配问题固有的约束集包括：飞机所需的最小跑道长度;最低跑道分类所需的飞机,被称为“路面分类编号”;运输速度;运输范围;运输人员能力;运输货物能力;和运输装卸时间。如果在该方案中没有路由到目的地,或由于约束或规范的传输没有可能选项分布,然后场景被认为是不可行的。
这种物流配送问题最相关的文献中的面积是指车辆路径问题（VRP） (Toth and Vigo, 2002)。VRP可以被看作是一个普遍的旅行推销员问题(TSP)在某些约束VRP的放松(Kulkarni Bhave,1985)。VRP涵盖许多物流配送活动,有许多变体(Toth and Vigo, 2002)。这是一个常见问题的研究作为NP难组合优化给定其复杂性(Toth and Vigo, 2002)。有大量的工作应用不同的技术来解决VRP。Laporte(1991)提供了一个全面审查各种作品的完成应用精确VRP和启发式技术等。(2008)提供了一个很好的回顾最近的VRP工作应用各种算法。其他一些更相关的最近的工作包括:Geiger (2010)提出了一些快速近似启发式算法求解VRP和Ma等人（2010）谁指定了两个快速贪婪算法求解车辆路径问题。
作为本文的主题,VRP是最接近问题文献的物流配送问题。它有一些显著的差异。第一个区别是,这个分布问题的目标是尽快交付,而不是试图VRP的整体成本最小化。在这种分布问题传输不需要完成在起始位置之间旅行,和距离可以有不同的能力和成本。也有许多不同类型的资源,需要运输,每个国家都有不同的尺寸和要求。传输也可以携带许多类型的资源,和客户也可以被一个以上的运输服务。最后,在这个分配问题有一个需求将大量的资源,这需要很多旅行进行,而不是客户的VRP节点只需要访问一次。
VRP有太多的显著差异，在这项工作中对物流配送问题进行了概述，如上所述，具体配方和解决方案文献所不能直接使用。因此定制贪婪算法被开发来找到解决这个特定问题。而本文的范围并不是完全描述贪婪的分布算法开发,这是下面的简要描述。
3贪婪的分配算法
贪婪的分配算法的目标是开发一个时间表为每个运输在该方案中,称为分销计划,以满足所有需要的动作。分配计划开发的阶段。在每一个阶段,该算法经过每个所需运动(重新部署部署、维护、管理,等等)是按优先级排序(从最高优先级运动),并通过在每一项运动(食物、水等),和分配的最佳传输运动基于每个运输的潜在“流量”。流量计算如下(1)中。
流量= （1）
流量计算是以项目容纳值h和需要移动值r中的最低值,除以时间t来加快当前运输项目需要的交付。流量越高,越能够运输,并交付项目。如果运输不能运动由于分布约束,应用的流量为0。注意不能通过距离除以计算旅行的运输速度。旅行的距离是使用简单的计算，这是一个启发式的最佳优先搜索(Nilsson, 1980)。鉴于有许多潜在的路径从源到目的节点，一个是用来寻找一个有效的途径，因此距离通过分销网络。这个计算也考虑第二节中提到的很多约束。
每个项目的每个动作每个运输执行上面的计算。所有的传输的流量分类,和交通流量最高的分配给当前项。如果有足够的传输场景中移动所有的全部项目,其余项目将在后续阶段的分配到传输分配计划。算法的思想是,它贪婪地分配当前阶段传输最快的可移动物品。运动通过优先级排序,最高优先级项目获得最大的运输能力。
一旦解决了所有动作在当前阶段或全部传输分配,仿真时转发到时间点运输完成当前阶段先安排其他传输信号,有免费的运输情况分配新的运动),该算法运行和新阶段计算如上(忽略传输,还有动作完成,并承认已经转移和分配在之前的阶段)。算法是重复,直到所有动作都满意,或剩余的运动不能满足约束。
鉴于上述分配算法计算出流量为每一项每一项要求运动和运输所有的计算阶段在该方案中,这将导致大量的计算。确切的贪婪的分配算法的计算复杂度不在本文的范围,但是可以预见,随着动作的数量,物品和运输增加的计算量增加。之前测试的分配算法在现实世界大型场景需要分钟计算电脑英特尔i7 2.80 GHz,4 GB的内存,而准确使用整数规划算法可以花费几天的时间来计算规模小得多的场景(Marsh, 2008)。这项工作的要求是在一个非常广泛的物流可行性分析时间的压力环境,因此精确的最优计划不是一个需求,虽然计算的速度。用户接受这项工作,要求这种分配算法所需的计算时间不到十分钟对于大型真实世界的计划,但是越快越好。鉴于整数规划技术可以把天产生一个最优的解决方案,解决方案的用户愿意接受位为了得到一个及时的结果。确定最优的解决方案和解决方案之间的质量差异这个贪婪的分布算法生成不在本文的讨论范围。虽然观察到这个贪婪的分布算法执行速度比最优算法快(Marsh,2008),仍然可以作出的改进的。
4对称性研究
模型中一个关键的冗余时发生在同一位置有多个类似的传输。分配算法在这种情况下将个人流量计算所有这些类似的传输所有项目和要求。然而它可以有利于计算传输的流量只有一次类似的类型(即它们具有相同的速度的一般属性,范围,和能力)和位置。
鉴于许多场景的复杂,许多传输并不总是彼此的确切位置。增加对称剥削的有效性的一种方法是执行只有一个流量计算相似类型的所有运输在一定范围内r .这个概念如图1所示,哪里有5节点(1 - 5)和两个传输(T1-T2),在本例中T1和T2是5单元之间的距离。如果T1和T2类似的传输和R指定是5,那么只有一个流量计算进行传输,从而节约计算处理。
图1 对称分布的例子场景强调可能的范围
存在有副作用增加范围值,它引入了一个误差ε规划计算。例如,在图1中,每个节点之间的距离是5单位。运输1(T1)在源节点(1),20个单位(5)前往目的地节点。运输2(T2)是在节点2和25个单位:5单位前往源节点,然后20单位前往目的地节点。如果R设置为5,一个计划执行计算、传输覆盖。两个传输的平均位置(节点1和2之间的中点)规划计算给出了22.5的最终成本传输的一条腿。如果选择随机执行旅行T1,实际的旅行成本20,ε= 0,最有效的旅行要花上20。如果T2是选择随机执行旅行,一个实际的旅行成本25,ε= 5,最有效的旅行要花上20。
在规划计算中,半径越大、传输越多,计算c要求越少,但有更大的可能误差ε。要探讨的问题是:有多少计算储蓄可以使用这种对称开采技术,和多少效率损失的总体布局计划由于引入的错误吗?这将是客户的这项工作,以确定的比例计算储蓄与低效分配中引入计划是可以接受使用这种技术。
5模拟
5.1初步分析
通过之前对影响半径计算和误差的模拟研究,初步确定问题有用的对称性破缺技术将是“有多少相同类型的对称性破缺的交通是否需要回报吗?“很明显,对称性破缺有任何影响,至少需要有两个相同类型的传输,与两个以上优先。在图1中越来越半径的概念,提出了一个约束在同一位置的传输可以放松。而不是说他们在同一个R的轨迹,它们可以被视为相同的传输对对称破坏的目的。正是这种放松着一种发自内心的惩罚的错误计算。这是之前所描述的例子的手,同样可能的情况下,错误是R / 2。自然随着R的增加直接影响有两种:首先,相同数量的运输遇到的可能性增加;其次,错误也会增加。一些假设下的相关的问题可能是“R可以确定,有一个令人满意的可能性遇到同样的传输类型吗?“随R的验收将接受的误差范围内。解决最后一个问题的第一步是使简化假设可用的传输是均匀分布的最大距离l .它很容易证明,在这个假设的概率传输是在一个半径:
(2)
如果有n个独立同分布的内传输的概率有k传输半径可以来源于二项分布,是:
非常繁琐发现，预期的平均误差为给定的R是alpha;/ 2。现在仍然是确定的概率有最低k内传输半径r .这是通过减去1的概率有不到k传输半径r .例如:
现在可以利用方程(4)指定三个变量,解决第四。在表中,n,k和一个可接受的概率是指定的并解决alpha;。
表1 alpha;= R / L的来源参数K，N和给定的概率：
表1的结果并不令人惊讶。传输n越多在该方案中,半径越小必须确保至少两个传输在指定半径。从上面的简化分析一个特定的演绎将是一个大胆的声明,但是有一些指标总数的传输需要相对较大,在10的顺序最低。对于较小的数字派生alpha;需要相当大,推断一个重要潜在错误成本。
5.2仿真和结果
从上一节中，据观察，使对称性破缺技术–即在半径和半径过大有两个或两个以上类似的运输（以不引入太多的错误）–似乎需要有大约十或更多的情况下运输。在此基础上分析大量的模拟运行与不同数量的传输,范围和资源移动为了确定多少计算储蓄可以使用这种对称开采技术,和多少效率损失分配计划由于引入的错误。
进行1000套模拟运行试验,从统计学意义出发,通过网络的10节点20和40传输放置在随机位置,范围为0,10、20、30、40、50和60个单位。这些模拟运行在两个场景,一个场景包含要交付2500套,和第二个场景包含5000台资源交付。这些资源将从源节点到目标节点,因此需要传输的多个旅行提供的资源。一系列值0表示没有使用对称性破缺,并基线比较对对称性破缺技术。在该方案中任意两个节点之间的最大距离大约是60台,而平均距离大约是26个单位。60台的范围包括整个分销网络。中使用了两种类型的传输场景中,一架飞机和一艘船。飞机可以旅行比船快10倍,但只能携带一个单位的一个资源。船旅行只能十分之一的飞机的速度,但是可以携带10个单位的资源。在每个试验中有一个相同的飞机比船只。在每个试验中一个节点是随机集的目标节点(即移动所需的资源),和一个节点随机源节点(即最初的资源在哪里举行)。
一旦场景中被初始化,第三节中描述的贪婪的分布算法运行为了任务的传输来完成资源的分布。完成分配的平均时间(在模拟时间步)和计算时间(以毫秒为单位)来完成这个场景被记录为每个审判。定义了仿真时间步,这样交通旅行的速度10单位超过100单位需要10时间步骤。场景设计是可行的,这样,在每次试验中,它是可能的传输提供的所有资源,从而完成一个成功的分布。图2显示了完成分配的平均时间(时间步)在1000年试验20和40传输放置在随机位置,范围值0,10、20、30、40、50和60台,在2500年和5000年两个场景包含单位的资源。立即可以看出更多的传输在该方案中,分配完成后,越快。然而,它也可以看到,10个或更多的范围值平均模拟时间增加。这表明增加引入的误差,减少分销计划的效率。误差的传播范围的所有场景20传输平均水平为0.3 - 5%,
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[502524]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
