GraphHopper.com | Forum | GitHub | Maps | Blog

Lower cost for the distribution of orders based on the maximum time of delivery and that are distributed among all available vehicles.


#1

I need to provide the lowest cost solution for the distribution of orders based on the maximum delivery time and that they are distributed among all available vehicles.

I have the following problem, “Orders 1” and “Order 4” are very close, in which case a vehicle could take both orders.

But I can not find the solution for that.

with that I did this algorithm. Could someone guide me to solve my problem?

private static final int TEMPO_MAXIMO_MOTOBOY = 137;

//TipoVeiculo.setFixedCost()
VehicleType type = TipoVeiculo.Builder.newInstance(“type”)
.addCapacityDimension(0, 50)
.setCostPerTransportTime(1)
.setFixedCost()
.build();

	VehicleType type = TipoVeiculo.Builder.newInstance("type")
		.addCapacityDimension(0, 50)
		.setCostPerTransportTime(1)
		.setFixedCost()
		.build();

Location.Builder builderInicio = Location.Builder.newInstance();
builderInicio.setId(“0”);
builderInicio.setCoordinate(coordenadas[0]);
Location inicio = builderInicio.build();

	//TipoVeiculo.setFixedCost()
	VehicleType type = TipoVeiculo.Builder.newInstance("type")
		.addCapacityDimension(0, 50)
		.setCostPerTransportTime(1)
		.setFixedCost()
		.build();
    
VehicleImpl vehicle1 = VehicleImpl.Builder.newInstance("Veiculo 1").setEarliestStart(0).setLatestArrival(TEMPO_MAXIMO_MOTOBOY).setStartLocation(inicio).setType(type).build();
    VehicleImpl vehicle2 = VehicleImpl.Builder.newInstance("Veiculo 2").setEarliestStart(0).setLatestArrival(TEMPO_MAXIMO_MOTOBOY).setStartLocation(inicio).setType(type).build();
    VehicleImpl vehicle3 = VehicleImpl.Builder.newInstance("Veiculo 3").setEarliestStart(0).setLatestArrival(TEMPO_MAXIMO_MOTOBOY).setStartLocation(inicio).setType(type).build();
    VehicleImpl vehicle4 = VehicleImpl.Builder.newInstance("Veiculo 4").setEarliestStart(0).setLatestArrival(TEMPO_MAXIMO_MOTOBOY).setStartLocation(inicio).setType(type).build();
    List<VehicleImpl> veiculos = new ArrayList<VehicleImpl>();
    veiculos.add(vehicle1);
    veiculos.add(vehicle2);
    veiculos.add(vehicle3);
    veiculos.add(vehicle4);
	
    List<Service> services = new ArrayList<Service>();
    VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
    
    for(int i = 0; i < coordenadas.length; i++) {
    	
    	if(i > 0) {
    		Service.Builder<?> sb = Service.Builder.newInstance(i + "").addSizeDimension(0, 1)
    				.setLocation(Location.Builder.newInstance().setId(i + "").setCoordinate(coordenadas[i]).build())
    				.addTimeWindow(TimeWindow.newInstance(0, Double.MAX_VALUE));
        	services.add(sb.build());
    	}
    	
    	for(int j = i + 1; j < coordenadas.length; j++) {
    		double distancia = getDistance(coordenadas[i], coordenadas[j]);
    		int tempo = (int) getTimeInSecondes(distancia);
    		costMatrixBuilder.addTransportTime(i + "", j + "", tempo);
    		//costMatrixBuilder.addTransportDistance(i + "", j + "", distancia);
    		
    		System.out.println("Tempo de " + i + " até " + j + ": " + tempo + " segundos");
    	}
    	
    }
    
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance().setFleetSize(FleetSize.FINITE)
    		.addAllVehicles(veiculos)
    		.addAllJobs(services)
    		.setRoutingCost(costMatrixBuilder.build())
    		.build();
    
    VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp)
        .setProperty(Jsprit.Parameter.FAST_REGRET, "true")
        .setProperty(Jsprit.Parameter.THREADS, "5")
        .setProperty(Jsprit.Parameter.FIXED_COST_PARAM, "1")
        .buildAlgorithm();
    
    Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();
    
    VehicleRoutingProblemSolution solution = Solutions.bestOf(solutions);
    
    SolutionPrinter.print(vrp, solution, SolutionPrinter.Print.VERBOSE);
    
    new GraphStreamViewer(vrp, solution).setRenderDelay(100).labelWith(Label.ID).display();
}

private static double getTimeInSecondes(double distance) {
	return distance * 0.072;
}

private static double getDistance(Coordinate c1, Coordinate c2) {
	
	final int R = 6371;

    double latDistance = Math.toRadians(c2.getY() - c1.getY());
    double lonDistance = Math.toRadians(c2.getX() - c1.getX());
    double a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2)
            + Math.cos(Math.toRadians(c1.getY())) * Math.cos(Math.toRadians(c2.getY()))
            * Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2);
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    double distance = R * c * 1000;
    return distance;
}

}