Minimize sum travel time for each employee

Hello all,

We are trying to use Jsprit for employee pickup/dropoff with the goal of minimising sum of travel time of individual employees.

For example lets say we have

  1. base location
  2. employee1 - 2 kms from base
  3. employee2 - 5 kms from emp1
  4. employee3 - 10 kms from emp2 and 15 kms from base

If all the employees need pickup from their homes to base, Jsprit randomly gives any of these 2 possibilities – clockwise (base-emp1-emp2-emp3-base) and anti-clockwise (base-emp3-emp2-3mp1-base). Lets say both the routes are equidistant (roads are two-way)

Clockwise Route
base -> emp1 -> emp2 -> emp3 -> base – in this solution

car runs empty for base-emp1 which is 2 kms
emp1 spends 5+10+15 = 30 kms in car
emp2 spends 10+15 = 25 kms in car
emp3 spends 15 kms in car

Total distance travelled by the car (2+5+10+15 = 32 kms)
Sum of KMs (hence time) spent in the car by employees = 70 and empty run = 2km

Anti-clockwise Route
base -> emp3 -> emp2 -> emp1 -> base – in this solution
The car run empty for base-emp3 which is 15 kms
emp3 spends 10 + 5 + 2 = 17 kms in car
emp2 spends 5 + 2 = 7 kms in car
emp1 spends 2 kms in car

Total distance travelled by the car 15+10+5+2 = 32 – same as above
Sum of KMs (hence time) spent in the car = 26 and empty run = 15 km

Obviously the second solution (anti-clockwise) is better solution as employee time spent is less (26 vs 70) even though the car travels the same distance (32)

What we are noticing is that jsprit is not consistent and outputs any of the above solutions as it thinks both routes have the same cost.

Since we are solving the problem for close to 200 employees with 50-70 cars, we can not just define soft-constraint for close-by employees.

Seems like we need another cost matrix which is not tied to vehicle but tied to the Job travel time


Hi @akmits,

Probably you can learn a thing or two from #261. It sets a hard constraint on the max in-vehicle time.

For your case, you can reuse the state updater. Regarding the constraint, you will need a soft activity constraint to impose costs that are associated with in-vehicle time. Lastly you will need a custom objective function in which you add the costs that are associated with in-vehicle time.

Hopefully the above helps.

Best regards,

1 Like

Thanks for pointing to it.
I think this should work.
much appreciated