Improving Dynamic Route Optimisation by making use of Historical Data

Abstract

In thedynamic world we live in, the transportation of people and goods in a reliable,efficient and timely manner has grown to be more important than ever. Roads andcities are becoming more congested and the impact of greenhouse gasses canalready be observed. The need for controlling transportation systems, andspecifically fleets of vehicles, more efficiently is therefore now higher thanever. Few methods exist in the literature which utilise historical data toincrease the efficiency of dynamic fleets of vehicles. This work thereforeproposes a novel anticipatory insertion method which incorporates a set ofpredicted requests to beneficially adjust the routes of a fleet of vehicles, inreal-time. This set of predicted requests is derived, in advance, fromhistorical data by clustering comparable requests and predicting similarrequests when assumed patterns in their occurrence are present. This method iscombined with a developed dynamic vehicle routing solver which makes use of arange of heuristics and adaptive large neighbourhood search. The proposedmethod is evaluated using numerical simulations on a range of real-worldproblem instances with up to 1.655 requests per day. These instances representdynamic multi-depot capacitated pickup and deliver vehicle routing problemswith time windows. The method is compared with several other approaches and inorder to quantify the added value of making use of historical data, the methodis benchmarked against a comparable reactive approach which also makes use ofadaptive large neighbourhood search. It is shown that, by making use of theproposed method, on average, 4,58% less distance is required to be travelled bya fleet vehicles while additionally 3,35% fewer vehicles are required to fulfilthe same set of requests.