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

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
2 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)1058-1073
JournalEuropean Journal of Operational Research
Volume264
Issue number3
DOIs
Publication statusPublished - 2018

Fingerprint

Precedence Constraints
Travel Time
Time Windows
Travel time
Optimality
Heuristics
Labeling Algorithm
Pickup and Delivery
Pickups
Congestion
Labeling
Profit
Computational Results
Labels
Profitability
Optimal Solution
Maximise
Costs
Demonstrate
Time windows

Cite this

@article{c19a435fd0b844bda3afc9d6daafd0d5,
title = "The time-dependent capacitated profitable tour problem with time windows and precedence constraints",
abstract = "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.",
author = "P. Sun and L.P. Veelenturf and S. Dabia and {van Woensel}, T.",
year = "2018",
doi = "10.1016/j.ejor.2017.07.004",
language = "English",
volume = "264",
pages = "1058--1073",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

The time-dependent capacitated profitable tour problem with time windows and precedence constraints. / Sun, P.; Veelenturf, L.P.; Dabia, S.; van Woensel, T.

In: European Journal of Operational Research, Vol. 264, No. 3, 2018, p. 1058-1073.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Sun, P.

AU - Veelenturf, L.P.

AU - Dabia, S.

AU - van Woensel, T.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

U2 - 10.1016/j.ejor.2017.07.004

DO - 10.1016/j.ejor.2017.07.004

M3 - Article

VL - 264

SP - 1058

EP - 1073

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -