A bi-objective study of the minimum latency problem

Abstract

We study a bi-objective problem called the Minimum Latency-Distance Problem (mldp) that aims to minimise travel time and latency of a single-vehicle tour designed to serve a set of client requests. This tour is a Hamiltonian cycle for which we aim to simultaneously minimise the total travel time of the vehicle and the total waiting time (i.e., latency) of the clients along the tour. This problem is relevant in contexts where both client satisfaction and company profit are prioritise. We propose two heuristic methods for approximating Pareto fronts for mldp: SMSA that is based on a classic multi-objective algorithm and EiLS that is based on a novel evolutionary algorithm with intelligent local search. We report computational experiments on a set of artificially generated problem instances using an exact method and the two proposed heuristics, comparing the obtained fronts in terms of various quality metrics.