Random search heuristics and motor ships

Published on August 18, 2012

Random search heuristics and motor ships

    Once upon a time I wrote a rather large article on the use of heuristics in programming , but today I want to give a small practical example. This summer I sailed on a ship on the route Moscow - Rostov-on-Don - Moscow, and noticed that every evening the cruise director tries to find the best seating arrangements for tourist groups by bus. The task is not so difficult, but at least 15 minutes a day is spent on its solution. Of course, I tried to automate this process.
    But, before describing my solution, it is necessary to more accurately formulate the problem. At the very beginning of the cruise, all tourists were divided into several excursion groups (in this case there were 15 groups), while in each group there were no more than 10 people. All groups were numbered in order, and the resulting list of groups did not change until the very end of the cruise. This list looked something like this:
    Every day, tourists inform the cruise director about what excursions they plan to go. Everyone who does not plan to go on the main tour is deleted from this list. It is with a modified list that we have to work. The cruise director considers how many people go on an excursion (usually 100-120 people) and makes an appropriate order for buses. Travel agencies on the shore accept this order and report the following information: "On the pier, you will find three buses with 48, 48 and 50 seats." As a result, the task is as follows: it is necessary to seat tourists on buses, observing the following requirements (in order of importance):
    1. Do not break up groups;
    2. Fill the buses as evenly as possible;
    3. It is advisable that groups sitting on the same bus go in a row. Those. the first bus - groups 1-5, the second bus 6-10, etc.
    The first step towards automation was made using Excel and the add-on “Solution Search” (to my surprise, very few people know about this setting, although the thing is incredibly useful).
    The first requirement, of course, was fulfilled, but the second and third requirements had to be forgotten. Given that the search for a solution took about 15 seconds on an old laptop, it was decided to write your bike. But here again the question arose, how to do all this: simplex method, dynamic programming, branch and bound method, heuristic? Surely there is some kind of complex algorithm that will help in solving this problem, but to write something difficult on vacation, and then debug it on a laptop with a small screen? I decided to try some kind of heuristic. I immediately postponed the ascent to the hill after a little thought, as well as the heuristics of minimum cost and balanced profit.
    And then I remembered the random search heuristic. To be honest, I had never used it before, and was pretty sure that a random search would not lead to an effective solution. But curiosity prevailed. As a result, the following seating algorithm was obtained:
    1. Choose a random group and a random bus
    2. Check if we can put the selected group in the selected bus (see if this group is sitting in another bus, and if there are enough seats)
    2.1. If we cannot, then we increase the counter of unsuccessful attempts by one
    2.2. If we can, we will reset the counter of unsuccessful attempts
    3. If the number of unsuccessful attempts has exceeded 50, we exit the loop, otherwise go to step 1
    4. Check if all groups are seated
    4.1. If that's all, calculate the maximum difference between the number of empty seats in buses (this number will be considered an estimate)
    4.2. If not all, report unsuccessful seating arrangements.
    Performing this procedure hundreds of times, we can choose the best-rated seating plan. This algorithm worked surprisingly well. At least the first and second paragraphs of the requirements were met perfectly.
    To fulfill the third point, a small change is necessary in the algorithm. Even before the start of the seating algorithm, we will plant 5 groups in each bus (1-5,6-10,11-15), and perform the seating. If she succeeded, we remember the best score, and the result is displayed. Then we try to put 4 groups in each bus (1-4, 5-8, ...), and again we perform seating. If the obtained estimate turned out to be better than it was at the previous stage, remember it and again display the result. Then we try to put in the bus initially 3 groups, 2, 1 each, and, finally, we perform the seating procedure without any preliminary information. If at some stage, the assessment has improved, the resulting solution is displayed.
    Actions, of course, are carried out more, but the value of the results obtained is much higher. In the end I will give a small example of the program:

    It is clear that most of you already know about the random search heuristic, but suddenly this post was read by people who do not know about it, or were afraid to use it for some reason. I hope that now, having learned this heuristic a little better, you can at least slightly simplify the solution of some of your problems.