Time-Dependent Traveling Salesman Problem with Multiple Time Windows

• Autorzy: Jarosław Hurkała
• Języki publikacji: EN

Abstrakty

EN

The TSP, VRP and OP problems with time constraints have one common sub-problem - the task of finding the minimum route duration for a given order of customers. While much work has been done on routing and scheduling problems with time windows, to this date only few articles considered problems with multiple time windows. Moreover, since the assumption of constant travel time between two locations at all times is very unrealistic, problems with time-dependent travel were introduced and studied. Finally, it is also possible to imagine some situations, in which the service time changes during the day. Again, both issues have been investigated only in conjunction with single time windows. In this paper we propose a novel algorithm for computing minimum route duration in traveling salesman problem with multiple time windows and time-dependent travel and service time. The algorithm can be applied to wide range of problems in which a traveler has to visit a set of customers or locations within specified time windows taking into account the traffic and variable service/visit time. Furthermore, we compare three metaheuristics for computing a one-day schedule for this problem, and show that it can be solved very efficiently.(original abstract)

Słowa kluczowe

EN

Algorithms; Time-series analysis

PL

Algorytmy; Analiza szeregów czasowych

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 6
• Strony: 71--78

Twórcy

autor

Jarosław Hurkała

Bibliografia

• Cerný, V., Thermodynamical approach to traveling salesman problem: ˇ An efficient simulation algorithm. J. Optim. Theory Appl., vol. 45 (1985) 41-51.
• Belhaiza S., P. Hansen, G. Laporte. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows, Computers & Operations Research, Volume 52 (2014), 269- 281.
• Favaretto D., E. Moretti, P. Pellegrini. Ant colony system for a VRP with multiple time windows and multiple visits, Journal of Interdisciplinary Mathematics, Volume 10, Issue 2 (2007), 263-284.
• Hurkała J., Minimum Route Duration Algorithm for Traveling Salesman Problem with Multiple Time Windows, Vehicle Routing and Logistics Optimization, June 8-10, 2015, Vienna, Austria [accepted for presentation].
• Hurkała, J. and Hurkała, A., Effective Design of the Simulated Annealing Algorithm for the Flowshop Problem with Minimum Makespan Criterion, Journal of Telecommunications and Information Technology 2 (2012) 92-98.
• Hurkała, J. and Hurkała, A., Fair optimization with advanced aggregation operators in a multicriteria facility layout problem, in Proceedings of the 2013 Federated Conference on Computer Science and Information Systems, IEEE, 2013, 355-362.
• Hurkała, J. and Sliwiński, T., Fair flow optimization with advanced ´ aggregation operators in Wireless Mesh Networks, in Proceedings of the Federated Conference on Computer Science and Information Systems, IEEE, 2012, 415-421.
• Jong C., G. Kant, A. van Vliet. On Finding Minimal Route Duration in the Vehicle Routing Problem with Multiple Time Windows, Tech. Rep., The Netherlands: Department of Computer Science, Utrecht University, 1996.
• Mladenovic, N., and Hansen, P. ´ Variable neighborhood search. Computers and Operations Research 24 (11), 1997, 1097-?1100.
• Kirkpatrick, S., Gellat, C.D. and Vecchi, M.P., Optimization by simulated annealing, Science, vol. 220 (1983) 671-680.
• ] Koulamas, C., Antony, S.R. and Jaen, R., A survey of simulated annealing applications to operations research problems, Omega, 22 (1994) 41-56.
• Lee, D.S., Vassiliadis, V.S., Park, J.M., A novel thresholdaccepting metaheuristic for the job-shop scheduling problem. Computers & Operations Research, 31 (2004) 2199-2213.
• Lee, D.S., Vassiliadis, V.S., Park, J.M., List-Based Threshold-Accepting Algorithm for Zero-Wait Scheduling of Multiproduct Batch Plants, Ind. Eng. Chem. Res. 41 (25), 2002, pp. 6579-?6588.
• Savelsbergh, M.W.P. The Vehicle Routing Problem with Time Windows: Minimizing Route Duration, ORSA Journal on Computing, Vol. 4, Issue 2 (1992), 146-161.
• Souffriau W., P. Vansteenwegen, G.V. Berghe, D. Van Oudheusden. . The Multi-Constraint Team Orienteering Problem with Multiple Time Windows, Transportation Science, Volume 47, Issue 1 (2013), 53-63.
• Tricoire F., Romauch, M., Doerner, K.F., Hartl, R.F. Heuristics for the multi-period orienteering problem with multiple time windows, Computers & Operations Research 37 (2010), 351-367.

Identyfikatory

DOI

10.15439/2015F311