AN EXCHANGE HEURISTIC FOR ROUTEING PROBLEMS WITH TIME WINDOWS

被引：90

作者：

POTVIN, JY

ROUSSEAU, JM

机构：

来源：

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 1995年 / 46卷 / 12期

关键词：

HEURISTICS; TIME WINDOWS; VEHICLE ROUTEING;

D O I：

10.2307/2584063

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we compare different exchange heuristics for vehicle routeing problems with time windows. We also introduce a new 2-opt* exchange heuristic, and show that a hybrid approach, based on Or-opt and 2-opt* exchanges, is particularly powerful for problems with time windows. Computational results are reported for randomly generated problems and for a standard test set.

引用

收藏

页码：1433 / 1446

页数：14

相关论文

共 14 条

[1] TRANSFORMATION OF MULTISALESMEN PROBLEM TO STANDARD TRAVELLING SALESMAN PROBLEM [J].

BELLMORE, M ;

HONG, S .

JOURNAL OF THE ACM, 1974, 21 (03) :500-504

[2]

BODIN L, 1983, COMPUT OPER RES, V10, P63, DOI 10.1016/0305-0548(83)90030-8

[3]

Johnson D. S., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P39, DOI 10.1109/SFCS.1985.31

[4] COMPUTER SOLUTIONS OF TRAVELING SALESMAN PROBLEM [J].

LIN, S .

BELL SYSTEM TECHNICAL JOURNAL, 1965, 44 (10) :2245-+

[5]

Or I., 1976, THESIS NW U

[6] A PARALLEL ROUTE BUILDING ALGORITHM FOR THE VEHICLE-ROUTING AND SCHEDULING PROBLEM WITH TIME WINDOWS [J].

POTVIN, JY ;

ROUSSEAU, JM .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 66 (03) :331-340

[7]

POTVIN JY, 1993, CRT755 U MONTR CTR R

[8] K-INTERCHANGE PROCEDURES FOR LOCAL SEARCH IN A PRECEDENCE-CONSTRAINED ROUTING PROBLEM [J].

PSARAFTIS, HN .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1983, 13 (04) :391-402

[9]

SAVELSBERGH M, 1986, ANN OPER RES, V4, P285

[10] ALGORITHMS FOR THE VEHICLE-ROUTING AND SCHEDULING PROBLEMS WITH TIME WINDOW CONSTRAINTS [J].

SOLOMON, MM .

OPERATIONS RESEARCH, 1987, 35 (02) :254-265