How do I add vehicle specific speeds in the vehicle routing problem?

jsprit
1

Hi, I wanted to add vehicle specific speeds in the vehicle routing problem. I tried using maxVelocity but it doesn’t seem to be making a difference.

Thanks

1 Like
2

Hello, you need to use a VehicleRoutingTransportCosts which takes your maxVelocity into account somehow.

Use setRoutingCost of your VehicleRoutingProblem.Builder with your implementation of VehicleRoutingTransportCosts to override the default CrowFlyCosts. Here is an example with a slightly customized implementation, you can probably adapt it to your own needs.

double[][] distances = {{0, 1}, {1, 0}};
double[] portCallCosts = {1, 1};
double minutesToUndock = 10;
double minutesToDock = 10;

VehicleRoutingTransportCosts costMatrix = FastTransportCostsMatrix.Builder.newInstance(distances).setPortCallCosts(portCallCosts, minutesToDock, minutesToUndock).build();
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.setRoutingCost(costMatrix);

And here is my FastTransportCostsMatrix implementation of VehicleRoutingTransportCosts:
package shortcutoptimizer;

import jsprit.core.problem.Location;
import jsprit.core.problem.cost.AbstractForwardVehicleRoutingTransportCosts;
import jsprit.core.problem.cost.TransportDistance;
import jsprit.core.problem.driver.Driver;
import jsprit.core.problem.vehicle.Vehicle;
import jsprit.core.problem.vehicle.VehicleTypeImpl;

import java.util.Arrays;

/**
 * FastTransportCostsMatrix including port-call costs and un/docking times that allows pre-compiled distance-matrices
 * to be considered as {@link jsprit.core.problem.cost.VehicleRoutingTransportCosts} in the
 * {@link jsprit.core.problem.VehicleRoutingProblem}.
 *
 * Applies the Floyd-Warshall algorithm for solving the all-pairs shortest path problem (for weighted graphs) to ensure
 * that we use a metric distance matrix (hollow symmetric matrix with positive off-diagonal entries satisfying the
 * triangle inequality).
 *
 * @author Mikael Sand msand@abo.fi
 */
public class FastTransportCostsMatrix extends AbstractForwardVehicleRoutingTransportCosts implements TransportDistance {

    private static final double minutesPerHour = 60;
    private final double[][] matrix;
    private final double[] portCallCost;
    private final double minutesToUndockAndDockAgain;

    private FastTransportCostsMatrix(Builder builder) {
        portCallCost = builder.portCallCost;
        minutesToUndockAndDockAgain = builder.minutesSpentDocking + builder.minutesSpentUndocking;
        FloydWarshall fw = new FloydWarshall(builder.matrix);
        if (fw.hasNegativeCycle()) {
            throw new IllegalArgumentException("distance matrix cannot be made metric");
        }
        matrix = fw.distances();
    }

    private double get(int from, int to) {
        return matrix[from][to];
    }

    public double getDistance(int fromIndex, int toIndex) {
        return get(fromIndex, toIndex);
    }

    public double getDistance(Location from, Location to) {
        return getDistance(from.getIndex(), to.getIndex());
    }

    public double getDistance(Location from, Location to, double departureTime, Vehicle vehicle) {
        return getDistance(from.getIndex(), to.getIndex());
    }

    @Override
    public double getTransportTime(Location from, Location to, double departureTime, Driver driver, Vehicle vehicle) {
        int fromIndex = from.getIndex();
        int toIndex = to.getIndex();
        if (fromIndex < 0 || toIndex < 0)
            throw new IllegalArgumentException("index of from " + from + " to " + to + " < 0 ");

        if (fromIndex == toIndex) return 0;

        return minutesToUndockAndDockAgain + minutesPerHour * get(fromIndex, toIndex) / vehicle.getType().getMaxVelocity();
    }

    @Override
    public double getTransportCost(Location from, Location to, double departureTime, Driver driver, Vehicle vehicle) {
        int fromIndex = from.getIndex();
        int toIndex = to.getIndex();
        if (fromIndex < 0 || toIndex < 0)
            throw new IllegalArgumentException("index of from " + from + " to " + to + " < 0 ");

        if (fromIndex == toIndex) return 0;

        if (vehicle == null) return get(fromIndex, toIndex);

        double portCall = 0;
        if (portCallCost != null) {
            portCall = portCallCost[toIndex];
        }

        VehicleTypeImpl.VehicleCostParams costParams = vehicle.getType().getVehicleCostParams();
        return portCall + costParams.perTransportTimeUnit * getTransportTime(from, to, departureTime, driver, vehicle);
    }

    public static class Builder {
        private double[][] matrix;
        private double[] portCallCost;
        private double minutesSpentDocking;
        private double minutesSpentUndocking;

        private Builder(int noLocations) {
            matrix = new double[noLocations][noLocations];
        }

        private Builder(double[][] matrix) {
            this.matrix = matrix;
        }

        public static Builder newInstance(int noLocations) {
            return new Builder(noLocations);
        }

        public static Builder newInstance(double[][] matrix) {
            return new Builder(matrix);
        }

        public Builder setPortCallCosts(double[] portCallCost, double minutesSpentDocking, double minutesSpentUndocking) {
            this.portCallCost = portCallCost;
            this.minutesSpentDocking = minutesSpentDocking;
            this.minutesSpentUndocking = minutesSpentUndocking;
            return this;
        }

        public Builder addTransportDistance(int fromIndex, int toIndex, double distance) {
            matrix[fromIndex][toIndex] = distance;
            return this;
        }

        public FastTransportCostsMatrix build() {
            return new FastTransportCostsMatrix(this);
        }
    }
}

class FloydWarshall {
    private double[][] distances;
    private boolean negativeCycle = false;

    public FloydWarshall(double[][] graph) {
        int n = graph.length;
        distances = Arrays.copyOf(graph, n);

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);
                }
            }

            if (distances[k][k] < 0.0) {
                this.negativeCycle = true;
            }
        }
    }

    public boolean hasNegativeCycle() {
        return this.negativeCycle;
    }

    public double[][] distances() {
        return distances;
    }
}
3

What you require are vehicle dependent transport times/costs. You can implement it by implementing VehicleRoutingTransportCosts. Or you just provide several different vehicle dependent cost matrices.