HiMCM 2016 赛题评论（11月25日发布）

整体印象

今年的两道赛题要求都比较明确，具体。问题的背景，需要完成的任务讲的都很清晰。在题意的理解和方向的把握方面，多数队应该没有问题。解决问题所需要的方法也比较基本，常见方法应该有不错的结果。但是，这些方法可能超出了高中正常的教学内容，如果事先没有储备，可能会比较吃力。不过，只用高中阶段的知识，或许也能很好的解决问题。

个人猜测选A题的队多一些。

Problem A: Swim, Bike, and Run

A题要求讨论在铁人三项比赛中，如何分组，如何安排赛程，尽量减少拥挤程度和竞赛时间。

从赛题的描述上看，这是一个典型的多目标优化问题。两个目标有一定的冲突，无法同时达到最优。赛题的关键是如何量化优化目标，以及多目标如何处理（比如，如何转化为单目标问题）。

Part I要求提供分组方案和出发时刻表。这是整个赛题的关键任务。在回答这两个问题之前，首先要解决如何度量两个目标，特别是如何度量拥挤。如果对两个目标没有清晰的定义（量化的指标），后面的寻优就无法进行。

• 分组方案和出发时刻表很难一起考虑，一同求解。可以分步处理，先确定分组方案，再讨论最佳出发时刻表。

• 分组方案中应指明分组的依据，或原则。可以讨论不同分组方案的差异。

• 安排赛程的分组方案与取奖的分组方案不是等同的。比如男子组与女子组一般会分开取奖，但出发时，不一定男女分开。题目要讨论的应该是安排赛程的分组，主要取决于每一组的成绩分布，如何影响两个目标。

• 在分组方案确定的前提下，定义好congestion和road closure time之后，问题有可能形式上写成规划模型，但是求解或许比较困难。

• 可以参考以往国际赛事中的分组方案和出发时刻表，如果有详细数据，最好有数值对比结果。

总之，不管用什么方法，以下几个方面都是要考虑的：

• congestion和road closure time要有明确的定义。

• 两个目标如何处理，如何折衷。

• 分组的依据和原则要明确、具体。

• 要给出具体的时刻表。

• 最好对比不同方案的结果，或者是与现有比赛的实际数据进行对比。

Part II要求讨论如果调整三个项目的距离，会对两个目标有什么影响。这一问实际上是要求做模型对参数的敏感性分析。如果第一问解决的比较好，这一问通常只需要调整不同的参数，对比结果。调整参数时，要注意不同参数的组合。

Part III要求给市长写信。这也是MCM/ICM竞赛中常见的要求。

这封信不同于摘要，要考虑读者的身份和写信的目的，重点介绍研究结果。方法简单概括即可。

Problem B: Shop and Ship

这是典型的配送中心选址问题。相关的研究应该比较多。

Part I要求在满足一天配送的条件下，确定最少的仓库数量和位置。可以近似为一个覆盖问题，相对比较容易解决。对最少仓库数的估计，可以先用最简单的方法得到一个很粗糙的下限，比如总面积除以每个仓库覆盖的平均面积。估计出数量的下限后，也可以把问题转化为聚类问题，将地图离散后，求得的类心即中仓库位置。如果不满足配送时限要求，仓库数量加一之后再求解，直到满足条件。离散化时，可以均匀离散化，也可以只考虑城镇。

Part II要求考虑不同的州的税率，讨论之前确定的仓库对客户交税的影响，并讨论如何调整仓库数量和位置，使得尽可能多的客户少交税。如果Part I可以写成规划模型，这一问要将税收放入目标，或者是约束（比如要求免税州至少有一个仓库）。如果Part I是使用遗传算法、模拟退火算法等智能计算方法求解，可能比较容易添加这一目标。如果对Part I的结果进行了调整，一定要有效果的对比，说明调整的必要性和可行性。

Part III要求进一步考虑衣帽类税率不同的问题，如何调整仓库数量和位置。感觉这一问只是再多考虑一个因素，方法上没有本质的区别。

Part IV要求给公司总裁写一封信。

相关链接

• 竞赛主页：http://www.comap.com/highschool/contests/himcm/index.html