Difficult algorithm (pseudo code accepted)

I am trying to write a program to solve a “simple” transportation problem and would aprreciate your ideas on how to code it

every week about 35 people come at meet at one place

many come by public trasportation, so usually there are only about 9 cars
could be pickup, could be small car, could be van

we need to split the people groups of about 4 but not exceeding the number of cars (e.g 9) (its ok to have extra cars)

They will go to different neighborhoods and visit and invite people to become part of the group

at least one “trainer” needs to be with each group

there are a ton of factors in deciding the groups
age
sex
married
has car
skill level
istrainer
spousepresent
mustgowith(x person)

etc, and I need to have control over the results, like saying I want these 3 to go together and let the program figure the rest etc
what kind of algorithm am I looking for?
do I start with the cars and fill in randomly then search for errors?, (such as married woman and unmarried man alone in pickup) or (all newbies) (or 4 older men and 1 young girl) etc

or

do I start paring people up and look for a driver

etc. What approach should I be taking?

it is not polynomial, so the only way is to give every combination a value ie certain rules to classify a value for a combination,
for example, Trainer is missing means 100 points less value, and go through all combinations and find the highest value.

There ist just a little chance of optimizing like branch and cut-algorithm.

thanks flashnfantasy, I hadn´t considered the brute force chess approach :slight_smile: somethings we do naturally in real life seem so simple til you try to code them.
I´ll start working on the point system

Anyone else got another way?

I think your best option is to create a variety of classes.

ie a vehicle class & people class. The vehicle class will probably need to be encapsulated into the people class as some will own a vehicle.

Afterwards right up a variety of Rules that the program must follow based on each objects variables. Once done place them in the most appropriate group, for example if they are aged 12 you would place them in a temporary category named “child”. Do this with the rest and you should have a variety of category’s. Once there in appropriate category’s.

You can then create a new set of Rules that will then put them in there final group for each car.

Thought the easiest solution would be to allow the people to choose which group they want to be in.

:smiley: yeah, really. but well, if youve ever actually tried to get a group of people to do that, you find it will take them quite a bit longer than if you just tell them what to do.

Thanks for the idea, I was personally planning on something more like you said, categorizing and placing according to rules.

Does anyone have a physics based solution? I was thinking that theres probably some way to represent this physically, where the pieces would have some shape or property based on attributes and certain rules would make the pieces sort of “fall” into place. Trainers attract newbies and older men repel young girls except when bound by family, cars attract already formed groups, but once they are full, other pieces just bounce off and settle in another one etc. I am just crazy or is that a reasonable idea (admittedly not the most efficient, but if it works it could be awsome, and even visualized with the blender game engine. :spin::smiley: Anybody ever done that kind of algorithm?

Combinatorial optimisation with no clear maxima? Genetic algorithms. Or, a fast evo approach like simulated annealing.

You will need to come up with a way of scoring the combination of people, and a representation. For the first part, penalties for bad mixes (old men + young girls = -1) will do most of the work, and just define a series of absolutes for required things (e.g. these two must be together).

A physics based approach would be to do a dampened newtonian simulation where people attract & repel each other, but groups repel when they reach a max size. Then you run it and see how many clusters you get.

Brute force? EEP! Combinatorial problems are NP-hard & complete, but they often have fairly nice search spaces, as long as your geno-pheno mapping is sensible (or search representation, whatever method you want to use).