15 Predictive repositioning

If you wish to use the predictive repositioning, we advise you to consult Open Door Logistics before attempting the configuration yourself.

15.1 Introduction

The predictive repositioning functionality (1) builds a model of demand locations where vehicles need to be going into to serve upcoming jobs, and then (2) translates these into a special type of stop which is included in the vehicle plans. By including the special reposition stops in the vehicle plans we can (a) send vehicles to better locations when they have no jobs pending and (b) assign jobs to vehicles taking into account vehicle placement for upcoming jobs. Both of these bring efficiency benefits.

The current repositions model has a couple of limitations:

• Currently the repositioning model assumes jobs are served with only one type of vehicle - e.g. cars only.

• Currently the repositioning model assumes all jobs must be completed ASAP after their creation time. Reposition stops only ever appear at the end of a planned route (i.e. always after any planned jobs). The optimiser won’t suggest doing a reposition before a planned job which, for example, is not due to open until 3 hours into the future.

Predictive repositionings is designed primarily for pickup-delivery problems where new jobs are created at short notice - e.g. taxis or restaurant food deliveries. From tests with simulations, we can show that predictive repositioning leads to jobs being completed faster (i.e. faster deliveries and passengers getting to their end destination earlier).

The prediction repositioning model is built using the ODL Live command line tool available to self-hosting ODL Live subscribers. The workflow for configuring predictive repositionings is as follows:

1. Prepare repositions configuration file (a JSON file).

2. Build ‘simulation-format-routes’ file. This is a JSON file containing the latitude and longitude positions (i.e. stops) on a route, relative to a prediction period. It can be built using one of two options, either (a) simulation-based routes or (b) historic routes:

   • Option 1. Simulation-based routes. Use simulations to build simulated vehicle routes based on historic jobs. This is done using the repBldJobs2SimResults command. You provide the command line interface with (a) a set of historic jobs, (b) a vehicle definition and (c) the repositions configuration file. It then runs simulations which analyse the incoming-vehicle locations for different numbers of available vehicles. We recommend using the simulation-based method, as it learns the dependence between reposition locations and the number of available vehicles.

   • Option 2. Historic routes. Use historic routes directly, saved in the stop arrival events in a set of routing models. This uses the repBldHistoricModels2SimResults command to parse routing models (in the normal ODL Live JSON model format) and turn them into the simulation-based-routes format.

3. Build repositions areas from simulation-format-routes.. The historic or simulated routes are analysed to generate sets of time-dependent reposition areas. This uses the command repBldSimResults2Areas. The sets of repositions areas are output to a JSON file, which is a JSON array where each element is a set of areas.

4. Validate reposition areas using simulations (optional). Run a set of simulations with and without repositions turned on to verify (a) that repositions are called and (b) they make delivery times quicker. It is advised to run this step, to check your repositions model is configured correctly, however running this step is not mandatory.

5. Set repositions on your live model.

We now walkthrough these steps using simulation-based-routes.

15.2 Walkthrough

The following walkthrough uses the ODL Live command line tool together with a set of files available in the supporting-data-for-docs\repositions-walkthrough data directory (both are available for self-hosting subscribers only). To start using the repositions model, first work through the section on setting up the command line. As per this section you should (1) create a new directory on your computer, (2) copy the file odl.live.commandline.jar into it and (3) open a command line prompt in this directory. Then try running the command line help:

java -Xmx4G -jar odl.live.commandline.jar -help

You should see a list of the available repositions builder (and other) commands. Repositions builder commands begin with ‘repBld’.

After setting up the command line, copy the files from supporting-data-for-docs\walkthroughs\repositions-walkthrough into this new directory. We will modify these original files and do the whole walkthrough inside this new directory. The following files should be present:

• list of commands to run.txt - list of all commands you run in this document (copying and pasting from a pdf adds extra spaces and new lines, so you have the original commands also available in this text file to copy from instead).
• Subdirectory Step1-InputFiles
  • conf.json - repositions builder configuration file.
  • historicjobs.json - an array of ODL Live routing model format job objects, used to train the predictions model.
  • vehicledfn.json - an ODL Live vehicle definition object.
• Subdirectory Step2-Build-sim-format-routes
  • simresults1.json - simulation-format-routes output by the repBldJobs2SimResults command.
• Subdirectory Step3-Build-reposition-areas
  • areas.json - built sets of repositions areas.
  • 20191021205353-Period1-NbGlobalVehs20.mp4 - video of the built reposition areas for 20 available vehicles (timestamp will differ).
  • 20191021205353-Period1-NbGlobalVehs25.mp4 - video of the build repositions areas for 25 available vehicles.
• Subdirectory Step4-Validate-reposition-areas
  • simcase4Compare0.json to simcase4Compare2.json - simulation case files for checking the reposition areas performance.
  • simcaseCompareResult0.json to simcaseCompareResult03.json - JSON files output from the validation process.
• Subdirectory Step5-Example-model-with-repositions
  • example-model-with-repos.json - example routing model using reposition areas.

You will use input files in the Step1-InputFiles and Step4-Validate-reposition-areas directories to create several different output files. Copies of the files you will generate are already available in the various subdirectories - for example you will generate your own areas.json file but there is already pre-generated areas.json file in the directory Step3-Build-reposition-areas, which will be more-or-less the same as the areas.json you generate.

The walkthrough files are derived from a public open data set on New York taxi journeys in Brooklyn. They contain real trips for real passengers who travelled by taxi within Brooklyn, NYC in January 2016. We sampled a subset of these historic trips and applied a reasonable set of assumptions to fill in the data fields that were unavailable in the original dataset. The trips were sampled from weekday mornings. We sampled a relatively small set of trips, so the walkthrough build process and comparison simulations run quickly. For each trip, we assumed a job creation time and pickup / dropoff time window based on the real recorded pickup time (jobs were assumed to be created 20 minutes before the recorded pickup time). Jobs were assumed to be open (i.e. available for pickup) as soon as they’re created. We setup the time windows with custom penalties such that ODL Live tries to complete the journey (i.e. do the dropoff) as soon as possible after the job creation time, with a large penalty being applied if the dropoff is completed more than 45 minutes after the job creation time. ODL Live therefore tries to complete the jobs as quickly as possible, and the time between job creation and dropoff therefore measures how good the plans are.

To make the problem more interesting, we’ve assumed ridesharing is allowed, and we setup the jobs and vehicles with quantities that allow a vehicle to serve up to 2 jobs at once.

15.2.1 Setting up the configuration file

Open the file Step1-InputFiles\conf.json in a text editor (we recommend Notepad++ as it provides good syntax highlighting for JSON). We look at the most important sections in this file, section by section.

{
  "periods" : [ {
    ... This section defines a set of prediction periods (e.g. weekday mornings).
  } ],
  "distancesConf" : {
    ... This is a standard distances config object, identical to model.configuration.distances
  },
  "jobs2SimResultsConf" : {
    ... This section includes the settings used to turn jobs into simulation-format-routes
  },
  "determineAreasConf" : {
    ... This section includes the settings used to turn simulation-format-routes into reposition areas
  },
  
  ... This is the number of CPU threads that will be used during the processing
  "nbThreads" : 6
}

Now set the nbThreads value in this file to be equal to the number of CPU cores on your machine minus 1 (assuming you have 2 or more CPU core). Setting to nbCores − 1 means you will use most of the CPU on your machine, but not all the CPU (which could make your computer unresponsive).

15.2.1.1 Setting the periods configuration

The periods configuration object config.periods defines one or more periods to build a set of reposition areas for. The following example defines a single period for all weekday mornings in America/New_York timezone:

 "periods" : [ {
    "localTimeZoneId" : "America/New_York",
    "localTimePeriodStartDaysOfWeek" : {
      "monday" : true,
      "tuesday" : true,
      "wednesday" : true,
      "thursday" : true,
      "friday" : true,
      "saturday" : false,
      "sunday" : false
    },
    "localTimeRange" : {
      "start" : "04:00",
      "end" : "12:00"
    }
  } ],

When running your own data through the areas builder, you must set the localTimeZoneId correctly to the timezone used in the city/country you’re modelling. You are advised to setup your prediction periods such that the demand (i.e. number of jobs being created per hour) is small at both the start and end of the period - so you start the prediction period before peak time and finish it after peak time.

The prediction period will be split up into multiple subperiods during the builder process, where each subperiod has its own set of reposition areas.

15.2.1.2 Setting the distances configuration

The distances object config.distancesConf is a standard distances object as found in model.configuration.distances. Set your road network graph on it as you would normally do. The example configuration in this walkthrough uses straight line distances (which don’t require a road network graph), so you don’t need to update the road network graph file path in the configuration.

15.2.1.3 Setting the jobs to simulation-format-routes configuration

The config.jobs2SimResultsConf object stores various settings used to turn historic jobs into simulation-format-routes. The simulation-format-routes are then analysed to create the reposition areas.

See the following example from the config file:

  "jobs2SimResultsConf" : {
    "scenarioGeneratorConf" : {
      "nbLocations4DistanceCalculations" : 2500,
      "minMetresLength4Discretisation" : 10.0,
      "vehicleNbs2Sample" : [ 20, 25 ],
      "blurJobCreationTimeMillis" : 600000
    },
    "simRunnerConf" : {
      "millisTimeResolutionInSim" : 300000,
      "iterationsPerStep" : 5
    },
    "nbScenarios" : 10
  }
  

Assuming you’re using the simulation-based-routes option to create the simulation-format-routes, the algorithm does the following:

1. Samples the historic jobs that fall within the defined prediction periods to create jobs2SimResultsConf.nbScenarios different scenarios.

2. Runs a simplified routing simulation for each of these scenarios, for different numbers of globally available vehicles. The numbers in the array vehicleNbs2Sample define the number of globally available vehicles that we test for. In this example JSON, we’re asking it to test for 20 and 25 available vehicles. We test for different numbers of global vehicles so we can model how reposition areas are dependent on the number of available vehicles (e.g. there’s no point defining 100 reposition areas if you only have 10 vehicles to go to them).

   • You should set vehicleNbs2Sample to contain the minimum and maximum number of vehicles you’re likely to have available in a typical delivery period. The maximum value should be large enough such that there’s enough vehicles available to serve the peak jobs without a queue of late jobs forming, but it should not be unrealistically large (i.e. should not be several times your real fleet size).

   • Values in vehicleNbs2Sample should be in ascending order.

   • If the range of vehicleNbs2Sample is wide - e.g. [5,100] - the algorithm may decide to sample extra simulations with in-between numbers of global vehicles, to increase predictive accuracy. For example if vehicleNbs2Sample is [5,100] the algorithm may decide to sample [5,10,25,50,100], i.e. filling in the blanks.

3. Outputs the simulations to the simulation-based-routes JSON.

When running your own data through the areas builder, you will need to set vehicleNbs2Sample appropriately.

15.2.1.4 Setting the determine areas configuration

The config.determineAreasConf object stores settings used to build the areas from the simulation-format-routes. The example determineAreasConf from conf.json is shown below:

  "determineAreasConf" : {
    "convert2StopsConfig" : {
      "probabilityCutoff" : 0.5,
      "unreadyCost" : 1.0,
      "arrivalTimePenaltyType" : "LINEAR_UNREADY_COST",
      "minNbAreas" : 1
    },
    "outputVideosDir" : "c:\\set-to-directory-on-your-computer",
    "minProbabilityOfIncomingVehs4AreaCalc" : 0.75,
    "sampleSecsResolution" : 10.0,
    "targetNbVehsPerArea" : 2.0,
    "nbBricks" : 500,
    "secsPerPredictionSubPeriod" : 3600,
    "maxSecsInFutureToConsider" : 3600.0,
    "maxBrickFractionOfMinClusterDemand" : 0.1,
    "maxNbAreas" : 100,
    "nbClusterOptimisationIts" : 250,
    "minNbLocations4Opt" : 100,
    "url4OSMTileDownload" : "http://tile.openstreetmap.org"
  },
 

Most of the settings here can be safely ignored, the following list covers fields in the determineAreasConf object you need to be aware of:

• convert2StopsConfig.probabilityCutoff. Reposition stops will not be created if the probability of a job upcoming in the reposition area is below this value. Recommended value is 0.5. If you only want to reposition when you’re sure there’s upcoming work, set to high (e.g. 0.8).

• convert2StopsConfig.unreadyCost. This is a cost that is applied in the vehicle routing model if a vehicle does not arrive at the reposition area by the time it’s predicted to be required. We advise that this cost should be similar in size to your costPerTravelHour field in the vehicle definition (both values default to 1 if not set).

• outputVideosDir. If this field is set, the determine areas process outputs videos of the time-evolving areas to your computer. Delete this field if you don’t want to output a video to sense-check your areas.

• secsPerPredictionSubPeriod. The prediction period is actually split into subperiods, which are by default 1 hour long. A different set of reposition areas is predicted per subperiod. This value sets the length of the subperiod in seconds. We recommend 3600 secs which is equal to one hour.

• maxSecsInFutureToConsider. Within a subperiod, we consider jobs that will occur within the next maxSecsInFutureToConsider. So if we’re creating a subperiod for 8:00, maxSecsInFutureToConsider=3600 (i.e. one hour) and jobs are not typically created/served until 9:30, no areas will be created as no jobs occur within the window. The recommended value is 3600 which equals one hour. Reposition stops will not be generated by the system and appear in the vehicle plans until the optimiser predicts jobs are due to be created within the next maxSecsInFutureToConsider seconds.

• maxNbAreas. A maximum number of areas to create, so the build process is not too slow and the JSON definition of the areas in your live routing model is not too large (for performance reasons the size of the JSON data defining a live routing model should not be more than a few MB ideally).

• url4OSMTileDownload. The URL to download free OpenStreetMap map tiles, for the background of the areas video (if you’ve set outputVideosDir). You may need to change this URL to a different tile server if the default one becomes unavailable.

As part of this walkthrough, ensure you set determineAreasConf.outputVideosDir to the path of an empty directory on your computer.

15.2.2 Building simulation-format-routes

In this step we will build simulation-format-routes from historic jobs. This involves calling a command line function which runs multiple routing simulations for different numbers of globally available vehicles. This command needs 3 input files, (1) the config file, (2) a vehicle definition file and (3) a set of historic jobs.

Now open the example vehicle definition file Step1-InputFiles\vehicledfn.json:

{
  "costPerTravelHour" : 1.0,
  "costPerWaitingHour" : 0.25,
  "costPerServicingHour" : 1.0,
  "costPerKm" : 1.0E-6,
  "costFixed" : 0.0,
  "costPerStop" : 0.0,
  "capacities" : [ 2 ]
}

This file includes several fields from the vehicle.definition object found in normal routing models. Generally the default values in this file are fine, except when you run on your own data, you will need to set the capacities array to the normal capacities of your vehicles. Currently we only support one type of vehicle when building the repositions model. If you use multiple types of vehicle, we recommend you build the repositions model for your most common type.

We have a JSON array of example historic pickup-delivery jobs (derived from the open data on New York taxis) saved in the file Step1-InputFiles\historicjobs.json. These are normal ODL Live job objects, except they have their createdTime field set as follows:

{
  "quantities" : [ 1 ],
  "stops" : [ {
    "type" : "SHIPMENT_PICKUP",
    "coordinate" : {
        ...
    },
    "_id" : "pickup1"
  }, {
    "type" : "SHIPMENT_DELIVERY",
    "coordinate" : {
        ...
    },
    "_id" : "delivery1"
  } ],
  "createdTime" : "2016-01-04T08:52:50",
  "_id" : "job1"
} 

The createdTime field is in UTC.

When you create your own set of historic jobs, you should ensure you add complete prediction periods to this set. For example, our period is setup to be any weekday from 04:00 to 12:00 New York time. So we add all the jobs created 04:00-12:00 NYC time on 2016-01-04, 2016-01-07, 2016-01-08 etc. and we never add just the jobs created between say 9:00 and 12:00 to the set (otherwise the demand for earlier in the day will be missed by the model). All times in the jobs are in UTC, as normal.

The following line executes 4 commands at once, where the 4th command uses data loaded by the first 3 commands. First we (1) load the configuration from conf.json using the command repBldLoadConf, then we (2) load the vehicle definition from vehicledfn.json using the command repBldLoadVehDfn, then we (3) load the list of historic jobs from historicjobs.json using the command repBldLoadHistoricJobs. Finally the fourth command repBldJobs2SimResults runs the set of simulations. In the simulations it records the positions (latitude and longitudes) vehicles drove to, to serve pickup stops. repBldJobs2SimResults outputs its result to a file called simresults1.json.

Now run this command, which will take a minute or two for the walkthrough data (dependent on the number of CPUs on your machine the number of threads you sent in config.nbThreads):

java -Xmx4G -jar odl.live.commandline.jar -repBldLoadConf Step1-InputFiles\\conf.json -repBldLoadVehDfn Step1-InputFiles\\vehicledfn.json -repBldLoadHistoricJobs Step1-InputFiles\\historicjobs.json -repBldJobs2SimResults simresults1.json

For running on Linux, change the path separator \ appropriately. Be aware that when you copy and paste from a pdf, extra lines and spaces can be added to the text which you will need to remove or you will get an error (or alternatively copy and paste the exact command from the file list of commands to run.txt instead).

When the command is running, you should see console output similar to:

13:53:54: Loading file conf.json
13:53:54: Loading file vehicledfn.json
13:53:54: Loading file historicjobs.json
13:53:54: jobs->sim results| Started
13:53:54: jobs->sim results| simId=p1scn1#v25| Started running sim p1scn1#v25, sim has 166 jobs, 25 vehs
13:53:54: jobs->sim results| simId=p1scn2#v20| Started running sim p1scn2#v20, sim has 110 jobs, 20 vehs
13:53:54: jobs->sim results| simId=p1scn1#v20| Started running sim p1scn1#v20, sim has 166 jobs, 20 vehs
13:53:54: jobs->sim results| simId=p1scn3#v25| Started running sim p1scn3#v25, sim has 110 jobs, 25 vehs
13:53:54: jobs->sim results| simId=p1scn2#v25| Started running sim p1scn2#v25, sim has 110 jobs, 25 vehs
13:53:54: jobs->sim results| simId=p1scn3#v20| Started running sim p1scn3#v20, sim has 110 jobs, 20 vehs
13:53:56: jobs->sim results| simId=p1scn3#v20| tLocal=04:00 dispStp=0 completeStp=0 planRoutes=1
13:53:56: jobs->sim results| simId=p1scn2#v20| tLocal=04:05 dispStp=3 completeStp=0 planRoutes=4

After the command has finished running, it should create the simulation-format-routes file simresults1.json in your working directory (if this step takes too long to complete, use the pre-generated file Step2-Build-sim-format-routes\simresults1.json file instead). The simresults1.json file contains an array of results for each prediction period object you defined in the config file (just one period object is used our walkthrough). Each result for a prediction period has a field called sims which stores the result of each simulation. Within each simulation, we have a set of routes. Here’s one example route in the compact format:

{
  "latitudes" : [ 40.68901, 40.68907, 40.67759, 40.67763 ],
  "longitudes" : [ -73.92700, -73.9256, -73.93511, -73.93510 ],
  "jobCreateSecsRel2PeriodStart" : [ 527.0001, 527.00006, 20996.0, 20996.002 ],
  "jobStartSecsRel2PeriodStart" : [ 1270.1831, 1492.6321, 21542.713, 21724.164 ],
  "firstStopInJob" : [ true, false, true, false ],
  "vehicleId" : "v6"
}

The arrays latitudes, longitudes, jobCreateSecsRel2PeriodStart, jobStartSecsRel2PeriodStart and firstStopInJob should all be the same length. Each index in these arrays refers to a single stop, and defines its latitude, longitude, creation time in seconds relative to the start of the prediction period, start work time in seconds relative to the start of the period, and whether the stop was the first stop in the job (i.e. the pickup stop). The format is designed to be compact for performance reasons, so it places the data in arrays to avoid duplicating field names in the JSON.

When you run your own data through this process, you should inspect the simulation-format-routes file and sense-check it. You should see routes defined in the same format, with stops being done throughout the prediction period.

15.2.3 Building reposition areas from simulation-format-routes

Next we take the simulation-format-routes and turn these into predicted reposition areas. We check these areas by also outputting a video of them.

Now run the following command in the command line prompt:

java -Xmx4G -jar odl.live.commandline.jar -repBldLoadConf Step1-InputFiles\\conf.json -repBldSimResults2Areas simresults1.json areas.json

This first loads our configuration file (-repBldLoadConf conf.json) and then runs the repBldSimResults2Areas which takes the simulation-format-routes file simresults1.json generated in the previous step as an input and then outputs the reposition areas to the file areas.json. Providing you set the field determineAreasConf.outputVideosDir correctly in the configuration file, it will also output two videos to the directory you set. The video filenames are prefixed by a timestamp - e.g. 20191018151837-Period1-NbGlobalVehs20.mp4.

You will have different videos for each number of global vehicles simulated. The videos show the evolving areas for the different subperiods inside the prediction period (i.e. the different hours) together with statistics on the expected number of vehicles per area. At the beginning of the period (early in the morning), there are not many areas, but as we go towards the peak demand (around 7am NYC time) you will see the number of areas growing and the areas getting correspondingly physically smaller.

The output areas.json file contains an array of elements, where each element is a set of areas (i.e. each element represents the set of areas at a particular time). To use repositionings, you will set this top-level array to the field model.data.repositionAreas in your live routing model.

The following JSON shows a single set of two reposition areas from this array:

{
  "period": {
    ... this defines the subperiod (e.g. 04:00-05:00 when this areas set is active
  },
  "areas": [
    {
      "statsByGlobalNbVehs": {
        "20": {
          "incomingVehs": {
            "tsecs": [1174,1441,1860,2417,2601,2881],
            "ps": [1,0.6492,0.5348,0.3442,0.1252,0.0266]
          },
          "estmTravel2NewJobFraction": 0.3813
        },
        "25": {
          "incomingVehs": {
            "tsecs": [ 1162,1420,1653,2504,2504,2716,3469],
            "ps": [1,0.6342,0.4941,0.2981,0.1288,0.0311,0.0072]
          },
          "estmTravel2NewJobFraction": 0.3809
        }
      },
      "centroid": {
        "latitude": 40.704410552978516,"longitude": -73.94364166259766
      },
      "boundingGeoJSONPolygon": {
        ... GeoJSON geometry format polygon boundary
      },
      "id": "Repos001T0_N3fP2LWDQ2mt8P_WkX3HCQ=="
    },
    {
      "statsByGlobalNbVehs": {
        ...
      },
      "centroid": {
        ...
      },
      "boundingGeoJSONPolygon": {
        ....
      }
    }
  ],
  "nbGlobalAvailableVehs": 20,
  "convert2Stops": {
    ... This contains the costs for the reposition stops not 
    ... being served on-time
  }
}

For each area, for different numbers of globally available vehicles, the object statsByGlobalNbVehs stores statistics on the times new incoming vehicles are expected and the probability the vehicle will be required. When you run with your own data, you should sense-check these numbers.

The field estmTravel2NewJobFraction is an estimate of how useful the area is, specifically the fraction of travel to a new job you’d be expected to do if you went to the centre of the area compared to staying at the location of a previous job. When estmTravel2NewJobFraction number approaches 1, the area is effectively too large to give significant reductions in delivery times by going to its centroid. When estmTravel2NewJobFraction is smaller (e.g. 0.3), it indicates a more effective repositioning area likely to bring delivery times down.

15.2.4 Checking reposition areas performance using simulator

Once you’ve built a prediction model you can validate it (i.e. check it is effective) using the ODL Live simulator tool, providing your routing problem is small enough to run through the simulator quickly (e.g. a couple of hundred live jobs at once maximum).

As part of the walkthrough we provide pre-prepared simulation case files for this taxi scenario. A simulation case file stores (1) a set of jobs with creation times, (2) a set of vehicles and (3) various settings which specify how the simulation runs (e.g. how often the optimiser runs in simulated time). See the chapter on the simulator for more details. Three simulation case files are provided with the walkthrough data:

- Step4-Validate-reposition-areas\\simcase4Compare0.json
- Step4-Validate-reposition-areas\\simcase4Compare1.json
- Step4-Validate-reposition-areas\\simcase4Compare2.json

Each file contains between 138 and 180 trips (i.e. jobs) to be served by 25 vehicles on a weekday morning in Brooklyn, with the jobs based on real historic data. This test data is independent of the data we used to build the repositions model - the repositions model was built using the first 10 weekdays in January 2016 and these simulation test cases were built using weekdays following these. The vehicles start the simulation at randomised locations scattered throughout Brooklyn. Crucially the simulation cases cover the same time period and days of the week as our repositions model, just on dates after the training data. Also the simulation cases have parity with the simulations we used to build the repositions model, both used straight line distances instead of road network distances and had jobs setup with the same pickup/dropoff stop durations etc. The jobs, vehicles and distance settings should be more-or-less the same in the data you use to build the repositions model and the data you use to test the reposition models, or to run the repositions model in real live models. If your repositions model is built with very different scenarios/settings to the setup you use in real-life, its predictions will not be accurate.

These simulation cases are set to run quickly, so they only run the optimiser for every 3 minutes of simulated time, running only 10 iterations per optimiser burst. If you are running simulations for what-if scenarios etc, you should set the optimiser to run more often (e.g. every minute of simulated time) and with a higher iterations per burst (e.g. 25 or 50).

Start the simulation by entering the following command in the command line prompt:

java -Xmx4G -jar odl.live.commandline.jar -repBldCompareOnOffInSim areas.json Step4-Validate-reposition-areas\\simcase4Compare0.json simcaseCompareResult0.json

This starts the comparison simulation using the areas file areas.json and the simulation case file simcase4Compare0.json and it will output its results to the file simcaseCompareResult0.json. The comparison runs two simulations (each on a separate thread, so using 2 CPUs at once your computer). The simulations are identical (both using the input simulation case file) except one has repositions turned on (as defined in the areas.json file) and one doesn’t.

The simulation will take a minute or two to run, and you should see output similar to the following:

11:40:52: Loading file areas.json
11:40:53: Loading file simcase4Compare0.json
11:40:58: simcase4Compare0.json reposOn=false 0.05 hrs simulated jstops-complete=0
11:40:58: simcase4Compare0.json reposOn=true 0 hrs simulated jstops-complete=0
11:40:58: simcase4Compare0.json reposOn=false 0.05 hrs simulated jstops-complete=0
.....
11:41:12: simcase4Compare0.json reposOn=true 6.55 hrs simulated jstops-complete=9 jstops-dispatch=18 repos-dispatch=7 pick-arrive-mins=11.33 del-arrive-mins=22.25
11:41:12: simcase4Compare0.json reposOn=false 7.9 hrs simulated jstops-complete=32 jstops-dispatch=39 pick-arrive-mins=8.72 del-arrive-mins=25.67
.....
11:41:37: Finished processing simcase4Compare0.json sim with areas areas.json
11:41:37: Without repositions: meanDelMins=26.48, #completeJobs=180, #dispatchRepos=0
11:41:37: With repositions: meanDelMins=23.55, #completeJobs=180, #dispatchRepos=179

The last two lines are crucial, they show the mean delivery minutes (meanDelMins), which is defined as the time duration from the job creation time to arrival at the dropoff location. We can see that meanDelMins without repositions is nearly 3 minutes more than meanDelMins with repositions. In other words, if we turn repositions on then passengers get to their end destination 3 minutes earlier!

For many scenarios, we would actually expect the gains to be significantly larger than 3 minutes. The repositions builder decides how many areas to create based on each predicted area being likely to have a couple of vehicles-worth of upcoming jobs. The walkthrough scenario uses small numbers of jobs so it runs through quickly, but a more realistically sized scenario would have more jobs, allowing the repositions builder to identify tighter (i.e. physically smaller) reposition areas, which would give more performance gains.

In the simulation, when we’re not using repositions the vehicles stay at the location of their last dropoff (or stay at their starting location if they haven’t served a job yet), until they’re assigned a new job. When we using repositions, the repositions model estimates how may vehicles it thinks are required in each predicted reposition area in the near future, and when taxis are idling (i.e. have no current job), they may be repositioned to the centroids of these areas. The simulation starts early in the morning before jobs start to be booked, and ends after the peak period in late morning, when the peak has passed and no more jobs are upcoming. As the reposition areas follow predicted demand, we start off with no reposition areas (i.e. no taxis are repositioned), then the number of areas and taxi repositions grows towards peak demand, then shrinks back to no areas / no taxi repositions after.

Taxis complete jobs 3 minutes earlier with repositionings on, largely because when they are idling they are repositioned to a nearby area (to the centroid of the area) where a pickup is likely to be created in the near future. When the pickup is created, they can therefore arrive at the pickup location much quicker, as they’re already nearby. This highlights an important point, the efficiency of predictive repositioning is dependent on the amount of time between a job being created and its earliest pickup time. In our taxi scenario, passengers are available for pickup as soon as the job is created, so having the taxis ready in the right place at the right time reaps large benefits. Conversely if jobs were booked an hour or two before their earliest pickup times, predictive repositioning would have little benefit as we would already know about jobs a long time before they need to be picked up.

We generated the following stats by running all three cases:

• simcase4Compare0.json
  • 11:41:37: Without repositions: meanDelMins=26.48, #completeJobs=180, #dispatchRepos=0
  • 11:41:37: With repositions: meanDelMins=23.55, #completeJobs=180, #dispatchRepos=179
• simcase4Compare1.json
  • 11:57:33: Without repositions: meanDelMins=24.39, #completeJobs=138, #dispatchRepos=0
  • 11:57:33: With repositions: meanDelMins=22.85, #completeJobs=138, #dispatchRepos=154
• simcase4Compare2.json
  • 12:19:36: Without repositions: meanDelMins=25.36, #completeJobs=154, #dispatchRepos=0
  • 12:19:36: With repositions: meanDelMins=22.26, #completeJobs=154, #dispatchRepos=162

Due to the use of random numbers within the optimiser, each run of a simulator with the same input data can generate slightly different results, so your numbers may not match the above completely. However the pattern is very consistent, for these scenarios passengers arrive at their final destination around three minutes earlier with repositioning on. Based on this, we can say the configuration of our repositions model for the walkthrough data works well, as the routing costs in the model are configured to get passengers to their end destinations as quickly as possible, and this happens quicker with repositions on. If you’re evaluating the effect of repositions on your own data, we recommend you run several simulations - e.g. 10 simulations - and get the average difference with or without repositions, as the true performance difference may not be obvious from just one or two simulations, due to random fluctuations.

The ratio of #completeJobs to dispatchRepos is also of-interest. When repositions are turned on we have a similar number of dispatched repositions to number of jobs, which means that vehicles are usually repositioned after finishing a job, and must frequently have gaps between having assigned jobs. If instead there was a backlog of jobs - e.g. if we didn’t have enough vehicles available - taxis would already have several pending jobs lined up when they finish a job, and they’re unlikely to be repositioned. As a result, we expect the repositioning model to be less relevant for transportation scenarios where drivers have many pending ASAP jobs queued up at once.

When these simulations run, they output a large JSON file to simcaseCompareResult0.json, simcaseCompareResult1.json, etc respectively. The structure of these files is as follows:

{
    "onResult" : .... standard simulator output with repositions on,
    "offResult" : .... standard simulator output with repositions off,
    "onSummary" : {
        ... summary of relevant stats with repositions on
        "meanDeliveryMinutes" : 22.793926203703716,
        "nbCompleteJobs" : 180,
        "nbDispatchedRepositions" : 183
    },
    "offSummary" : {
        ... summary of relevant stats with repositions on
        "meanDeliveryMinutes" : 26.41668083333332,
        "nbCompleteJobs" : 180,
        "nbDispatchedRepositions" : 0
    }

}

You can use the standard simulator commands to export videos of the comparison simulation (one video with repositions on and one with it off), e.g. 

java -Xmx4G -jar odl.live.commandline.jar -simVidOutput "outputfile.mp4" -simVidQuality HIGH -repBldCompareOnOffInSim areas.json Step4-Validate-reposition-areas\\simcase4Compare0.json simcaseCompareResult0.json

will actually generate two videos outputfile_reposOn.mp4 and outputfile_reposOff.mp4. For smaller simulations like this walkthrough exporting a video makes the processing time several times slower. For larger simulations (i.e. with many more jobs), exporting a video will make less difference to the total processing time. The following image shows a screenshot of a video generated for this walkthrough data with repositions turned on. The reposition areas are shown as coloured polygons with a large star at their centroid (which is where the simulation directs the repositioned vehicles too). The centroid is calculated as the weighted centre of demand.

15.2.5 Using repositions in live model

To use simulations in live model, you must:

1. Set the JSON array stored in the areas.json file to the field model.data.repositionAreas. Each element in the array is a different set of reposition areas.

2. Set the field repositionUntilTime in the vehicle.definition to the time in UTC when you want a vehicle to be available for repositions until. For example if you set repositionUntilTime to 2016-01-19T10:00:00 the vehicle will be available for repositions until 10:00 am UTC on 2016-01-19. (If you don’t set this field, the optimiser will assume the vehicle is not available for repositions).

The example model file example-model-with-repos.json has both of these set. When repositions are set in a model, if the current time is within a prediction period (as defined in the original repositions builder’s configuration file), repositions should be active. In the example model, the current time is overridden using model.configuration.timeOverride to ensure the time is inside the prediction period.

Start up your ODL Live server and then PUT example-model-with-repos.json to a model id in the server, i.e.

PUT my-base-URL/models/RepositionsModel

If you wait a few seconds, the optimiser will do a burst and then the optimiser state, containing vehicle plans, will be available. GET the optimiser state:

GET my-base-URL/models/RepositionsModel/optimiserstate

Now inspect the JSON and look for the field optimiserState.currentRepositionAreas. This field stores the current set of repositions areas, which was selected based on current time and the number of globally available vehicles. It corresponds to one of the elements in the model.data.repositionAreas array, which is copied directly from areas.json.

Also try getting the plan from:

GET my-base-URL/models/RepositionsModel/optimiserstate/plan

If you inspect the planned stops (plan.vehiclePlans[].plannedStops[]), you will see some reposition planned stops. Reposition planned stops have a type field which is equal to REPOSITION and a special object set on the plannedStop.reposition field. The following JSON shows a reposition planned stop from our example model’s plan:

{
  "stopId": "Repos000T3600000_lycfCCaxQNOKBYLIJNbzYA==#000",
  "timeEstimates": {
    ...
  },
  "type": "REPOSITION",
  "reposition": {
    "coordinate": {
      "latitude": 40.67151641845703,
      "longitude": -73.99113464355469
    },
    "consecutiveAnalysis": {
        ... experimental, ignore the data in here
    },
    "medianCrowFlyKm2Centre": 1.0193197620099248,
    "stopId2UseInDispatchObject": "Repos000T3600000_lycfCCaxQNOKBYLIJNbzYA=="
}

You can get the latitude-longitude of the reposition from plannedStop.reposition.coordinate. The stopId of a reposition stop is a combination of the automatically assigned reposition area id and a randomly generated UUID. The convention ODL Live uses for generating reposition stop ids may change in future releases of ODL Live so you should not base any logic on the format of this id.

The logic to use planned reposition stops is different from the logic for normal stops, as the optimiser treats the reposition as optional (i.e. a driver may decide not to perform the reposition). These are the rules:

• Creating the dispatch object. Dispatching a reposition is optional, but advised. You dispatch a reposition in more-or-less the same way you dispatch a normal stop, except you set dispatch.stopId to the id saved in the field stopId2UseInDispatchObject in the object plannedStop.reposition and not to the value in plannedStop.stopId.

  • Unlike normal stops, you can create multiple dispatch objects with the same stopId field.

  • Unlike normal stops, if you dispatch a reposition, the reposition stop will not disappear from the vehicle’s planned stops list.

  • If you have the situation where your last dispatch is a reposition, and the vehicle’s first planned stop is also a reposition, and both repositions are to the same coordinate, ODL Live is telling the vehicle to keep driving to the same reposition location (or to remain at the reposition location if it’s already there).

  • If you have the situation where your last dispatch is a reposition, and the vehicle’s first planned stop is also a reposition, but the repositions are not to the same coordinate, ODL Live is telling the vehicle to stop driving to the dispatched reposition and start driving to the new reposition location.

• Dispatch stickiness. If you create a dispatch object for a reposition stop, and you set this as the last dispatch in the vehicle’s dispatches, ODL Live will apply reposition ‘stickiness’. Reposition ‘stickiness’ encourages the optimiser to stick to the same reposition location, when the last dispatch and first planned stops are both repositions. If there are minor changes in the model (e.g. changed vehicle positions), ODL Live will still keep the vehicle going to the same reposition location unless (by default) this creates more than 5 minutes extra travel time or lateness. This prevents the next reposition location ‘bouncing around’ in response to minor changes in GPS location, but still allows it to be changed when really needed. When the set of repositions areas changes (i.e. into another sub-period, for example every hour), the stickiness applies to the closest area in the currently active set of reposition areas. Therefore if you dispatch to one reposition area at 11:59 but then the set of repositions areas changes at 12:00, ODL Live will try to ‘stick’ the vehicle to the closest new reposition area to the old dispatch.

• Never create stop arrival or completed events for a reposition stop, even if you have dispatched it. ODL Live does not expect arrival or completed events for reposition stops.

• Always send regular GPS updates when you’re doing repositions (e.g. at least every minute). Without GPS updates, ODL Live will not know that a driver has actioned a reposition (i.e. is actually performing it). Without GPS updates it would plan stops using the last dropoff location of the driver instead of the driver’s current location, and would make poor planning decisions if the driver has repositioned. (Note if you’re sending GPS updates you should batch them for efficiency reasons - e.g. update all vehicles or many vehicles in a single HTTP request).

There are two other considerations when implementing repositions:

• Should I send the driver to a reposition location when they’re already near to it? In-practice if a driver is already near to the planned reposition area (e.g. within 1 km), and you know the driver won’t move without being told, you may decide it’s not worth sending them the new reposition message as their current position is fine. Generally speaking ODL Live will try to reposition drivers to areas that they’re already near to. The field plannedStop.reposition.medianCrowFlyKm2Centre gives a measure of the size of the area, derived from the median crow fly distance between the demand points contributing to the area and the centroid of the area itself. You may therefore chose to adopt a rule to skip telling the driver if (for example) the driver’s current distance to the reposition is less than 100m or less than medianCrowFlyKm2Centre. If the driver’s distance to the reposition area is significantly less than medianCrowFlyKm2Centre, they can be considered to be close to the centroid.

• Is an area small enough to be worth travelling to? At slow periods (e.g. at the start or towards the end of a delivery period), the optimiser can predict just one or two areas, which can cover most or all of the delivery region (all in the case of one area). These areas will have a value of estmTravel2NewJobFraction close to 1 in their statistics, in the areas.json file. Travelling to the centroids of these areas will be more-or-less equivalent to travelling to the centroid of demand for your delivery region, and may or may not be worthwhile doing. In practice you may find it worthwhile to just remove areas with higher estmTravel2NewJobFraction from the areas.json file before adding to the model (e.g. for estmTravel2NewJobFraction > 0.75).