-2

Edit: I had to specify this question. Originally I wanted to discuss different algorithmic approaches. But now I want to ask specifically how an evolutionary algorithm would have to be designed to solve the problem.

The Problem

It is about creating a timetable for a carpool of employees who start and finish work at different times of the day. The best example of this is probably teachers who have very individualised daily working hours. 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.
  • ...

The Approaches

Different solutions sound promising at first glance, but all have moderate to serious shortcomings. For example, off the top of my head, I can think of four ways to tackle the problem:

  1. Naive approach. 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.
  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.
  3. AI. The solution for everything, of course. The problem here is that I don't have nearly enough examples for training an AI.
  4. Evolutionary algorithm. This is my choice.

As far as I know, an evolutionary algorithm 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 problem is so complex (find an optimal driver, an optimal vehicle crew, create an optimal day of the week, an optimal week and make sure that all people drive with similar frequency, ...) that I cannot imagine how I should represent it with just population, genome and gene. Is there such a thing like a multi-layered evolutionary algorithm? Hoping for your help.

The Question

How can I solve this problem with the help of an evolutionary algorithm? More precisely: How do I map people, vehicles, days of the week to genes, genomes and populations?

Improve this question
3
  • 1
    Welcome to Stack Overflow. I think your question is too broad. Questions that ask for general guidance regarding a problem approach are typically are not a good fit for this site. Split your task into smaller ones and start working on them. And ask particular questions related to particular issues you encounter. Here's how: how-to-ask Commented Feb 4, 2024 at 15:25
  • "On average, all participants should drive approximately the same number of times to be fair." << If this takes place over many days, it shouldn't be too much of a problem. You could keep an accounting sheet of who has driven whom how much, just like roommates keep an accounting sheet of who has paid the pizzas for whom how much. Then whenever you have to choose between two drivers A and B, pick the driver who has the least positive balance, and update the accounting sheet accordingly. Commented Feb 4, 2024 at 18:49
  • I agree that your question is too broad. You are also asking readers to help flesh out your question, not just provide answers. For example, you say, "On average, all participants should drive approximately the same number of times to be fair." It's your job, not ours, to decide what is "fair". To be helpful to you we need something like, "The maximum number of hours driven per week by any driver cannot be more than 30% greater than the hours driven per week by the driver who drives least." or some-such. Also, you are trying to re-invent the wheel. Try googling "carpooling software". Commented Feb 5, 2024 at 5:20

1 Answer 1

Reset to default
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?

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I thought you were going to say, "If you are #1 then you are in the right place."¯\_(ツ)_/¯. (Finding an optimum for this problem is clearly out of the question, however.) #2 falls under "heuristics", which are only interesting when a bound can be product that shows the maximum amount by which the measure one would like to optimized differs from the optimum (which doesn't apply here either). Otherwise, there's no way of knowing how "good" a proposed heuristic is so I don't see a place for that here.
@CarySwoveland "only interesting" Interesting use of the word 'interesting'. Why be so dismissive of what you call 'heuristics'? That is how many problems in the real world are tackled. I myself have built applications to solve, in the real world, many problems similar to this one, using the techniques I describe in my answer.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.