If you're curious what the actual optimal Paris cost is, I suggest formulating the problem as an integer linear program and submitting it to Gurobi on NEOS [0]. Gurobi is arguably the strongest commercial ILP solver; big companies pay big dollars to use it to optimise schedules, industrial processes, etc. I'm not sure it could solve this problem to optimality in the 8 hours NEOS provides you, but it might -- KIRO has some similarities to the Vehicle Routing Problem, variants of which are very commercially important. In any case, Gurobi is a monster, and even if you don't get an exact solution, it will give you a lower bound (which may not be tight, but it's nonetheless interesting).

[0] https://neos-server.org/neos/