Formulation and a heuristic approach for the orienteering location-routing problem
RAIRO. Operations Research, Tome 55 (2021), pp. S2055-S2069

In this paper, a new version of the location-routing problem (LRP), named orienteering location-routing problem (OLRP) is investigated. The problem is composed of two-well known problems: team orienteering problem (TOP) and LRP. There are some challenging practical applications in logistics, tourism, military operations, and other fields, which can be modeled by OLRP. The problem is to consider the location and routing with a special objective function. In the OLRP, a set of nodes with specific scores is given, and some stations among candidate stations should be established. Moreover, there are some routes limited in length, which start from a station, visit some nodes and then return to the same station. Maximizing the sum of the collected scores is the goal of OLRP. To model the problem, an integer linear programming model is proposed. Against a commercial solver, a heuristic GRASP is developed for solving the standard test problems. Most test problems are found difficult to solve optimally with commercial software while the GRASP can find the best known or close to the best-known solution in a short time.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2020058
Classification : 90B06, 90C27, 90B80
Keywords: Orienteering problem, location routing problem, GRASP 
@article{RO_2021__55_S1_S2055_0,
     author = {Nadizadeh, Ali},
     title = {Formulation and a heuristic approach for the orienteering location-routing problem},
     journal = {RAIRO. Operations Research},
     pages = {S2055--S2069},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020058},
     mrnumber = {4223082},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020058/}
}
TY  - JOUR
AU  - Nadizadeh, Ali
TI  - Formulation and a heuristic approach for the orienteering location-routing problem
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S2055
EP  - S2069
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020058/
DO  - 10.1051/ro/2020058
LA  - en
ID  - RO_2021__55_S1_S2055_0
ER  - 
%0 Journal Article
%A Nadizadeh, Ali
%T Formulation and a heuristic approach for the orienteering location-routing problem
%J RAIRO. Operations Research
%D 2021
%P S2055-S2069
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020058/
%R 10.1051/ro/2020058
%G en
%F RO_2021__55_S1_S2055_0
Nadizadeh, Ali. Formulation and a heuristic approach for the orienteering location-routing problem. RAIRO. Operations Research, Tome 55 (2021), pp. S2055-S2069. doi: 10.1051/ro/2020058

[1] A. Ahmadi-Javid, E. Amiri and M. Meskar, A profit-maximization location-routing-pricing problem: a branch-and-price algorithm. Eur. J. Oper. Res. 271 (2018) 866–881. | MR | DOI

[2] J. Ahn, O. De Weck, Y. Geng and D. Klabjan, Column generation based heuristics for a generalized location routing problem with profits arising in space exploration. Eur. J. Oper. Res. 223 (2012) 47–59. | MR | Zbl | DOI

[3] L. Alfandari, Improved approximation of the general soft-capacitated facility location problem. RAIRO:OR 41 (2007) 83–93. | MR | Numdam | DOI

[4] C. Archetti, F. Carrabs and R. Cerulli, The set orienteering problem. Eur. J. Oper. Res. 267 (2018) 264–272. | MR | DOI

[5] D. G. Baklagis, G. Dikas and I. Minis, The team orienteering pick-up and delivery problem with time windows and its applications in fleet sizing. RAIRO:OR 50 (2016) 503–517. | MR | Zbl | Numdam | DOI

[6] R. Baldacci, A. Mingozzi and R. Wolfler Calvo, An exact method for the capacitated location-routing problem. Oper. Res. 59 (2011) 1284–1296. | MR | Zbl | DOI

[7] S. Barreto, Available at: http://sweet.us.pt/iscf143 (2003).

[8] S. Barreto, C. Ferreira, J. Paixao and B. Sousa Santos, Using clustering analysis in a capacitated location-routing problem. Eur. J. Oper. Res. 179 (2007) 968–977. | Zbl | DOI

[9] J. M. Belenguer, E. Benavent, C. Prins, C. Prodhon and R. Wolfler-Calvo, A branch-and-cut method for the capacitated location-routing problem. Comput. Oper. Res. 38 (2011) 931–941. | MR | Zbl | DOI

[10] N. Bianchessi, R. Mansini and M. G. Speranza, A branch-and-cut algorithm for the Team Orienteering Problem. Int. Trans. Oper. Res. 25 (2018) 627–635. | MR | DOI

[11] M. Boccia, T. G. Crainic, A. Sforza and C. Sterle, Multi-commodity location-routing: flow intercepting formulation and branch-and-cut algorithm. Comput. Oper. Res. 89 (2018) 94–112. | MR | DOI

[12] T. Capelle, C. E. Cortés, M. Gendreau, P. A. Rey and L.-M. Rousseau, A column generation approach for location-routing problems with pickup and delivery. Eur. J. Oper. Res. 272 (2019) 121–131. | MR | DOI

[13] I. M. Chao, B. L. Golden and E. A. Wasil, A fast and effective heuristic for the orienteering problem. Eur. J. Oper. Res. 88 (1996) 475–489. | Zbl | DOI

[14] W. R. Cherif-Khettaf, M. H. Rachid, C. Bloch and P. Chatonnay, New notation and classification scheme for vehicle routing problems. RAIRO:OR 49 (2015) 161–194. | MR | Zbl | Numdam | DOI

[15] C. Contardo, V. Hemmelmayr and T. G. Crainic, Lower and upper bounds for the two-echelon capacitated location-routing problem. Comput. Oper. Res. 39 (2012) 3185–3199. | MR | DOI

[16] Z. Dai, F. Aqlan, K. Gao and Y. Zhou, A two-phase method for multi-echelon location-routing problems in supply chains. Expert Syst. App. 115 (2019) 618–634. | DOI

[17] H. Derbel, B. Jarboui, S. Hanafi and H. Chabchoub, Genetic algorithm with iterated local search for solving a location-routing problem. Expert Syst. App. 39 (2012) 2865–2871. | DOI

[18] M. Drexl and M. Schneider, A survey of variants and extensions of the location-routing problem. Eur. J. Oper. Res. 241 (2015) 283–308. | MR | DOI

[19] T. Drezner, Z. Drezner and D. Zerom, Competitive facility location with random attractiveness. Oper. Res. Lett. 46 (2018) 312–317. | MR | DOI

[20] C. Duhamel, P. Lacomme, C. Prins and C. Prodhon, A GRASP×ELS approach for the capacitated location-routing problem. Comput. Oper. Res. 37 (2010) 1912–1923. | Zbl | DOI

[21] J. W. Escobar, R. Linfati and P. Toth, A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. Comput. Oper. Res. 40 (2013) 70–79. | MR | DOI

[22] K. M. Ferreira and T. A. De Queiroz, Two effective simulated annealing algorithms for the Location-Routing Problem. Appl. Soft Comput. 70 (2018) 389–422. | DOI

[23] D. Gavalas, V. Kasapakis, C. Konstantopoulos, G. Pantziou, N. Vathis and C. Zaroliagis, The eCOMPASS multimodal tourist tour planner. Expert Syst. App. 42 (2015) 7303–7316. | DOI

[24] H. Gavranović and M. Buljubašić, A hybrid approach combining local search and constraint programming for a large scale energy management problem. RAIRO:OR 47 (2013) 481–500. | MR | Zbl | Numdam | DOI

[25] B. L. Golden, L. Levy and R. Vohra, The orienteering problem. Nav. Res. Logist. 34 (1987) 307–318. | Zbl | DOI

[26] A. Gunawan, H. C. Lau and P. Vansteenwegen, Orienteering problem: a survey of recent variants, solution approaches and applications. Eur. J. Oper. Res. 255 (2016) 315–332. | MR | DOI

[27] M. Khorbatly, H. Dkhil, H. Alabboud and A. Yassine, A hybrid algorithm Tabu Search – GRASP for wounded evacuation in disaster response. RAIRO:OR 54 (2020) 19–36. | MR | Numdam | DOI

[28] G. Kobeaga, M. Merino and J. A. Lozano, An efficient evolutionary algorithm for the orienteering problem. Comput. Oper. Res. 90 (2018) 42–59. | MR | DOI

[29] R. Kohli and R. Krishnamurti, A total-value greedy heuristic for the integer knapsack problem. Oper. Res. Lett. 12 (1992) 65–71. | MR | Zbl | DOI

[30] G. Laporte, Location-routing problems, edited by B. L. Golden and A. A. Assad. In: Vehicle Routing: Methods and Studies. North-Holland, Amsterdam (1988) 163–198. | MR | Zbl

[31] J. Li, P. M. Pardalos, H. Sun, J. Pei and Y. Zhang, Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups. Expert Syst. App. 42 (2015) 3551–3561. | DOI

[32] B. Ludwig, B. Zenker and J. Schrader, Recommendation of personalized routes with public transport connections. Intelligent Interactive Assistance and Mobile Multimedia Computing, edited by D. Tavangarian, T. Kirste and D. Timmermann. In: International Conference, IMC 2009, Rostock-Warnemünde, Germany, November 9–11, 2009. Proceedings. Springer Berlin Heidelberg, Berlin, Heidelberg (2009) 97–107.

[33] S. Majidi, S.-M. Hosseini-Motlagh, S. Yaghoubi and A. Jokar, Fuzzy green vehicle routing problem with simultaneous pickup – delivery and time windows. RAIRO:OR 51 (2017) 1151–1176. | MR | Zbl | Numdam | DOI

[34] F. Malucelli, A. Giovannini and M. Nonato, Designing single origin-destination itineraries for several classes of cycle-tourists. Transp. Res. Proc. 10 (2015) 413–422.

[35] S. M. H. Manzour-Al-Ajdad, S. A. Torabi and S. Salhi, A hierarchical algorithm for the planar single-facility location routing problem. Comput. Oper. Res. 39 (2012) 461–470. | MR | Zbl | DOI

[36] A. Nadizadeh, The fuzzy multi-depot vehicle routing problem with simultaneous pickup and delivery: formulation and a heuristic algorithm. Int. J. Ind. Eng. Prod. Res. 28 (2017) 325–345.

[37] A. Nadizadeh and H. Hosseini Nasab, Modelling and solving the capacitated location-routing problem with simultaneous pickup and delivery demands. Int. J. Transp. Eng. 6 (2019) 217–235.

[38] A. Nadizadeh and B. Kafash, Fuzzy capacitated location-routing problem with simultaneous pickup and delivery demands. Transp. Lett. 11 (2019) 1–19. | DOI

[39] A. Nadizadeh and H. H. Nasab, Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm. Eur. J. Oper. Res. 238 (2014) 458–470. | MR | DOI

[40] A. Nadizadeh, R. Sahraeian, A. Sabzevari Zadeh and S. M. Homayouni, Using greedy clustering method to solve capacitated location-routing problem. Afr. J. Bus. Manage. 5 (2011) 7499–7506.

[41] A. Nadizadeh, A. Sadegheih and A. Sabzevari Zadeh, A hybrid heuristic algorithm to solve capacitated location-routing problem with fuzzy demands. Int. J. Ind. Math. 9 (2017) 1–20.

[42] G. Nagy and S. Salhi, Location-routing: issues, models and methods. Eur. J. Oper. Res. 177 (2007) 649–672. | MR | Zbl | DOI

[43] V. P. Nguyen, C. Prins and C. Prodhon, Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking. Eur. J. Oper. Res. 216 (2012) 113–126. | MR | Zbl | DOI

[44] J. Pietz and J. O. Royset, Generalized orienteering problem with resource dependent rewards. Nav. Res. Logist. 60 (2013) 294–312. | MR | DOI

[45] C. Prins, C. Prodhon and R. Wolfler Calvo, Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. Oper. Res. Q. 4 (2006) 221–238. | MR | Zbl | DOI

[46] C. Prodhon and C. Prins, A survey of recent research on location-routing problems. Eur. J. Oper. Res. 238 (2014) 1–17. | MR | DOI

[47] S. Rath and W. J. Gutjahr, A math-heuristic for the warehouse location–routing problem in disaster relief. Comput. Oper. Res. 42 (2014) 25–39. | MR | DOI

[48] M. Rodrigues De Holanda Maia, A. Plastino and P. H. Vaz Penna, Hybrid data mining heuristics for the heterogeneous fleet vehicle routing problem. RAIRO:OR 52 (2018) 661–690. | MR | Zbl | Numdam | DOI

[49] R. Sahraeian and A. Nadizadeh, Using greedy clustering method to solve capacitated location-routing problem. In: XIII Congreso de Ingeniería de Organización. Barcelona (2009) 1721–1729.

[50] S. Salhi and G. K. Rand, The effect of ignoring routes when locating depots. Eur. J. Oper. Res. 39 (1989) 150–156. | MR | Zbl | DOI

[51] W. Souffriau, P. Vansteenwegen, J. Vertommen, G. V. Berghe and D. V. Oudheusden, A personalized tourist trip design algorithm for mobile tourist guides. Appl. Artif. Intell. 22 (2008) 964–985. | DOI

[52] P. Vansteenwegen, W. Souffriau and D. V. Oudheusden, The orienteering problem: a survey. Eur. J. Oper. Res. 209 (2011) 1–10. | MR | Zbl | DOI

[53] E. Yakıcı, Solving location and routing problem for UAVs. Comput. Ind. Eng. 102 (2016) 294–301. | DOI

[54] J. Yang and H. Sun, Battery swap station location-routing problem with capacitated electric vehicles. Comput. Oper. Res. 55 (2015) 217–232. | MR | Zbl | DOI

[55] Q. Yu, K. Fang, N. Zhu and S. Ma, A matheuristic approach to the orienteering problem with service time dependent profits. Eur. J. Oper. Res. 273 (2019) 488–503. | MR | Zbl | DOI

[56] V. F. Yu, P. Jewpanya, S.-W. Lin and A. A. N. P. Redi, Team orienteering problem with time windows and time-dependent scores. Comput. Ind. Eng. 127 (2019) 213–224. | DOI

[57] Y. Zare Mehrjerdi and A. Nadizadeh, Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. Eur. J. Oper. Res. 229 (2013) 75–84. | MR | Zbl | DOI

[58] Y. Zare Mehrjerdi and A. Nadizadeh, Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. Int. J. Ind. Eng. Prod. Res. 27 (2016) 1–19.

[59] S. Zhang, J. W. Ohlmann and B. W. Thomas, A priori orienteering with time windows and stochastic wait times at customers. Eur. J. Oper. Res. 239 (2014) 70–79. | MR | Zbl | DOI

[60] J. Zhao and V. Verter, A bi-objective model for the used oil location-routing problem. Comput. Oper. Res. 62 (2015) 157–168. | MR | Zbl | DOI

Cité par Sources :