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/2/1
Y1 - 2018/2/1
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.
KW - Pickup and delivery problem
KW - Profitable tour problem
KW - Tailored labeling algorithm
KW - Time-dependent travel times
KW - Transportation
UR - http://www.scopus.com/inward/record.url?scp=85025106601&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2017.07.004
DO - 10.1016/j.ejor.2017.07.004
M3 - Article
SN - 0377-2217
VL - 264
SP - 1058
EP - 1073
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 3
ER -