Simulating Dynamic Vehicle Routing Problems with Athos

Hoffman, Benjamin; Guckert, Michael; Chalmers, Kevin; Urquhart, Neil

Abstract

Complex routing problems, such as vehicle routing problems with additional constraints, are both hard to solve and hard to express in a form that is accessible to the human expert and at the same time processible by a computer system that is supposed to produce a solution of sufficient quality. The formulation must be formal enough to avoid ambiguities and also comprehensible enough to be created, discussed and shared by domain experts. In this paper, we present the domain specific language Athos in which complex routing problems can be expressed in a computationally independent, human-readable form. Athos is then transformed into code that can be run in an adequate target platform. Suitable methods for solving problems are available and applied to the given problem. We present a case study in which we use a genetic algorithm to solve instances of a vehicle routing problem with time windows and demonstrate the end to end process to produce a solution in the Athos environment. Moreover, we show how the Athos system goes beyond optimisation of static routes and can be used as a tool to simulate the impact of traffic and congestion on the tours. We call this extended problem a dynamic vehicle routing problem with time windows.

Citation

Hoffman, B., Guckert, M., Chalmers, K., & Urquhart, N. (2019, June). Simulating Dynamic Vehicle Routing Problems with Athos. Presented at ECMS2019: 33rd INTERNATIONAL ECMS CONFERENCE ON MODELLING AND SIMULATION, Napoli, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: ECMS2019: 33rd INTERNATIONAL ECMS CONFERENCE ON MODELLING AND SIMULATION
• Start Date: Jun 11, 2019
• End Date: Jun 14, 2019
• Acceptance Date: Mar 25, 2019
• Publication Date: 2019-06
• Deposit Date: Mar 28, 2019
• Publicly Available Date: Jun 30, 2019
• Volume: 33
• Pages: 296-302
• Series ISSN: 2522-2414
• Book Title: Proceedings of the 33rd International ECMS Conference on Modelling and Simulation ECMS 2019
• ISBN: 978-3-937436-65-4
• DOI: https://doi.org/10.7148/2019-0296
• Keywords: Domain-specific language, Agent-based modelling, Evolutionary Algorithms, Vehicle Routing With Time Windows
• Public URL: http://researchrepository.napier.ac.uk/Output/1693394
• Contract Date: Mar 28, 2019