设施选址问题的遗传算法 [英] Genetic Algorithm for Facility Location Problem

问题描述

我正在尝试解决设施位置问题，其中一个解决方法是使用遗传算法。我对算法如何工作有一个公平的理解，但我无法将其放入代码表格。



示例问题



共有3个级别，共有5个潜在的设施位置。



5个设施中的2个位于1级，其余3个位于3级在2级。



等级3由5个客户组成。



要到达3级的任何客户，必须从1级开始，然后转到2级，最后到达特定的客户。



设置设施需要支付固定费用。



给出任意2个位置之间的距离，即1级设施与2级设施，2级设施与3级客户之间的距离。我需要尽量降低成本。



成本=（设置仓库的成本）+（距离*单位距离成本）

<必须满足每个客户的
需求。



如果有人能够使用遗传算法大致了解如何解决这个问题，那将会有很大的帮助。

Hi ,
I am trying to solve the facility location problem and one of the methods to solve it is by using the genetic algorithm . I have a fair understanding of how the algorithm works but i am unable to put it into code form .

example problem

There are 3 levels and a total of 5 potential facility locations .

2 out of the 5 facilities are on level 1 and the rest of the 3 are on level 2 .

level 3 consists of 5 clients .

To reach any client on level 3 , one has to start at level 1 then move on to level 2 and then finally to a particular client .

There is a fixed cost associated with setting up a facility .

The distances between any 2 locations , i.e , facilities on level 1 to facilities on level 2 , facilities on level 2 to clients on level 3 is given . I need to minimise the cost .

cost = (cost of setting up warehouse) + (distance * cost per unit distance)

demand for each client has to be satisfied .

If someone could give me a rough idea of how to go about this using the Genetic Algorithm it would be of massive help .

推荐答案

hi，

首先需要很好地定义遍历路径。即所有可能的遍历。

示例。

startPoint - > level1facility1 - > level2facility1 - > client1

startPoint - > level1facility1 - > level2facility2 - > client2

startPoint - > level1facility1 - > level2facility3 - > client3

- -------------------------------------------------- ----

.................................等


基本上，这个算法解决的是：

从level1facility1到client3的最小成本路径是什么？



现在选择合适的数据结构。在这种情况下，图表将有助于表示级别。考虑通用解决方案而不仅限于3个级别。

如果选择图形 Dijkstra的算法 [ ^ ]可以帮到你。



希望这会有所帮助!!



或

看看在遗传算法和旅行商问题 [

title =新窗口 > ^ ]并查看它是否适合您的情况。

first of all the traversal paths need to be well defined. i.e. which all are the possible traversals.
example.
startPoint-->level1facility1-->level2facility1-->client1
startPoint-->level1facility1-->level2facility2-->client2
startPoint-->level1facility1-->level2facility3-->client3
--------------------------------------------------------
.................................etc.

Basically, what this algo solves is :
what is the minimal cost path to reach from say,level1facility1 to client3 ??

Now select a suitable data structure. A graph would be helpful in this case to represent the levels. Thinking in terms of a generic solution and not just limited to 3 levels.
If you select a graph the Dijkstra's algorithm[^] would help you.

hope this helps !!

OR
take a look at Genetic Algorithms and the Traveling Salesman Problem[
title="New Window">^] and see how it suits your case.

有趣。是的，这是我可以建立的东西。最后，我需要决定在潜在设施中建立的理想设施数量，同时最大限度地降低总成本。严格的限制是必须满足每个客户的需求。



非常感谢！

Interesting . Yes it is something i can build upon . Finally i need to decide upon the ideal number of facilities to be set up among the potential facilities while minimizing the total cost . The hard constraint being that the demand at every client must be met .

Thanks a lot !

这篇关于设施选址问题的遗传算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！