A memetic algorithm for the orienteering problem with hotel selection. (English) Zbl 1304.90220
Summary: In this paper, a memetic algorithm is developed to solve the orienteering problem with hotel selection (OPHS). The algorithm consists of two levels: a genetic component mainly focuses on finding a good sequence of intermediate hotels, whereas six local search moves embedded in a variable neighborhood structure deal with the selection and sequencing of vertices between the hotels. A set of 176 new and larger benchmark instances of OPHS are created based on optimal solutions of regular orienteering problems. Our algorithm is applied on these new instances as well as on 224 benchmark instances from the literature. The results are compared with the known optimal solutions and with the only other existing algorithm for this problem. The results clearly show that our memetic algorithm outperforms the existing algorithm in terms of solution quality and computational time. A sensitivity analysis shows the significant impact of the number of possible sequences of hotels on the difficulty of an OPHS instance.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C27 | Combinatorial optimization |
Keywords:
orienteering problem; memetic algorithm; population management; intermediate facilities; hotel selectionReferences:
| [1] | Angelelli, E.; Speranza, M. G., The periodic vehicle routing problem with intermediate facilities, European Journal of Operational Research, 137, 233-247 (2002) · Zbl 0998.90021 |
| [2] | Angelelli, E.; Speranza, M. G., The application of a vehicle routing model to a waste-collection problem: two case studies, Journal of the Operational Research Society, 53, 944-952 (2002) · Zbl 1139.90396 |
| [3] | Beasley, J. E., Route first—Cluster second methods for vehicle routing, Omega, 11, 403-408 (1983) |
| [4] | Benjamin, A. M.; Beasley, J. E., Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities, Computers & Operations Research, 37, 2270-2280 (2010) |
| [5] | Boudia, M.; Prins, C., A memetic algorithm with dynamic population management for an integrated production-Distribution problem, European Journal of Operational Research, 195, 703-715 (2009) · Zbl 1156.90344 |
| [7] | Castro, M.; Sörensen, K.; Vansteenwegen, P.; Goos, P., A memetic algorithm for the travelling salesperson problem with hotel selection, Computers & Operations Research, 40, 1716-1728 (2013) · Zbl 1348.90438 |
| [8] | Crevier, B.; Cordeau, J.-F.; Laporte, G., The multi-depot vehicle routing problem with inter-depot routes, European Journal of Operational Research, 176, 756-773 (2007) · Zbl 1103.90032 |
| [9] | Dang, D.-C.; Guibadj, R. N.; Moukrim, A., An effective PSO-inspired algorithm for the team orienteering problem, European Journal of Operational Research, 229, 332-344 (2013) · Zbl 1317.90114 |
| [10] | Divsalar, A.; Vansteenwegen, P.; Cattrysse, D., A variable neighborhood search method for the orienteering problem with hotel selection, International Journal of Production Economics, 145, 150-160 (2013) |
| [11] | Gendreau, M.; Laporte, G.; Semet, F., A branch and cut algorithm for the undirected selective traveling salesman problem, Networks, 32, 263-273 (1998) · Zbl 1002.90044 |
| [12] | Ghiani, G.; Federico, N., The capacitated arc routing problem with intermediate facilities, Networks, 37, 134-143 (2001) · Zbl 0981.90059 |
| [13] | Ghiani, G.; Guerriero, F.; Laporte, G.; Musmanno, R., Tabu search heuristics for the arc routing problem with intermediate facilities under capacity and length restrictions, Journal of Mathematical Modelling and Algorithms, 3, 209-223 (2004) · Zbl 1058.90031 |
| [14] | Ghiani, G.; Laganà, D.; Laporte, G.; Mari, F., Ant colony optimization for the arc routing problem with intermediate facilities under capacity and length restrictions, Journal of Heuristics, 16, 211-233 (2008) · Zbl 1188.90264 |
| [15] | Golden, B. L.; Levy, L.; Vohra, R., The orienteering problem, Naval Research Logistics, 34, 307-318 (1987) · Zbl 0647.90099 |
| [16] | Kek, A. G.H.; Cheu, R. L.; Meng, Q., Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots, Mathematical and Computer Modelling, 47, 140-152 (2008) · Zbl 1146.90332 |
| [17] | Kim, B.-I.; Kim, S.; Sahoo, S., Waste collection vehicle routing problem with time windows, Computers & Operations Research, 33, 3624-3642 (2006) · Zbl 1113.90035 |
| [18] | Mendoza, J. E.; Castanier, B.; Guéret, C.; Medaglia, A. L.; Velasco, N., A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands, Computers & Operations Research, 37, 1886-1898 (2010) · Zbl 1188.90035 |
| [19] | Moscato, P., Memetic algorithms: A short introduction, (Corne, D.; Dorigo, M.; Glover, F., New Ideas in Optimization (1999), McGrw-Hill), 219-234 |
| [20] | Ngueveu, S. U.; Prins, C.; Wolfler Calvo, R., An effective memetic algorithm for the cumulative capacitated vehicle routing problem, Computers & Operations Research, 37, 1877-1885 (2010) · Zbl 1188.90037 |
| [22] | Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research, 31, 1985-2002 (2004) · Zbl 1100.90504 |
| [23] | Schilde, M.; Doerner, K. F.; Hartl, R. F.; Kiechle, G., Metaheuristics for the bi-objective orienteering problem, Swarm Intelligence, 3, 179-201 (2009) |
| [24] | Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35, 254-265 (1987) · Zbl 0625.90047 |
| [25] | Sörensen, K.; Sevaux, M., MAPM: memetic algorithms with population management, Computers & Operations Research, 33, 1214-1225 (2006) · Zbl 1126.90081 |
| [26] | Talbi, E.-G., Metaheuristics: From design to implementation (2009), Wiley · Zbl 1190.90293 |
| [27] | Tarantilis, C. D.; Zachariadis, E. E.; Kiranoudis, C. T., A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities, INFORMS Journal on Computing, 20, 154-168 (2008) · Zbl 1243.90027 |
| [28] | Tsiligirides, T., Heuristic methods applied to orienteering, Journal of the Operational Research Society, 35, 797-809 (1984) |
| [29] | Vansteenwegen, P.; Souffriau, W.; Sörensen, K., The travelling salesperson problem with hotel selection, Journal of the Operational Research Society, 63, 207-217 (2012) |
| [30] | Vansteenwegen, P.; Souffriau, W.; Van Oudheusden, D., The orienteering problem: A survey, European Journal of Operational Research, 209, 1-11 (2011) · Zbl 1205.90253 |
| [31] | Vansteenwegen, P.; Souffriau, W.; Vanden Berghe, G.; Van Oudheusden, D., The City Trip Planner: An expert system for tourists, Expert Systems with Applications, 38, 6540-6546 (2011) |
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.
