A heuristic method for the open vehicle routing problem

被引：152

作者：

Sariklis, D ^{[1
]}

Powell, S ^{[1
]}

机构：

[1] Univ London London Sch Econ & Polit Sci, Dept Operat Res, London WC2A 2AE, England

来源：

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 2000年 / 51卷 / 05期

关键词：

distribution management; heuristics; open vehicle routing problem;

D O I：

10.1057/palgrave.jors.2600924

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The open vehicle routing problem (OVRP) differs from the classic vehicle routing problem (VRP) because the vehicles either are not required to return to the depot, or they have to return by revisiting the customers assigned to them in the reverse order. Therefore, the vehicle routes are not closed paths but open ones. A heuristic method for solving this new problem, based on a minimum spanning tree with penalties procedure, is presented. Computational results are provided.

引用

页码：564 / 573

页数：10

共 14 条

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

BODIN, L ;

GOLDEN, B .

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

[2]

Christofides N., 1979, Combinatorial optimization, P315

[3] A CLASSIFICATION SCHEME FOR VEHICLE-ROUTING AND SCHEDULING PROBLEMS [J].

DESROCHERS, M ;

LENSTRA, JK ;

SAVELSBERGH, MWP .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 46 (03) :322-332

[4]

EILON S, 1971, DISTRIBUTION MANAGEM, P180

[5] AN EXACT ALGORITHM FOR THE ASYMMETRICAL CAPACITATED VEHICLE-ROUTING PROBLEM [J].

LAPORTE, G ;

MERCURE, H ;

NOBERT, Y .

NETWORKS, 1986, 16 (01) :33-46

[6] A BRANCH AND BOUND ALGORITHM FOR THE CAPACITATED VEHICLE-ROUTING PROBLEM [J].

LAPORTE, G ;

NOBERT, Y .

OR SPEKTRUM, 1983, 5 (02) :77-85

[7] OPTIMAL ROUTING UNDER CAPACITY AND DISTANCE RESTRICTIONS [J].

LAPORTE, G ;

NOBERT, Y ;

DESROCHERS, M .

OPERATIONS RESEARCH, 1985, 33 (05) :1050-1073

[8] A BRANCH AND BOUND ALGORITHM FOR A CLASS OF ASYMMETRICAL VEHICLE ROUTEING PROBLEMS [J].

LAPORTE, G ;

MERCURE, H ;

NOBERT, Y .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1992, 43 (05) :469-481

[9] EFFECTIVE HEURISTIC ALGORITHM FOR TRAVELING-SALESMAN PROBLEM [J].

LIN, S ;

KERNIGHAN, BW .

OPERATIONS RESEARCH, 1973, 21 (02) :498-516

[10] SHORTEST CONNECTION NETWORKS AND SOME GENERALIZATIONS [J].

PRIM, RC .

BELL SYSTEM TECHNICAL JOURNAL, 1957, 36 (06) :1389-1401

← 1 2 →