Research Output

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

  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.

  • Date:

    13 July 2019

  • Publication Status:

    Published

  • DOI:

    10.1145/3321707.3321767

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    000 Computer science, information & general works

  • Funders:

    Edinburgh Napier Funded

Citation

Urquhart, N., Hoehl, S., & Hart, E. (2019). An Illumination Algorithm Approach to Solving the Micro-Depot Routing Problem. In Genetic and Evolutionary Computation Conference (GECCO '19)https://doi.org/10.1145/3321707.3321767

Authors

Keywords

vehicle routing problems (VRP); quality-diversity algorithms; micro-depots; delivery companies; illumination algorithm; couriers; emissions

Monthly Views:

Available Documents