Search code examples
c#algorithmbrute-forcetraveling-salesmanrostering

Today's algorithmic challenge

I'm currently working on an algorithm to schedule pub-crawling (it can be much more generic applied, though). This is what is known:

  • There is a certain number of teams and bars, the amount of teams never exceeding the amount of bars
  • The teams must visit all bars
  • The teams cannot be at the same bar at the same time
  • The whole process is temporal; teams are at the bars in the same discrete time intervals between the starting and ending time of the pub-crawl.

I'm thinking of this as a mix between the travelling salesman problem and some roster planning, but right now I've tried to implement it using brute force since I can't figure how to implement the mentioned mix. What I expect the result could look like:

Expected result

Brute force is working, but it's simply too slow. When all rows and columns are unique, a solution is found - just like Sudoku. The numbers can then be mapped to time intervals/arrival and departure time of specific bars. I'm looking for ideas and suggestion, but an implementation is very welcome as well (C#).

At the moment I'm brute forcing by doing:

  • Initializing a 2D array with as many rows as teams and columns as bars. The values are initialized as well ranging from 1-columns.
  • Checking whether the array is a solution, if not: Shuffle the array and check again.

Lastly, I need to mention that when this can be done fast enough one more layer of complexity will be introduced. The chosen route for a specific team must be optimal meaning that all groups must take the most optimal routes in regard to travel time - to do this I'll use the Google Maps API. I guess if this first part of the algorithm is relatively fast the distance optimization can be brute forced.

Looking forward to creative solutions!

Solution

  • Seems like you should solve the optimal route problem first. If you do that, then you can start the first team at the first bar in the solution, second team at second bar, etc., just as you did in your example.

    So if you determine the optimal (or almost optimal) path through the bars is B4,B3,B1,B2,B6,B5, then you just rearrange the order of bars in your table header to match. So during the first time period, team 1 would visit bar 4, etc.