2012-B-数模美赛读书报告-

1、2012 B读书报告-Camping along the Big Long River.一、自己对问题的理解（初步）该问题是一种分配最优化的问题，在于如何将旅行时间、持续时间、露营地点、每时刻 河流上旅行人次和旅行工具选择进行最合理的安排，合理的标准之一就是能使游客更充分的 欣赏风景，即最大化经历，不与其他的旅行队伍碰面；之二就是充分利用Y个campsites。题目初步读起来难度有一些，不容易分析清楚变量对问题的限制关系以及我们要通过哪 些量的输出来达到优化的指标。待我们将题目所给出的条件逐一列出，思路便变得相对清晰， 接下来我们要寻找恰当的算法刻画该动态分配过程。Schedule要安排到什么

2、程度？是每一条船选择和类型，哪一天发船，每天航行多久， 先快还是先慢。等，这些度还得把握商榷。不过我对题目中的X、Y两个未定量的参量仍不能很明确，是否我们最终的优化输出中会 带有这两个参量，来适应不同的情况？哦，好像X是不用考虑的，因为我们还要求解河流的 最大承载量。而对于Y，我估计需要分情况讨论，因为从极限原则来考虑，Y的大小直接影响 了一些限制航行时间的航行类型的停留。不过我又注意到U “In other words, how many more boat trips could be added to the Big Long Rivers rafting如半这个意思，好像是说要我们在X

3、的基础上考虑优化时 间安排后能够在加入多少组旅行。解决该问题，我们最好充分利用控制变量法，将个待分配的变量依次考虑（其他的先 做出适合的定量），从而发现个变量对全局的影响。可能用到模拟退火算法，和对于依据概率合理分配资源的算法等，需要我们将个 待分配的变量合理的对应上去。二、论文的思路理解、分析关于 13074-B-Peking University 的读书报告关于后两个模型，实用性强，与实际游客的喜好不确定性相符，不过游客的喜好应该 能够根据数据库进行提取，猜测会符合一个正态分布，而不一定是左右待选择项的等概率 分配的模拟。该论文优势在于，考虑了游客的自由选择（露营地点，旅行动力）的情况下河

4、流的最大 承载量和最优时间表，与实际相符，因为设想如果agency设计出了承载量最大的最优的旅行 时间表，却因为时间安排让大部分游客觉得不符合自己的意愿而不愿意去旅行，结果只能导 致安排是一纸空文，门票一张也卖不出去。这也是我们初步审题所没有想到的。估计我们得 到最大承载量结果后，发现旅行类型过于集中或者单一，就能知道这一问题了。当然平均也 不一定是适应实际情况的。走了点弯路。文章算法描述很是周折，在学习过程中，我重点想去抠一下作者算法层面上是怎么实 现时间表安排的，尤其是关于所谓的campsite set的概念，是否准确，是否符合实际。1. Introduction论文在该部分重述了问题的重

5、点，分配propulsion （动力）和duration （持续时间）是 关键，作者根据这两大关键，将可以航行的类型分为了 26类。提出了解决大方向，根据 实例研究了旅行者的习惯：白天航行，晚上休息，假设游客在所有可选择的旅行类型中是 随即选择，即选每一个的概率相同。根据实际可能的情况，提出或者按照以前每年航6个 月中的各航行类型比例安排航行时间表，或者根据旅行者随即选择的航行类型的结果安排 航行时间表，使减少互相碰面机会并最大程度的提高河流6个月中的总体承载量。并且还 提出了可以再知道X的基础上对模型进行建立。感觉introduction部分写的有条有理，有规范化的模型解法，也有灵活性、应用

6、性较强 的模型方法，可供商家参考比较，让人耳目一新。作者思路清晰，明确问题的限制点和发挥点，把握了安排的时间表要与实际相符（这一 点很重要，要不然徒有巨大的河流承载量，确实充分利用了，但安排不合理，游客也不会选 择在这里河流旅行）对于作者说的，充分利用campsites就是不让它闲着，我基本同意，而要尽量增加河流的 6个月总的承载量，我认为还要确定各个类型的比例到底是多少，因为航行速度快的船增加 了流动性，对总承载量起到的权重显然大。如果人们都喜欢航行快的就好了。作者给出的是 解决方法，即如模型一，可以改动各个航行类型的分配，我认为这一点较好，可根据实际航 行类型受欢迎程度进行改动。2. De

7、finition关于一些变量的定义，理解起来尤为重要，要不然我都读不懂作者在干什么，尤其是 关于“orbit的定义，和“campsite sets的概念，真是在第一个固定模型中着实让读 者费解一番。(1) “optimal” ：最佳地利用营地，六个月中最大化旅行总数；“route” ：在给定的旅行中，游客选择停留的露营地点；(3) “orbit”:允许某一些旅行类型游历的一系列特殊的露营地点；给营地自然数编号，从0到Y+1；给旅行类型自然数编号；(6)由：某旅行类型每天平均航行时间；ni :每一类型相应的orbit中的露营地点数；mi :六个月中(i旅行类型)的旅行次数；3.Specific

8、formulation of problems做出了营地均匀分布、总开放时间通天的基本说明。然后将文章模型大致分为了三部分考虑：第一部分，游客严格按照river agency的安排行动；第二部分，我们建立一个随机模型让游客自己随即等概率地挑选露营地点，将小概率事件作为不可能处理，虽然此时他们是可能产生见面冲突的，从而我们优化他们的旅行类型，使见面概率下降；第三部分，游客自己随机选择旅行动力和露营地点，同样用随机等概率分配进行模拟该过程，优化航行持续时间（duration）,选出满足小概率事件的进行排列，得到优化表。我感觉model2、3中随机等概率分配和modell中做等比例安排得出的结果貌似

9、没有什么大 的区别。应该是算法层面的区别吧，modell中做出的是简单的规律排列，而model2、 3中用到的概率判断和贪婪算法加入引子的方式会显得更加无规律，从算法层次上感觉贴 近实际一些。Assumptions1、不能返程；2、每个露营地只能留一天；3、每次持续航行在24h内，每晚要休息，以天为单位度量时间；（每天露营一次吧）4、根据查阅，设定游客平均每天旅行8小时；5、假设每一种路线安排都是随机等位的。6、根据统计学原理，主观设定小概率事件的边界值；7、设定Y=150（ Y的设定影响模型的修正）经查阅亚马逊相关的河流数据。假设基本合理， 恰当的限定了无关的因素，又方便了定量研究河道分配。

10、Parti Fixed dates, types and routes充分利用露营地已达到河流的承载量，尽量让露营地处于有人状态。这样就认为我们 的承载量能达到最大，充分利用了河流能力，且尽量让船都较快航行，增加动态流动量， 文章假设的是不管什么船，在相应的航行天数内，每天最多不超过平均的8个小时，即最 大跨越度。该模型对于每一次航行的方式，包括具体细节都安排，也就是省去了游客的主管随机 的选择，是一个具体到细节的比较模试化的时间安排model.首先为每一类型旅行类型安排一特殊系列营地，系列之间没有交集，应用于Y306的 时候；然后，Y很小时给每组旅行类型们安排一系列特殊营地，一个组包含两个和

11、三个旅行类 型的组的情况分别列出；Y很很小，仅仅将所有营地分为两个系列，按照两种航行动力进行 分类。总之就是Y小时不足够每一种航行类型都有自己的一个单独的campsite set。作者通过平均分配的政策进行了列表验证，然后让各种旅行类型占满自己的campsite set。并且对于不同参数的Y都有相应的策略。具体来看作者的设计：对于a specific campsite set ,变化trip types，从一个类型到多个类型，对应着对Y的减少的 适应。综合各个campsite sets，就能得出河流的承载量。文章论述较长，难以一次性通读后还记得作者的概念，文章在Keywords部分也做了大概的

12、设计结构的说明。我姑且先把作者的几个逐次递进的小标题列出来：5.2.1Every campsite set for every single trip typeEvery campsiteset for every multiple trip types5.2.3One campsite set for all trip types 那个图比较重要：先是对于较大的Y值，暂时不考虑各个旅行类型的比例，按照平均分配的原则（在露 营地很大的情况下，认为所有船都有充分的露营地可以停留），Y=425，ni=17 （但实际上 各个ni是不相同的，由我们要设定的各个类型的船的比例mi来决定，即作者在 div

13、ide the campsite sets部分没有叙述清楚），按照首尾相接的方式，（a campsite set 中的点是固定间隔的排列在河道上的），该类型的船在相应的campsite set中以规定 天数按部就班的紧密连续的航行，保证占满这相应的一系列露营地点。直观理解如下：然后，如果Y小于306的话，就不能像上面那么简单的考虑了，就不可能同时 每一类型的船都在河流上在自己露营地系列（a specific campsite set）里面首尾相连 的航行了，要么共用露营地系列（对于提升承载量没有太大帮助，不过考虑时间表排列 的首和尾，直观的是优先排列航行天数短的）。另一个角度说，Y过小的话，显

14、然河流 的承载能力就要小很多，因为没有船一天能走完，假设每一天是一定要在露营地休 息的。因此，保守考虑，要有船可以航行，至少也要5个露营地。此时我们的航行 方案也就不同了。然后作者就Y=150的情况在他的假设上作出了分析，并列出了包 含所有旅行类型的航行情况。模型最终达到的结果，是公司可以利用各种航行动力方式的比例（mi的比例得到ni的 比例），从而利用模型得到最优化的航行时间表安排和相应的最大河流承载量。整理作者的思路和我的看法：段密度先假设相同（即每一类型都有自己独自相应的campsite set）,然后提出 可以受mi的改变，列举段密度相同的计算结果求出了河流的最大承载量。不足之处，我认

15、为作者既然提出可以通过mi改变ni的可能，来适应实际的情 况，那就应该做出这样的结果和验证，而不是一直用段密度平均的政策将 campsites分为17个，貌似所有的分配结果都是以ni=17为划分，让读者半天摸不 到头脑。另外作者在论述的过程中有不少毛病，例如：我认为的一些错误：Q ziin,中i的重复定义；i 1For every day we let Q trips come into the river to occupy all of the campsitesin frontof the leaders campsiteand they just copy the leaders ro

16、ute and get to Final Exit the same day with “leader”.；其中个人认为in front of用错了，而且当航行类型数较大的时候 如果Y依旧为425，则不能一次性让Q trips进行最远航行，会与该例子中的环路造 成较大偏差；后来才说mi决定ni，让人产生ni恒等于17的矛盾？；关于“Ij-k”如“3 M-6s”的说明放错位置了，应该是在model2中的贪婪算法求得 的结果的说明，有些混乱。第四页的 As we can see from the chart below, the distance between two adjacent camp

17、sites in a specific orbit is less than the length of what we call an interval =（25/225）miles.”没看懂，不应该是相等么？在实际安排过程中，关于皮划艇的7天航行的旅行类型，其中有几天的航行时 间一定超过了 8个小时，甚至有一天航行16个小时以上的，远超出了作者的基本假设，这是一点不足，作者没有说明它是可以适当灵活变动的。而且在开始的one campsite set for every trip type ,当 Y=425 时，Q 值为2.41,不会是三，也超出了 8 小 时航行。作者列出的以campsit

18、e set为基础的航行表格，有相当的误差，又不具有 可调整能力的代表性。ni比例真的可以任意调整么？关于共用露营地系列(即a campsite set group包含很多trip types)，作者还应 该提出，是航行天数较为接近的共用效果会更好，因为如果航行天数相差较大，势 必航行天数多的相对航行天数少的成为了 leader，会压制航行天数少的向前走，除 非两中航行类型时间上聚集并且区别开，而这样又出现了分配时间段过于集中的现 象。而且，这样排列的方案，为了最大承载量，规划好了哪一天你游客要航行多少，必 须在一些地点停靠，确实限制了游客的自主选择性，作者也清楚分析了该part1的弱点。 该模

19、型适用性不是很强，不过对于很抢手的情况，抢手到游客甘愿任何安排只要能买到 票，那么就会盈利很大了。优先排列那些航行天数少的旅行方式，会有更大的承载量， 体现为河流上的船只更新速度快。Part2 fixed dates and types, but unrestrained routes考虑让游客自由选择旅行停靠休息的露营地。用随机分配的方法进行游客选择的模拟， 认为左右停靠点等概率。当两游客在同一地点重复停靠的概率小于0.05当做小概率事件处 理，忽略。运用经典的概率学公式，设计f(T,x,t), P(T,x,t), trip(n), q(x,day.。贪心算法的思想我理解的就是：每一步都是最

20、优的，结果也就是最优的。本模型运用贪婪算法和迭代的方式，逐个加入trip，每加入的都是对于当前环境最好的 选择，即让加入的游客所停靠的露营地不与已经存在的游客航行停靠的露营地重合，是否 重合通过以上的q(x,day)来具体到对应的露营地点和绝对时间(天数)来判断(这样得到的 结果一定就是最好的么？哦，是加到不能加为止，贪婪的算法寻找所有可能的，为了最大 承载量)。这其中运用到了 minimum的原理，即通过调整搜索到的点之间的相互影响，来调整出 满足条件的子集最大的调整方案。最后作者又联系了 X，只要给出了具体的X的值和这些trip相应的航行类型和情况，就 能作为贪婪算法的初始条件，从而在mo

21、del之上继续加trips即可达到要优化的结果。我觉得 该模型能实现较好的拟合，至于开始选择哪一种航行类型先航行是否会影响整体的分配结果， 作者在模型敏感性部分做了验证，说明了 the first trip对整体承载量的影响是微小的。而贪婪 算法的搜索，结合概率公式的计算和minimum的调整原理，使得几乎每一天的安排都是满负 荷的，这样应该可以说是每天都尽量做到了在随即分配routes的情况下的较为充分利用 campsite的安排，总体也应该是最优化的安排。继续发挥作者的思路，如果某一天安排不是最优化，那么会不会接下来几天能够最优 化的比原方案更好呢？比如作者安排的180天中有那么一段时间是

22、连续一周几乎每天都只 加入一次航行，如果我在这一周的前两天不安排航行，第三天开始在安排，是不是剩下的 五天得到更多的航行的安排呢？因为航行的船是不断往前走的，会留下更多空间，这需要 通过算法进行具体的数据验证。因为我考虑到，在180天中的中间的部分，每一天地位应 该差别不大，那么按照逐天优化，不一定是整体的最优解吧。或许我们可以再对180天的 安排顺序做调整，该part6中只是模拟游客自由选择route。或者说，贪心算法用在此处， 它的优化可信度值得考虑。运用Jordan Formula来进行两游客见面概率q(x,day.)的求解，是个不错的选择。Jordan Formula简单来说是n个人帽

23、子混合重拍，至少有一组配对正确的概率。不过感觉作者的概 率求解公式有一定问题：f (T,Y+1-x,duration存在么？到了相应类型T的持续时间 duration却还没有到终点Y+1 ？在此model的公式说明中说还要用到对应的campsite set的概念，那么是如何 分的set的呢？是不是仍旧受到Y的影响，作者也没有明确说明，算法细节之处让 人费解，道不明具体实现。Part3 fixed dates, but unrestrained types and routes同上一个模型，模拟露营地点的自由选择，多考虑的一项是自由选择航行动力，同理将 航行动力做等概率随即分布来模拟游客的自由选

24、择。优化保证是同一露营地点相与的概率小 于0.05视为可忽略的小概率事件。仍用贪婪算法进行循环处理，Day每加一，随机挑选可以加入的一个类型加入，进行Jordan formula概率计算，随机分配满足条件的露营地，直到该天没有什么类型的船可以加入，则Day+1,继续上述步骤。看法和part6相同。Sensitivity analysis通过改变首发船，即贪婪算法的初值，验证model的结果-河流承载量无较大变化。 实际上在180天当中，这些变化本身我认为就是微小的。改变每天航行最长时间，有一定的代表性。不过作者是否也有很多近似化整计算呢？ 那样的化貌似与微小的最长时间变化不协调。改变认定的小概

25、率事件的概率值显然是影响全局的，这是我们优化的主要指标，即是 否不同的游客在同一地点见面。敏感性分析行之有效，因为对于有不确定因素的解决实际问题的model，我们几乎都 要做敏感性分析，看model适应环境的稳定性和应对环境变化的反应速度。9.Strengths and weaknesses优点：1、基本所有营地6个月中每天都被占2、限制经过露营地量和为每一种航行方式分配营地的方法有简化作用。3、适应不同的Y4、允许对所有航行方式不均等分配，与实际相符。1、概率模型随即描述游客挑选，2、模拟游客兴趣所向的选择露营。1、游客自由选择营地和交通方式。缺点：2、概率模型模拟游客兴趣所向有失真；3、所

26、有提供的旅行不一定等概率的被选择；（也就可能和实际验证结果不很相符）4、不同类型旅行数量区别太大在part2和part3里面。作者很清楚自己models的优缺点，思路清晰，缺点在根本上就有，不过这也不失为一 种叫可以执行的假设。假设过于严谨，也可能造成我们model无法建立，难以权衡各个要 设定的变量。读后小结:作者给出的模型也没有实质性的时间安排表啊，只有part6中给出了一个每天发船的表。因 为X，Y的不确定，我们似乎也只能这样，方案最重要。重要的是，我们要控制什么变量，怎样控制的与实际接近，怎样顺序安排的合理达到 承载量最大。而且作者还充分考虑了应对不同的Y和X，很全面。算法层面，我们考

27、虑模拟退火算法，和贪心算法结果作比较，不管两者谁得到结 果更好，都会使模型总体更加完善。总体感觉，文章算法层面上描述的比较磕磕绊绊，或许因为我是Chinese reader，但文 章中确实有很多叙述矛盾或者错误，让人难以理解。总体构架比较清晰，摘要和结论写的较 好，明确的提出了面对该优化时间表问题，要从几个方面下手，如何与实际更接近，如何考 虑Y和X这两个参量，估计这也是让评委印象深刻的地方。值得我们学习，当模型具体执行 出现难度时，我们要保证解题思路准确，对问题的认识和自己要优化哪些东西必须很明确。 文章利用到的方法比较多，考虑的关于分配的方式也很多，都值得我一个建模者学习，当我 以后遇到类

28、似的分配问题时，估计思路会清晰很多。关于 13955-B-Western Washington University 的读书报告文章的叙述让人容易理解，几乎没有废话，目录也几乎将行为思路展现的很完整，让 人感觉总体model效果很好，这是我们应该学习的论文格式，要在以后注重加强思维轮廓 的概括和抽象。文章的核心算法就是实现 uses priority values to move groups downstream in anorderly manner”，而priority是关于理论平均位置（即按照规定航行天数每天应该航行多少的 理论位置而又不无休止航行的地点）的滞后还是超前，从而判断接下来

29、是加速前进还是原地 停留。每天整体都是前移的，因此每天都连续不断的加入新的航行，逐个占领每一个campsite。也就充分利用了 campsites，文章也是认为尽量占领满campsites能达到最大化的承 载量。而且最后还得出了关于安排船类型的比例和持续时间对最大承载量的影响，对实际应 用有很大的实用价值。Abstract加入限制条件，输出最优时间表，由以上算法过程的分析，结合实际航船的行为特征， 可以得出相应的最大承载量；并应用实际的一个旅行河段的案例来进行了模型输出的实用性。最 后通过改变propulsion、duration和Y来验证模型的敏感性。我认为摘要基本描述了自己对问题的认识，但

30、为说明限制条件就是减少游客在同一露 营地点的碰面，信息量不是很大，也比较含糊，都是一些一语带过的描述。不过也算是循 序渐进，不至于让读者产生思维的矛盾。Introduction TOC o 1-5 h z Defining the Problem3Model Overview3Constraints4 HYPERLINK l bookmark23 o Current Document Assumptions4Variables5单从introduction列表来看，已经将解题准备工作明确，分别列出，层次鲜明，容易让 读者掌握，我们应该学习。“our model is easily adapta

31、ble to find optimal trip schedules for rivers of varying length, numbers of campsites, trip durations, and boat propulsions.作者很清楚模型要分析什么变量， 在该部分体现的很好，正确理解了题目的意义，并且找到了合理的解决方向，体现了论文 赢在了开头。问题解释，进一步接近model要处理的因素。说明了 model解决的问题：河流承载量 关于营地分布、动力选择、每一天发出多少组航行和如何安排航行时间的关系，从而最优化 了河流承载量。列出了已知条件。基本假设重要的有：由我们决定两

32、种航行动力的比例，为了承载量最大，不能设置过多的oar-power 且航行距离短的；充分考虑输入的变量，为了让结果更有意义，令oar-power航行12至18天，令 motorized-power 航行 6 至 12 天；每天必须往前走，只能停留一次，不能返程；只能白天航行，最多10个小时；忽略天气因素；Campsite均匀等间隔分布；必须在规定的最后一天到达end。Methods我理解的算法设置了四个有效概念：Open Campsite; Moving to an open campsite; Waitlist; Off the River.特别是优先级的概念，即通过与理论的平均航行位置比较

33、，得到当前该船只 的相应的优先等级，较落后的（behind schedule）优先等级就比较高，较超前的（ahead schedule）优先等级就比较低，从而进行航行快慢的调整补充。具体做法是从最后（C_final）往起点（C_0）算起，有开放的营地就判断有能力到达它（每天航行不超过10h）的优先级高的航行到此处，在一次往下考虑开放营地，直到起点（C_0）,（等待 的C_0处的船也加以考虑）从而完成一天的航行。总体原则就是向着理论平均航行位置进行靠近，一个挨一个的排列，充分利用每一个 campsite。疑问是该模型初始条件是如何设置的呢？没有明确说明。我理解应该可以认为设定候 选梯队的groups数量，然后按照优先级排列即可。Scheduling Simulation设定起始点等待groups的数量，设定Y值，得到四条船的时间安排表。不过我觉得应 该给出连续的campsites的占领情况，而不只是开始的四条船的航行情况，因为我们要知晓 连续的数据。而且，貌似作者没有给出解决如每天发送如k跳船和这k跳船在左右可能的26中航行 类型的根据优先级挑选的情况。Case Study很精彩该部分，因为作者给出了最大承载量和Y和R （露营地数和航行动力比率、D和R （持续天数比率和航