Multi-Objective Optimization of Bike Routes for Last-Mile Package Delivery with Drop-Offs

This paper focuses on modeling and solving a last-mile package delivery routing problem with third-party drop-off points. The study is applicable to small or medium-sized delivery companies, which use bikes for performing the routes in an influence area bounded to a city. This routing setup has been formulated as a multi-objective optimization problem, balancing three conflicting objectives: a weighted measure of distance of the route, the safety of the biker, and the economic profit yielded by the delivery of goods to customers. Six different and heterogeneous multi-objective algorithms have been applied to the modeled problem: NSGA-II, MOCell, SMPSO, MOEA/D, NSGA-III and MOMBI2. In order to evaluate the performance of these algorithms, we have devised three experimental setups encompassing different real localizations in Madrid (Spain). For deploying a realistic simulation platform, the open-source Open Trip Planner framework has been used as a proxy evaluator of the produced routes. Results have been compared using the obtained Median and Inter Quartile Range of the hypervolume values reached by the algorithms. Conclusions drawn from this study show that MOCell is the best method for the proposed problem, reaching routes that balance the considered three objectives in a more Pareto-optimal fashion than the rest of counterparts in the benchmark.