Problem definition and formulation: HF-CVRP Section 6 contains the conclusions and proposed future research directions.Ģ. Section 5 provides an overview of the experimental results. Section 4 describes the proposed approach in details. Section 3 offers a brief literature review. This paper is organised as follows: Section 2 gives a general problem overview and formulation. Validation of the proposed solution through extensive benchmarking. This paper provides the following contributions:įormalisation of a two-step clustering technique to group customers based on different multiple constraints įormalisation of the Monte Carlo Tree Search (MCTS) applied to the Hybrid Fleet-Capacitated Vehicle Routing problem (HF-CVRP) Īpplication of a flexible MCTS to solve the HF-CVRP combined with a cluster-first route-second approach This solution aims to reflect a real case scenario, where a transportation company has different types of vehicles, ICEs and EVs, with variable capacities, available at their depot and would like to effectively maximise the usage of EVs for delivering its parcels, but also minimise the travelled distance while maximising the number of visited customers. In this paper, we propose a flexible solution for scheduling parcels' delivery using a hybrid fleet of vehicles. A graduate shift towards the usage of the Electric Vehicles (EVs) powered by renewed energy sources could help reducing GHG emissions by 80–95% by 2050 in Europe (European Environment Agency, 2016). Given the global concern related to the CO 2 emissions, the need to move away from Internal Combustion Engines (ICEs) or progressively reduce their usage, is becoming a priority. With growing online retail competition and a shift towards one-day delivery, vehicle pollution is increasing, and roads are becoming even more congested. Medium and heavy-duty trucks are responsible for the 23% of the emissions (United States Environmental Protection Agency, 2020). The transportation sector is one of the largest contributors to greenhouse gas (GHG) emissions in the USA. The solution quality is similar to other CVRP implementations when applied to classic VRP test-instances and its quality is superior in real-world scenarios when constraints for EVs must be used. This two-step procedure allows problems with thousands of customers and hundreds of vehicles to be solved accomodating customised vehicle constraints. A Tabu Search step further optimises the solution. Moreover, EVs are preferred overother vehicles when assigning parcels to vehicles. The routing heuristic introduces a novel Monte–Carlo Tree Search enriched with a custom objective function, rollout policy and a tree pruning technique. This reduces the solution space in a meaningful way for the routing. Clustering is achieved with two algorithms: a capacitated k-median algorithm that groups parcel drop-offs based on customer location and parcel weight and a hierarchical constrained minimum weight matching clustering algorithm which considers EVs' range. A cluster-first, route-second heuristic approach is proposed to maximise the number of parcels delivered. Driving range and different vehicles' capacity constraints must be considered.
The fleet heterogeneity brings new challenges to the Capacitated Vehicle Routing Problem (CVRP).
The rise in EVs popularity, combined with reducing emissions and cutting costs, encouraged delivery companies to integrate them in their fleets.
0 kommentar(er)
