Network Based VRPs

This example covers:

• loading a network
• loading Carriers with their VehicleRoutingProblem and their locations based on the network
• defining the routing problem, i.e. transforming the problem into a jsprit-vrp
• loading a vehicle-routing-algorithm
• solving the problem
• transforming problem and solution to MATSim-Carrier again and
• visualize the solution dynamically

Note that this example is based on MATSim stuff. If you want to use this, bear in mind that MATSim is distributed under the Gnu Public Licence (GPL).

Prerequisites:

1) Downloads (see how to use nightly builds of MATSim)

• Download the latest nightly build of MATSim [MATSim_r####.jar] and its according libs [MATSim_libs.zip]
• Download the latest nightly build of the freight extension [freight-#.#.#-SNAPSHOT-r#####.zip]
• Download the latest nightly build of OTFVis [otfvis-#.#.#-SNAPSHOT-r#####.zip]

Note that if you have included the freight extension, you automatically have jsprit (so you do not have to add the dependencies additionally).

2) Unzip

Put these files into a shared folder and unzip the zip-files.

3) Classpath

Add the jar-files to your classpath. If you use Eclipse, right-click your java-project, go to Properties, go to Java Build Path and Add External JARs....

Lets assume the following grid-scenario (representing a distribution case for a transport carrier)

with one depot and 10 customers each demanding 1 unit of something.

All required entities of this scenario are defined in xml-files. The carrier is defined and described in carrier.xml. Here you can basically find the vehicle-routing-problem a carrier face and the resources it can employ, i.e. vehicles. The vehicle-types a carrier can employ are defined in vehicleTypes.xml. The network in turn is defined in network.xml. The vehicle-routing-algorithm that is used in this example is defined in algorithm.xml. To download these files, click on it, right click Raw and save target as.

To solve the network-based routing problem, you first need to load the network and some matsim prerequisites by coding

MatsimStuff matsimStuff = MatsimStuffLoader.loadNetworkAndGetStuff("yourFolder/network.xml");

Read the carrier with its problem, its vehicles and its vehicle-types:

//make carrier container
Carriers carriers = new Carriers();

//read carriers and their capabilities
new CarrierPlanXmlReaderV2(carriers).read("yourFolder/carrier.xml");

//read vehicle-types
CarrierVehicleTypes vehicleTypes = new CarrierVehicleTypes();
new CarrierVehicleTypeReader(vehicleTypes).read("yourFolder/vehicleTypes.xml");
//assign them to their corresponding vehicles (defined in carrier.xml)
new CarrierVehicleTypeLoader(carriers).loadVehicleTypes(vehicleTypes);

Get the carrier you want to solve the problem for. Here, there is only one carrier with the carrierId 'gridCarrier'

Carrier gridCarrier = carriers.getCarriers().get(new IdImpl("gridCarrier");

Use jsprit to solve the vehicle-routing-problem for 'gridCarrier'.

//build the routing problem - here jsprit comes into play (if you know some of the jsprit-examples this might be familiar to you)
VehicleRoutingProblem.Builder vrpBuilder = MatsimJspritFactory.createRoutingProblemBuilder(gridCarrier,matsimStuff.getNetwork());

/*
 * build the network-based routing costs
 * by default, transportTimes are calculated with the freeSpeed values defined for each link in the network 
 * and the maxVelocity defined in vehicleTypes.xml (if maxVelocity is less than freeSpeed then it uses maxVelocity, otherwise freeSpeed)
 * The default-leastCostPathCalculator is a fast version of the Dijkstra-algorithm.
 * Unit costs per time and distance-unit are retrieved from vehicleType.
 */
NetworkBasedTransportCosts netBasedCosts = 
   NetworkBasedTransportCosts.Builder.newInstance(matsimStuff.getNetwork(), vehicleTypes.getVehicleTypes().values()).build();

//assign routingCosts to the routingProblem
vrpBuilder.setRoutingCost(netBasedCosts);

//build the problem
VehicleRoutingProblem vrp = vrpBuilder.build();

//read and create a pre-configured algorithms to solve the vrp
VehicleRoutingAlgorithm vra = VehicleRoutingAlgorithms.readAndCreateAlgorithm(vrp,"yourFolder/algorithm.xml);

//solve the problem
Collection solutions = vra.searchSolutions();
//get best (here, there is only one)
VehicleRoutingProblemSolution solution = Solutions.getBest(solutions);

You can now either display and analyse this solution with the tools described in jsprit-example or you can make use of matsim's dynamic visualizer 'OTFVis'. To get to know some prerequisites, please visit MATSim's OTFVIS-Site.

To use the latter, transform the solution back to the carrier yielding to a CarrierPlan.

//create a carrierPlan from the solution 
CarrierPlan plan = MatsimJspritFactory.createPlan(gridCarrier, solution);

jsprit does not memorizes the actual paths through the network (it only memorizes their costs), thus you need to route the CarrierPlan again.

//route plan 
NetworkRouter.routePlan(plan,netBasedCosts);

//assign this plan now to the carrier and make it the selected carrier plan by coding
gridCarrier.setSelectedPlan(plan);

Now you can write out the carrierPlan to an xml-file (for later use and/or analysis)

new CarrierPlanXmlWriterV2(carriers).write("yourFolder/plannedCarrier.xml");

The result should look like carrierPlanned.xml.

To make a live visualisation of this plan, code:

new Visualiser(matsimStuff.config,matsimStuff.scenario).visualizeLive(carriers);

which should work if your graphic card supports this (see OTFVIS-Site). You might have to increase the HeapMemory for this, by adding for example -Xmx1024m to your VM. In eclipse, this works as follows: Right click your main.java, Run As, Run Configurations..., (x)= Arguments, VM arguments: -Xmx1024m.

This is a snapshot of the live sim:

You might also want to make a movie for later use. Instead of visualizeLive(carriers), code:

new Visualiser(matsimStuff.config,matsimStuff.scenario).makeMVI(carriers,"yourFolder/carrierMVI.mvi",1);

//to watch this write
OTFVis.playMVI("yourFolder/carrierMVI.mvi");

... now play with results.