A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes

被引：0
作者：
Tânia Rodrigues Pereira Ramos
Maria Isabel Gomes
Ana Paula Barbosa-Póvoa
机构：
[1] Instituto Superior Técnico (CEG-IST),Centre for Management Studies
[2] Universidade de Lisboa,Business Research Unit
[3] ISCTE (BRU-ISCTE),Centre for Mathematics and Applications, Faculdade de Ciências e Tecnologia (CMA
[4] Instituto Universitário de Lisboa,FCT)
[5] Universidade Nova de Lisboa,undefined
来源：
OR Spectrum | 2020年 / 42卷
关键词：
Multiple depots; Vehicle routing problem; Inter-depot routes; Mixed integer linear programming; Matheuristic;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The multi-depot vehicle routing problem with inter-depot routes is studied in this paper, where vehicles may reset their capacity at any depot during the working day. Due to the complexity of this problem, exact approaches are limited to small-size applications. In order to overcome this limitation, we propose a matheuristic which integrates a mixed integer linear programming formulation with a set of relax-and-fix strategies. This solution approach is shown to be very efficient, and for the first time, large-size benchmarking instances are solved.
引用
收藏
页码：75 / 110
页数：35
相关论文
共 90 条
  • [1] Angelelli E(2002)The periodic vehicle routing problem with intermediate facilities Eur J Oper Res 137 233-247
  • [2] Speranza MG(2009)A unified exact method for solving different classes of vehicle routing problems Math Program 120 347-380
  • [3] Baldacci R(2004)An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation Oper Res 52 723-738
  • [4] Mingozzi A(1998)A branch and cut algorithm for the VRP with satellite facilities IIE Trans 30 821-834
  • [5] Baldacci R(2010)Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities Comput Oper Res 37 2270-2280
  • [6] Hadjiconstantinou E(1997)A tabu search algorithm for the multi-trip vehicle routing and scheduling problem Eur J Oper Res 100 180-191
  • [7] Mingozzi A(2014)A memetic algorithm for the multi trip vehicle routing problem Eur J Oper Res 236 833-848
  • [8] Bard JF(1993)A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions Am J Math Manag Sci 13 371-406
  • [9] Huang L(1964)Scheduling of vehicles from a central depot to a number of delivery points Oper Res 12 568-581
  • [10] Dror M(1997)A tabu search heuristic for periodic and multi-depot vehicle routing problems Networks 30 105-119
123456789