LAPSE:2021.0364
Published Article
LAPSE:2021.0364
Fitness Landscape Analysis and Edge Weighting-Based Optimization of Vehicle Routing Problems
May 17, 2021
Vehicle routing problem (VRP) is a highly investigated discrete optimization problem. The first paper was published in 1959, and later, many vehicle routing problem variants appeared to simulate real logistical systems. Since vehicle routing problem is an NP-difficult task, the problem can be solved by approximation algorithms. Metaheuristics give a “good” result within an “acceptable” time. When developing a new metaheuristic algorithm, researchers usually use only their intuition and test results to verify the efficiency of the algorithm, comparing it to the efficiency of other algorithms. However, it may also be necessary to analyze the search operators of the algorithms for deeper investigation. The fitness landscape is a tool for that purpose, describing the possible states of the search space, the neighborhood operator, and the fitness function. The goal of fitness landscape analysis is to measure the complexity and efficiency of the applicable operators. The paper aims to investigate the fitness landscape of a complex vehicle routing problem. The efficiency of the following operators is investigated: 2-opt, order crossover, partially matched crossover, cycle crossover. The results show that the most efficient one is the 2-opt operator. Based on the results of fitness landscape analysis, we propose a novel traveling salesman problem genetic algorithm optimization variant where the edges are the elementary units having a fitness value. The optimal route is constructed from the edges having good fitness value. The fitness value of an edge depends on the quality of the container routes. Based on the performed comparison tests, the proposed method significantly dominates many other optimization approaches.
Record ID
Keywords
fitness landscape, Optimization, traveling salesman problem, vehicle routing problem
Subject
Suggested Citation
Kovács L, Agárdi A, Bányai T. Fitness Landscape Analysis and Edge Weighting-Based Optimization of Vehicle Routing Problems. (2021). LAPSE:2021.0364
Author Affiliations
Journal Name
Processes
Volume
8
Issue
11
Article Number
E1363
Year
2020
Publication Date
2020-10-28
Published Version
ISSN
2227-9717
Version Comments
Original Submission
Other Meta
PII: pr8111363, Publication Type: Journal Article
Record Map
Published Article
LAPSE:2021.0364
This Record
External Link
doi:10.3390/pr8111363
Publisher Version
Download
Meta
Record Statistics
Record Views
408
Version History
[v1] (Original Submission)
May 17, 2021
Verified by curator on
May 17, 2021
This Version Number
v1
Citations
Most Recent
This Version
URL Here
https://psecommunity.org/LAPSE:2021.0364
Original Submitter
Calvin Tsay
Links to Related Works