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 条

[1]

Aas B., 2007, INT J PHYS DISTR LOG, V37, P164

[2] An exact algorithm for the traveling salesman problem with deliveries and collections [J].

Baldacci, R ;

Hadjiconstantinou, E ;

Mingozzi, A .

NETWORKS, 2003, 42 (01) :26-41

[3] Branch-and-price: Column generation for solving huge integer programs [J].

Barnhart, C ;

Johnson, EL ;

Nemhauser, GL ;

Savelsbergh, MWP ;

Vance, PH .

OPERATIONS RESEARCH, 1998, 46 (03) :316-329

[4] Static pickup and delivery problems: a classification scheme and survey [J].

Berbeglia, Gerardo ;

Cordeau, Jean-Francois ;

Gribkovskaia, Irina ;

Laporte, Gilbert .

TOP, 2007, 15 (01) :1-31

[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] A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection [J].

Dell'Amico, Mauro ;

Righini, Giovanni ;

Salani, Matteo .

TRANSPORTATION SCIENCE, 2006, 40 (02) :235-247

[7]

Desaulniers G, 1998, FLEET MANAGEMENT AND LOGISTICS, P57

[8] 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

[9]

Desrosiers J., 2005, COLUMN GENERATION, P1, DOI DOI 10.1007/0-387-25486-2_1

[10] Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up Fahrzeugeinsatzplanung und Redistribution: Tourenplanung mit simultaner Auslieferung und Rückholung [J].

Jan Dethloff .

OR-Spektrum, 2001, 23 (1) :79-96

← 1 2 3 →