路由与波长分配问题是通信领域中的重要问题, 具有较高的实际应用价值.
路由与波长分配问题主要研究如何为通信业务规划传输路径并分配波长, 使得所有业务可以在互不干扰的情况下传输.
高效的路由与波长分配问题的求解算法对提高网络的传输效率具有意义重大.
同时, 路由与波长分配问题还与多智能体路径规划以及芯片布线十分相似, 具有重要的理论意义.

路由与波长分配算法训练

问题概述

给定一个有向图, 以及一系列通信业务, 每个通信业务有固定的起点和终点.
请为每个通信业务规划一条传输路径, 并为其分配一个波长, 在确保每条有向边上经过的所有业务波长互不相同的前提下, 最小化使用的波长数.

参考文献.
- [1] Y. Fang, Z. Lü, Z. Su, Y. Wang, T. Zhang, and Q. Zhang, “Local Search based on a New Neighborhood for Routing and Wavelength Assignment,” in 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2020, pp. 1123–1128. doi: 10.1109/SMC42975.2020.9283031.

命令行参数

请大家编写程序时支持两个命令行参数, 依次为运行时间上限 (单位为秒) 和随机种子 (0-65535).
算例文件已重定向至标准输入 stdin/cin, 标准输出 stdout/cout 已重定向至解文件 (如需打印调试信息, 请使用标准错误输出 stderr/cerr).
例如, 在控制台运行以下命令表示调用可执行文件 rwa.exe 在限时 300 秒, 随机种子为 12345 的情况下求解路径为 ../data/ATT.n90e274t359.txt 的算例, 解文件输出至 sln.ATT.n90e274t359.txt:

1	rwa.exe 300 123456 <../data/ATT.n90e274t359.txt >sln.ATT.n90e274t359.txt

运行时间上限.
- 超出运行时间上限后测试程序会强行终止算法, 请确保在此之前已输出解 (最好还能自行正常退出).
随机种子设置.
- 使用 C 语言随机数生成器请用 srand.
- 使用 C++ 随机数生成器 (如 mt19937) 请在构造时传参或调用 seed() 方法设置.

输入的算例文件格式

所有算例的节点从 0 开始连续编号.

第一行给出 3 个由空白字符分隔的整数, 分别表示节点数 N, 有向边数 E, 以及通信业务数 T.
接下来连续 E 行, 每行包含 2 个由空白字符分隔的整数, 第 i 行表示第 i 条有向边的源点和宿点.
接下来连续 T 行, 每行包含 2 个由空白字符分隔的整数, 第 i 行表示第 i 个通信业务的起点和终点.

例如, 以下算例文件表示在 4 个节点和 5 条有向边的有向图上传输 3 个通信业务; 其中,
有向图包含 0, 1, 2, 3 共 4 个节点以及 0-1, 1-2, 2-3, 3-0, 1-0 共 4 条有向边,
通信业务 0 的起点为 0 终点为 1,
通信业务 1 的起点为 1 终点为 0,
通信业务 2 的起点为 1 终点为 3:

输出的解文件格式

输出 T 行整数表示 T 个通信业务的传输方案, 第 i 行表示第 i 个通信业务的波长分配和传输路径.
每行第一个整数表示第 i 个通信业务使用的波长, 第二个整数表示传输路径上的节点数, 随后连续 P 个由空白字符分隔的整数表示传输路径上依次经过的节点.

波长可以取 int 范围内任意整数, 检查程序自动统计不同的整数的数量.
传输路径上的节点若不包含通信业务的起点和终点, 检查程序将自动将其添加至路径中.

例如, 以下解文件表示 3 个通信业务的波长分配和传输路径; 其中,
通信业务 0 使用的波长为 1, 依次经过节点 0 和 1;
通信业务 1 使用的波长为 1, 直接从起点 1 到达终点 0;
通信业务 2 使用的波长为 0, 依次经过节点 1 和 2, 最后到达终点 3:

1
2
3

1 2 0 1
1 0
0 2 1 2

提交要求

发送至邮箱 szx@duhe.tech.
邮件标题格式为 “Challenge2021RWA-姓名-学校-专业“.
邮件附件为单个压缩包 (文件大小 2M 以内), 文件名为 “姓名-学校-专业“, 其内包含下列文件.
- 必要算法的可执行文件 (Windows 平台).
  - 建议基于官方 SDK 开发 (https://gitee.com/suzhouxing/npbenchmark/tree/main/SDK.RWA).
  - 用 g++ 的同学编译时请静态链接, 即添加 -static-libgcc -static-libstdc++ 编译选项.
- 必要算法源码.
  - 可重入 (可在同一线程内反复调用而不会出现数据初始化错误或内存泄漏).
  - 可并发 (可在同一进程内的多个线程同时运行多个算法求解实例而互不干扰, 满足此要求一般不能有全局的非只读变量).
  - 可伸缩 (数据结构可以根据算例规模动态申请内存, 而非根据预先指定的编译期常量进行内存分配).
- 可选算法在各算例上的运行情况概要, 至少包括以下几项信息 (仅在无法成功调用算法输出可通过检查程序的解时作为参考).
  - 算例名.
  - 使用的波长数.
  - 计算耗时.
- 可选算法在各算例上求得的使用波长数最少的解文件 (仅在无法成功调用算法输出可通过检查程序的解时作为参考).
其他所有问题通用的要求见 SmartLab Challenge - ReadMe.

例如:

苏宙行-华科-计科.zip
|   rwa.exe
|   results.csv
|
+---src
|       main.cpp
|       algorithm.cpp
|       algorithm.h
|
+---results
        ATT.n90e274t359.txt
        ATT2.n71e350t2918.txt
        ...

算例清单

下载地址: https://gitee.com/suzhouxing/npbenchmark.data/tree/data/RWA/Instance

算例规模从小到大依次为 (求解难度不一定随规模增加, 但除 Z* 以外的算例应该都很容易求解):

ATT.n90e274t359
ATT2.n71e350t2918
Brasil.n27e140t1370
EON.n20e78t373
Finland.n31e102t930
NSF-01.n14e42t284
NSF-03.n14e42t285
NSF-12.n14e42t551
NSF-48.n14e42t547
NSF2-01.n14e44t284
NSF2-03.n14e44t285
NSF2-12.n14e44t551
NSF2-48.n14e44t547
Y3-020-1.n100e344t1975
Y3-020-2.n100e368t1961
Y3-020-3.n100e356t2055
Y3-020-4.n100e354t1989
Y3-020-5.n100e350t1975
Y3-040-1.n100e344t3894
Y3-040-2.n100e368t3956
Y3-040-3.n100e356t4012
Y3-040-4.n100e354t3959
Y3-040-5.n100e350t3996
Y3-060-1.n100e344t5967
Y3-060-2.n100e368t5907
Y3-060-3.n100e356t5989
Y3-060-4.n100e354t5932
Y3-060-5.n100e350t5990
Y3-080-1.n100e344t7959
Y3-080-2.n100e368t7911
Y3-080-3.n100e356t7987
Y3-080-4.n100e354t7908
Y3-080-5.n100e350t7924
Y3-100-1.n100e344t9900
Y3-100-2.n100e368t9900
Y3-100-3.n100e356t9900
Y3-100-4.n100e354t9900
Y3-100-5.n100e350t9900
Y4-020-1.n100e440t1975
Y4-020-2.n100e460t1961
Y4-020-3.n100e436t2055
Y4-020-4.n100e442t1989
Y4-020-5.n100e430t1975
Y4-040-1.n100e440t3894
Y4-040-2.n100e460t3956
Y4-040-3.n100e436t4012
Y4-040-4.n100e442t3959
Y4-040-5.n100e430t3996
Y4-060-1.n100e440t5967
Y4-060-2.n100e460t5907
Y4-060-3.n100e436t5989
Y4-060-4.n100e442t5932
Y4-060-5.n100e430t5990
Y4-080-1.n100e440t7959
Y4-080-2.n100e460t7911
Y4-080-3.n100e436t7987
Y4-080-4.n100e442t7908
Y4-080-5.n100e430t7924
Y4-100-1.n100e440t9900
Y4-100-2.n100e460t9900
Y4-100-3.n100e436t9900
Y4-100-4.n100e442t9900
Y4-100-5.n100e430t9900
Y5-020-1.n100e570t1975
Y5-020-2.n100e504t1961
Y5-020-3.n100e582t2055
Y5-020-4.n100e548t1989
Y5-020-5.n100e568t1975
Y5-040-1.n100e570t3894
Y5-040-2.n100e504t3956
Y5-040-3.n100e582t4012
Y5-040-4.n100e548t3959
Y5-040-5.n100e568t3996
Y5-060-1.n100e570t5967
Y5-060-2.n100e504t5907
Y5-060-3.n100e582t5989
Y5-060-4.n100e548t5932
Y5-060-5.n100e568t5990
Y5-080-1.n100e570t7959
Y5-080-2.n100e504t7911
Y5-080-3.n100e582t7987
Y5-080-4.n100e548t7908
Y5-080-5.n100e568t7924
Y5-100-1.n100e570t9900
Y5-100-2.n100e504t9900
Y5-100-3.n100e582t9900
Y5-100-4.n100e548t9900
Y5-100-5.n100e568t9900
Z04x25-020.n100e400t1975
Z04x25-040.n100e400t3894
Z04x25-060.n100e400t5967
Z04x25-080.n100e400t7959
Z04x25-100.n100e400t9900
Z05x20-020.n100e400t1975
Z05x20-040.n100e400t3894
Z05x20-060.n100e400t5967
Z05x20-080.n100e400t7959
Z05x20-100.n100e400t9900
Z06x17-020.n102e408t1975
Z06x17-040.n102e408t3894
Z06x17-060.n102e408t5967
Z06x17-080.n102e408t7959
Z06x17-100.n102e408t10302
Z08x13-020.n104e416t1975
Z08x13-040.n104e416t3894
Z08x13-060.n104e416t5967
Z08x13-080.n104e416t7959
Z08x13-100.n104e416t10712
Z10x10-020.n100e400t1975
Z10x10-040.n100e400t3894
Z10x10-060.n100e400t5967
Z10x10-080.n100e400t7959
Z10x10-100.n100e400t9900

SmartLab Challenge 2021 - Routing and Wavelength Assignment