An Illumination Algorithm Approach to Solving the Micro-Depot Routing Problem

Urquhart, Neil; Hoehl, Silke; Hart, Emma

Abstract

An increasing emphasis on reducing pollution and congestion in city centres combined with an increase in online shopping is changing the ways in which logistics companies address vehicle routing problems (VRP). We introduce the {\em micro-depot}-VRP, in which a single supply vehicle is used to supply a set of micro-depots distributed across a city; deliveries are then made from the micro-depot by couriers using electric vehicles, bicycles and on foot.
We present a formal definition of the problem, and propose a representation that can be used with an optimisation algorithm to minimise the total cost associated with delivering packages. Using five instances created from real-data obtained from delivery companies operating within the City of Frankfurt, we apply an illumination algorithm in order to obtain a set of results that minimise costs but have differing characteristics in terms of emissions, distance travelled and number of couriers used. Results show that solutions can be obtained that have equivalent costs to the baseline standard VRP solution, but considerably improve on this in terms of minimising the secondary criteria relating to emissions, couriers and distance.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: Genetic and Evolutionary Computation Conference (GECCO '19)
• Start Date: Jul 13, 2019
• End Date: Jul 17, 2019
• Acceptance Date: Mar 21, 2019
• Publication Date: Jul 13, 2019
• Deposit Date: Apr 8, 2019
• Publisher: Association for Computing Machinery (ACM)
• Pages: 1347-1355
• Book Title: GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion
• ISBN: 978-1-4503-6748-6
• DOI: https://doi.org/10.1145/3321707.3321767
• Keywords: vehicle routing problems (VRP); quality-diversity algorithms; micro-depots; delivery companies; illumination algorithm; couriers; emissions
• Public URL: http://researchrepository.napier.ac.uk/Output/1715163
• Publisher URL: https://dl.acm.org/citation.cfm?doid=3321707.3321767