A column generation approach for a multi-attribute vehicle routing problem

被引：42

作者：

Dayarian, Iman ^{[1
,4
]}

Crainic, Teodor Gabriel ^{[2
,4
]}

Gendreau, Michel ^{[3
,4
]}

Rei, Walter ^{[2
,4
]}

机构：

[1] Univ Montreal, DIRO, Montreal, PQ, Canada

[2] Univ Quebec, ESG, Montreal, PQ H3C 3P8, Canada

[3] Ecole Polytech, MAGI, Montreal, PQ H3C 3A7, Canada

[4] CIRRELT, Montreal, PQ 3P8 QC, Canada

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2015年 / 241卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Multi-attribute vehicle routing problem; Heterogeneous fleet; Multiple depots; Branch-and-price; Dairy transportation problem; SHORTEST-PATH PROBLEM; OPTIMIZATION ALGORITHM; RESOURCE CONSTRAINTS; TIME WINDOWS; TABU SEARCH; ELEMENTARY; DEPOT; RELAXATION; STRATEGIES; HEURISTICS;

D O I：

10.1016/j.ejor.2014.09.015

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we consider a multi-attribute vehicle routing problem derived from a real-life milk collection system. This problem is characterized by the presence of a heterogeneous fleet of vehicles, multiple depots, and several resource constraints. A branch-and-price methodology is proposed to tackle the problem. In this methodology, different branching strategies, adapted to the special structure of the problem, are implemented and compared. The computational results show that the branch-and-price algorithm performs well in terms of solution quality and computational efficiency. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：888 / 906

页数：19

共 26 条

[1] New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows [J].

Baldacci, Roberto ;

Mingozzi, Aristide ;

Roberti, Roberto .

INFORMS JOURNAL ON COMPUTING, 2012, 24 (03) :356-371

[2] New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem [J].

Baldacci, Roberto ;

Mingozzi, Aristide ;

Roberti, Roberto .

OPERATIONS RESEARCH, 2011, 59 (05) :1269-1283

[3] A unified exact method for solving different classes of vehicle routing problems [J].

Baldacci, Roberto ;

Mingozzi, Aristide .

MATHEMATICAL PROGRAMMING, 2009, 120 (02) :347-380

[4] A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows [J].

Bettinelli, Andrea ;

Ceselli, Alberto ;

Righini, Giovanni .

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2011, 19 (05) :723-740

[5] Accelerated label setting algorithms for the elementary resource constrained shortest path problem [J].

Boland, N ;

Dethridge, J ;

Dumitrescu, I .

OPERATIONS RESEARCH LETTERS, 2006, 34 (01) :58-68

[6] SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].

CLARKE, G ;

WRIGHT, JW .

OPERATIONS RESEARCH, 1964, 12 (04) :568-&

[7]

Cordeau JF, 1997, NETWORKS, V30, P105, DOI 10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO

[8]

2-G

[9] THE TRUCK DISPATCHING PROBLEM [J].

DANTZIG, GB ;

RAMSER, JH .

MANAGEMENT SCIENCE, 1959, 6 (01) :80-91

[10] Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows [J].

Desaulniers, Guy ;

Lessard, Francois ;

Hadjar, Ahmed .

TRANSPORTATION SCIENCE, 2008, 42 (03) :387-404

← 1 2 3 →