Employee Bus Allocation Algorithm -
my company started transportation employees. want build algorithm allocates employees bus based on bus stop.
no. of buses , bus routes fixed: ex:
(capacity:40) bus #1, ------ stop1 ----- stop3 ------- stop5 ---------- (capacity:50) bus #2, ------ stop2 ----- stop3 ------- stop6 ---------- stop5 (capacity:40) bus #3, ------ stop3 ----- stop4
no. of employees availing transportation:
stop1: 10, stop2: 10, stop3: 20, stop4: 18, stop5: 20, stop6: 10
how can allocate optimal no. of employees buses?
there standard algorithm defines solution problem? googled couldnt find relevant algo this. please guide me in correct direction.
thanks in advance!
i think might end similar bin packing, knapsack , cutting stock, although not identical. problems np-hard, suspect problem too.
- check if solvable: total(employees) < total (bus spaces)
- for stops 1 bus serves: allocation space on bus. (e.g. stop 1,2,4,6 in example).
maybe:
- sort stops number of buses serving stop.
- allocate passengers first fit?
Comments
Post a Comment