A case based approach for an intelligent route optimization technology

Takashi Kawabe, Takaaki Motomura, Masaki Suzuki, Yukiko Yamamoto, Setsuo Tsuruta, Yoshitaka Sakurai, Rainer Knauf

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)

Abstract

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 often similar to previous ones at least for route scheduling. Thus, a solution can be derived from former solutions as follows: (1) selecting a most similar TSP from a library (CB: Case Base) of former TSP solutions, (2) removing the locations that are not including in the newly given problem or TSP and (3) adding the new locations by Nearest Insertion (NI) and possibly adjusting by NI incorporated GA. This way of creating solutions by Case Based Reasoning (CBR) avoids the computational costs to create new solutions from scratch. The evaluation of this method revealed remarkable results. Though even the world fastest most optimal approximate TSP solving method LKH needed more than 3 seconds or the worst error rate exceeded 3 seconds, the worst error rate of the proposed method is less than 1 % within 3 seconds. This is about 10-100 times better than that of our former approach BR-GA (Backtrack and Restart type GA).

Original languageEnglish
Title of host publicationProceedings - 10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014
EditorsRichard Chbeir, Richard Chbeir, Kokou Yetongnon, Albert Dipanda
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages141-146
Number of pages6
ISBN (Electronic)9781479979783
DOIs
Publication statusPublished - 7 Apr 2015
Event10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014 - Marrakech, Morocco
Duration: 23 Nov 201427 Nov 2014

Publication series

NameProceedings - 10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014

Conference

Conference10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014
CountryMorocco
CityMarrakech
Period23/11/1427/11/14

Keywords

  • Genetic Algorithm (GA)
  • Knowledge maintenance
  • case based reasoning (CBR)
  • heuristics
  • traveling salesman problems (TSP)

Fingerprint Dive into the research topics of 'A case based approach for an intelligent route optimization technology'. Together they form a unique fingerprint.

  • Cite this

    Kawabe, T., Motomura, T., Suzuki, M., Yamamoto, Y., Tsuruta, S., Sakurai, Y., & Knauf, R. (2015). A case based approach for an intelligent route optimization technology. In R. Chbeir, R. Chbeir, K. Yetongnon, & A. Dipanda (Eds.), Proceedings - 10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014 (pp. 141-146). [7081539] (Proceedings - 10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SITIS.2014.102