The time-dependent capacitated profitable tour problem with time windows and precedence constraints

被引：46

作者：

Sun, Peng ^{[1
]}

Veelenturf, Lucas P. ^{[1
]}

Dabia, Said ^{[2
]}

Van Woensel, Tom ^{[1
]}

机构：

[1] Eindhoven Univ Technol, Sch Ind Engn Operat Planning Accounting & Control, NL-5600 MB Eindhoven, Netherlands

[2] Vrije Univ Amsterdam, Dept Informat Logist & Innovat, NL-1081 HV Amsterdam, Netherlands

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2018年 / 264卷 / 03期

关键词：

Transportation; Profitable tour problem; Pickup and delivery problem; Tailored labeling algorithm; Time-dependent travel times; VEHICLE-ROUTING PROBLEM; TRAVELING SALESMAN PROBLEM; SHORTEST-PATH PROBLEM; ORIENTEERING PROBLEM; RESOURCE CONSTRAINTS; DELIVERY PROBLEM; ALGORITHM; BRANCH; PICKUP; PRICE;

D O I：

10.1016/j.ejor.2017.07.004

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We introduce the time-dependent capacitated profitable tour problem with time windows and precedence constraints. This problem concerns determining a tour and its departure time at the depot that maximizes the collected profit minus the total travel cost (measured by total travel time). To deal with road congestion, travel times are considered to be time-dependent. We develop a tailored labeling algorithm to find the optimal tour. Furthermore, we introduce dominance criteria to discard unpromising labels. Our computational results demonstrate that the algorithm is capable of solving instances with up to 150 locations (75 pickup and delivery requests) to optimality. Additionally, we present a restricted dynamic programing heuristic to improve the computation time. This heuristic does not guarantee optimality, but is able to find the optimal solution for 32 instances out of the 34 instances. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：1058 / 1073

页数：16

共 28 条

[1]

[Anonymous], 1987, Encyclopedia of Artificial Intelligence

[2] THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM [J].