Fast upper and lower bounds for a large‐scale real‐world arc routing problem

Arc routing problems (ARPs) are a special kind of vehicle routing problem, in which the demands are located on edges or arcs, instead of nodes. There is a huge literature on ARPs, and a variety of exact and heuristic algorithms are available. Recently, however, we encountered some real‐life ARPs wit...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2023-01, Vol.81 (1), p.107-124
Main Authors: Boyacı, Burak, Dang, Thu Huong, Letchford, Adam N.
Format: Article
Language:English
Subjects:
Algorithms
arc routing
combinatorial optimization
Heuristic methods
integer programming
Lower bounds
Route planning
Vehicle routing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c2220-b817eb29ff876a0aaa4ed2abcfb8c3c922ada5e19bf7b02ab31b6014dad704093
container_end_page 124
container_issue 1
container_start_page 107
container_title Networks
container_volume 81
creator Boyacı, Burak
Dang, Thu Huong
Letchford, Adam N.
description Arc routing problems (ARPs) are a special kind of vehicle routing problem, in which the demands are located on edges or arcs, instead of nodes. There is a huge literature on ARPs, and a variety of exact and heuristic algorithms are available. Recently, however, we encountered some real‐life ARPs with over 10 000 roads, which is much larger than those usually considered in the literature. For these problems, we develop fast upper‐ and lower‐bounding procedures. We also present extensive computational results.
doi_str_mv 10.1002/net.22120
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2754838927</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2754838927</sourcerecordid><originalsourceid>FETCH-LOGICAL-c2220-b817eb29ff876a0aaa4ed2abcfb8c3c922ada5e19bf7b02ab31b6014dad704093</originalsourceid><addsrcrecordid>eNp1kE1OwzAQhS0EEqWw4AaWWLFIO3aSOlmiqi1IFbAoa2uc2FUrNw52oqo7jsAZOQmGsGU1P--bedIj5JbBhAHwaaO7CeeMwxkZMShFApCKczKKWpGkkOWX5CqEPQBjOStG5HWJoaN922pPsampdcfYKdc3daDGxSW16Lf66-MzVGg19RptHI7O25qir6h3fbdrtrT1Tll9uCYXBm3QN391TN6Wi838MVm_rJ7mD-uk4pxDogomtOKlMYWYISBipmuOqjKqqNKq5BxrzDUrlREKopAyNQOW1VgLyKBMx-Ru-Bt933sdOrl3vW-ipeQiz4q0KLmI1P1AVd6F4LWRrd8d0J8kA_kTmIyByd_AIjsd2OPO6tP_oHxebIaLb5qQbvs</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2754838927</pqid></control><display><type>article</type><title>Fast upper and lower bounds for a large‐scale real‐world arc routing problem</title><source>Wiley</source><creator>Boyacı, Burak ; Dang, Thu Huong ; Letchford, Adam N.</creator><creatorcontrib>Boyacı, Burak ; Dang, Thu Huong ; Letchford, Adam N.</creatorcontrib><description>Arc routing problems (ARPs) are a special kind of vehicle routing problem, in which the demands are located on edges or arcs, instead of nodes. There is a huge literature on ARPs, and a variety of exact and heuristic algorithms are available. Recently, however, we encountered some real‐life ARPs with over 10 000 roads, which is much larger than those usually considered in the literature. For these problems, we develop fast upper‐ and lower‐bounding procedures. We also present extensive computational results.</description><identifier>ISSN: 0028-3045</identifier><identifier>EISSN: 1097-0037</identifier><identifier>DOI: 10.1002/net.22120</identifier><language>eng</language><publisher>Hoboken, USA: John Wiley &amp; Sons, Inc</publisher><subject>Algorithms ; arc routing ; combinatorial optimization ; Heuristic methods ; integer programming ; Lower bounds ; Route planning ; Vehicle routing</subject><ispartof>Networks, 2023-01, Vol.81 (1), p.107-124</ispartof><rights>2022 The Authors. published by Wiley Periodicals LLC.</rights><rights>2022. This article is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c2220-b817eb29ff876a0aaa4ed2abcfb8c3c922ada5e19bf7b02ab31b6014dad704093</cites><orcidid>0000-0003-2184-191X</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Boyacı, Burak</creatorcontrib><creatorcontrib>Dang, Thu Huong</creatorcontrib><creatorcontrib>Letchford, Adam N.</creatorcontrib><title>Fast upper and lower bounds for a large‐scale real‐world arc routing problem</title><title>Networks</title><description>Arc routing problems (ARPs) are a special kind of vehicle routing problem, in which the demands are located on edges or arcs, instead of nodes. There is a huge literature on ARPs, and a variety of exact and heuristic algorithms are available. Recently, however, we encountered some real‐life ARPs with over 10 000 roads, which is much larger than those usually considered in the literature. For these problems, we develop fast upper‐ and lower‐bounding procedures. We also present extensive computational results.</description><subject>Algorithms</subject><subject>arc routing</subject><subject>combinatorial optimization</subject><subject>Heuristic methods</subject><subject>integer programming</subject><subject>Lower bounds</subject><subject>Route planning</subject><subject>Vehicle routing</subject><issn>0028-3045</issn><issn>1097-0037</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2023</creationdate><recordtype>article</recordtype><sourceid>24P</sourceid><recordid>eNp1kE1OwzAQhS0EEqWw4AaWWLFIO3aSOlmiqi1IFbAoa2uc2FUrNw52oqo7jsAZOQmGsGU1P--bedIj5JbBhAHwaaO7CeeMwxkZMShFApCKczKKWpGkkOWX5CqEPQBjOStG5HWJoaN922pPsampdcfYKdc3daDGxSW16Lf66-MzVGg19RptHI7O25qir6h3fbdrtrT1Tll9uCYXBm3QN391TN6Wi838MVm_rJ7mD-uk4pxDogomtOKlMYWYISBipmuOqjKqqNKq5BxrzDUrlREKopAyNQOW1VgLyKBMx-Ru-Bt933sdOrl3vW-ipeQiz4q0KLmI1P1AVd6F4LWRrd8d0J8kA_kTmIyByd_AIjsd2OPO6tP_oHxebIaLb5qQbvs</recordid><startdate>202301</startdate><enddate>202301</enddate><creator>Boyacı, Burak</creator><creator>Dang, Thu Huong</creator><creator>Letchford, Adam N.</creator><general>John Wiley &amp; Sons, Inc</general><general>Wiley Subscription Services, Inc</general><scope>24P</scope><scope>WIN</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0003-2184-191X</orcidid></search><sort><creationdate>202301</creationdate><title>Fast upper and lower bounds for a large‐scale real‐world arc routing problem</title><author>Boyacı, Burak ; Dang, Thu Huong ; Letchford, Adam N.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c2220-b817eb29ff876a0aaa4ed2abcfb8c3c922ada5e19bf7b02ab31b6014dad704093</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2023</creationdate><topic>Algorithms</topic><topic>arc routing</topic><topic>combinatorial optimization</topic><topic>Heuristic methods</topic><topic>integer programming</topic><topic>Lower bounds</topic><topic>Route planning</topic><topic>Vehicle routing</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Boyacı, Burak</creatorcontrib><creatorcontrib>Dang, Thu Huong</creatorcontrib><creatorcontrib>Letchford, Adam N.</creatorcontrib><collection>Wiley Online Library Open Access</collection><collection>Wiley Online Library Free Content</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Networks</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Boyacı, Burak</au><au>Dang, Thu Huong</au><au>Letchford, Adam N.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Fast upper and lower bounds for a large‐scale real‐world arc routing problem</atitle><jtitle>Networks</jtitle><date>2023-01</date><risdate>2023</risdate><volume>81</volume><issue>1</issue><spage>107</spage><epage>124</epage><pages>107-124</pages><issn>0028-3045</issn><eissn>1097-0037</eissn><abstract>Arc routing problems (ARPs) are a special kind of vehicle routing problem, in which the demands are located on edges or arcs, instead of nodes. There is a huge literature on ARPs, and a variety of exact and heuristic algorithms are available. Recently, however, we encountered some real‐life ARPs with over 10 000 roads, which is much larger than those usually considered in the literature. For these problems, we develop fast upper‐ and lower‐bounding procedures. We also present extensive computational results.</abstract><cop>Hoboken, USA</cop><pub>John Wiley &amp; Sons, Inc</pub><doi>10.1002/net.22120</doi><tpages>18</tpages><orcidid>https://orcid.org/0000-0003-2184-191X</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0028-3045
ispartof Networks, 2023-01, Vol.81 (1), p.107-124
issn 0028-3045
1097-0037
language eng
recordid cdi_proquest_journals_2754838927
source Wiley
subjects Algorithms
arc routing
combinatorial optimization
Heuristic methods
integer programming
Lower bounds
Route planning
Vehicle routing
title Fast upper and lower bounds for a large‐scale real‐world arc routing problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T00%3A59%3A01IST&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=Fast%20upper%20and%20lower%20bounds%20for%20a%20large%E2%80%90scale%20real%E2%80%90world%20arc%20routing%20problem&rft.jtitle=Networks&rft.au=Boyac%C4%B1,%20Burak&rft.date=2023-01&rft.volume=81&rft.issue=1&rft.spage=107&rft.epage=124&rft.pages=107-124&rft.issn=0028-3045&rft.eissn=1097-0037&rft_id=info:doi/10.1002/net.22120&rft_dat=%3Cproquest_cross%3E2754838927%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c2220-b817eb29ff876a0aaa4ed2abcfb8c3c922ada5e19bf7b02ab31b6014dad704093%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2754838927&rft_id=info:pmid/&rfr_iscdi=true