Metaheuristics for the single vehicle routing problem with deliveries and selective pickups

In this work we propose some metaheuristics to solve a routing problem with mandatory deliveries and selective pickups. There are two integer programming formulations proposed in the literature but they are able to solve to optimality only small-sized instances. Some greedy heuristics and metaheuris...

Full description

Saved in:
Bibliographic Details
Main Authors: Bruck, B. P., dos Santos, Andre Gustavo, Arroyo, J. E. C.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
evolutionary algorithm
Evolutionary computation
Maintenance engineering
metaheuristics
Routing
Sociology
Statistics
vehicle routing
Vehicles
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 728
container_issue
container_start_page 723
container_title
container_volume
creator Bruck, B. P.
dos Santos, Andre Gustavo
Arroyo, J. E. C.
description In this work we propose some metaheuristics to solve a routing problem with mandatory deliveries and selective pickups. There are two integer programming formulations proposed in the literature but they are able to solve to optimality only small-sized instances. Some greedy heuristics and metaheuristics have also been proposed: Tabu Search, General Variable Neighborhood Search and Evolutionary Algorithm. Here we proposed an Iterated Local Search and a Variable Neighborhood Search algorithms, and improve the performance of the previous Evolutionary Algorithm. We present experimental results on 68 instances and show that our methods outperforms the others in several cases, finding better solutions for 21 of them. Using a theoretical lower bound we prove the optimality of the solutions for 8 instances.
doi_str_mv 10.1109/ISDA.2012.6416626
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_6416626</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>6416626</ieee_id><sourcerecordid>6416626</sourcerecordid><originalsourceid>FETCH-LOGICAL-i175t-df42035fed19f8ad122b873e9119fbf84fc1dada7681a81bf9178273980a7c933</originalsourceid><addsrcrecordid>eNpVkMtKAzEYheMNLLUPIG7yAlPzJzO5LEu9FSou1JWLkpn8caLTdkjSim_vgEVwdTjfB2dxCLkENgVg5nrxfDObcgZ8KkuQkssjMjFKQymVqAC0PiYjDrIsFFRw8s8pOP1zpTgnk5Q-GGPAlNFGjcjbI2bb4i6GlEOTqN9GmlukKWzeO6R7bEMzZNzu8kBoH7d1h2v6FXJLHXZhjzFgonbjaMIOmzwQ2ofmc9enC3LmbZdwcsgxeb27fZk_FMun-8V8tiwCqCoXzpecicqjA-O1dcB5rZVAA0OvvS59A846q6QGq6H2BpTmShjNrGqMEGNy9bsbEHHVx7C28Xt1uEr8ALU6Wbw</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Metaheuristics for the single vehicle routing problem with deliveries and selective pickups</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Bruck, B. P. ; dos Santos, Andre Gustavo ; Arroyo, J. E. C.</creator><creatorcontrib>Bruck, B. P. ; dos Santos, Andre Gustavo ; Arroyo, J. E. C.</creatorcontrib><description>In this work we propose some metaheuristics to solve a routing problem with mandatory deliveries and selective pickups. There are two integer programming formulations proposed in the literature but they are able to solve to optimality only small-sized instances. Some greedy heuristics and metaheuristics have also been proposed: Tabu Search, General Variable Neighborhood Search and Evolutionary Algorithm. Here we proposed an Iterated Local Search and a Variable Neighborhood Search algorithms, and improve the performance of the previous Evolutionary Algorithm. We present experimental results on 68 instances and show that our methods outperforms the others in several cases, finding better solutions for 21 of them. Using a theoretical lower bound we prove the optimality of the solutions for 8 instances.</description><identifier>ISSN: 2164-7143</identifier><identifier>ISBN: 9781467351171</identifier><identifier>ISBN: 1467351172</identifier><identifier>EISSN: 2164-7151</identifier><identifier>EISBN: 9781467351188</identifier><identifier>EISBN: 1467351199</identifier><identifier>EISBN: 1467351180</identifier><identifier>EISBN: 9781467351195</identifier><identifier>DOI: 10.1109/ISDA.2012.6416626</identifier><language>eng</language><publisher>IEEE</publisher><subject>Algorithm design and analysis ; evolutionary algorithm ; Evolutionary computation ; Maintenance engineering ; metaheuristics ; Routing ; Sociology ; Statistics ; vehicle routing ; Vehicles</subject><ispartof>2012 12th International Conference on Intelligent Systems Design and Applications (ISDA), 2012, p.723-728</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/6416626$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,27925,54555,54920,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/6416626$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Bruck, B. P.</creatorcontrib><creatorcontrib>dos Santos, Andre Gustavo</creatorcontrib><creatorcontrib>Arroyo, J. E. C.</creatorcontrib><title>Metaheuristics for the single vehicle routing problem with deliveries and selective pickups</title><title>2012 12th International Conference on Intelligent Systems Design and Applications (ISDA)</title><addtitle>ISDA</addtitle><description>In this work we propose some metaheuristics to solve a routing problem with mandatory deliveries and selective pickups. There are two integer programming formulations proposed in the literature but they are able to solve to optimality only small-sized instances. Some greedy heuristics and metaheuristics have also been proposed: Tabu Search, General Variable Neighborhood Search and Evolutionary Algorithm. Here we proposed an Iterated Local Search and a Variable Neighborhood Search algorithms, and improve the performance of the previous Evolutionary Algorithm. We present experimental results on 68 instances and show that our methods outperforms the others in several cases, finding better solutions for 21 of them. Using a theoretical lower bound we prove the optimality of the solutions for 8 instances.</description><subject>Algorithm design and analysis</subject><subject>evolutionary algorithm</subject><subject>Evolutionary computation</subject><subject>Maintenance engineering</subject><subject>metaheuristics</subject><subject>Routing</subject><subject>Sociology</subject><subject>Statistics</subject><subject>vehicle routing</subject><subject>Vehicles</subject><issn>2164-7143</issn><issn>2164-7151</issn><isbn>9781467351171</isbn><isbn>1467351172</isbn><isbn>9781467351188</isbn><isbn>1467351199</isbn><isbn>1467351180</isbn><isbn>9781467351195</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2012</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNpVkMtKAzEYheMNLLUPIG7yAlPzJzO5LEu9FSou1JWLkpn8caLTdkjSim_vgEVwdTjfB2dxCLkENgVg5nrxfDObcgZ8KkuQkssjMjFKQymVqAC0PiYjDrIsFFRw8s8pOP1zpTgnk5Q-GGPAlNFGjcjbI2bb4i6GlEOTqN9GmlukKWzeO6R7bEMzZNzu8kBoH7d1h2v6FXJLHXZhjzFgonbjaMIOmzwQ2ofmc9enC3LmbZdwcsgxeb27fZk_FMun-8V8tiwCqCoXzpecicqjA-O1dcB5rZVAA0OvvS59A846q6QGq6H2BpTmShjNrGqMEGNy9bsbEHHVx7C28Xt1uEr8ALU6Wbw</recordid><startdate>201211</startdate><enddate>201211</enddate><creator>Bruck, B. P.</creator><creator>dos Santos, Andre Gustavo</creator><creator>Arroyo, J. E. C.</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>201211</creationdate><title>Metaheuristics for the single vehicle routing problem with deliveries and selective pickups</title><author>Bruck, B. P. ; dos Santos, Andre Gustavo ; Arroyo, J. E. C.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i175t-df42035fed19f8ad122b873e9119fbf84fc1dada7681a81bf9178273980a7c933</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2012</creationdate><topic>Algorithm design and analysis</topic><topic>evolutionary algorithm</topic><topic>Evolutionary computation</topic><topic>Maintenance engineering</topic><topic>metaheuristics</topic><topic>Routing</topic><topic>Sociology</topic><topic>Statistics</topic><topic>vehicle routing</topic><topic>Vehicles</topic><toplevel>online_resources</toplevel><creatorcontrib>Bruck, B. P.</creatorcontrib><creatorcontrib>dos Santos, Andre Gustavo</creatorcontrib><creatorcontrib>Arroyo, J. E. C.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Bruck, B. P.</au><au>dos Santos, Andre Gustavo</au><au>Arroyo, J. E. C.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Metaheuristics for the single vehicle routing problem with deliveries and selective pickups</atitle><btitle>2012 12th International Conference on Intelligent Systems Design and Applications (ISDA)</btitle><stitle>ISDA</stitle><date>2012-11</date><risdate>2012</risdate><spage>723</spage><epage>728</epage><pages>723-728</pages><issn>2164-7143</issn><eissn>2164-7151</eissn><isbn>9781467351171</isbn><isbn>1467351172</isbn><eisbn>9781467351188</eisbn><eisbn>1467351199</eisbn><eisbn>1467351180</eisbn><eisbn>9781467351195</eisbn><abstract>In this work we propose some metaheuristics to solve a routing problem with mandatory deliveries and selective pickups. There are two integer programming formulations proposed in the literature but they are able to solve to optimality only small-sized instances. Some greedy heuristics and metaheuristics have also been proposed: Tabu Search, General Variable Neighborhood Search and Evolutionary Algorithm. Here we proposed an Iterated Local Search and a Variable Neighborhood Search algorithms, and improve the performance of the previous Evolutionary Algorithm. We present experimental results on 68 instances and show that our methods outperforms the others in several cases, finding better solutions for 21 of them. Using a theoretical lower bound we prove the optimality of the solutions for 8 instances.</abstract><pub>IEEE</pub><doi>10.1109/ISDA.2012.6416626</doi><tpages>6</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 2164-7143
ispartof 2012 12th International Conference on Intelligent Systems Design and Applications (ISDA), 2012, p.723-728
issn 2164-7143
2164-7151
language eng
recordid cdi_ieee_primary_6416626
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Algorithm design and analysis
evolutionary algorithm
Evolutionary computation
Maintenance engineering
metaheuristics
Routing
Sociology
Statistics
vehicle routing
Vehicles
title Metaheuristics for the single vehicle routing problem with deliveries and selective pickups
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-03T22%3A45%3A01IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Metaheuristics%20for%20the%20single%20vehicle%20routing%20problem%20with%20deliveries%20and%20selective%20pickups&rft.btitle=2012%2012th%20International%20Conference%20on%20Intelligent%20Systems%20Design%20and%20Applications%20(ISDA)&rft.au=Bruck,%20B.%20P.&rft.date=2012-11&rft.spage=723&rft.epage=728&rft.pages=723-728&rft.issn=2164-7143&rft.eissn=2164-7151&rft.isbn=9781467351171&rft.isbn_list=1467351172&rft_id=info:doi/10.1109/ISDA.2012.6416626&rft.eisbn=9781467351188&rft.eisbn_list=1467351199&rft.eisbn_list=1467351180&rft.eisbn_list=9781467351195&rft_dat=%3Cieee_6IE%3E6416626%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i175t-df42035fed19f8ad122b873e9119fbf84fc1dada7681a81bf9178273980a7c933%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=6416626&rfr_iscdi=true