How to set multiple objectives

Currently the objective functions in jsprit use only one double cost. Is it possible to set more than one objectives?

In our case, each vehicle’s fixed cost could cover, for example, 100km transport distance. When beyond 100km, it will cost more. We want of course firstly minimize the transport cost. But when a vehicle’s distance is already less than 100km, we also want to minimize its transport distance (this will not affect cost). Is there any way to accomplish this goal?

I saw that graphhopper’s route-optimization API supports multiple objectives, is it implemented with jsprit? How?

You don’t need multiple objective here, all the objectives can be converted into cost and Jsprit will try to minimize the total cost.

In your case you need to define custom SolutionCostCalculator.

1 Like

Is it possible to “compress” all objectives into one single double value?

For example if I’d like to use # of vehicles as the first objective, routing costs as the second objective, how could I convert tuple [# of vehicles, routing costs] into one double value?

I know that there is fixed costs for each vehicle, but it’s not the same with letting # of vehicles to be the first objective.

As you must have seen in SolutionCostCalculator it takes solution as input and returns double total cost.

You can use all the properties of solution to define your cost function.
e.g: For getting total number of vehicles you can use,
cost += solution.getRoutes().size();

But min{#ofVehicles + routingCost) is not equivalent to min{[#ofVehicles, routingCost]} …

What is your exact objective? Your total cost should be sum of many component and Jsprit will try to minimize it.

Multiple objectivities means that the first objective value must be smallest whatever the values of the latter ones. If two solutions’ first objective value are the same, compare their second objective values.

Say, if our objectives are 1: # of vehicles, 2: routing cost, and there are 3 available solutions, their objective values are:

  • solution 1: 10 vehicles, cost 500
  • solution 2: 9 vehicles, cost 510
  • solution 3: 9 vehicles cost 550

The best one should be solution 2, because it has smaller # of vehicles than solution 1, and smaller cost than solution 3.

I cannot use # of vehicles + routing cost as the objective, which will cause solution 1 to be the best one.

==

The real case in our problem is that we have a fixed cost for each vehicle, say $300. This fixed cost could cover 60km of routing distance. If a vehicle runs more than 60km, it will cost $10 for each addition km.

Our first objective is to minimize the cost, of course. If the cost are the same, we prefer the smaller distance one.

Take 3 solutions for example:

  • s1: vehicle 1 runs 93km; total cost $630, total distance 93km
  • s2: vehicle 1 runs 50km, vehicle 2 runs 50km; total cost $600, total distance 100km
  • s3: vehicle 1 runs 40km, vehicle 2 runs 55km; total cost $600, total distance 95km

s3 will be the best one because it has lower cost than s1; and comparing to s2, its total distance is smaller.

perhaps related?

as you have noticed, you can assign a fixed cost to each vehicle (type), but it does not guarantee that you get the least number of vehicles.

just quote stefan’s answer:

Reducing the # of vehicles is just one special case of multiple objectives. Using fixed cost is one method of compressing # of vehicles and routing cost into a double value.

If the cost calculator returns a user defined Comparable object (could default to Double, which implements Comparable interface), it can simply solve the # of vehicles issue or multiple objectives issue. User can just define his own cost class, which containing all objective values, and define his own comparison method.

public class MyCost implements Comparable<MyCost> {
  private int noVehicles;
  private double routingCost;
  public int compareTo(MyCost other) {
    // compare noVehicles first, then routing Cost
  }
}

public interface SolutionCostCalculator {
  public Comparable getCosts(VehicleRoutingProblemSolution solution);
}

public class DefaultSolutionCostCalculator implements SolutionCostCalculator {
  public Comparable getCosts(VehicleRoutingProblemSolution solution) {
    return (Double) routingCost;
  }
}

public class MyCostCalculator implements SolutionCostCalculator {
  public Comparable getCosts(VehicleRoutingProblemSolution solution) {
    return new MyCost(noVehicles, routingCost);
  }
}