本文讨论计划的最大数量的漂流之旅沿大泷的问题.doc

本文讨论计划的最大数量的漂流之旅沿大泷的问题。对这个问题的一个最优调度，尽量减少交叉，同时最大限度地使用露营地和行程长度相匹配的目标分配的百分比。对这个问题提出了三种主要模式。优先模式迭代产生一个每天的日程安排日程安排行程位置，并允许交叉。的密度扰动模型在他们的最佳露营地的所有行程，然后进行扰动结构，直到没有任何行程有冲突。骨骼生长模型解决的没有交叉全球范围内使用启发式贪婪算法，建立了一个初始输入序列的出行计划。因为所有的模型试图最大限度地涵盖露营地，每一个假设，有没有发射，或recieving许多游，或相互交叉的船的成本，但是这不会是难以解决的，小的改进。优先模式是能够覆盖到每程30交叉骨生长模型占地约50 ，无交叉的80 的露营地。这两种型号都能够覆盖更多的露营地露营地增加。这也是朝较短长度的行程的行程长度的分布歪斜的倾向。骨模型是非常强大的露营地和目标分布的数量变化，但工作存在的条件比较敏感。“优先级模型的交叉数成倍增加露营地的数量变大。优先级模型的日程安排是首选，如果一条宽阔的河流交叉是没有问题的，而没有交叉骨生长模型是首选。任何长度的旅行，每个模型产生相当均匀分布的推出日期，并在不同的时间窗口，它可以混合模型。由于各种各样的目标，我们认为，这些模型中的一个或多个可产生接近最优的解决方案。大泷的优化调度队154202012年2月13日摘要本文解决问题的计划的最大数量的漂流之旅，沿大泷。对这个问题的一个最优调度，尽量减少交叉的比例，同时最大限度地使用露营地和目标相匹配分布之旅长度。对这个问题提出了三种主要模式。 “优先级”模型迭代通过安排行程的位置，每天产生的时间表，并允许交叉。密度摄动模型在他们的最佳露营地的所有行程，然后进行扰动了这一点结构，直到没有旅行CON信息和通信技术。骨骼生长模型解决了一个没有时间表分频器全球范围内使用启发式贪心算法，建立吗？的初始输入序列中的旅行。因为所有的模型试图最大限度地涵盖露营地，每一个假设有没有成本在启动或recieving多人次，一次或相互交叉的船其他，但是这不会是二邪教组织，以解决小的改进。优先模式到30每程和骨生长模型的交叉能够覆盖80的露营地占地约50，无交叉。这两种模型能够覆盖更多的露营地露营地的数量增加。还设有一个的行程长度的分布倾向倾斜对长度较短的行程。的骨模型是非常健壮的变化在露营地和目标的分布，但比较敏感INTIAL条件。优先级模型的交叉数成倍增加露营地的数量变大。优先级模型的日程安排是首选，如果交叉是没有问题的一条宽阔的河流，而骨生长模型是首选的没有交叉。每个模型产生相当一致的分布发射任何长度的旅行日期，它可以混合车型超过二？erent时间窗。由于各种各样的目标，我们认为，这些模型中的一个或多个可以产生一个近似最优的解决方案。1引言我们解决这个问题的产生最优调度漂流之旅沿大朗河在六个月的期间。所有在初溪漂流之旅开始，在0英里，和225英里处。漂流之旅，泛舟河上6至7日至19日的实际在晚上18停在露营地。这些露营地都相当均匀分布在整个河流和每个营地都可以拥有一个以上的行程上一晚。此外，游不应该的交叉或通过其他车次河上，以帮助保护野生动物的经验。乘客可以采取桨为动力的胶筏，平均每小时4英里的速度上行驶，或机动船，移动平均8英里每小时。我们的目标，给定一组数露营地，是创建一个计划，为管理者的河流，最大限度地提高数字各种旅行，同时保持的正宗野生动物体验。这个问题提出了许多具体的挑战是值得的。首先，这是非常难以取得各种旅行，有没有传递彼此的行程，并没有相互交叉的行程。其次，大多数调度算法和排队论在以前的工作，并不适用于大泷问题的。大多数的这些算法设计的情况下，有相同的并行机或一台机器。最后，这是不容易优化，通过整数规划的大型解决方案空间。因此，我们开发了多种尝试，试图解决这个问题的原始算法。 首先，我们创建了一个呐？已经算法，增加了一次前往的时间表。如果一个新的行程就可以了，然后将其丢弃。这是用推广的一个优先模式，优先的行程，去最远的每一天。为了实现这一点，每一天预定迭代，而不是一次一个调度跳闸。如果两趟尝试停在相同营地，那么这个算法安排他们，他们没有越过，因此较少前往被丢弃。下一个模型，试图密度扰动算法。优先模式类似，预计每天反复。这两种模式之间的差异考虑，而不是停在露营地，每船各船的行驶里程。因此，该问题是在连续空间处理，并然后将其转换回的Hermitian矩阵的离散空间露营地之后数。如果行程尝试移动到位置太靠近对方，然后创建NDS密切的车次是如何彼此和他们除了移动，所以一到一的映射的露营地可以发现密度矢量。最后一个模型，创建了骨骼的生长模型。这款机型采用了启发式算法来最大化的往返次数，同时保证不交叉。旅行的骨结构序列初始化和肥饱和度增加额外的旅行。该模型是一个贪婪的确定性模型的初始骨骼结构，这是非常敏感的，但guarentees局部最优的解决方案。2定义和变量下面的定义和变量将被使用在我们讨论的大泷问题的。？ A交叉“发生时，行程经过另一个白天的行程。？ A之旅“露营地和夜晚，表示对序列，其中一组乘客预计将在任何一个晚上。？ X是要安排出游人数？ Y是露营地沿大泷。？ T是晚上露营在6个月内的数量。？ P是一个分布的旅行喜好。？ S为附表。有两个调度矩阵格式，S1，S2，我们使用了。在RST格式是S1i;，J 2 F0，.，Y1克介绍了营地的旅行中，我使夜间。每一行代表一个乘客的行程，每一列代表一个晚上。第二格式在S2i J 2 F0; 1; :; XG介绍的跳闸数（0表示“无”）营地，我主持晚上J。？ 打开的营地“的比例是空置的露营地，在180天的划分的总数露营地。这个百分比将永远不会达到100，自最后初期的露营地和一个露营地在最后的日子里不能用旅行。？ Dmax是保证的最大距离，一趟可以预期在一天旅行。在我们的时间表，没有任何行程安排旅行比DMAX，但它假定所有的行程可以DMAX。？的的大泷问题是下面。由于某种概率分布的行程喜好P和一些露营地沿河的目标间距是生成一个调度S的出行X和露营地使用，最大限度地数，数降到最低交叉，尝试匹配相同的分布行程。？ C（Y）是河流的承载能力，这是定义的最大数量在180天的行程除以总数的露营地就在大泷到一些出行分布。 MAXX C（Y）=（Y）= Y。3假设3.1桨供电橡胶筏，机动船和出行长度 我们假设我们只需要担心的行程长度，而不是容器类型，因为有强大的容器类型和行程长度之间的关系。下表是2010年的科罗拉多河的河流之旅统计，2009年，2008年和2007年1。船舶类型2010年2009年2008年2007年电机415 409 426 425非机动车183 183 184 181 由于机动船可以随时旅行必要的距离，到达终点所需的天数和桨为动力的胶筏几乎总是必要的距离到达结束旅行，这是整个计划可以独立机动船或橡皮筏的选择和之后的任何行程，不能容纳一个橡皮筏将自动使用机动船，其余的车次，可根据需要选择。3.2无混合人次我们假设乘客不允许切换哪种类型的船，他们是在他们的行程。3.3保证“的行驶距离的旅行是保证旅游的最大距离为64公里的机动船。这是因为，我们假设将前往对平均和8英里摩托艇在每一天，每天允许8小时的行程。我们假设这条河没有足够的挑战性，以减缓乘客显著下降。我们注意到，最河大峡谷漂流之旅，行程达8个小时的漂流站徒步和午餐2，3。我们假设以外的漂流游在白天是neglibile并没有关注太多各方停止在一个营地，午餐或其他活动。我们也将忽略的影响，天气和河流水位在我们的模型中，将影响橡胶筏和摩托艇的速度。3.4分布和大致数量的营地我们假设，沿大泷露营地的距离是沿着鲑鱼河在爱达荷州和科罗拉多河的大峡谷露营地的距离。据白水露营，8，沿250英里的科罗拉多河和185180.6英里的鲑鱼河露营地沿着有162个露营地。下面的直方图显示的分布的沿着河边露营地之间的距离。图1：直方图露营地之间的距离因此，可以假设营地分布与二之间的距离露营地在不同的试验不同的是统一的。之间的距离露营地，我们测试不同的，1.5和1英里/营地，这意味着我们的测试都是为Y = 45，150，和225个露营地。3.5设备和劳动力约束假设我们有足够多的人采用的起始位置有一个足够大的码头，使任何长度之旅的船，无限数量的可能推出顺流而下，在一天之内。3.6白天不要紧，在我们的模型中，我们假设时间是离散的，只担心每次出差，每天晚上的营地位置。我们假设所有的船和木筏，使他们能够设计的营地去年底的一天，能够很早就开始一天。这相当于假设小船和木筏在河的任何部分的密度没有任何影响的距离，能去的车次。这个假设是不太现实的，但是我们可以考虑到这一点，在两个方面，我们在我们的模型评估和惩罚交叉，我们可以减少预期的最大距离，行程允许拆开。4款车型我们的模型解决大泷问题的尝试，以产生最佳的赛程。最优被定义为一个时间表，满足约束实现的，在同一天晚上，住在同一营地没有两趟。目前的算法在调度理论和排队论不解决的大泷问题。的的大泷问题是相似的调度n体验活动“（TRIPS），其中每个活动都需要Y 1工作（沿河段）precendence秩序问题。可以被视为一个作业的机器，它的每个部分的河流。然而，大多数的今天的调度算法解决的情况下，有相同的并行机或一台机器。我们的问题需要一系列的工作，是为了完成，但独特的机器之间（不同江段）。马尔可夫过程和排队论也没有申请，但这个问题是，每一个营地只有一个队列，一个人每晚的价格，以外的任何人的经验犹豫不决的概率等于1。4.1天真的模型我们第一次尝试在一个算法来解决这个问题是从一个空的日程和反复添加行程直到没有更多的行程可以被添加。我们没想到这个解决方案是最佳的，但我们belived将提供一个良好的初步探索的问题。总体思路？可以随机选择要添加的分布长度之旅。？如果行其上的任何地方的时间表，将它添加在这一点上。？如果没有发现整个6个月内，取出行程长度的分布。该算法输入：空附表，行程长度分布输出：人口时间表虽然分布：1。随机选择一个行程长度t分布2。对于n 1，T - T：（a）试图插入行的时间表开始在夜间n：(一)试图掩盖等于部分的河流每一天（二）如果所需的营地，移动到最近的可用的编缉，打破随机关系（三）如果没有camptites是在公差范围内，然后插入失败（四）如果一个有效的营地发现每天晚上在n，n+t，然后插入了成功（b）如果成功再突破图2：安排三趟的朴素模型的步骤3。如果失败，对所有n分布：distrubution这种方法的问题？此计划分配有没有考虑交叉。？调度所有在一次长途旅行可能会阻止大的距离，以支付使用他们所需要的露营地的短途旅行。这些问题propmted