Whatever the sector your business operates in, it’s likely that one, or many, of your key organisational challenges start with a defined objective measure;
How many units will we sell this year? How do we schedule our large fleet of vehicles? how do we automate production processes and reduce expenditure? Each case requires a detailed understanding of the problem in combination with the confidence to apply the right business intelligence tool that is required to find a solution: optimisation.
Solving an optimisation problem involves finding a solution which gives the optimal result in terms of defined objective measures. This solution often must satisfy many constraints. There are many forms that these problems can take, each of which requiring a different class of algorithm to find a solution efficiently.
Amid the exponential growth in data of the digital age, with a plethora of tools at our fingertips, one area where optimisation problems arise abundantly is in the on-demand economy.
The Dial-a-Ride-Problem
A new on-demand business model in a traditional sector is the emergence of on-demand public transport. A hybrid between taxi and bus; a passenger may be picked up at a non-standard location, convenient for them, but will probably share their ride and take an in-direct path to their destination which accommodates other passengers’ journeys.
Such a service, launched by the Oxford Bus Company in June 2019, is PickMeUp; On-Demand public transport, cheaper than taxis yet more accessible than buses. The provision of this kind of service has become feasible due to the public’s familiarity with procuring transport via apps, thanks to Uber and other private ride-sharing platforms.
The efficient dispatch of a fleet of vehicles to deliver these services presents a significant operational challenge. With dynamically emerging pick-up and drop-off points, combined with multiple, overlapping, routes to consider, select, and combine; this is an excellent example of an application for which mathematical optimisation offers great value. The assignment of vehicles to on-demand transport services is known as the dial-a-ride problem (DARP). The difference between a taxi-service and DARP is that DARP allows ridesharing. This extra flexibility adds to the complexity of the optimisation problem. Other applications with similar underlying resource dispatch problems include same-day courier services, meal delivery and non-emergency medical transport.
It is relatively simple to formulate an algorithm to solve a DARP — e.g. using a 3-index formulation — but the time taken to find a solution rapidly increases as the numbers of passengers and vehicles increase. To mitigate this, one can turn to approximate methods which aim to find a near-optimal solution with significantly less computational effort. One such class of methods are known as cluster first — route second methods. These methods first group together pick-up and drop-off requests to reduce the number of variables in the model before constructing a route. In general, these methods require far less computation than direct optimisation (without first clustering the journey requests) but at the cost of finding only a near-optimal solution. However, as many problems are intractable when posed as a direct optimisation, these approximations are often necessary.
As shown above, one particular cluster first — route second method is to form mini-clusters of routes where each mini-cluster consists of a series of journeys for a vehicle and where this series of routes begins and ends with the vehicle empty. Once the mini-clusters have been determined and an initial vehicle assignment to each of these has been made, column generation can be used to determine which vehicle assignment changes would lead to an improved solution. The column generation method selects the alternative assignment with the most negative marginal cost repeatedly until no more negative marginal cost alternatives remain. Once this procedure terminates, the optimal assignments of vehicles to mini-clusters is chosen. Finally, each vehicle’s assigned route, which at this point is a series of mini-clusters, is optimised by removing the clustering restriction which allows for the vehicle to perform its assigned tasks in a more optimal order.
Are you implementing the right solutions?
There are many off-the-shelf software solutions available for DARPs. Off-the-shelf solutions can be cheaper and simpler to implement for standard problems. However, in the cases in which services have more complex or unique features, a bespoke mathematical optimisation solution may offer benefits to productivity and customer experience by incorporating a greater number of situation specific requirements. Some examples of features that increase the complexity of these DARP are:
- A heterogeneous vehicle fleet (e.g. a mixture of deliverers on motorbike, bicycle, or car),
- A range of passenger access requirements,
- Multiple and competing objectives (e.g. minimise costs and maximise customer service),
- Travel times which are significantly affected by traffic conditions (e.g. inner-city journeys in rush hours),
- Fleet availability which changes throughout the day (e.g. drivers are self-employed),
- Multiple vehicle depots (e.g. drivers own the vehicles).
In general, the more unique the problem at hand, the more there is to be gained from a bespoke approach beyond what can be achieved with off-the-shelf software.
Solve your key challenges
The Smith Institute creates bespoke optimisation algorithms for our clients and DARP was the focus of our recent internal hackathon. This hackathon comprised of two and a half days of our team implementing an algorithm based on mini-clustering and column generation to solve a DARP. Proof of concept software was created, tested and implemented to optimise an example scenario. These hackathons allow us to extend our optimisation capabilities through trying new algorithms, learning their strengths and limitations in the process. Increasing our capability enables us to offer algorithms which are more closely aligned to our clients’ needs.
