一个图优化问题-有点难度

给定一个矩阵A,aij表示货站i到需求点j的时间,如果aij=0则表示货站i不能前往需求点j。每次运输的货物不限量。不同货站间不能串货。货站与需求点之间直达。
例如一个矩阵A= [[1,2,3,5][2,4,6,8][3,5,6,3]] 表示时间,向量B=[3,3,1]表示1到3号货站的货物数量,向量C=[1,3,2,1]表示需求点1,2,3,4的货物需求量。
下面是必须满足的要求:
1. 对于每一个货站,累计送货时间尽可能短。
2. 只要存在通路,货站需要往尽量多的需求点运送货物。
3. 保证优先分配最近的需求点(每一个货站的运输总时间/每一个货站的运输次数达到最低)。
下面是可以尽量满足的要求:
1. 货站的货物不超额分配,或者最多超额5%。
2. 保证每一个需求点的需求,如果不可能,将不可实现的需求量降到最小。
求解:
1. 货物配送方式,以出发货站,目的地,运送货物量的形式输出。
备注:测试数据可能有问题。
备注:实际生产数据为1w个需求点,1k个货站。#算法##图优化#
2023-06-29
在牛客打卡11天,今天也很努力鸭!
全部评论
订正:必须满足的需求有修改。应为1. 对于每一个货站,累计(送货时间*送货量)应尽可能小。
点赞 回复 分享
发布于 2023-06-29 06:54 英国
用贪心算法拿到了次优解
点赞 回复 分享
发布于 2023-06-29 07:20 英国

相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
1
分享
牛客网
牛客企业服务