technical-note

A case based approach for an intelligent route optimization technology

Authors:

Yoshitaka SakuraiAuthors Info & Claims

GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation

Pages 1069 - 1072

https://doi.org/10.1145/2598394.2605676

Published: 12 July 2014 Publication History

Get Access

Abstract

The paper introduces a Case Based Approximation method to solve large scale Traveling Salesman Problems in a short time with a low error rate. It is useful for domains with most solutions being similar to solutions that have been created. Thus, a solution can be derived by (1) selecting a most similar TSP from a library of former TSP solutions, (2) removing the locations that are not part of the current TSP and (3) adding the missing locations of the current TSP by mutation, namely Nearest Insertion (NI). This way of creating solutions by Case Based Reasoning (CBR) avoids the computational costs to create new solutions from scratch.

References

[1]

http://www.math.uwaterloo.ca/tsp/concorde/index.html.

Google Scholar

[2]

Proc. IEEE Symp. Computational Intelligence in Scheduling (SCIS 07), IEEE Press, 57--64.

Google Scholar

[3]

Gutin, G., Punnen, A. P. 2007. The Traveling Salesman Problem and its Variations, Springer, NY, USA.

Google Scholar

[4]

Helsgaun, K. 2009. General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation, 1, 119--163.

Crossref

Google Scholar

[5]

Huellermeier, E. 2007. Case-Based Approximate Reasoning. Springer, Berlin.

Digital Library

Google Scholar

[6]

Karp, R. M., 1977. "robabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane." Math. Oper. Res., 2, 3, 209--224.

Digital Library

Google Scholar

[7]

Ken, H., Kokolo, I., Jun, S., Isao, O., and Shigenobu, K. 2006. Hybridization of Genetic Algorithm with Local Search in Multiobjective Function Optimization: Recommendation of GA then LS. Transactions of the Japanese Society for Artificial Intelligence, 21, 482--492.

Crossref

Google Scholar

[8]

Lin, S., Kernighan, B. W. 1973. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research 21 (2), 498--516.

Digital Library

Google Scholar

[9]

Nguyen, H. D., Yoshihara, I., Yamamori, K., Yasunaga, M. 2007. Implementation of an Effective Hybrid GA for Large-Scale Traveling Salesman Problems. IEEE Transactions on Systems, Man and Cybernetics, Part B, 37, 1, 92--99.

Digital Library

Google Scholar

[10]

Sakurai, Y., Onoyama, T., Kubota, S., Nakamura, Y., Tsuruta, S. 2006. A Multiworld Intelligent Genetic Algorithm to Interactively Optimize Largescale TSP. Proc. of the 2006 IEEE International Conference on Information Reuse and Integration (IEEE IRI2006), 248--255.

Crossref

Google Scholar

[11]

Sakurai, Y., Onoyama, T., Kubota, S., Tsuruta, S. 2008. A Multi-inner-world Genetic Algorithm to Optimize Delivery Problem with Interactive-time. Proc. of 4th IEEE Conf. on Automation Science and Engineering (CASE 2008), 583--590.

Crossref

Google Scholar

[12]

Sakurai, Y., Takada, K., Tsukamoto, N., Onoyama, T., Knauf, R. 2011. A Simple Optimization Method based on Backtrack and GA for Delivery Schedule. Proc. of the IEEE Congress on Evolutionary Computation 2011 (CEC 2011), 2790--2797.

Crossref

Google Scholar

[13]

Yamamoto, Y., and Kubo, M. 1997. Invitation to Traveling Salesman Problem. Asakura Syoten, Tokyo.

Google Scholar

Cited By

View all

Ayari ENasri SAggoune-Mtalaa WBouziri H(2023)Learning routes within an intelligent on demand transport service2023 20th ACS/IEEE International Conference on Computer Systems and Applications (AICCSA)10.1109/AICCSA59173.2023.10479296(1-7)Online publication date: 4-Dec-2023
https://doi.org/10.1109/AICCSA59173.2023.10479296
Bouzar-Benlabiod LRubin SLila M(2018)Randomization-Based Knowledge Discovery with Application to Weather Prediction2018 IEEE International Conference on Information Reuse and Integration (IRI)10.1109/IRI.2018.00032(163-169)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1109/IRI.2018.00032
Bouabana-Tebibel TH. Rubin SBouzar-Benlabiod LBentaiba-Lagrid MHanini M(2018)Knowledge-Based Randomization for Amplification2018 IEEE International Conference on Information Reuse and Integration (IRI)10.1109/IRI.2018.00030(147-154)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1109/IRI.2018.00030
Show More Cited By

Index Terms

A case based approach for an intelligent route optimization technology
1. Computing methodologies
  1. Artificial intelligence
    1. Planning and scheduling

Recommendations

Intelligent Route Optimization Technology by Case Based GA
SITIS '13: Proceedings of the 2013 International Conference on Signal-Image Technology & Internet-Based Systems

A delivery route optimization system greatly improves the real time delivery efficiency. To realize such an optimization, its distribution network requires solving several tens to hundreds (maximum 2 thousands or so) cities Traveling Salesman Problems (...
A Case Based Approach for an Intelligent Route Optimization Technology
SITIS '14: Proceedings of the 2014 Tenth International Conference on Signal-Image Technology and Internet-Based Systems

This paper introduces a Case Based Approximation method to solve large scale Traveling Salesman Problems in a short time (around 3 seconds) with an error rate below 3%. This method is based on the insight, that a majority of real world problems are very ...
A multi-inner-world genetic algorithm using multiple heuristics to optimize delivery schedule
SMC'09: Proceedings of the 2009 IEEE international conference on Systems, Man and Cybernetics

Building a delivery route optimization system that improves the delivery efficiency in real time requires to solve several tens to hundreds cities Traveling Salesman Problems (TSP) within interactive response time, with expert-level accuracy (less than 3%...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation

July 2014

1524 pages

ISBN:9781450328814

DOI:10.1145/2598394

Editor-in-chief:
Christian Igel
Ruhr University of Bochum, University of Copenhagen
,
General Chair:
Dirk V. Arnold
Dalhousie University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Technical-note

Funding Sources

KAK ENHI
Research Institute for Science and Technology of Tokyo Denki University

Conference

GECCO '14

Sponsor:

SIGEVO

GECCO '14: Genetic and Evolutionary Computation Conference

July 12 - 16, 2014

BC, Vancouver, Canada

Acceptance Rates

GECCO Comp '14 Paper Acceptance Rate 180 of 544 submissions, 33%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
114
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ayari ENasri SAggoune-Mtalaa WBouziri H(2023)Learning routes within an intelligent on demand transport service2023 20th ACS/IEEE International Conference on Computer Systems and Applications (AICCSA)10.1109/AICCSA59173.2023.10479296(1-7)Online publication date: 4-Dec-2023
https://doi.org/10.1109/AICCSA59173.2023.10479296
Bouzar-Benlabiod LRubin SLila M(2018)Randomization-Based Knowledge Discovery with Application to Weather Prediction2018 IEEE International Conference on Information Reuse and Integration (IRI)10.1109/IRI.2018.00032(163-169)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1109/IRI.2018.00032
Bouabana-Tebibel TH. Rubin SBouzar-Benlabiod LBentaiba-Lagrid MHanini M(2018)Knowledge-Based Randomization for Amplification2018 IEEE International Conference on Information Reuse and Integration (IRI)10.1109/IRI.2018.00030(147-154)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1109/IRI.2018.00030
Yamamoto YTsuruta SMuranushi THada-Muranushi YKobashi SMizuno YKnauf R(2016)Solar flare prediction by SVM integrated GA2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7744314(4127-4134)Online publication date: Jul-2016
https://doi.org/10.1109/CEC.2016.7744314
Yamamoto YTsuruta SMuranushi TMuranushi YKobashi SMizuno YKnauf R(2015)Improvement of Sun Flare Prediction by SVM Integrated GAProceedings of the 2015 11th International Conference on Signal-Image Technology & Internet-Based Systems (SITIS)10.1109/SITIS.2015.37(719-724)Online publication date: 23-Nov-2015
https://dl.acm.org/doi/10.1109/SITIS.2015.37
Kawabe TSuzuki MMatsumaru TYamamoto YTsuruta SSakurai YKnauf R(2014)Distributed GAs with case-based initial populations for real-time solution of combinatorial problems2014 IEEE Symposium on Evolving and Autonomous Learning Systems (EALS)10.1109/EALS.2014.7009509(95-101)Online publication date: Dec-2014
https://doi.org/10.1109/EALS.2014.7009509

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Intelligent Route Optimization Technology by Case Based GA

A Case Based Approach for an Intelligent Route Optimization Technology

A multi-inner-world genetic algorithm using multiple heuristics to optimize delivery schedule