An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs

Carlos Rey; Paolo Toth; Daniele Vigo

doi:10.1109/SCCC51225.2020.9281164

An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs

Carlos Rey
, Paolo Toth
, Daniele Vigo

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

In this paper the Traveling Salesman Problem with pickup, delivery and handling costs is studied. We have to find a route from a depot to a set of customers, each of which requires a pickup and delivery service the goal is to minimize the global routing and handling cost. We have developed an Iterated Local Search for this problem combining different heuristics of the Traveling Salesman Problem, and using frequency of improvements and a perturbation with memory the proposed algorithm is tested on different benchmark instances from the literature with up to 200 vertices, obtaining high quality solutions in reasonable computing times.

Original language	English
Title of host publication	2020 39th International Conference of the Chilean Computer Science Society (SCCC)
Subtitle of host publication	[Proceedings]
Publisher	IEEE Computer Society
Number of pages	8
ISBN (Electronic)	9781728183282
DOIs	https://doi.org/10.1109/SCCC51225.2020.9281164
Publication status	Published - 9 Dec 2020
Event	39th International Conference of the Chilean Computer Science Society, SCCC 2020 - Coquimbo, Chile Duration: 16 Nov 2020 → 20 Nov 2020

Publication series

Name	Proceedings - International Conference of the Chilean Computer Science Society, SCCC
Volume	2020-November
ISSN (Print)	1522-4902

Conference

Conference	39th International Conference of the Chilean Computer Science Society, SCCC 2020
Country/Territory	Chile
City	Coquimbo
Period	16/11/20 → 20/11/20

Bibliographical note

Funding Information:
This work was funded by the National Agency for Research and Development (ANID)/ Scholarship Program/Doctorado Becas Chile/2018-72190600.

Publisher Copyright:
© 2020 IEEE.

Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

Funding

This work was funded by the National Agency for Research and Development (ANID)/ Scholarship Program/Doctorado Becas Chile/2018-72190600.

Keywords

Combinatorial Optimization
Handling Cost
Iterated Local Search
Traveling Salesman Problem

Access to Document

10.1109/SCCC51225.2020.9281164

Persistent URL (handle)

Persistent link

Cite this

Rey, C., Toth, P., & Vigo, D. (2020). An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs. In 2020 39th International Conference of the Chilean Computer Science Society (SCCC): [Proceedings] Article 9281164 (Proceedings - International Conference of the Chilean Computer Science Society, SCCC; Vol. 2020-November). IEEE Computer Society. https://doi.org/10.1109/SCCC51225.2020.9281164

@inproceedings{c9fd1196b7604d8687baad9ffd48c7dc,

title = "An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs",

abstract = "In this paper the Traveling Salesman Problem with pickup, delivery and handling costs is studied. We have to find a route from a depot to a set of customers, each of which requires a pickup and delivery service the goal is to minimize the global routing and handling cost. We have developed an Iterated Local Search for this problem combining different heuristics of the Traveling Salesman Problem, and using frequency of improvements and a perturbation with memory the proposed algorithm is tested on different benchmark instances from the literature with up to 200 vertices, obtaining high quality solutions in reasonable computing times.",

keywords = "Combinatorial Optimization, Handling Cost, Iterated Local Search, Traveling Salesman Problem",

author = "Carlos Rey and Paolo Toth and Daniele Vigo",

note = "Funding Information: This work was funded by the National Agency for Research and Development (ANID)/ Scholarship Program/Doctorado Becas Chile/2018-72190600. Publisher Copyright: {\textcopyright} 2020 IEEE. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 39th International Conference of the Chilean Computer Science Society, SCCC 2020 ; Conference date: 16-11-2020 Through 20-11-2020",

year = "2020",

month = dec,

day = "9",

doi = "10.1109/SCCC51225.2020.9281164",

language = "English",

series = "Proceedings - International Conference of the Chilean Computer Science Society, SCCC",

publisher = "IEEE Computer Society",

booktitle = "2020 39th International Conference of the Chilean Computer Science Society (SCCC)",

address = "United States",

}

Rey, C, Toth, P & Vigo, D 2020, An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs. in 2020 39th International Conference of the Chilean Computer Science Society (SCCC): [Proceedings]., 9281164, Proceedings - International Conference of the Chilean Computer Science Society, SCCC, vol. 2020-November, IEEE Computer Society, 39th International Conference of the Chilean Computer Science Society, SCCC 2020, Coquimbo, Chile, 16/11/20. https://doi.org/10.1109/SCCC51225.2020.9281164

An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs. / Rey, Carlos; Toth, Paolo; Vigo, Daniele.
2020 39th International Conference of the Chilean Computer Science Society (SCCC): [Proceedings]. IEEE Computer Society, 2020. 9281164 (Proceedings - International Conference of the Chilean Computer Science Society, SCCC; Vol. 2020-November).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs

AU - Rey, Carlos

AU - Toth, Paolo

AU - Vigo, Daniele

N1 - Funding Information: This work was funded by the National Agency for Research and Development (ANID)/ Scholarship Program/Doctorado Becas Chile/2018-72190600. Publisher Copyright: © 2020 IEEE. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/12/9

Y1 - 2020/12/9

N2 - In this paper the Traveling Salesman Problem with pickup, delivery and handling costs is studied. We have to find a route from a depot to a set of customers, each of which requires a pickup and delivery service the goal is to minimize the global routing and handling cost. We have developed an Iterated Local Search for this problem combining different heuristics of the Traveling Salesman Problem, and using frequency of improvements and a perturbation with memory the proposed algorithm is tested on different benchmark instances from the literature with up to 200 vertices, obtaining high quality solutions in reasonable computing times.

AB - In this paper the Traveling Salesman Problem with pickup, delivery and handling costs is studied. We have to find a route from a depot to a set of customers, each of which requires a pickup and delivery service the goal is to minimize the global routing and handling cost. We have developed an Iterated Local Search for this problem combining different heuristics of the Traveling Salesman Problem, and using frequency of improvements and a perturbation with memory the proposed algorithm is tested on different benchmark instances from the literature with up to 200 vertices, obtaining high quality solutions in reasonable computing times.

KW - Combinatorial Optimization

KW - Handling Cost

KW - Iterated Local Search

KW - Traveling Salesman Problem

UR - https://www.scopus.com/pages/publications/85098625790

UR - https://www.scopus.com/pages/publications/85098625790#tab=citedBy

U2 - 10.1109/SCCC51225.2020.9281164

DO - 10.1109/SCCC51225.2020.9281164

M3 - Conference contribution

AN - SCOPUS:85098625790

T3 - Proceedings - International Conference of the Chilean Computer Science Society, SCCC

BT - 2020 39th International Conference of the Chilean Computer Science Society (SCCC)

PB - IEEE Computer Society

T2 - 39th International Conference of the Chilean Computer Science Society, SCCC 2020

Y2 - 16 November 2020 through 20 November 2020

ER -

Rey C, Toth P, Vigo D. An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs. In 2020 39th International Conference of the Chilean Computer Science Society (SCCC): [Proceedings]. IEEE Computer Society. 2020. 9281164. (Proceedings - International Conference of the Chilean Computer Science Society, SCCC). Epub 2020 Nov 16. doi: 10.1109/SCCC51225.2020.9281164

An Iterated Local Search for the Traveling Salesman Problem with Pickup, Delivery and Handling Costs

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this