0

Possible Duplicate:
Seat guests based on prioritized parameters

I've been struggling for a while now with this problem. I just can't wrap my head around it. Would be very grateful if someone that's smarter or has more algorithmic and/or mathematical insight could explain to me how I should proceed.

The client is arranging sits at events, varying from restaurants to large arenas. The goal of my client's software is to provide the guests with an SMS/e-mail/paper ticket that says where the guest should be seated when arriving at the event. The seating (which guest should sit where) must be manually controlled, some tables are "VIP" etc. I'm working on an algorithm that can help the user by letting him determine some parameters, such as which company a guest belongs to and which language the guest can speak. Today, the seating process is made by hand at large whiteboards (one section at a time if the event is 1k+ guests).

My job is to automate this a bit, not entirely but "good-enough". I've built an application that can visually present the tables, chairs (seats) and guests. However, the most important functionality is still missing; to be able to distribute the guests to the existing tables and seats, based on the parameters that the user chooses.

The parameters are an arbitary number of data on each guest, such as: "39 years, Male, Redwine Corp, CTO, English & Italian". The user takes these (all guests have the same data fields) and sorts them in order of importance. Each parameter must also be set to "next to" or "apart from". So for example, the user can control that guests that are speaking the same language should sit next to each other, but those working at the same company should be seated apart from each other.

Given this, the function definition I'm about to implement would be something like this: function getGuestSeatings(tables, seats, guests, parameters) and return an array of which guests should be seated at which seats. The parameters tables, seats and guests contains your choice of information, but most important is probably the X, Y of chairs. That combined with information on what table the chair connected to, should be enough to calculate a "good-enough" guest sit configuration. Of course, the parameters variable contains information on the parameter's priority and if it's a "seat-next-to"- or a "seat-apart-from"-parameter.

The question I'm asking is: What algorithm can be used to provide a solution, and how do I implement it? A mathematical answer might do no good, so to be on the safe side I suggest code (JS/C/C#) or psuedo code.

I'll give you some more info that may or may not fill any gaps to a solution (I'll complement with your comment feedback here):

  • The tables can be either elliptic or rectangular
  • If there is no seating configuration that matches the criteria (prioritized parameters), then I still want a "good-enough" solution, even though it will not be the best
  • I understand that investigating all possibilities will probably hog memory
  • Maybe a lazy-loaded point-based tree system of some kind could suffice? Just investigating the paths that are looking promising and ignoring other paths...?

Here is a mockup that gives you an idea behind the software: mockup

Community
  • 1
  • 1
Simeon
  • 5,519
  • 3
  • 29
  • 51

2 Answers2

1

Simulated Annealing.

The idea is you have an initial assignment of people to seats, and you have a "goodness" function. You want to maximize the goodness function. To put it crudely, the way you do it is to randomly switch people's seats, and if that results in a higher value of the function, you do it again starting from there. If the switch results in a lower value of the goodness function, you might still accept it randomly, and that can help you avoid local maxima. This is called Metropolis-Hastings.

You let this run thousands of times, and see what you get.

Mike Dunlavey
  • 40,059
  • 14
  • 91
  • 135
0

I would place the first person at the first table, then from there, based on parameters and priority compute a score, per table, per guest. A language match to the others at that table is a positive score, times the score priority (bigger number priority is higher priority), if they are from the same company or different language or other factor to spread them out make it a negative score. If after scoring that guest does not have a high enough score (or a positive score) then go to the next table and try again with guests there, if no guests are there then put this guest there or for the spacing thing put this guest a few tables away. Repeat for each guest. An alternative might be for each guest, compute the score for each table with guests already assigned, whichever table this guest gets the highest score on assign to that table. If all scores are negative then move them to a new table if possible evenly spaced away from other tables.

just a thought, good luck.

old_timer
  • 69,149
  • 8
  • 89
  • 168