Route optimization


The methodology and the complexity of the Route Optimisation depend on the nature of the DRT routes and its degree of flexibility. Options for the route include:

  • Route is defined, may deviate on request and must return to deviation point
  • Route ends and broad direction are defined. Service may deviate on request within a given boundary, does not have to return to deviation point.
  • Route ends are defined. One or more intermediate points are defined through which the service must pass (this fixes the general direction of the route). Optionally, the time at the intermediate point may be also fixed – e.g. if this is an interchange point with other routes or modes.
  • Notional route is established in the system just as a starting point. The route is formed based on the customer requests.
  • A service area is defined without any predefined route. The service takes shape based entirely on customer requests.

The Route Optimisation application arranges the route to find the best balance of:

  • The customer requests
  • The service specification
  • The resources utilised

This balance is usually achieved by a number of constraints built in to the optimising algorithms, such as:

  • Maximum deviation permitted:
    • Service boundary set at a maximum distance from the notional route (e.g. 2 kilometres either side)
    • Total time/distance not permitted to exceed a set percentage of direct time/distance (e.g. not greater that 25% additional time/distance
  • Requirement to pass through intermediate points
  • No backtracking permitted
  • Pick-up/set-down times permitted to deviate up to a maximum number of minutes from the customer’s request (or even from the initial commitment at time of booking)

As with the Traveller Assignment, the Route Optimisation application may be run three levels:

  • Adjust the route if/as required for each booking, subject to the constraints, without any re-optimisation or inter-route optimisation.
  • At some time prior to the trip, re-optimise across all routes in the service area (or sub-area), and reassign travellers if necessary
  • Dynamically re-optimise across the service area

The Route Optimisation application generates the route data for the Operations Management function and for the driver’s on-board unit (if used).

Technologies, data and resources

The Route Optimisation system consists of software applications. The algorithms provide the central ‘engine’ and achieve the optimisation. The Route Optimisation application requires interfaces with the Traveller Assignment application. It must also export the assignments to the Operations Management or CAD/AVM systems, and the driver’s on-board unit.

Advantages and Cautions

The primary advantages of Route Optimisation applications for DRT are to:

  • Manage the Route Optimisation process, which is beyond human capacity where significant numbers of routes, vehicles and bookings are involved
  • Manage the Route Optimisation quickly (i.e. within seconds) to support the Traveller Assignment process, and hence so that the booking call is completed in acceptable time
  • Facilitate re-optimisation, both to optimise resource requirements and to improve the service quality for travellers (e.g. find more direct paths).
  • Generate the driver’s route/schedule in electronic and/or printout form

The principal cautions in relation to Route Optimisation applications for DRT are:

  • Route optimisation algorithms are complex. This has three main implications:
    • The desired level of route design and flexibility might be beyond the capacity of what the DRT operator can afford, or indeed that the supplier can develop
    • It can be difficult to determine if the route optimisation produces truly optimal results
    • Significant processing power may be required (this is a diminishing problem as even PCs are increasingly powerful and have substantial RAM/ROM)
  • The data requirements, set-up and calibration may be onerous. Travel times may be onerous to establish initially, although the CAD/AVM service should be able to populate that accurately over some months of usage.
  • Maps might not have all possible links, and some links shown in the maps might not be suitable for vehicles (especially in rural areas). In urban areas, information on one-way streets and restricted turns may be absent or out of date.

Relevant Case Studies

Prince William County

References

You are here ITS Applications Demand Responsive Transport Route optimization