Journal
MEMETIC COMPUTING
Volume 14, Issue 1, Pages 31-44Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s12293-021-00352-7
Keywords
Vehicle routing problem(VRP); Knowledge transfer; Memetic algorithm; Evolutionary multitasking
Funding
- National Natural Science Foundation of China (NSFC) [61876025]
- joint project JD User Growth Engine [H20211431]
- Venture & Innovation Support Program for Chongqing Overseas Returnees [cx2018044, cx2019020]
Ask authors/readers for more resources
This paper proposes a memetic search with evolutionary multitasking approach to solve vehicle routing problem on multiple problem forms. By constructing multiple simplified vehicle routing problems as auxiliary tasks and performing evolutionary search, the sharing of routing traits and enhancement of evolutionary search can be achieved.
Vehicle routing problem (VRP) is a well-known NP-hard combinational optimization problem. In the literature, existing approaches can be generally classified into two categories: exact methods and metaheuristics methods. The former is only effective for small problem instances while the latter is more suitable for practical applications with larger scale. However, these methods perform evolutionary search only on a single problem form of VRP, while the efficient problem form of a given VRP is often unknown before hand. Keeping the above in mind, this paper proposes memetic search with evolutionary multitasking for solving vehicle routing problem on multiple problem forms. In particular, multiple simplified vehicle routing problems are firstly constructed and acted as the auxiliary tasks of original VRP. The memetic evolutionary search is thus simultaneously performed on simplified vehicle routing problems and original VRP. In this way, the useful routing traits can be shared by knowledge transfer among the tasks to enhance the evolutionary search. To verify the performance of the proposed method, comprehensive empirical experiments have been conducted on commonly used VRP benchmarks.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available