WELL OVER HALF A CENTURY HAS PASSED since an article in a management journal originally tackled what has come to be known as the vehicle routing problem. The world is a very different place today, which is why the challenges and impacts of addressing this increasingly complex issue have perhaps never been so significant.
Vehicle routing problems – otherwise known as VRPs – have been a focus of operational research for more than 60 years. They first appeared in an academic paper in 1959, when George Dantzig and John Ramser’s The Truck Dispatching Problem proposed an algorithm for organising fuel deliveries.
As Dantzig and Ramser noted, a VRP represents a generalisation of the travelling salesperson problem (TSP) – one of the most intensively studied puzzles in fields ranging from O.R. to theoretical computer science. As with the TSP, the challenge is essentially one of logistical optimisation.
Specifically, the aim is to maximise the efficiency of transportation operations for a fleet of vehicles based out of a designated hub. It was with this goal in mind that Dantzig and Ramser delineated what they called a ‘near-best solution’ for trucks moving between an oil terminal and a number of service stations.
It hardly need be said that much has changed since 1959. It is unlikely, for example, that the necessary calculations for successful responses to VRPs would now be ‘readily performed by hand’, as Dantzig and Ramser suggested. Ours is a much more complicated and interconnected world.
As a result, increasingly complex VRPs can now be found in numerous sectors – including distribution, travel, waste collection, tourism, healthcare and even humanitarian efforts. Moreover, they no longer revolve almost exclusively around cost considerations: environmental concerns must be taken into account as well.
Fortunately, O.R. has also come a long way. The work described here is a powerful illustration of how state-of-the-art approaches to VRPs are now benefiting a wide array of stakeholders by enhancing the practices of businesses and organisations around the globe.
One of the reasons why VRPs fall within the academic domain of O.R. is that they’re extremely hard to solve
A CHALLENGE DEMANDING TRUE EXPERTISE
More than a decade ago, following a request from a major charity, Güneş Erdoğan started working on what would become known as the VRP Spreadsheet Solver. Arising from a collaboration between five UK universities, the project recognised the growing difficulties facing real-world practitioners confronted by VRPs.
‘One of the reasons why VRPs fall within the academic domain of O.R. is that they’re extremely hard to solve,’ says Erdoğan, now a Professor of Management at the University of Bath. ‘Developing an algorithm for a VRP is a daunting undertaking and not for the faint-hearted.’
Among the principal hurdles is the dynamic retrieval of data from a geographic information system. The recurring costs of acquisition can be prohibitive, and even a measure of in-house knowledge might be insufficient to draw on the consequent wealth of travel and distance data needed to visualise and compare potential solutions.
There are commercial software packages for VRPs, but these can present issues of their own. They must be integrated into existing software, and they are also likely to have a black-box component that protects their programmers’ intellectual property – that is, the algorithm that determines optimal routes.
Erdoğan and the rest of the team sought to circumvent all these obstacles by making the VRP Spreadsheet Solver uniquely accessible, useable and flexible. The result: an open-source, easy-to-understand-and-modify program with an interface in Microsoft Excel – arguably the standard software for small-to-medium-scale quantitative analysis the world over. An example of the output from the VRP Spreadsheet Solver for a tourism company based in Finland can be seen in . Buses subcontracted by the company based in Helsinki pick up customers and return to the port.
FIGURE 1 THE VISUAL OUTPUT FOR A CASE STUDY IN THE TOURISM SECTOR (from Erdoğan, G. (2017): see below).
The VRP Spreadsheet Solver was first released in a beta version in 2013. Its story was only just beginning. A year later, following his arrival at Bath, Erdoğan embarked on research that would eventually greatly expand its scope and functionality.
CYCLE OF IMPROVEMENT
In light of the general shift towards ‘greener’ urban transportation, one of the most common VRPs today is what is sometimes known as the Static Bicycle Rebalancing Problem. This refers to the challenge of how to most effectively redistribute the bikes used in a bike-sharing system.
Ideally, redistribution entails one or more centrally based vehicles picking up and delivering bikes in a way that ensures an optimum mix of bicycles and empty parking slots at every bike-sharing station in a town or city. Having accomplished this task, the vehicles then return to their depot.
‘There have been many initiatives to encourage users themselves to relocate bikes from areas of high supply and low demand to areas of low supply and high demand, but it’s still trucks that tend to do the job,’ says Erdoğan. ‘This can mean significant expense and a heavy CO2 footprint, which is why routing optimisation is acknowledged as key to reducing costs and mitigating environmental impact.’
In 2014, in collaboration with colleagues in the UK and abroad, Erdoğan set about developing an optimal algorithm for managing bike-sharing systems. Crucially, it encompassed those requiring several vehicles and station visits to achieve redistribution.
‘The demands of many large bike-sharing systems simply can’t be satisfied by a single vehicle and a single visit,’ explains Erdoğan. ‘The involvement of multiple vehicles and multiple visits is much more representative of the real world, and it was important to reflect that.’
The algorithm was found to work for systems with up to 60 stations. Its success compelled Erdoğan to incorporate his new research into the design and operation of the VRP Spreadsheet Solver, which was duly transformed into a tool capable of generating substantial savings – sometimes amounting to hundreds of thousands of pounds – in a variety of sectors.
A GLOBAL SOLUTION FOR A GLOBAL PROBLEM
The updated version of the VRP Spreadsheet Solver was downloaded several thousand times after being made freely available on an academic website. Erdoğan now emails it directly to interested parties. To date, it has been used in countries including the US, Finland, Argentina, Turkey and Taiwan.
Its appeal may be especially manifest amid a post-pandemic commercial landscape in which concepts such as working from home, just-in-time logistics and all-round hyperconnectivity have become new normals. As Erdoğan points out, variants of the VRP are now emerging in any context where a pick-up or delivery service is performed.
Take, for instance, a non-profit organisation that provides at-home healthcare services in Istanbul. With three bases, around 90 vehicles and more than 3,000 patients, it has to visit around a thousand separate locations every day. In this case the VRP Spreadsheet Solver has helped address management concerns over the equal allocation of work.
The challenge for another corporate user was to optimise the distribution of food from its warehouses to its 45 supermarkets in central Taiwan. The VRP Spreadsheet Solver’s innate versatility and ease of use meant the company was able to adapt the program to perfectly suit its purposes.
One of the business’s senior managers later contacted Erdoğan, telling him: ‘Since you wrote your solver in Excel, its interface is familiar enough for non-programmers to use and change. We let real users modify your program to split large orders, match truck types to stores, add multiple runs and generate reports.’ The feedback further highlighted distance savings of 30% and cost savings of up to 20% for perishable goods.
There has even been a throwback to the formative work of Dantzig and Ramser: like The Truck Dispatching Problem of 1959, the VRP Spreadsheet Solver has assisted the oil industry. A US-based firm reported savings of around $2 million between 2016 and 2020 after using the software to plot routes between wells for its fleet of 150 tankers.
THE BOTTOM LINE – AND BEYOND
‘The feedback we’ve received shows how widely and effectively this software can be applied,’ says Erdoğan. ‘On the strength of correspondence alone, we know the total savings made possible by the VRP Spreadsheet Solver so far run to millions of pounds. Maybe more so than ever, we also know VRPs are an issue for businesses and organisations all around the world.’
Data from Google Analytics underlines Erdoğan’s observations about the global nature of modern-day VRPs. More than 25,000 people from 136 countries – the US, India, Turkey, Brazil, the UK, Colombia, Germany, Thailand, Canada and Indonesia foremost among them – viewed the VRP Spreadsheet Solver’s host page in the 40 months leading up to December 2020, while a YouTube tutorial video was watched over 70,000 times.
‘I think the bigger picture is vital here,’ says Erdoğan. ‘We’re living in an age when every business is seeking cost efficiencies and when corporate social responsibility and ESG – environmental, social and governance considerations – should be high on the agenda of any organisation. Together, these factors have brought VRPs into ever-sharper focus.’
It is the second of these concerns, particularly in the form of climate action, that really distinguishes the VRPs of today from those of yesteryear. So-called G-VRPs – Green Vehicle Routing Problems – have quickly become a cornerstone of research in this area, with a focus on minimising emissions, noise pollution and accidents. Less distance and less duration frequently translate into benefits that extend far beyond the bottom line.
We’re living in an age when every business is seeking cost efficiencies and when corporate social responsibility and ESG – environmental, social and governance considerations – should be high on the agenda of any organisation
Mindful of this truth, it is perhaps worth noting the final sentence of the abstract of Dantzig and Ramser’s trailblazing paper of 64 years ago. Having outlined their ground-breaking ‘near-optimal solution,’ the authors conceded: ‘No practical applications of the method have been made yet.’
It’s not just a question of producing better outcomes for companies and other organisations: it’s also a question of producing better outcomes for their stakeholders, including society as a whole
The same could hardly be said of Erdoğan’s research. ‘We feel our work is genuinely making a difference in lots of ways,’ he says. ‘It’s not just a question of producing better outcomes for companies and other organisations: it’s also a question of producing better outcomes for their stakeholders, including society as a whole. For me, that goes to the heart of what O.R. should be all about in the 21st century.’
Neil Robinson is the managing editor of Bulletin, a communications consultancy that specialises in helping academic research have the greatest economic, cultural or social impact.
ENSURING FAMILIARITY AND FLOW
Familiarity and ease of use are among the VRP Spreadsheet Solver’s principal attractions from the perspective of businesses and organisations. The software’s Microsoft Excel underpinnings are key here.
For example, the program keeps data about the elements of a specific VRP in separate worksheets. These are then generated in sequence. The incremental flow of information between worksheets is shown in , with the arrows signifying interdependencies.
FIGURE 2 SPREADSHEET STRUCTURE OF VRP SPREADSHEET SOLVER (from Erdoğan, G. (2017): see below).
A CLOSER LOOK AT THE VRP SPREADSHEET SOLVER CONSOLE
The first worksheet users encounter is known as the VRP Solver console. It stores information that is provided to the other worksheets.
As shown in , the console is home to numerous parameters that define a VRP. These include the number of depots and customers, the number of vehicle types and the width of time windows. Users can also adjust settings around options such as the retrieval of data from a geographic information system and the time allowed to work on a problem.
FIGURE 3 VRP SOLVER CONSOLE SPREADSHEET (from Erdoğan, G. (2017): see below).
FOR FURTHER READING
Bulhões, T., A. Subramanian, G. Erdoğan and G. Laporte (2018). The static bike relocation problem with multiple vehicles and visits. European Journal of Operational Research 264: 508-523.
Dantzig, G. and J. Ramser (1959). The truck dispatching problem. Management Science 6: 80-91.
Erdoğan, G., M. Battarra and R. Wolfler Calvo (2015). An exact algorithm for the static rebalancing problem arising in bicycle-sharing systems. European Journal of Operational Research 245: 667-679.
Erdoğan, G. (2017). An open-source spreadsheet solver for vehicle routing problems. Computers and Operations Research 84: 62-72.