A bi-objective study of the minimum latency problem

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 o...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c319t-40302930ef56a7f03338afc41b37c811591d6c70522630251e71248d0e92eb523
cites cdi_FETCH-LOGICAL-c319t-40302930ef56a7f03338afc41b37c811591d6c70522630251e71248d0e92eb523
container_end_page 454
container_issue 3
container_start_page 431
container_title Journal of heuristics
container_volume 25
creator Arellano-Arriaga, N. A.
Molina, J.
Schaeffer, S. E.
Álvarez-Socarrás, A. M.
Martínez-Salazar, I. A.
description 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.
doi_str_mv 10.1007/s10732-019-09405-0
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2172482434</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2172482434</sourcerecordid><originalsourceid>FETCH-LOGICAL-c319t-40302930ef56a7f03338afc41b37c811591d6c70522630251e71248d0e92eb523</originalsourceid><addsrcrecordid>eNp9kEFLxDAQhYMouK7-AU8Bz9GZTNM0x2VRV1jwoufQZlNt2bZr0gr7741W8OZp5vC99-Bj7BrhFgH0XUTQJAWgEWAyUAJO2AKVlsKQ0afppwIFSsJzdhFjCwCmULRgtOJVI4aq9W5sPj2P47Q78qHm47vnXdM33dTxfTn63h35IQzV3neX7Kwu99Ff_d4le324f1lvxPb58Wm92gpHaEaRAYE0BL5WealrIKKirF2GFWlXICqDu9xpUFLmiVToNcqs2IE30ldK0pLdzL1p92PycbTtMIU-TVqJOqEyoyxRcqZcGGIMvraH0HRlOFoE-y3HznJskmN_5FhIIZpDMcH9mw9_1f-kvgDdsGQu</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2172482434</pqid></control><display><type>article</type><title>A bi-objective study of the minimum latency problem</title><source>ABI/INFORM Global</source><source>Springer Nature</source><creator>Arellano-Arriaga, N. A. ; Molina, J. ; Schaeffer, S. E. ; Álvarez-Socarrás, A. M. ; Martínez-Salazar, I. A.</creator><creatorcontrib>Arellano-Arriaga, N. A. ; Molina, J. ; Schaeffer, S. E. ; Álvarez-Socarrás, A. M. ; Martínez-Salazar, I. A.</creatorcontrib><description>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.</description><identifier>ISSN: 1381-1231</identifier><identifier>EISSN: 1572-9397</identifier><identifier>DOI: 10.1007/s10732-019-09405-0</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>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</subject><ispartof>Journal of heuristics, 2019-06, Vol.25 (3), p.431-454</ispartof><rights>Springer Science+Business Media, LLC, part of Springer Nature 2019</rights><rights>Journal of Heuristics is a copyright of Springer, (2019). All Rights Reserved.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c319t-40302930ef56a7f03338afc41b37c811591d6c70522630251e71248d0e92eb523</citedby><cites>FETCH-LOGICAL-c319t-40302930ef56a7f03338afc41b37c811591d6c70522630251e71248d0e92eb523</cites><orcidid>0000-0002-7002-2753</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2172482434/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2172482434?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11687,27923,27924,36059,44362,74666</link.rule.ids></links><search><creatorcontrib>Arellano-Arriaga, N. A.</creatorcontrib><creatorcontrib>Molina, J.</creatorcontrib><creatorcontrib>Schaeffer, S. E.</creatorcontrib><creatorcontrib>Álvarez-Socarrás, A. M.</creatorcontrib><creatorcontrib>Martínez-Salazar, I. A.</creatorcontrib><title>A bi-objective study of the minimum latency problem</title><title>Journal of heuristics</title><addtitle>J Heuristics</addtitle><description>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.</description><subject>Approximation</subject><subject>Artificial Intelligence</subject><subject>Calculus of Variations and Optimal Control; Optimization</subject><subject>Evolutionary algorithms</subject><subject>Heuristic methods</subject><subject>Management Science</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Multiple objective analysis</subject><subject>Operations Research</subject><subject>Operations Research/Decision Theory</subject><subject>Travel time</subject><issn>1381-1231</issn><issn>1572-9397</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2019</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp9kEFLxDAQhYMouK7-AU8Bz9GZTNM0x2VRV1jwoufQZlNt2bZr0gr7741W8OZp5vC99-Bj7BrhFgH0XUTQJAWgEWAyUAJO2AKVlsKQ0afppwIFSsJzdhFjCwCmULRgtOJVI4aq9W5sPj2P47Q78qHm47vnXdM33dTxfTn63h35IQzV3neX7Kwu99Ff_d4le324f1lvxPb58Wm92gpHaEaRAYE0BL5WealrIKKirF2GFWlXICqDu9xpUFLmiVToNcqs2IE30ldK0pLdzL1p92PycbTtMIU-TVqJOqEyoyxRcqZcGGIMvraH0HRlOFoE-y3HznJskmN_5FhIIZpDMcH9mw9_1f-kvgDdsGQu</recordid><startdate>20190601</startdate><enddate>20190601</enddate><creator>Arellano-Arriaga, N. A.</creator><creator>Molina, J.</creator><creator>Schaeffer, S. E.</creator><creator>Álvarez-Socarrás, A. M.</creator><creator>Martínez-Salazar, I. A.</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>8AL</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>M0C</scope><scope>M0N</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PYYUZ</scope><scope>Q9U</scope><orcidid>https://orcid.org/0000-0002-7002-2753</orcidid></search><sort><creationdate>20190601</creationdate><title>A bi-objective study of the minimum latency problem</title><author>Arellano-Arriaga, N. A. ; Molina, J. ; Schaeffer, S. E. ; Álvarez-Socarrás, A. M. ; Martínez-Salazar, I. A.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c319t-40302930ef56a7f03338afc41b37c811591d6c70522630251e71248d0e92eb523</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2019</creationdate><topic>Approximation</topic><topic>Artificial Intelligence</topic><topic>Calculus of Variations and Optimal Control; Optimization</topic><topic>Evolutionary algorithms</topic><topic>Heuristic methods</topic><topic>Management Science</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Multiple objective analysis</topic><topic>Operations Research</topic><topic>Operations Research/Decision Theory</topic><topic>Travel time</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Arellano-Arriaga, N. A.</creatorcontrib><creatorcontrib>Molina, J.</creatorcontrib><creatorcontrib>Schaeffer, S. E.</creatorcontrib><creatorcontrib>Álvarez-Socarrás, A. M.</creatorcontrib><creatorcontrib>Martínez-Salazar, I. A.</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ABI/INFORM Global</collection><collection>Computing Database</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>ABI/INFORM Collection China</collection><collection>ProQuest Central Basic</collection><jtitle>Journal of heuristics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Arellano-Arriaga, N. A.</au><au>Molina, J.</au><au>Schaeffer, S. E.</au><au>Álvarez-Socarrás, A. M.</au><au>Martínez-Salazar, I. A.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A bi-objective study of the minimum latency problem</atitle><jtitle>Journal of heuristics</jtitle><stitle>J Heuristics</stitle><date>2019-06-01</date><risdate>2019</risdate><volume>25</volume><issue>3</issue><spage>431</spage><epage>454</epage><pages>431-454</pages><issn>1381-1231</issn><eissn>1572-9397</eissn><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.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s10732-019-09405-0</doi><tpages>24</tpages><orcidid>https://orcid.org/0000-0002-7002-2753</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1381-1231
ispartof Journal of heuristics, 2019-06, Vol.25 (3), p.431-454
issn 1381-1231
1572-9397
language eng
recordid cdi_proquest_journals_2172482434
source ABI/INFORM Global; Springer Nature
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
title A bi-objective study of the minimum latency problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-11T19%3A33%3A21IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20bi-objective%20study%20of%20the%20minimum%20latency%20problem&rft.jtitle=Journal%20of%20heuristics&rft.au=Arellano-Arriaga,%20N.%20A.&rft.date=2019-06-01&rft.volume=25&rft.issue=3&rft.spage=431&rft.epage=454&rft.pages=431-454&rft.issn=1381-1231&rft.eissn=1572-9397&rft_id=info:doi/10.1007/s10732-019-09405-0&rft_dat=%3Cproquest_cross%3E2172482434%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c319t-40302930ef56a7f03338afc41b37c811591d6c70522630251e71248d0e92eb523%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2172482434&rft_id=info:pmid/&rfr_iscdi=true