员工总线分配算法 [英] Employee Bus Allocation Algorithm

问题描述

我公司最近开始运输员工。我们想建立一个算法分配员工的基础上公共汽车站公共汽车。

My company recently started transportation for employees. We want to build an algorithm which allocates employees to a bus based on bus stop.

没有。巴士及巴士路线是固定的： 例如：

no. of buses and bus routes are fixed: Ex:

(Capacity:40) Bus #1, ------ stop1 ----- stop3 ------- stop5 ----------    
(Capacity:50) Bus #2, ------ stop2 ----- stop3 ------- stop6 ---------- stop5    
(Capacity:40) Bus #3, ------ stop3 ----- stop4

没有。员工援用交通：

stop1: 10,    
stop2: 10,    
stop3: 20,    
stop4: 18,    
stop5: 20,    
stop6: 10    

我们如何可以分配最优的没有。员工巴士？
有没有标准算法，它定义了一个解决这个问题？我用Google搜索，但无法找到任何相关的算法中这一点。请指引我正确的方向。

How can we allocate optimal no. of employees to buses?
Is there any standard algorithm that defines a solution for this problem? I googled but couldnt find any relevant algo for this. Please guide me in the correct direction.

在此先感谢！

推荐答案

我想，这可能最终类似的装箱，背包和的切割下料，但不完全相同。这些问题是NP难的，所以我怀疑你的问题了。

I think this might end up similar to the Bin Packing, Knapsack and Cutting stock, although not identical. Those problems are NP-hard, so I suspect your problem is too.

1. 检查是否有解：总（员工）LT;总（总线空格）
2. 有关站只有一个公交服务：分配空间总线上。 （例如停在你的例子1,2,4,6）。

也许

1. 排序停止巴士服务站的数量。
2. 先适应分配的乘客？

这篇关于员工总线分配算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！