THE TRAVELING SALESMAN PROBLEM WITH DELIVERY AND BACKHAULS

被引：43

作者：

ANILY, S

MOSHEIOV, G

机构：

[1] HEBREW UNIV JERUSALEM,SCH BUSINESS ADM,JERUSALEM,ISRAEL

[2] HEBREW UNIV JERUSALEM,DEPT STAT,JERUSALEM,ISRAEL

来源：

OPERATIONS RESEARCH LETTERS | 1994年 / 16卷 / 01期

关键词：

TRAVELING SALESMAN PROBLEM; VEHICLE ROUTING; HEURISTIC; WORST-CASE ANALYSIS; COMPUTATIONAL COMPLEXITY;

D O I：

10.1016/0167-6377(94)90016-7

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The problem that we consider here deals with a single vehicle of a given capacity that needs to serve N customers: some of the customers require a delivery of stock from the warehouse, whereas others need to deliver stock from their location to the warehouse. The objective is to find a shortest feasible tour visiting all customers, emanating from the ending at the warehouse. We introduce an efficient (O(N2)) heuristic for this problem. The heuristic improves the worst-case bound known in the literature from 2.5 to 2. However, its average performance is shown in our numerical study to be slightly worse than that of a previously published (O(N3)) solution method.

引用

页码：11 / 18

页数：8