A bi-objective study of the minimum latency problem

被引:4
作者
Arellano-Arriaga, N. A. [1 ,2 ]
Molina, J. [3 ]
Schaeffer, S. E. [1 ]
Alvarez-Socarras, A. M. [1 ]
Martinez-Salazar, I. A. [1 ]
机构
[1] Univ Autonoma Nuevo Leon, PISIS, FIME, San Nicolas De Los Garza, Mexico
[2] Univ Malaga, Programa Doctorado Econ & Empresa, Malaga, Spain
[3] Univ Malaga, Dept Econ Aplicada Matemat, Malaga, Spain
关键词
Combinatorial optimisation; Distance; Genetic algorithms; Latency; Meta-heuristics; Multi-objective optimisation; Multiple-objective programming; EFFICIENT; DISTANCE;
D O I
10.1007/s10732-019-09405-0
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:431 / 454
页数:24
相关论文
共 71 条
[41]   An adaptive energy-efficient and low-latency MAC for tree-based data gathering in sensor networks [J].
Lu, Gang ;
Krishnamachari, Bhaskar ;
Raghavendra, Cauligi S. .
WIRELESS COMMUNICATIONS & MOBILE COMPUTING, 2007, 7 (07) :863-875
[42]   TIME-DEPENDENT TRAVELING SALESMAN PROBLEM - THE DELIVERYMAN CASE [J].
LUCENA, A .
NETWORKS, 1990, 20 (06) :753-763
[43]  
Madhyastha HV, 2006, P 6 ACM SIGCOMM C IN, P99, DOI DOI 10.1145/1177080.1177092
[44]   An improved version of the augmented ε-constraint method (AUGMECON2) for finding the exact pareto set in multi-objective integer programming problems [J].
Mavrotas, George ;
Florios, Kostas .
APPLIED MATHEMATICS AND COMPUTATION, 2013, 219 (18) :9652-9669
[45]   Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems [J].
Mavrotas, George .
APPLIED MATHEMATICS AND COMPUTATION, 2009, 213 (02) :455-465
[46]   A new formulation for the Traveling Deliveryman Problem [J].
Mendez-Diaz, Isabel ;
Zabala, Paula ;
Lucena, Abilio .
DISCRETE APPLIED MATHEMATICS, 2008, 156 (17) :3223-3237
[47]   INTEGER PROGRAMMING FORMULATION OF TRAVELING SALESMAN PROBLEMS [J].
MILLER, CE ;
TUCKER, AW ;
ZEMLIN, RA .
JOURNAL OF THE ACM, 1960, 7 (04) :326-329
[48]   A Multi-start Algorithm with Intelligent Neighborhood Selection for solving multi-objective humanitarian vehicle routing problems [J].
Molina, J. ;
Lopez-Sanchez, A. D. ;
Hernandez-Diaz, A. G. ;
Martinez-Salazar, I. .
JOURNAL OF HEURISTICS, 2018, 24 (02) :111-133
[49]   SSPMO:: A scatter tabu search procedure for non-linear multiobjective optimization [J].
Molina, Julian ;
Laguna, Manuel ;
Marti, Rafael ;
Caballero, Rafael .
INFORMS JOURNAL ON COMPUTING, 2007, 19 (01) :91-100
[50]  
Nagarajan V, 2008, LECT NOTES COMPUT SC, V5171, P193