A Parallelised Large Neighbourhood Search Heuristic for the Asymmetric Two-Echelon Vehicle Routing Problem with Swap Containers for Cargo-Bicycles

Abstract Cargo-bicycles are a promising alternative to conventional vans in city logistics in response to increasing urbanisation and environmental damage caused by city traffic. The delivery structure is modelled with the well studied Two-Echelon Capacitated Vehicle Routing Problem (2E-CVRP), which uses cross-docking from vans to cargo-bicycles at so-called satellites. To reduce the extra handling effort compared to single-tier systems, swap containers are used. Furthermore, for cargo-bicycles the consideration of asymmetric distance matrices is important. Therefore, we present the Asymmetric 2E-CVRP with Swap Containers and develop an efficient Parallelised Large Neighbourhood Search heuristic, that is further improved using a first-level heuristic. The heuristic is tested using the symmetric 2E-CVRP benchmark instances from the literature, outperforms previous heuristics for large instances and finds new best-known solutions. Subsequently, the heuristic is applied to a case study in Munich with 22 newly generated instances, each containing 200 customers and asymmetric distances. The results allow quantitative insights into the cost and CO2e emissions savings of the investigated cargo-bicycle set-up compared to conventional van delivery.