Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints

被引：312

作者：

Baldacci, Roberto ^{[2
]}

Mingozzi, Aristide ^{[1
]}

Roberti, Roberto ^{[3
]}

机构：

[1] Univ Bologna, Dept Math, I-47521 Cesena, Italy

[2] Univ Bologna, DEIS, I-47521 Cesena, Italy

[3] Univ Bologna, DEIS, I-40136 Bologna, Italy

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2012年 / 218卷 / 01期

关键词：

Vehicle routing; Exact algorithms; Survey; SHORTEST-PATH PROBLEM; RESOURCE CONSTRAINTS; INEQUALITIES; ELIMINATION; FORMULATION; CUTS;

D O I：

10.1016/j.ejor.2011.07.037

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper provides a review of the recent developments that had a major impact on the current state-of-the-art exact algorithms for the vehicle routing problem (VRP). The paper reviews mathematical formulations, relaxations and recent exact methods for two of the most important variants of the VRP: the capacitated VRP (CVRP) and the VRP with time windows (VRPTW). The paper also reports a comparison of the computational performances of the different exact algorithms for the CVRP and VRPTW. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：1 / 6

页数：6

共 29 条

[1] INTEGER LINEAR-PROGRAMMING FORMULATION FOR A VEHICLE-ROUTING PROBLEM [J].