A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows

被引：68

作者：

Gutierrez-Jarpa, Gabriel ^{[3
,4
]}

Desaulniers, Guy ^{[1
,2
]}

Laporte, Gilbert ^{[5
,6
]}

Marianov, Vladimir ^{[7
]}

机构：

[1] Ecole Polytech, Gerad, Montreal, PQ H3C 3A7, Canada

[2] Ecole Polytech, Dept Math & Genie Ind, Montreal, PQ H3C 3A7, Canada

[3] Pontificia Univ Catolica Chile, Grad Program, Santiago, Chile

[4] Univ Catolica Santisima Concepcion, Dept Ind Engn, Concepcion, Chile

[5] CIRRELT, Gerad, Montreal, PQ H3T 2A7, Canada

[6] HEC Montreal 3000, Montreal, PQ H3T 2A7, Canada

[7] Pontificia Univ Catolica Chile, Dept Elect Engn, Santiago, Chile

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2010年 / 206卷 / 02期

基金：

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

关键词：

Transportation; Vehicle routing; Deliveries and selective pickups; Time windows; Branch-and-price; Shortest paths with resources; SHORTEST-PATH PROBLEM;

D O I：

10.1016/j.ejor.2010.02.037

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：341 / 349

页数：9

共 30 条

[11] An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems [J].

Feillet, D ;

Dejax, P ;

Gendreau, M ;

Gueguen, C .

NETWORKS, 2004, 44 (03) :216-229

[12] The single vehicle routing problem with deliveries and selective pickups [J].

Gribkovskaia, Irina ;

Laporte, Gilbert ;

Shyshou, Aliaksandr .

COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (09) :2908-2924

[13]

Gribkovskaia I, 2008, OPER RES COMPUT SCI, V43, P359, DOI 10.1007/978-0-387-77778-8_16

[14] A single vehicle routing problem with fixed delivery and optional collections [J].

Gutierrez-Jarpa, G. ;

Marianov, V. ;

Obreque, C. .

IIE TRANSACTIONS, 2009, 41 (12) :1067-1079

[15] Heuristics for the one-commodity pickup-and-delivery traveling salesman problem [J].

Hernández-Pérez, H ;

Salazar-González, JJ .

TRANSPORTATION SCIENCE, 2004, 38 (02) :245-255

[16] Lasso solution strategies for the vehicle routing problem with pickups and deliveries [J].

Hoff, Arild ;

Gribkovskaia, Irina ;

Laporte, Gilbert ;

Lokketangen, Arne .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 192 (03) :755-766

[17]

Irnich Stefan., 2006, COLUMN GENERATION, P33

[18] THE MULTIPLE VEHICLE-ROUTING PROBLEM WITH SIMULTANEOUS DELIVERY AND PICK-UP POINTS [J].

MIN, HK .

TRANSPORTATION RESEARCH PART A-POLICY AND PRACTICE, 1989, 23 (05) :377-386

[19] An exact method for the vehicle routing problem with backhauls [J].

Mingozzi, A ;

Giorgi, S ;

Baldacci, R .

TRANSPORTATION SCIENCE, 1999, 33 (03) :315-329

[20]

Parragh S.N., 2008, J. fur Betriebswirtschaft, V58, P21, DOI [10.1007/s11301-008-0033-7, 10.1007/s11301-008-0036-4]

← 1 2 3 →