Solving a Multi-objective Vehicle Routing Problem with Synchronization Constraints.

In this paper, we solve a multi-objective vehicle routing problem with synchronization constraints at the delivery location. Our work is motivated by the delivery of parcels and consumer goods in urban areas, where customers may await deliveries from more than one service provider on the same day. In addition to minimizing travel costs, we also consider a second objective to address customer preferences for a compact schedule at the delivery location, so that all deliveries to a customer happen within a non-predefined time interval. To determine the Pareto fronts, three metaheuristic methods based on large neighborhood search are developed. The results on small instances are compared with an \(\epsilon \)-constraint method using an exact solver. Results for large real-world instances are also presented.