8

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.

  • 1
    Shouldn't the driver be part of the group? From your description it sounds like he/she's just driving the car. Are drivers just dedicated drivers or are they part of the workers? – null Aug 13 '15 at 12:12
  • 3
    I would say you are just plain going about it wrong. The basis of the algorithm should be to fill up every vehicle but the the last. Fixed group size it a big hole in this optimization. – paparazzo Aug 13 '15 at 14:56
  • 1
    Might be a good idea to look at the literature around the "fleet size and mix vehicle routing problem" which is as far as I can tell the problem that you are trying to solve – Renaud M. Aug 17 '15 at 10:12
  • 1
    @russellhoff I do not know about JaCoP, but you would probably want to give a try at OR-tools. It is another CP solver, that has a Java API (given the libraries that you are listing it seems to be important), which seems to provide some "specialization" for vehicle routing problems. If you give a look at the examples that they provide you can probably find something that you can adapt (you can also give a look at developers.google.com/optimization/routing/tsp) – Renaud M. Aug 24 '15 at 14:09
  • 1
    "TSP (Travelling Salesman Problem) algorithm" -- I'm not aware that there is a specific algorithm for solving TSP. AIUI, the most common solution is simulated annealing, but there are other approaches too, I believe... – Jules Jul 13 '16 at 8:04
2

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...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.