A bi-objective study of the minimum latency problem

• Published in: Journal of heuristics 2019-06, Vol.25 (3), p.431-454
• Main Authors: Arellano-Arriaga, N. A., Molina, J., Schaeffer, S. E., Álvarez-Socarrás, A. M., Martínez-Salazar, I. A.
• Format: Article
• Language: English
• Subjects: Approximation; Artificial Intelligence; Calculus of Variations and Optimal Control; Optimization; Evolutionary algorithms; Heuristic methods; Management Science; Mathematics; Mathematics and Statistics; Multiple objective analysis; Operations Research; Operations Research/Decision Theory; Travel time
• ISSN: 1381-1231; 1572-9397
• DOI: 10.1007/s10732-019-09405-0

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.