The time-dependent capacitated profitable tour problem with time windows and precedence constraints. (English) Zbl 1375.90058
Summary: 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.
Keywords:
transportation; profitable tour problem; pickup and delivery problem; tailored labeling algorithm; time-dependent travel timesReferences:
| [1] | Balas, E., The prize-collecting traveling salesman problem, Networks, 19, 6, 621-636 (1989) · Zbl 0676.90089 |
| [2] | Bisiani, R., Beam search, (Shapiro, S., Encyclopedia of artificial intelligence (1987), Wiley and Sons), 56-58 · Zbl 0664.68085 |
| [3] | Dabia, S.; Ropke, S.; van Woensel, T.; de Kok, T., Branch and cut and price for the time dependent vehicle routing problem with time windows, Transportation Science, 47, 3, 380-396 (2013) |
| [4] | Dell’ Amico, M.; Maffioli, F.; Varbrand, P., On prize-collecting tours and the asymmetric traveling salesman problem, International Transactions in Operational Research, 2, 3, 297-308 (1995) · Zbl 0860.90121 |
| [5] | Donati, A.; Montemanni, R.; Casagrande, N.; Rizzolo, A. E.; Gambardella, L., Time dependent vehicle routing problem with a muti-ant colony system, European Journal of Operational Research, 185, 3, 1174-1191 (2008) · Zbl 1146.90328 |
| [6] | Dumitrescu, I.; Ropke, S.; Cordeau, J., The traveling salesman problem with pickup and delivery: polyhedral results and branch-and-cut algorithm, Mathematic Programming Series A, 121, 2, 269-305 (2010) · Zbl 1184.90108 |
| [7] | Feillet, D.; Dejax, P.; Gendreau, M., An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems, Networks, 44, 3, 216-229 (2004) · Zbl 1056.90014 |
| [8] | Feillet, D.; Dejax, P.; Gendreau, M., Traveling salesman problems with profits, Transportation Science, 39, 2, 188-205 (2005) |
| [9] | Fomin, F.; Lingas, A., Approximation algorithms for time-dependent orienteering, Information Processing Letters, 83, 2, 57-62 (2002) · Zbl 1043.90076 |
| [10] | Gromicho, J.; van Hoorn, J.; Kok, A.; Schutten, J., Restricted dynamic programming: A flexible framework for solving realistic VRPs, Computers and Operations Research, 39, 5, 902-909 (2012) · Zbl 1251.90380 |
| [11] | Gunawan, A.; Lau, H. C.; Vansteenwegen, P., Orienteering problem: A survey of recent variants, solution approaches and applications, European Journal of Operational Research, 255, 2, 315-332 (2016) · Zbl 1346.90703 |
| [12] | Ibaraki, T.; Imahori, S.; Nonobe, K.; Sobue, K.; Uno, T.; Yagiura, M., An iterated local search algorithm for the vehicle routing problem with convex time penalty functions, Discrete Applied Mathematics, 156, 11, 2050-2069 (2008) · Zbl 1153.90446 |
| [13] | Ichoua, S.; Gendreau, M.; Potvin, J., Vehicle dispatching with time-dependent travel times, European Journal of Operational Research, 144, 2, 379-396 (2003) · Zbl 1012.90003 |
| [14] | Laporte, G.; Martello, S., The selective traveling salesman problem, Discrete Applied Mathematics, 26, 2-3, 193-207 (1990) · Zbl 0695.90098 |
| [15] | Li, J., Model and algorithm for time-dependent team orienteering problem, (Lin, S.; Huang, X., Advanced research on computer education, simulation and modeling. Communications in computer and information science, vol. 175 (2011)), 1-7 |
| [16] | Malandraki, C.; Daskin, M., Time dependent vehicle routing problems: Formulations, properties, and heuristic algorithms, Transportation Science, 26, 3, 185-200 (1992) · Zbl 0758.90029 |
| [17] | Malandraki, C.; Dial, R., A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem, European Journal of Operational Research, 90, 1, 45-55 (1996) · Zbl 0916.90262 |
| [18] | Righini, G.; Salani, M., Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Discrete Optimization, 3, 3, 255-273 (2006) · Zbl 1149.90167 |
| [19] | Ropke, S.; Cordeau, J.-F.; Laporte, G., Branch and cut and price for the pickup and delivery problem with time windows, Transportation Science, 43, 3, 267-286 (2009) |
| [20] | Ruland, K.; Rodin, E., The pickup and delivery problem: Faces and branch-and-cut algorithm, Computers Mathematics with Applications, 33, 12, 1-13 (1997) · Zbl 0894.90128 |
| [21] | Ruland, K. S., Polyhedral solution to the pickup and delivery problem (1994), Ph.D. thesis, Sever Institute, Washington University in St.Louis |
| [22] | Sigurd, M.; Pisinger, D., Scheduling transportation of live animals to avoid the spread of diseases, Transportation Science, 38, 2, 197-209 (2004) |
| [23] | Sol, M., Column generation techniques for pickup and delivery problems (1994), Ph.D thesis, Technische Universiteit Eindhoven · Zbl 0833.90037 |
| [24] | Taş, D.; Dellaert, N.; van Woensel, T.; de Kok, T., The time-dependent vehicle routing problem with soft time windows and stochastic travel times, Transportation Research Part C: Emerging Technologies, 48, 66-83 (2014) · Zbl 1304.90044 |
| [25] | Vansteenwegen, P.; Souffriau, W.; Oudheusden, D. V., The orienteering problem: a survey, European Journal of Operational Reseach, 209, 1, 1-10 (2011) · Zbl 1205.90253 |
| [26] | Verbeeck, C.; Aghezzaf, E. H.; Vansteenwegen, P., A fast solution method for the time-dependent orienteering problem with time windows, European Journal of Operational Research, 236, 2, 419-432 (2014) · Zbl 1317.90056 |
| [27] | Verbeeck, C.; Vansteenwegen, P.; Aghezzaf, E.-H., Solving the stochastic time-dependent orienteering problem with time windows, European Journal of Operational Research, 255, 3, 699-718 (2016) · Zbl 1394.90131 |
| [28] | van Woensel, T.; Kerbache, L.; Peremans, H.; Vandaele, N., Vehicle routing with dynamic travel times: A queueing approach, European Journal of Operational Research, 186, 3, 990-1007 (2008) · Zbl 1146.90426 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
