Program > By author > Breunig Ulrich

A simple LNS-based heuristic for Two-Echelon Routing Problems
Ulrich Breunig  1, *@  , Verena Schmid  2@  , Richard Hartl  3@  , Thibaut Vidal  4@  
1 : University of Vienna  -  Website
Oskar-Morgenstern-Platz 1, 1090 Vienna -  Austria
2 : Christian Doppler Laboratory for Effcient Intermodal Transport Operations, University of Vienna
3 : University of Vienna
4 : Pontifical Catholic University of Rio de Janeiro  (PUC Rio)
* : Corresponding author

We address optimisation problems arising in the context of city logistics. The focus lies on two-level transportation systems with a single depot: both the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Two-Echelon Location Routing Problem (2ELRP) seek to produce vehicle itineraries to deliver goods to customers with mandatory transit through intermediate facilities. In the 2EVRP the locations of intermediate facilities – called satellites – are given and their use is not associated with additional cost. The 2ELRP problem class explicitly takes strategical decisions into account: the use of vehicles and satellites incurs additional fixed costs. The first echelon with large trucks operating between depot and satellites can be seen as a VRP with split deliveries. The second echelon corresponds to a multi-depot VRP: smaller vehicles operate between several satellites and the customers.

A local-search metaheuristic, based on the principle of destroy and repair from Large Neighbourhood Search, is developed and implemented to find high quality solutions within limited computing time. The proposed algorithm is tested with several different benchmark instances for two-tiered problem classes with a single depot.


Online user: 1