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

Peng Sun, Lucas P. Veelenturf, Said Dabia, Tom Van Woensel

Research output: Contribution to JournalArticleAcademicpeer-review

306 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
Number of pages16
JournalEuropean Journal of Operational Research
Volume264
Issue number3
Early online date12 Jul 2017
DOIs
Publication statusPublished - 1 Feb 2018

Funding

The authors gratefully acknowledge funds provided by China Scholarship Council (CSC) under Grant No. 201206160092 .

FundersFunder number
China Scholarship Council201206160092

    Keywords

    • Pickup and delivery problem
    • Profitable tour problem
    • Tailored labeling algorithm
    • Time-dependent travel times
    • Transportation

    Fingerprint

    Dive into the research topics of 'The time-dependent capacitated profitable tour problem with time windows and precedence constraints'. Together they form a unique fingerprint.

    Cite this