数学建模-Camping along the Big Long River

PROBLEM B: Camping along the Big Long River

Visitors to the Big Long River (225 miles) can enjoy scenic views and exciting white water rapids. The river is inaccessible to hikers, so the only way to enjoy it is to take a river trip that requires several days of camping. River trips all start at First Launch and exit the river at Final Exit, 225 miles downstream. Passengers take either oar- powered rubber rafts, which travel on average 4 mph or motorized boats, which travel on average 8 mph. The trips range from 6 to 18 nights of camping on the river, start to finish… The government agency responsible for managing this river wants every trip to enjoy a wilderness experience, with minimal contact with other groups of boats on the river. Currently, X trips travel down the Big Long River each year during a six month period (the rest of the year it is too cold for river trips). There are Y camp sites on the Big Long River, distributed fairly uniformly throughout the river corridor. Given the rise in popularity of river rafting, the park managers have been asked to allow more trips to travel down the river. They want to determine how they might schedule an optimal mix of trips, of varying duration (measured in nights on the river) and propulsion (motor or oar) that will utilize the campsites in the best way possible. In other words, how many more boat trips could be added to the Big Long River’s rafting season? The river managers have hired you to advise them on ways in which to develop the best schedule and on ways in which to determine the carrying capacity of the river, remembering that no two sets of campers can occupy the same site at the same time. In addition to your one page summary sheet, prepare a one page memo to the managers of the river describing your key findings.

游客到大长河(225英里)可以领略风光和令人兴奋的白色激流这条河是进不去登山者的，因此观光的方式只能是沿河旅行，这需要几天的露营。

所有的沿河旅行都始于第一站并在下游225英里远的最终出口退出。观光者或者乘坐浆动力船只以平均每小时4英里速度旅行，或者乘坐摩托船以平均每小时8英里旅行。

这趟沿河行程可能有6至18个夜晚需要在河边露营。政府管理当局负责管理这条河，使得每一个旅行者都可享受一份野营体验，且在河岸可以最少地接触其他的船只。

目前，在每年六月份的旅游季节中，有X个旅行团队沿着大长河旅行，一年其余部分的天气太冷不适合做这种河流旅行。有Y个营地差不多均匀分布在大长河河道两岸上。

因为沿河漂流受欢迎程度上升，有关方要求公园管理者允许更多的旅行团队沿河旅行。他们想确定怎样可以安排一种最优的混合旅行方式，可以是不同的持续时间(以在河边过夜为单位)，和不同的旅行方式进(马达或浆)，可以最大限度地利用好营地。换句话说，在漂流季节可能容纳多少旅行团队？河流管理者雇用你给他们提供建议，安排一个最佳行程方式和测算河流的承载能力，记住没有两队露营者在同一时间占据同一露营地点。

摘要

我们开发了一个模型去安排沿着大长河旅行的方案。我们的目标是优化

定义问题

如何安排不同长度和推进力的行程，使得在六月的旅游季使旅行次数最大化？
在任意给定的一天，有多少新小组能够展开一段河流旅行？
这条河流的承载能力怎样？即在六月旅行季中，能够下河旅行的小组数是多少？

模型概述

我们设计了一个模型，它具有如下特征：

该模型能够应用到具有类似属性的现实世界的河流中。
该模型足够灵活，能够应对大规模的可行输入。
用一个函数来模拟河流旅行的安排，该函数特点如下，
- 与旅行时长分布相关（如6天，12天，18天）
- 与推进速度的变化分布
- 与不同数量的营地

完成了如下任务，

这个模型预测了旅行者在六月旅游季的数量。
回答了关于这个河流的承载容量，推进速度与旅行时长分配的有利分布。
回答了每天有多少组能够开始一段河流旅行并且如何安排行程。

问题约束

旅行始于第一个起点，终于最后的出口，全程 $225 mile$
只有两种类型的船
- 桨动力的橡皮艇，平均 $4mph$
- 摩托船，平均 $8mph$
大约花费6~18个晚上要露营
旅游被安排在每年的六月份
营地被统一沿河安放
不会有两队在相同的时间出现在同一个营地中

模型假设

我们可以规定每天在河流上行驶的浆动力船与摩托艇的比例

在短时间内如果太多的浆动力船被启用，将导致一些问题。

如果乘坐的是浆动力船，那么旅行时长为12天或18天。如果是摩托艇，那么旅行时长为6天或12天

这一步的简化仍然能使我们的模型得出有意义的结果，同时让我们比较不同旅行长度带来的影响。
每个营地在每个晚上只能有一组

这正是河流管理者期待的
每天，某个旅行团仅仅只能向下游移动或者继续住在当前营地。即不能返回上游

这约束了这些旅行团的流动是单向的，这极大地简化了我们如何从一个营地到另一个营地去移动旅行团。
旅行团只能在早上8点到晚上6点之间旅行，每天最多旅行9小时（其中被减去的一小时用来吃饭之类的）

这意味着每天浆动力船能行驶至少 $4\times 9=36mile$ ,而摩托艇至少行驶 $8\times 9=72mile$ . 这个假设允许我们决定哪些组能够合理地到达一个指定营地。
旅行团从来不会超过他们一天能够旅行的距离：即浆动力船每天36英里，摩托船每天72英里
我们忽略了可能影响每天最大行程距离的可变因素，如天气，河流状况等。

这没有办法精准地包含在模型中
营地均匀分布，即营地之间的距离等于河流长度除以营地数量。

我们因此可以把这条河流表示成间距相当的营地数组。
一个旅行团在旅行的最后一天必须到达终点，即
- 一个旅行团不会早退
- 旅行结束也不会比预期晚
这一假设符合我们认为的对河流管理员与旅行质量的重要标准。

符号说明

$g_i$ 第 $i$ 个旅行团
$t_i$ 第 $i$ 个旅行团的旅行时长，以过夜为衡量标准; $6\leq t_i \leq 18$
$d_i$ 第 $i$ 个旅行团已经度过的夜晚数
Y 河流上的营地数量
$c_Y$ 营地Y在下游的位置坐标 $0<c_Y<255$
$c_0$ 表达起点的营地(用于构造旅行团的waiitlist)
$c_{final}$ 表达终点的营地(总是open状态)
$l_i$ 第 $i$ 个旅行团当前在下游的坐标 $0<l_i<255$
$a_i$ 第 $i$ 个小组每天应当计划移动的平均距离 $a_i=225/t_i$
$m_i$ 第 $i$ 个小组一天能够旅行的最大距离
$P_i$ 旅行团 $i$ 的优先级 $P_i=\frac{d_i}{t_i}\times\frac{l_i}{255}$
$G_c$ 能够到达营地c的旅行团集合
$R$ 每一天启动的浆动力船与摩托船的比值
$X$ 目前沿大长河顺流而下的人数
$M$ 河流的承载容量(在6月旅行季能够顺流而下的最大组数)
$D$ 旅行团在河流上的旅行时间的分布

方法

我们定义了一些术语和短语如下

开放营地

如果当前没有旅行团占领该营地，那么称一个营地是开放营地。

移动到一个开放营地

对于一个旅行团 $g_i$ ，他们的当前营地是 $c_n$ ，移动到另一个开放营地 $c_m$ ，即 $c_m \neq c_n$ ，相当于把 $g_i$ 分配到新的营地。由于一个旅行团仅能顺流而下，或者保持当前位置不动，所以必然有 $m \geq n$ 。

等待名单

PS: 以下存在长难句翻译

The waitlist for a given day
某天的等待名单
is composed of the groups
是由旅行团所组成
that are not yet on the river
这些旅行团不是已经在河流上的那种
but will start their trip on the day
而是将要开始他们的旅行的那种
when their ranking on the waitlist
根据他们在等待队列中的排名
and their ability to reach a campsite c
和他们能够到达营地c的能力
includes them in the set $G_c$ of groups
把这些旅行团放到到可以到达营地c的集合 $Gc$ 中
that can reach campsite c
这些旅行团都能够到达营地c
and the groups are deemed“the highest priority .”
并且这些旅行团被认为具有最高的优先级

等待名单中的旅行团在当前的营地 $c_0$ （0号营地）已经准备好出发，并假定此时他们具有优先级1, 直到他们从等待名单上移到河流上。

离开河流

我们考虑这个河流的的第一个可以离开的地方就是最终营地 $c_{final}$ 总是一个开放的营地(以便于它能够被分配任意多数量的旅行团)。这与人们的理解相一致，即任意数量的旅行团都能够在同一天离开河流

最远的空闲营地

我们的调度算法使用了一个数组作为数据结构来表示这条河流，它的每个元素都是一个营地。算法每天寻找最远的开放营地c，然后生成一个集合 $G_c$ ，其中包含了所有的能够在当晚到达营地c的所有旅行团。因此集合 $G_c$ 定义如下，

$G_c=\{g_i \space | \space l_i+m_i\geq c\}$

其中 $l_i$ 是当前旅行团的坐标， $m_i$ 是该旅行团一天能行驶的最大里程。

$l_i+m_i\geq c$ 条件说明了旅行团 $g_i$ 在一天内必然能够到达营地 $c$
$G_c$ 是由河流上的旅行团与等待名单上的旅行团所构成
如果 $G_c=\phi$ ，那么TODO
TODO

调度算法将按照这种方式继续执行，直到最远的空营地是第0个营地 $c_0$ ，从这个角度出发，当天能够在河流上移动的每一组都将移动到一个营地，然后我们再次启动算法去模拟下一天的情况。

优先级

一旦一个特定的营地c的集合 $G_c$ 形成，算法就必须决定哪些小组要移动到营地c。优先级 $P_i$ 是一种度量方法，用来衡量某个旅行团超前或落后的情况。

$P_i > 1$ : 旅行团 $g_i$ 落后于预期
$P_i < 1$ : 旅行团 $g_i$ 超前于预期
$P_i = 1$ : 旅行团 $g_i$ 恰好等于预期

我们尝试将拥有最高优先级的旅行团移动到营地c。

图1和图2中概括了出现这些情况的例子，以及如何使用优先级来解决这些情况。