华为云DevCloud软件编程大赛·口罩配送大作战（赛道一）
用于测试
使用方式：
编译命令（要求jdk1.8）：javac MaskTest.java
运行命令：java MaskTest <你的代码进程启动命令>
例如：
C++(windows): java MaskTest Main.exe
C++(linux): java MaskTest ./Main.out
java: java MaskTest java Main
python: java MaskTest python Main.py
【赛题规则】
1）某市每日会公布五个已预约口罩派送的小区和每个小区的需求量（50-200）盒。
2）当日会安排一名志愿者配送员向已预约的五个小区投递口罩。配送员从仓库出发前往各小区派送点。（仓库容量：无限；配送员负载容量：100盒）
3）在派送过程中，配送员可能会收到某个新小区主动捐献口罩（1-100）盒的消息，他根据自己负载情况和原计划投送的路线进行评估，决定后续行走策略。
4）任务完成条件：五个已预约小区口罩投送完成。
5）评分标准：在满足任务完成条件后，按配送员的行走步数来排名；步数越少排名越高。
6）失败条件：代码执行错误、判题超时5分钟、单幅地图步数超过500。
【地图说明】
1）配送员路过捐赠口罩的小区/仓库，会将捐赠口罩装车，如果小区口罩数量变为0，则表示该小区的取货完成。 小区/仓库的口罩扣除量 = 配送员的口罩增加数量（最多满载）
2）如果配送员路过待配送的小区，会将车内口罩配送给小区，如果小区口罩数量变为0，则表示该小区的配送任务完成 小区的口罩增加数量 = 配送员的口罩扣除量（最少为0）
3）配送过程中，可捐赠小区会随机在10-20步以内生成。
【思路】
1）审题：题目给出二维的12x12的地图，地图中有一个仓库、五个需要口罩的目标小区、随机出现的捐赠口罩的小区，且配送员车辆只有一辆，载重最大为100个口罩。 题目有点类似包含单源最短路径规划，有点类似带约束型的车辆路径规划。
2）构思：即如大赛最后一位点评老师所说，题目设计之初融合了NP旅行商问题和迷宫避障行走问题。开始的时候，也想使用地杰斯特拉最短路径算法，暴力搜索并规划路径，但想到问题：最优解的获取。此时即涉及到多目标多约束情况下的进行路径规划，正好想到运筹学课上学到的动态规划和车辆路径规划的问题。自己在启发式算法方面知识储备也不是很多，学过地杰斯特拉最短路径以及AStar算法求解单源最短路径，经过一番百度谷歌之后，了解了禁忌搜索算法和遗传算法在运筹规划方面的应用。对比禁忌搜索算法和遗传算法，发现禁忌搜索算法在实现上有点吃力，然后选择了遗传算法，思路简单（编码、初始化种群、计算种群适应度和累积概率、选择进化、变异、再计算累积概率，再进化）。
3）实现，
3.1 路径规划： 将坐标x、y、weight(口罩数量)分别存入数组List，因为在算法执行过程中随机存取的操作远多于更新删除操作，故选择java数组。然后将数组下标作为坐标点的索引进行染色体基因编码，形成一条染色体序列（eg：0123456,0代表当前位置，1、2、3、4、5、6代表地图中的可能的需要口罩的小区和捐赠口罩的小区），然后进行随机编码形成初代种群（eg.50-300）。结合题目中的条件约束作为此处每一条染色体的适应度评价参考，即：距出发点的距离、口罩需求、是否满足车辆当前载重（此处在口罩需求处理上，将第i个需要口罩的目标小区的口罩需求值设为正数赋值于weight[i]，将第k个捐赠口罩的小区的目标值设为负数赋值于weight[k]）。计算出每一条染色体的适应度之后，基于预设的选择概率值和累积概率进行轮盘赌选择（即：累积概率=当前染色体适应度/所有染色体适应度之和）。完成选择作为新的种群并进行交叉变换（模拟染色体变异）形成新的种群，再结合条件约束计算适应度得出累积概率。利用最后形成的种群再次模拟新一代的遗传进化。最后在完成指定的遗传进化次数（eg. 1000-3000）的遗传进化之后，选择出适应度最好的一条染色体作为规划序列，并作为函数返回值。
3.2 路径执行：基于路径规划的路径序列值于地图上进行移动，并输出方向符号。移动的同时，会记录地图状态（车辆的当前位置、需要口罩的目标小区的口罩需求量、捐赠口罩小区的口罩捐赠量），基于状态会重新进行路径规划，直至口罩送完。
4）结果，
4.1 在线下结合官方的测试代码修改为随机地图测试，测试结果显示，在调整种群规模以及进化次数的情况，移动步数（100-200）和地图解决时间（单幅：200-2000ms）都较大，可能自己在遗传算法中的选择策略以及变异算法的实现上不够好，没有办法获取到全局最优解，想过引入精英选择策略和局部搜索算法提高准确率以及时间复杂度。
4.2 自己上传到官网提交测试的时候，结果总显示运行超时以及存在未配送的小区，结合交流群的讨论，可能自己在一开始的题意理解上有误：即只要路过捐赠小区，口罩必须发生变化，不可以选择不要口罩。然后自己也基于线下的测试结果手动解析了一番，在解析中发现就是，我自己的程序确实已经配送完口罩，但官方提供的线下测试程序提示“存在未配送的小区”，而且自己也同小伙伴一同解析了结果，确实已经配送完成了，这个到现在也没有弄清楚问题所在。同时也希望官网提交测试的位置能提供代码运行的日志结果，自己线下解决问题手动debug实在太费时间了。
4.3 自己也对结果反思了，就是确实算法可能最后无法收敛到全局最优解，但是权衡5min测试1000张地图的效率，确实难以平衡，但说明算法仍然存在优化空间。