Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

5G万物互联时代,井喷式增长的流量对传统网络带来巨大挑战,智能化的业务路径优化对建立一个高效的网络管道布局至关重要。特别是如何能在提供用户低时延,高带宽的网络服务前提下,提高整体利用率,更是网络规划,网络优化领域的重中之重。

通信网络架构复杂,涉及广泛的通信原理,理解起来需要很多背景知识。在某些场景下,我们可以将其理解为一个“高速运输网络”,那么我们的赛题可以如下描述定义:

描述:

给出一个运输网络,以及若干需要运送货物的出发点和目的地,求出整体运输成本最小的运送路线方案,其中:

  1. 运输网络为无向图,各个运输站(节点)的度不超过10,即最多与10个运输站相连;
  2. 运输站个数不超过300个;
  3. 两个邻接运输站之间的通路(边),由于距离不同,运输成本不同;
  4. 每两个邻接运输站之间的通路,可分为多条车道,车道数上限不超过40条,编号为1-40;
  5. 每条车道有运输限制,总承重量不能超过10吨,总承重量不超上限的前提下,可同时运送多个货物;

比如:邻接运输站A、B之间车道1总承重量是10吨,运送一个4吨的货物后,A、B间车道1的总承重量就减为6吨(由于是无向图,承重量被双向占用。即,无论是A到B还是B到A都只剩下6吨),此时车道1仍能运送1吨、4吨的货物若干,但无法运送10吨的货物。

  1. 运送的货物不超过1000个;
  2. 运送的货物重量一般分为三种,即重量为1吨,4吨,10吨;
  3. 一个货物,在整个运输网络中,只能使用唯一编号的车道;

比如,若运输站A,B之间走车道1,那么在其他站点之间也只能使用车道1。

 

要求:

  1. 所有货物的运输线路为预先规划,一旦分配则不能释放;
  2. 求出整体运输成本最小的方案;
  3. 算法需适应一系列场景,即给出的场景上均可求解;
  4. 算法不限于机器学习、深度学习或传统算法;
  5. 用时不超过30分钟。


评估标准:

提交可运行的算法代码

提交算法在数据集上每个样本的总体成本值,以及计算时间

最终综合考虑成本值最小,计算时间最短两个指标,给出排名


数据集描述:

数据集包含若干样本,每个样本包含:

运输线路网络图描述,json结构:

{

     nodes:[0,1,2], # 节点id列表

     edges:[

            (0,1):{ # (起点, 终点)

               roads: [0,1,2], # 路的id列表,数组长度为总条数

              load_weights:[10, 10, 20] # 每条路的承重量

}

    ]

}

货物描述,每个货物也以json字符串的方式表示,即:[{"起点": 138, "终点": 206, "重量": 1}, {"起点": 74, "终点": 156, "重量": 1}]