Media Coverage
June 2011
The Travelling Delegate Problem
We decided, since SAPICS around the corner, to optimising your experience at SAPICS for maximum benefit. We’ve worked on a hypothetical scenario where the average SAPICS user would want to visit all the booths for an average of 10 minutes in order to get a fair idea of what the companies have on offer, arrange meetings, attend presentations and ultimately squeeze as much in as possible.
Firstly, we looked at the booth layout within the Sun City Superbowl. Using Concorde - an exact Travelling Salesmen Problem (TSP) solver, widely acknowledged to be the best exact solver that delivers the results in a reasonable amount of time. Plotted over the SAPICS exhibition layout, we were able to quickly achieve a route of around 229m, allowing for a variance of 20m which allowed you to reach all of the stands.
Of course, applying something like the TSP to a real-world problem has its limitations. In the initial scenario, Concorde would cut across booth walls as it was the most efficient path. Assuming that you’re looking to make business acquaintances and forge partnership, barrelling through the booth walls would certainly harm those chances.
To solve this problem, we added nodes to the corner of booth groupings, which allowed Concorde to generate a more reasonable scenario. There is still some minor cutting across dining tables – discretion is advised and should you not wish to deviate from the most optimal route, consider tucking your name badge under your jacket.
At ten minutes on average, you are dedicated around 550 minutes over the course of two days. Add 25 minutes to gather lunch and you’re looking at a total of 10 hours of booth time.
Assuming a rational person would split their booth visits across the two days and that a conservative 45 minutes will be spent with additional bathroom breaks, getting drinks, running into acquaintances and walking to meeting venues, we are left with roughly only 2h15min to attend workshops on Monday and 3h15min on Tuesday. That’s only five workshops, six max.
Based on the above, and taking into account the level and duration of the presentations, we were able to generate two schedules: one that spaces out the stand visits and incorporates three shorter presentations and the expense of certain booths, and the second which has a priority on the exhibition booths.
In these instances, the window weightings for each schedule significantly alter the schedules generated. You can see the amount of time lost significantly increases when attempting to force every booth being visited.
If you have any comments or questions, please e-mail me at rick.de.klerk@opsi.co.za.
