Optimised solutions to the last-mile delivery problem in London using a combination of walking and driving
- PDF / 876,864 Bytes
- 49 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 165 Views
Optimised solutions to the last-mile delivery problem in London using a combination of walking and driving Antonio Martinez-Sykora1 · Fraser McLeod2 · Carlos Lamas-Fernandez3 · Tolga Bekta¸s4 · Tom Cherrett2 · Julian Allen5 Accepted: 29 August 2020 © The Author(s) 2020
Abstract Inspired by actual parcel delivery operations in London, this paper describes a two-echelon distribution system that combines the use of driving and walking as part of last-mile deliveries in urban areas for a single driver. The paper presents an optimisation model that explicitly treats and integrates the driving and walking elements, and describes a branch-and-cut algorithm that uses new valid inequalities specifically tailored for the problem at hand. Computational results based on real instances obtained from a courier operating in London are presented to show the performance of the algorithm. Keywords Vehicle routing · Last-mile delivery · Branch-and-cut · Urban freight
1 Background and motivation Sharp growth in e-commerce sales in developed countries worldwide over the last decade has led to substantial increases in urban freight goods transport, with associated negative impacts on road traffic, availability of kerbside space and air quality. In the UK, total measured national volumes in the parcels market increased by 10%, to 2.6 billion items, in 2018–19 (Ofcom 2019). This growth and worsening road traffic and parking conditions in city centres make parcel deliveries ever-more difficult to perform. Factors that increase vehicle use for parcel deliveries include the growing trend for same-day and ‘instant’ deliveries (within 2 h) leading to fragmentation of consignments and increasing the number and frequency of
B
Tolga Bekta¸s [email protected]
1
Centre for Operational Research, Management Science and Information Systems, University of Southampton, Southampton SO17 1BJ, UK
2
Faculty of Engineering and Physical Sciences, University of Southampton, Southampton SO17 1BJ, UK
3
NIHR CLAHRC Wessex, University of Southampton, Southampton SO17 1BJ, UK
4
University of Liverpool Management School, University of Liverpool, Chatham Street, Liverpool L69 7ZH, UK
5
Faculty of Architecture and the Built Environment, University of Westminster, London NW1 5LS, UK
123
Annals of Operations Research
deliveries (Dablanc et al. 2017) and the substantial number of competing freight transport operators that result in much duplication of van activity (Browne et al. 2014). Last-mile parcel delivery operations, characterised by multi-player, multi-drop vehicle rounds where kerbside access is needed are at direct odds with an infrastructure designed and legislated in favour of passenger transportation (Allen and Browne 2014). Many of our major cities and particularly London have seen a considerable shift to walking, cycling and the use of buses over the past 20 years together with a fall in car traffic (Transport for London 2016). As a result, road space is being increasingly reallocated in favour of dedicated cycle and bus lanes, as w
Data Loading...
