Capacitated Facility Location Problem

本次算法项目中,我们被要求解决一个“仓库选址问题”。在该问题中,我们被给定了一定数量的顾客和一定数量的仓库。每个顾客到不同的仓库有不同的服务成本,同时每个仓库也有最小的经营成本(这意味着一旦仓库服务了顾客,其就会产生一个额外的成本)。我们的目标是寻找到一个顾客分配方案,使得总的服务成本(包含经营成本)最少。

FLP 是一个经典的 NP 难问题,CFLP 也一样。由于 NP 难问题夸张的求解时间复杂度,我们不能够寻求一个常规的,最优的方案来求解。相对的,我们只能够构建一个能够收敛到近似全局最优的启发式算法来获得一个近似解。

在本次项目中,我们选择了 爬山算法(Hill Climbing Algorithm))遗传算法(Genetic Algorithm) 作为我们的代码实现,并通过对比来寻求二者间的差异。

代码仓库

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×