The Delivery Man Problem with time windows

被引：24

作者：

Heilporn, Geraldine ^{[1
,2
,3
]}

Cordeau, Jean-Francois ^{[2
,3
]}

Laporte, Gilbert ^{[1
,3
]}

机构：

[1] HEC Montreal, Canada Res Chair Distribut Management, Montreal, PQ H3T 2A7, Canada

[2] HEC Montreal, Canada Res Chair Logist & Transportat, Montreal, PQ H3T 2A7, Canada

[3] HEC Montreal, CIRRELT, Montreal, PQ H3T 2A7, Canada

来源：

DISCRETE OPTIMIZATION | 2010年 / 7卷 / 04期

基金：

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

关键词：

Delivery Man Problem; Traveling Salesman Problem; Time windows; Polyhedral analysis; Mixed integer linear programming; TRAVELING SALESMAN PROBLEM; VEHICLE-ROUTING PROBLEM; BRANCH-AND-CUT; EXACT ALGORITHM; FORMULATION;

D O I：

10.1016/j.disopt.2010.06.002

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, a variant of the Traveling Salesman Problem with Time Windows is considered, which consists in minimizing the sum of travel durations between a depot and several customer locations. Two mixed integer linear programming formulations are presented for this problem: a classical arc flow model and a sequential assignment model. Several polyhedral results are provided for the second formulation, in the special case arising when there is a closed time window only at the depot, while open time windows are considered at all other locations. Exact and heuristic algorithms are also proposed for the problem. Computational results show that medium size instances can be solved exactly with both models, while the heuristic provides good quality solutions for medium to large size instances. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：269 / 282

页数：14

共 37 条

[1]

ABELEDO H, 2008, P 6 ALIO EURO WORKSH, P1

[2] Interval-indexed formulation based heuristics for single machine total weighted tardiness problem [J].

Altunc, Arife Burcu Colak ;

Keha, Ahmet Burak .

COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (06) :2122-2131

[3]

[Anonymous], THESIS TU BERLIN

[4]

Ascheuer N, 2000, NETWORKS, V36, P69, DOI 10.1002/1097-0037(200009)36:2<69::AID-NET1>3.0.CO

[5]

2-Q

[6] Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut [J].

Ascheuer, N ;

Fischetti, M ;

Grötschel, M .

MATHEMATICAL PROGRAMMING, 2001, 90 (03) :475-506

[7] AN EXACT ALGORITHM FOR THE TIME-CONSTRAINED TRAVELING SALESMAN PROBLEM [J].

BAKER, EK .

OPERATIONS RESEARCH, 1983, 31 (05) :938-945

[8] THE TRAVELING SALESMAN PROBLEM WITH CUMULATIVE COSTS [J].

BIANCO, L ;

MINGOZZI, A ;

RICCIARDELLI, S .

NETWORKS, 1993, 23 (02) :81-91

[9] The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times [J].

Bigras, Louis-Philippe ;

Gamache, Michel ;

Savard, Gilles .

DISCRETE OPTIMIZATION, 2008, 5 (04) :685-699

[10]

Blum A., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P163, DOI 10.1145/195058.195125

← 1 2 3 4 →