How to improve overall execution time

Hello,

I am trying to solve a problem with 1500 shipments and 20 vehicles (with same vehicle type) with 36 threads. The total time taken was - 8853.256 seconds (More that 2 hours)

PFA log below :
> 2017-04-04 10:46:30 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.problem.VehicleRoutingProblem.(VehicleRoutingProblem.java:596).{39}:596] : setup problem: [fleetSize=FINITE][#jobs=1500][#vehicles=20][#vehicleTypes=1][transportCost=com.graphhopper.jsprit.core.util.VehicleRoutingTransportCostsMatrix@5b6c11f2][activityCosts=com.graphhopper.jsprit.core.problem.cost.WaitingTimeCosts@4fc9b295]
2017-04-04 10:46:37 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm.searchSolutions(VehicleRoutingAlgorithm.java:194).searchSolutions{39}:194] : algorithm starts: [maxIterations=100]
2017-04-04 10:46:37 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.InsertionInitialSolutionFactory.createSolution(InsertionInitialSolutionFactory.java:52).createSolution{39}:52] : create initial solution
2017-04-04 10:47:44 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm.searchSolutions(VehicleRoutingAlgorithm.java:202).searchSolutions{39}:202] : iterations start
2017-04-04 10:47:44 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm$Counter.incCounter(VehicleRoutingAlgorithm.java:79).incCounter{39}:79] : iterations 1
2017-04-04 10:48:24 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm$Counter.incCounter(VehicleRoutingAlgorithm.java:79).incCounter{39}:79] : iterations 2
2017-04-04 10:50:06 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm$Counter.incCounter(VehicleRoutingAlgorithm.java:79).incCounter{39}:79] : iterations 4
2017-04-04 10:53:51 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm$Counter.incCounter(VehicleRoutingAlgorithm.java:79).incCounter{39}:79] : iterations 8
2017-04-04 11:02:46 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm$Counter.incCounter(VehicleRoutingAlgorithm.java:79).incCounter{39}:79] : iterations 16
2017-04-04 11:20:06 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm$Counter.incCounter(VehicleRoutingAlgorithm.java:79).incCounter{39}:79] : iterations 32
2017-04-04 11:58:56 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm$Counter.incCounter(VehicleRoutingAlgorithm.java:79).incCounter{39}:79] : iterations 64
2017-04-04 13:14:10 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm.searchSolutions(VehicleRoutingAlgorithm.java:219).searchSolutions{39}:219] : iterations end at 100 iterations
2017-04-04 13:14:10 - [INFO] [Executor-9] [com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm.searchSolutions(VehicleRoutingAlgorithm.java:222).searchSolutions{39}:222] : took 8853.256 seconds

Could you please tell me if this is expected time or i am doing something wrong here.

1 Like

Can anyone tell me if i am thinking right or please point in right direction here.

Thanks!

if possible, maybe try dividing the problem into a few smaller problems? For example, divide the region into, say, 5 zones, each zone with a few hundred shipments and a few vehicles, and call jsprit to solve for each of them.

@koradeprashant Stuck in same problem now. Have you solved how we can decease the solving time. If yes, please share.
Thanks

Are you using FastVehicleRoutingTransportCostsMatrix or VehicleRoutingTransportCostsMatrix?

@Bhoumik_Shah - FastVehicleRoutingTransportCostsMatrix. If you use “Service” then its faster but its comparatively slow with “Shipment”.

@Rahul_kumar -

  1. Use FastVehicleRoutingTransportCostsMatrix.
  2. Try to use Service instead of Shipment. (only if you can)
  3. Try to divide the problem into few smaller problems. As suggested by @jie31best in the previous comment.

I have been stuck with the same problem as well
Please check the Iterations for the search , i have reduced mine from 2000 to 50, it obtained an accurate result as intended

# step  solving the algorithm through running

# get the algorithm out-of-the-box.
algorithm = Jsprit.createAlgorithm(vrp);

# Print the solution progress as function of the iteration, added before the solution
algorithm.getAlgorithmListeners().addListener(AlgorithmSearchProgressChartListener(os.path.join(config.OUTPUT_DIRECTORY, "solution_progress.png")))

# and search a solution which returns a collection of solutions (here only one solution is constructed)
# Set the maximum number of iterations
algorithm.setMaxIterations(20)


#solve the vehicle routing algorithm
solutions = algorithm.searchSolutions();


# Retrieve the best solution
bestSolution = SelectBest().selectSolution(solutions)

Also, can anybody tell me how can i select a specific algorithm instead of choosing best of(VRP) in the code
I appreciate your help and sorry for any inconvenience caused

TLDR; You cannot.

First thing you must undestand is you solve heuristic problem. Even if this is meta-heuristic solver. There is no final solution, the problem cannot be solved at deterministic time. So what JSprit does is, it try to search through defined space and by ruin-and-recreate method find sub-optimal solution. The rule here is more computation time equals better results. So if your problem contains 1500 shipments and 20 vehicles, 2 hours might be even less then needed for good result. The complexity even increase if there is more then one source location. I have 20_000 iteration as base and using PrematureAlgorithmTermination to stop interations.

So question is what is more important to you. Computation time or result quality?

If time is main objective, you can use com.graphhopper.jsprit.core.algorithm.termination.TimeTermination and set max time you want to provide algorithm to search space

But if main objective is better solution, then you should use another termination which watch solution score

Decrease interation count isn’t way to go, becase if you have large problem, there wont be much iteration and result will be worse. But for smaller problem, algorighm will be faster and make more iteration thus find better solution.

So my advice is set iteration count to high, very high. Start with 2k-4k, even 10k is good and choose right termination algorithm based on time or score.

I even develop own termination algorithm which is balancing between score, progress of iterations, and variation of last several scores.