SINGLE-VEHICLE ROUTING AND SCHEDULING TO MINIMIZE THE NUMBER OF DELAYS

被引：6

作者：

GENDREAU, M ^{[1
]}

LAPORTE, G ^{[1
]}

SOLOMON, MM ^{[1
]}

机构：

[1] NORTHEASTERN UNIV,COLL BUSINESS ADM,BOSTON,MA 02115

来源：

TRANSPORTATION SCIENCE | 1995年 / 29卷 / 01期

关键词：

D O I：

10.1287/trsc.29.1.56

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In, this paper we examine the following problem arising in vehicle routing and in production scheduling. Consider a single uncapacitated vehicle and n customers j with deadlines d(j). The objective is to minimize the number of deliveries completed after their deadline. This problem is NP-hard, but a class of solvable cases cart be characterized. An integer linear programming formulation is proposed, and the problem is solved optimally by means of a specialized enumerative algorithm. Computational results are presented for problems involving up to 100 customers.

引用

页码：56 / 62

页数：7

共 19 条

[1]

[Anonymous], 2012, DYNAMIC PROGRAMMING

[2] SEQUENCING WITH EARLINESS AND TARDINESS PENALTIES - A REVIEW [J].

BAKER, KR ;

SCUDDER, GD .

OPERATIONS RESEARCH, 1990, 38 (01) :22-36

[3]

Blazewicz J., 1991, International Journal of Flexible Manufacturing Systems, V4, P5, DOI 10.1007/BF01325094

[4] SCHEDULING WITH EARLIEST START AND DUE DATE CONSTRAINT [J].

BRATLEY, P ;

ROBILLAR.P ;

FLORIAN, M .

NAVAL RESEARCH LOGISTICS QUARTERLY, 1971, 18 (04) :511-&

[5] SURVEY OF SCHEDULING RESEARCH INVOLVING DUE DATE DETERMINATION DECISIONS [J].

CHENG, TCE ;

GUPTA, MC .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 38 (02) :156-166

[6] IMPROVEMENTS AND EXTENSIONS TO THE MILLER-TUCKER-ZEMLIN SUBTOUR ELIMINATION CONSTRAINTS [J].

DESROCHERS, M ;

LAPORTE, G .

OPERATIONS RESEARCH LETTERS, 1991, 10 (01) :27-36

[7]

Garey MR., 1979, COMPUTERS INTRACTABI

[8]

GUPTA SK, 1987, OMEGA-INT J MANAGE S, V15, P207, DOI 10.1016/0305-0483(87)90071-5

[9]

HART C, 1986, CARUSOS PIZZA EXPRES

[10] DYNAMIC SCHEDULING OF AUTOMATED GUIDED VEHICLES FOR A CERTAIN CLASS OF SYSTEMS [J].

JAIKUMAR, R ;

SOLOMON, MM .

JOURNAL OF MANUFACTURING SYSTEMS, 1990, 9 (04) :315-323

← 1 2 →