The time-dependent capacitated profitable tour problem with time windows and precedence constraints
| Autor: | Said Dabia, Peng Sun, Tom Van Woensel, Lucas P. Veelenturf |
|---|---|
| Přispěvatelé: | Information, Logistics and Innovation, Logistics, Amsterdam Business Research Institute, Operations Planning Acc. & Control, Department of Technology and Operations Management |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
050210 logistics & transportation
Time-dependent travel times 021103 operations research Information Systems and Management General Computer Science Operations research Computer science Heuristic 05 social sciences 0211 other engineering and technologies Transportation 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering Tailored labeling algorithm Dynamic programming Time windows Modeling and Simulation 0502 economics and business Profitable tour problem Pickup and delivery problem |
| Zdroj: | European Journal of Operational Research, 264(3), 1058-1073. Elsevier Sun, P, Veelenturf, L P, Dabia, S & Van Woensel, T 2018, ' The time-dependent capacitated profitable tour problem with time windows and precedence constraints ', European Journal of Operational Research, vol. 264, no. 3, pp. 1058-1073 . https://doi.org/10.1016/j.ejor.2017.07.004 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2017.07.004 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect