Algorithmic approaches to generating a timetable for a carpool of teachers

Question

In the hope that StackOverflow is the best place to ask such a question, I would like to ask the swarm intelligence for suggestions on the best possible algorithmic approaches to solve the following problem. As specific as it may seem, I feel that the approach to solving such and similar problems is universally valid.

The Problem

It is about creating a timetable for a carpool of employees who start and finish work at different times of the day, namely teachers with individual timetables. As simple as this may sound at first glance, the problem can quickly become abnormally complex when you consider:

• Anyone who drives on the way back must also have driven on the way there, otherwise the car for the return journey would be missing.
• On average, all participants should drive approximately the same number of times to be fair.
• Overall, as few drives as possible should be made in order to save costs.
• Cars traveling in the same direction at the same time should be evenly loaded.
• People board at different collection points; some collection points are on the route of people from other collection points (drive-by pick up possible), but not the other way round.
• People can also board at other (nearby) collection points if necessary, but they must get off at exactly the same collection point on the way back on the same day, for example to be able to pick up a bicycle parked there.
• Each person has a different number of free seats in their vehicle and can only take a corresponding number of other people with them.
• ...

Approaches

Off the top of my head, I can think of four ways to tackle the problem:

1. Naive approach. I try to implement all of the above constraints manually and imperatively by somehow mapping the individual trips and cars in a data structure and then iteratively filling them with people who fulfill certain properties. I then count the number of trips where each person is driving and then try to manually replace individual people who are used too frequently as drivers, only to realize that the problem becomes too complex for me at this point at the latest.
2. Brute force approach. I generate more or less random constellations of people and have hundreds of thousands of them generated in order to select the least bad constellation. This costs time and electricity, is not optimal and certainly does not meet any algorithmic requirements.
3. Evolutionary algorithm. This works in the same way as the brute force approach, but in a more targeted way, in that the most successful parts of the generated timetable are combined to create an even better timetable. The problem here is that the question is so complex that I can no longer imagine how I should represent it with population, genome and gene. Is there such a thing like a multi-layered evolutionary algorithm?
4. AI. The solution for everything, of course. The problem here is that I don't have nearly enough examples for training an AI. I only have two or three manually created timetables to hand. I can hardly use them to train a neural network to generate a new timetable from a given set of data.

I'm a computer scientist by profession, but I'm really at a loss here: Is there a "classic" approach to such a problem that you would "naturally" use - or is there a concrete approach for one or the other of my ideas on how to proceed? Thank you for sharing my headache!

Answer 1

This is a particular case of the 'assign agents to tasks in timeslots with specified constraints'

The approach depends on what your purpose here is. There are two categories of purpose:

1. Computer scientist wants to develop an optimal algorithm which is guaranteed to provide the best possible answer for all cases, no matter how unrealistic.

2. Software engineer wants to develop an algorithm that will provide a decent answer in most normal cases without too much complexity.

Which are you?

If you are #1 then you are in the wrong place.

If you are #2 then we can discuss your particular constraints and I can adapt my code for your case.

The collection points you mention actually make this two problems. First you need to assign agents to collection points, which will be a graph theory problem. Once that is achieved, you can look at the assignment problem, where the collection points are modelled by a constraint that some people can only be assigned to a subset of the tasks ( i.e. the rides that service the pickup point that agent is assigned to. )

Some definitions

• Shift: a pair of times e.g. 8am and 4pm, or 9am and 5pm
• Agent: a pair, one shift and one collection point.
• Task: pick up all the agents that share the same shift and collection point

The problem now becomes rotating the driving assignment among the agents assigned to a task.

I do not think you have provided enough information to give any advice on assigning agents to collection points. As a first pass, maybe you could do that manually?