货物运输线路优化
- Liya Yuan
5G万物互联时代，井喷式增长的流量对传统网络带来巨大挑战，智能化的业务路径优化对建立一个高效的网络管道布局至关重要。特别是如何能在提供用户低时延，高带宽的网络服务前提下，提高整体利用率，更是网络规划，网络优化领域的重中之重。
通信网络架构复杂，涉及广泛的通信原理，理解起来需要很多背景知识。在某些场景下，我们可以将其理解为一个“高速运输网络”，那么我们的赛题可以如下描述定义：
描述：
给出一个运输网络，以及若干需要运送货物的出发点和目的地，求出整体运输成本最小的运送路线方案，其中：
- 运输网络为无向图，各个运输站（节点）的度不超过10，即最多与10个运输站相连；
- 运输站个数不超过300个；
- 两个邻接运输站之间的通路（边），由于距离不同，运输成本不同；
- 每两个邻接运输站之间的通路，可分为多条车道，车道数上限不超过40条，编号为1-40；
- 每条车道有运输限制，总承重量不能超过10吨，总承重量不超上限的前提下，可同时运送多个货物；
比如：邻接运输站A、B之间车道1总承重量是10吨，运送一个4吨的货物后，A、B间车道1的总承重量就减为6吨（由于是无向图，承重量被双向占用。即，无论是A到B还是B到A都只剩下6吨），此时车道1仍能运送1吨、4吨的货物若干，但无法运送10吨的货物。
- 运送的货物不超过1000个；
- 运送的货物重量一般分为三种，即重量为1吨，4吨，10吨；
- 一个货物，在整个运输网络中，只能使用唯一编号的车道；
比如，若运输站A，B之间走车道1，那么在其他站点之间也只能使用车道1。
要求：
- 所有货物的运输线路为预先规划，一旦分配则不能释放；
- 求出整体运输成本最小的方案；
- 算法需适应一系列场景，即给出的场景上均可求解；
- 算法不限于机器学习、深度学习或传统算法；
- 用时不超过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}]