A column generation and a post optimization VNS heuristic for the vehicle routing problem with multiple time windows

被引:0
作者
Eduardo Theodoro Bogue
Huggo Silva Ferreira
Thiago F. Noronha
Christian Prins
机构
[1] Universidade Federal de Mato Grosso do Sul,
[2] Universidade Federal de Minas Gerais,undefined
[3] Universite de Technologie de Troyes,undefined
来源
Optimization Letters | 2022年 / 16卷
关键词
Vehicle Routing Problem; Multiple Time Windows; Variable Neighborhood Search; Column Generation Heuristic;
D O I
暂无
中图分类号
学科分类号
摘要
The Vehicle Routing Problem with Multiple Time Windows (VRPMTW) is a generalization of the Vehicle Routing Problem (VRP), where the customers have one or more time windows in which they can be visited. In this paper, we propose a Column Generation (CG) algorithm and a post optimization heuristic based on a Variable Neighborhood Search (VNS) to provide both lower and upper bounds for the cost of optimal solutions to VRPMTW. As in CG algorithms for VRP, the master problem is based on a Weighted Set Covering formulation. However, due to the multiple time windows, the pricing subproblem is an Elementary Shortest Path Problem with Multiple Time Windows and Capacity Constraints, which is more difficult to solve than the classical Elementary Shortest Path Problem with a Single Time Window and Capacity Constraints. Computational experiments were performed on 594 instances generated from classical Solomon instances with up to 17 customers. They showed that CG was able to produce lower bounds, within one hour of running time, for 66.7% of the instances. Besides, the post optimization heuristic was able to improve the solution provided by the VNS heuristic in 28.9%, finding integer optimal solutions for 39.9% of the instances. Moreover, for the instances where lower bounds are known, the average optimality gap was 6.0% on average.
引用
收藏
页码:79 / 95
页数:16
相关论文
共 43 条
  • [1] Amor HMB(2009)On the choice of explicit stabilizing terms in column generation Discrete Appl. Math. 157 1167-1184
  • [2] Desrosiers J(1998)Branch-and-price: column generation for solving huge integer programs Oper. Res. 46 316-329
  • [3] Frangioni A(2014)A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows Comput. Oper. Res. 52 269-281
  • [4] Barnhart C(2006)Vehicle routing problem with elementary shortest path based column generation Comput. Oper. Res. 33 2972-2990
  • [5] Johnson EL(1959)The truck dispatching problem Manag. Sci. 6 80-91
  • [6] Nemhauser GL(2007)Ant colony system for a vrp with multiple time windows and multiple visits J. Interdiscip. Math. 10 263-284
  • [7] Savelsbergh MW(2016)A column generation based heuristic for the multicommodity-ring vehicle routing problem Transp. Res. Procedia 12 227-238
  • [8] Vance PH(1973)An effective heuristic algorithm for the traveling-salesman problem Oper. Res. 21 498-516
  • [9] Belhaiza S(2006)A set-covering-based heuristic approach for bin-packing problems INFORMS J. Comput. 18 71-85
  • [10] Hansen P(2014)Iterated local search heuristics for the vehicle routing problem with cross-docking Expert Syst. Appl. 41 7495-7506