THE SPACEFILLING CURVE WITH OPTIMAL PARTITIONING HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM

被引：25

作者：

BOWERMAN, RL ^{[1
]}

CALAMAI, PH ^{[1
]}

HALL, GB ^{[1
]}

机构：

[1] UNIV WATERLOO,DEPT URBAN & REG PLANNING,WATERLOO N2L 3G1,ONTARIO,CANADA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1994年 / 76卷 / 01期

基金：

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

关键词：

ROUTING; SPACEFILLING CURVES; HEURISTICS; DYNAMIC PROGRAMMING;

D O I：

10.1016/0377-2217(94)90011-6

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper introduces the Spacefilling Curve with Optimal Partitioning (SFC OP) heuristic strategy for producing solutions to the Vehicle Routing Problem (VRP). This heuristic has the property that it generates good routes extremely quickly and the time required increases nearly linearly with problem size. Additionally, the SFC OP heuristic can easily be modified to generate routes to VRP formulations with multiple objective functions.

引用

页码：128 / 142

页数：15

共 20 条

[1] A 3-OPT BASED SIMULATED ANNEALING ALGORITHM FOR VEHICLE-ROUTING PROBLEMS [J].

ALFA, AS ;

HERAGU, SS ;

CHEN, MY .

COMPUTERS & INDUSTRIAL ENGINEERING, 1991, 21 (1-4) :635-639

[2] HEURISTICS BASED ON SPACEFILLING CURVES FOR COMBINATORIAL PROBLEMS IN EUCLIDEAN-SPACE [J].

BARTHOLDI, JJ ;

PLATZMAN, LK .

MANAGEMENT SCIENCE, 1988, 34 (03) :291-305

[3]

Bellman R., 1957, DYNAMIC PROGRAMMING

[4] CLASSIFICATION IN VEHICLE-ROUTING AND SCHEDULING [J].

BODIN, L ;

GOLDEN, B .

NETWORKS, 1981, 11 (02) :97-108

[5]

Bodin L. D., 1979, Transportation Science, V13, P113, DOI 10.1287/trsc.13.2.113

[6]

BOWERMAN RL, 1991, 188O300991 U WAT DEP

[7] CLUSTERING FOR ROUTING IN DENSELY POPULATED AREAS [J].

CHAPLEAU, L ;

FERLAND, JA ;

ROUSSEAU, JM .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1985, 20 (01) :48-57

[8] AN ALGORITHM FOR VEHICLE-DISPATCHING PROBLEM [J].

CHRISTOF.N ;

EILON, S .

OPERATIONAL RESEARCH QUARTERLY, 1969, 20 (03) :309-&

[9] SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].

CLARKE, G ;

WRIGHT, JW .

OPERATIONS RESEARCH, 1964, 12 (04) :568-&

[10] A GENERALIZED ASSIGNMENT HEURISTIC FOR VEHICLE-ROUTING [J].

FISHER, ML ;

JAIKUMAR, R .

NETWORKS, 1981, 11 (02) :109-124

← 1 2 →