Algorithms – Grouping Algorithm Techniques

algorithms

We've developed an algorithm that depending on the check-in time of some workers and their living place, calculates the way to group them into some vehicles and the route which must be followed by the vehicles to carry them to the workplace. This has been accomplished using the TSP (Travelling Salesman Problem) algorithm and some other customisation.

We want to go beyond and improve it. For the time being, vehicles' seats capacity are fixed to 4 (5 places but one occupied by the driver) and we want to make this amount "variable". In other words, we want to, prior to the execution of the main algorithm, determine the combinations of vehicles (and their free seats) which may be needed. It is important to know that when I speak of vehicles, I speak about types of vehicles, e.g. Vehicle A is of 4 seats, Vehicle B is of 7 seats, and so on. So I'm not talking about having one Audi A8 of 5 seats, Seat Ibiza of 5 seats, one Bus of 20 seats, say.

So far, what I've thought up is the following:

  1. Determine workers' groups.
  2. Determine how many vehicles will be needed and their (free) seats. That's what I'm asking in that question [a].
  3. The user selects the preferred combination and goes on.
  4. Apply the algorithm which is already developed using the combination of vehicles and see whether it reaches a feasible solution.

My question is how to develop the [a] algorithm. The following example will show you the result of the execution of [a]:

Imagine we have the following people to group into vehicles of 4, 7, 10 seats free.
enter image description here

After the execution of [a], we will have as a result:

  • G3 (2 workers): One vehicle of 4 seats free (vehicles with more seats free are discarded).
  • G2 (2 workers): one vehicle of 4 seats free (vehicles with more seats free are discarded).

  • G1 (9 workers):

    • Option A: 3 vehicles of 4 seats.
    • Option B: 1 vehicle of 4 seats and another one of 7.
    • Option C: 2 vehicles of 7 seats.
    • Option D: one vehicle of 10 seats.

I've thought of an approximation:

  • Create the types of vehicles and add them to a sorted list (sorting criterion must be the seats).
  • For each group of workers, do:
    • Calculate combinations [b].
  • Print results on screen.

So the main problem is how to develop [b].

Any suggestions? Sorry if I've explained myself badly.

Best Answer

I've come up with a possible solution: make use of Constraint Satisfaction Problem to solve it.

There will be one constraint per Group, as follows:

workers amount of the group <= sum per each vehicle(vehicle amount X vehicle's seats)

The only variable there is the vehicle amount, the rest are constants. So, in my example there would be the following contraints:

9 <= 4x + 7y + 10z
2 <= 4a + 7b + 10c
2 <= 4j + 7k + 10i

I found several libraries (JaCoP, Drools and OptaPlanner), and I'm currently using the first one. But I don't know how to define these constraints properly...

Related Topic