Heterogeneous Fleet

This example covers

• illustrating different problem types,
• specifying heterogeneous fleet with its vehicles and vehicle-types,
• specifying the algorithm
• benchmarking the algorithm

Specifying the problem

Penna et al. (2013) distinguish 5 types of VRP dealing with heterogeneous fleet.

FSMD - Fleet Size and Mix with Dependent costs

FSMF - Fleet Size and Mix with Fixed costs

FSMFD - Fleet Size and Mix with Fixed and Dependent costs

HVRPD - Heterogeneous Vehicle Routing Problem with Dependent costs and finite (limited) fleet

HVRPFD - Heterogeneous Vehicle Routing Problem with Fixed and Dependent costs and finite (limited) fleet

Generally, Fleet Size and Mix (FSM) is applied on tactical level to design a vehicle fleet, whereas HVRP is applied on operational level to employ existing vehicles/fleet as efficient as possible.

Assuming you know the basics of jsprit, implementing these types is fairly straightforward. Basically, you specify these types with the VehicleRoutingProblem.Builder and a specification of different VehicleType(s).

Lets assume a single depot @(40,40) and the following 3 vehicle types:

vehicleId	capacity	fixed costs	variable costs	#vehicles
1	120	1000	1.0	2
2	160	1500	1.1	2
3	300	3500	1.4	1

To implement the above problem types you need to code:

FSMD

/*
 * build the types and vehicles from table above 
 * here it is assumed the variable costs are dependent on distance (rather than time or any other measure)
 */
VehicleTypeImpl vehicleType1 = VehicleTypeImpl.Builder.newInstance("type1").addCapacityDimension(0,120).setCostPerDistance(1.0).build();
VehicleImpl vehicle1 = VehicleImpl.Builder.newInstance("vehicle1").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType1).build();
VehicleTypeImpl vehicleType2 = VehicleTypeImpl.Builder.newInstance("type2").addCapacityDimension(0,160).setCostPerDistance(1.2).build();
VehicleImpl vehicle2 = VehicleImpl.Builder.newInstance("vehicle2").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType2).build();
VehicleTypeImpl vehicleType3 = VehicleTypeImpl.Builder.newInstance("type3").addCapacityDimension(0,300).setCostPerDistance(1.4).build();
VehicleImpl vehicle3 = VehicleImpl.Builder.newInstance("vehicle3").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType3).build();
//Use VehicleRoutingProblem.Builder to specify the problem
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addVehicle(vehicle1).addVehicle(vehicle2).addVehicle(vehicle3);
//set fleetSize to FleetSize.INFINITE (which you actually do not need to set since it is the default option)
vrpBuilder.setFleetSize(FleetSize.INFINITE);
//add jobs as you know it from SimpleExample and build the routing problem
...
VehicleRoutingProblem vrp = vrpBuilder.build();

FSMF

The only difference to the FSMD is that you specify fixed costs rather than distance-dependent costs such as

/*
 * Still you probably want to somehow consider variable distance costs, thus distance-costs are equally set
 * to 1.0 (which is the default value - thus you do not need to set explicitly).
 */
VehicleTypeImpl vehicleType1 = VehicleTypeImpl.Builder.newInstance("type1").addCapacityDimension(0,120).setFixedCosts(1000).build();
VehicleImpl vehicle1 = VehicleImpl.Builder.newInstance("vehicle1").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType1).build();

FSMFD

Both fixed and variable costs are specified here such as

VehicleTypeImpl vehicleType2 = VehicleTypeImpl.Builder.newInstance("type2").addCapacityDimension(0,160).setFixedCosts(1500).setCostPerDistance(1.2).build();
VehicleImpl vehicle2 = VehicleImpl.Builder.newInstance("vehicle2").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType2).build();

HVRPD

As already mentioned, the HVRP distinguishes itself from FSM such that the vehicle fleet is given. Thus you need to implement each and every vehicle and set the fleet-size to FINITE. If you have a lean fleet, i.e. sum of available capacities is not much greater than the total demand, you need to allow the algorithm to temporarilly generate infeasable solution (i.e. with vehicles you actually do not have in your fleet). By setting sufficient penalties, you should end up with a feasible solution (assuming there is one).

/*
 * build the types and vehicles from table above 
 * here it is assumed the variable costs are dependent on distance (rather than time or any other measure)
 */
VehicleTypeImpl vehicleType1 = VehicleTypeImpl.Builder.newInstance("type1").addCapacityDimension(0,120).setCostPerDistance(1.0).build();
VehicleImpl vehicle1_1 = VehicleImpl.Builder.newInstance("vehicle1_1").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType1).build();
VehicleImpl vehicle1_2 = VehicleImpl.Builder.newInstance("vehicle1_2").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType1).build();

VehicleTypeImpl vehicleType2 = VehicleTypeImpl.Builder.newInstance("type2").addCapacityDimension(0,160).setCostPerDistance(1.2).build();
VehicleImpl vehicle2_1 = VehicleImpl.Builder.newInstance("vehicle2_1").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType2).build();
VehicleImpl vehicle2_2 = VehicleImpl.Builder.newInstance("vehicle2_2").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType2).build();

VehicleTypeImpl vehicleType3 = VehicleTypeImpl.Builder.newInstance("type3").addCapacityDimension(0,300).setCostPerDistance(1.4).build();
VehicleImpl vehicle3 = VehicleImpl.Builder.newInstance("vehicle3").setStartLocationCoordinate(Coordinate.newInstance(40, 40)).setType(vehicleType3).build();

//Use VehicleRoutingProblem.Builder to specify the problem
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addVehicle(vehicle1_1).addVehicle(vehicle1_2).addVehicle(vehicle2_1).addVehicle(vehicle2_2).addVehicle(vehicle3);

//set fleetSize to FleetSize.FINITE 
vrpBuilder.setFleetSize(FleetSize.FINITE);

/*
 * add penalty vehicles
 * para1 is a penalty-factor - variable costs are penalty-factor times higher than in the original vehicle type
 * para2 is an absolute penalty-fixed costs value - if fixed costs are 0.0 in the original vehicle type, multiplying it with
 * penalty factor does not make much sense (at least has no effect), thus penalty fixed costs are an absolute penalty value
 */
vrpBuilder.addPenaltyVehicles(5.0, 5000);

//add jobs as you know it from SimpleExample and build the routing problem
...
VehicleRoutingProblem vrp = vrpBuilder.build();

Accordingly, you implement the HVRPFD problem by additionally setting fixed costs as illustrated above (see FSMF).

Specifying the algorithm

Have a look at the following xml-file: algorith-config.xml

The insertion heuristic is specified in line 28-30. Once you ommit 'id' as attribute in insertion-tag all subsequent insertion calls in the xml-file are referred the specification made in line 28-30. The tag 'considerFixedCosts' triggers an approach to consider fixed costs when inserting a job.

It is a fixed costs allocation approach that distinguishes between different insertion phases depending on the completeness of the solution. It is based on Dell' Amico et al. (2007) and basically works as follows: If a significant share of jobs still have to be inserted, vehicles with a low fixed costs per capacity ratio (which they call relative fixed costs) are preferred which usually prefers bigger vehicles. Thus total capacity is expanded. If almost all jobs are already in the solution, vehicles with low absolute fixed costs are preferred which in turn prefers smaller vehicles. Thus total capacity is tighten and kept lean, respectively. It is implemented here.

The 'weight' attribute specifies a fixed costs scaling parameter and determines the importance of fixed costs compared to variable costs. If weight is 0.0, fixed costs do not matter (are not considered). You need to find out an appropriate parameter for your problem. 'weight=1.0' is a good point to start from.

Play around with this option and also omit 'considerFixedCosts' to get a notion of its impact.

Loading and using the above algorithm is as simple as taking the following two steps:

1. Download config-file (open config-file in Browser (just click on link), right click 'Raw' and save target as) and
2. Code VehicleRoutingAlgorithm vra = VehicleRoutingAlgorithms.readAndCreateAlgorithm(yourProblem,"yourPath/downloadedConfigFile.xml")

Benchmarking the algorithm

Have a look at this example. It shows you how to benchmark an algorithm on classical VRP instances with heterogeneous fleet.

For two algorithm-configuration (an extensive search and a greedy one) you can find benchmarking results for the above problem types here.