A hybrid iterated local search algorithm for the multi-compartment vehicle routing problem

被引:2
作者
Hou, Yan-e [1 ,2 ]
Wang, Chunxiao [2 ]
Wang, Congran [2 ]
Fan, Gaojuan [2 ]
机构
[1] Henan Univ, Henan Key Lab Big Data Anal & Proc, Kaifeng, Peoples R China
[2] Henan Univ, Coll Comp & Informat Engn, Kaifeng, Peoples R China
关键词
Multi-compartment vehicle routing problem; hybrid metaheuristic; iterated local search; large neighborhood search; simulated annealing; ANT COLONY ALGORITHM; TABU SEARCH; WMA;
D O I
10.3233/JIFS-223404
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Multi-compartment vehicle routing problem (MCVRP) is an extension of the classical capacitated vehicle routing problem where products with different characteristics are transported together in one vehicle with multiple compartments. This paper deals with this problem, whose objective is to minimize the total travel distance while satisfying the capacity and maximum route length constraints. We proposed a hybrid iterated local search metaheuristic (HILS) algorithm to solve it. In the framework of iterated local search, the current solutionwas improved iteratively by five neighborhood operators. For every obtained neighborhood solution after the local search procedure, a large neighborhood search-based perturbation method was executed to explore larger solution space and get a better neighborhood solution to take part in the next iteration. In addition, the worse solutions found by the algorithm were accepted by the nondeterministic simulated annealing-based acceptance rule to keep the diversification of solutions. Computation experiments were conducted on 28 benchmark instances and the experimental results demonstrate that our presented algorithm finds 17 new best solutions, which significantly outperforms the existing state-of-the-art MCVRP methods.
引用
收藏
页码:257 / 268
页数:12
相关论文
共 28 条
  • [1] Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem
    Abdulkader, Mohamed M. S.
    Gajpal, Yuvraj
    ElMekkawy, Tarek Y.
    [J]. APPLIED SOFT COMPUTING, 2015, 37 : 196 - 203
  • [2] Unsupervised text feature selection technique based on hybrid particle swarm optimization algorithm with genetic operators for the text clustering
    Abualigah, Laith Mohammad
    Khader, Ahamad Tajudin
    [J]. JOURNAL OF SUPERCOMPUTING, 2017, 73 (11) : 4773 - 4795
  • [3] Gazelle optimization algorithm: a novel nature-inspired metaheuristic optimizer
    Agushaka, Jeffrey O.
    Ezugwu, Absalom E.
    Abualigah, Laith
    [J]. NEURAL COMPUTING & APPLICATIONS, 2023, 35 (05) : 4099 - 4131
  • [4] Multicommodity vs. Single-Commodity Routing
    Archetti, Claudia
    Campbell, Ann Melissa
    Speranza, M. Grazia
    [J]. TRANSPORTATION SCIENCE, 2016, 50 (02) : 461 - 472
  • [5] BODIN L, 1983, COMPUT OPER RES, V10, P63, DOI 10.1016/0305-0548(83)90030-8
  • [6] A multi-compartment vehicle routing problem with time windows for urban distribution - A comparison study on particle swarm optimization algorithms
    Chen, Jiumei
    Shi, Jing
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2019, 133 : 95 - 106
  • [7] A multi-compartment vehicle routing problem in cold-chain distribution
    Chen, Lu
    Liu, Yang
    Langevin, Andre
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2019, 111 : 58 - 66
  • [8] SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS
    CLARKE, G
    WRIGHT, JW
    [J]. OPERATIONS RESEARCH, 1964, 12 (04) : 568 - &
  • [9] A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem
    El Fallahi, Abdellah
    Prins, Christian
    Calvo, Roberto Wolfler
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (05) : 1725 - 1741
  • [10] A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants
    Elshaer, Raafat
    Awad, Hadeer
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2020, 140 (140)