×

Skewed general variable neighborhood search for the location routing scheduling problem. (English) Zbl 1348.90406

Summary: The integrated location routing scheduling problem is a variant of the well-known location routing problem. The location routing problem consists in selecting a set of depots to open and in building a set of routes from these depots, to serve a set of customers at minimum cost. In this variant, a vehicle can perform more than a single route in the planning period. As a consequence, the routes have to be scheduled within the workdays of each vehicle. The problem arises typically when routes are constrained to have a short duration. It happens for example within the boundaries of small geographic areas or in the transportation of perishable goods. In this paper, we propose a skewed general variable neighborhood search based heuristic to solve it. The algorithm is tested extensively and we show that it is efficient and provides the proven optimal solution in a significant number of cases. Moreover, it clearly outperforms a multi-start VND based heuristic that uses the same neighborhood structures.

MSC:

90B80 Discrete location and assignment
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Akca, Z.; Berger, R.; Ralphs, T., A branch-and-price algorithm for combined location and routing problems under capacity restrictions, (Chinneck, J.; Kristjansson, B.; Saltzman, M.; Sharda, R.; Voß, S., Operations research and cyber-infrastructure, operations research/computer science interfaces series, vol. 47 (2009), Springer: Springer US), 309-330
[3] Albareda-Sambola, M.; Díaz, J.; Fernández, E., A compact model and tight bounds for a combined location-routing problem, Comput Oper Res, 32, 3, 407-428 (2005) · Zbl 1061.90016
[4] Azi, N.; Gendreau, M.; Potvin, J.-Y., An exact algorithm for a single-vehicle routing problem with time windows and multiple routes, Eur J Oper Res, 178, 3, 755-766 (2007) · Zbl 1159.90306
[5] Azi, N.; Gendreau, M.; Potvin, J.-Y., An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, Eur J Oper Res, 202, 3, 756-763 (2010) · Zbl 1176.90047
[7] Barreto, S.; Ferreira, C.; Paixão, J.; Santos, B., Using clustering analysis in a capacitated location-routing problem, Eur J Oper Res, 179, 3, 968-977 (2007) · Zbl 1163.90589
[8] Belenguer, J.-M.; Benavent, E.; Prins, C.; Prodhon, C.; Calvo, R., A branch-and-cut method for the capacitated location-routing problem, Comput Oper Res, 38, 6, 931-941 (2011) · Zbl 1205.90172
[9] Berger, R.; Coullard, C.; Daskin, M., Location-routing problems with distance constraints, Transp Sci, 41, 1, 29-43 (2007)
[11] Clautiaux, F.; Alves, C.; Valério de Carvalho, J., A survey of dual-feasible and superadditive functions, Ann Oper Res, 179, 317-342 (2010) · Zbl 1229.90155
[14] Cordeau, J.-F.; Gendreau, M.; Laporte, G., A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks, 30, 105-119 (2007) · Zbl 0885.90037
[17] Derbel, H.; Jarboui, B.; Hanafi, S.; Chabchoub, H., Genetic algorithm with iterated local search for solving a location-routing problem, Expert Syst Appl, 39, 3, 2865-2871 (2012)
[19] Hansen, P.; Mladenović, N., Variable neighborhood searchprinciples and applications, Eur J Oper Res, 130, 3, 449-467 (2001) · Zbl 0981.90063
[20] Hansen, P.; Mladenović, N.; Moreno-Pérez, J., Variable neighbourhood searchmethods and applications, 4OR A Quarterly Journal of Operations Research, 6, 4, 319-360 (2008) · Zbl 1179.90332
[21] Hernandez, F.; Feillet, D.; Giroudeau, R.; Naud, O., A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration, 4OR, 12, 3, 235-259 (2014) · Zbl 1307.90022
[22] Iori, M.; Salazar-Gonzalez, J.-J.; Vigo, D., An exact approach for the vehicle routing problem with two-dimensional loading constraints, Transp Sci, 41, 2, 253-264 (2007)
[23] Jarboui, B.; Derbel, H.; Hanafi, S.; Mladenović, N., Variable neighborhood search for location routing, Comput Oper Res, 40, 1, 47-57 (2013) · Zbl 1349.90091
[24] Lancia, G.; Rinaldi, F.; Serafini, P., A time-indexed lp-based approach for min-sum job-shop problems, Annals OR, 175-198 (2011) · Zbl 1225.90053
[25] Laporte, G., Location-routing problems, (Golden, B.; Assad, A., Vehicle routing: methods and studies, studies in management science and systems, vol. 16 (1988), Elsevier Science Publishers B.V.: Elsevier Science Publishers B.V. North-Holland, Amsterdam) · Zbl 0644.90030
[26] Laporte, G.; Nobert, Y.; Arpin, D., An exact algorithm for solving a capacitated location-routing problem, Ann Oper Res, 6, 9, 291-310 (1986)
[27] Laporte, G.; Nobert, Y.; Taillefer, S., Solving a family of multi-depot vehicle routing and location-routing problems, Transp Sci, 22, 3, 161-172 (1988) · Zbl 0662.90039
[28] Lin, C.; Chow, C.; Chen, C., A location-routing-loading problem for bill delivery services, Comput Ind Eng, 43, 5-25 (2002)
[29] Lin, C.; Kwok, C. R., Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data, Eur J Oper Res, 175, 1833-1849 (2006) · Zbl 1142.90325
[30] Macedo, R.; Alves, C.; Valério de Carvalho, J., Arc-flow model for the two-dimensional guillotine cutting stock problem, Comput Oper Res, 37, 6, 991-1001 (2010) · Zbl 1178.90292
[31] Macedo, R.; Alves, C.; Valério de Carvalho, J.; Clautiaux, F.; Hanafi, S., Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model, Eur J Oper Res, 214, 3, 536-545 (2011) · Zbl 1219.90022
[35] Min, H.; Jayaraman, V.; Srivastava, R., Combined location-routing problemsa synthesis and future research directions, Eur J Oper Res, 108, 1, 1-15 (1998) · Zbl 0943.90008
[36] Mladenović, N.; Hansen, P., Variable neighborhood search, Comput Oper Res, 24, 1097-1100 (1997) · Zbl 0889.90119
[37] Mladenović, N.; Todosijević, R.; Urošević, D., An efficient general variable neighborhood search for large travelling salesman problem with time windows, Yugosl J Oper Res, 23, 1, 19-30 (2013) · Zbl 1299.90417
[38] Mladenović, N.; Urošević, D.; Hanfi, S.; Ilić, A., A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem, Eur J Oper Res, 220, 1, 270-285 (2012) · Zbl 1253.90200
[39] Nagy, G.; Salhi, S., Nested heuristic methods for the location-routeing problem, J Oper Res Soc, 47, 9, 1166-1174 (1996) · Zbl 0869.90019
[40] Nagy, G.; Salhi, S., Location-routingissues, models and methods, Eur J Oper Res, 177, 2, 649-672 (2007) · Zbl 1109.90056
[41] Oliveira, A.; Vieira, O., Adaptive memory programming for the vehicle routing problem with multiple trips, Comput Oper Res, 34, 1, 28-47 (2007)
[42] Pessoa, A.; Uchoa, E.; de Aragão, M.; Rodrigues, R., Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems, Math Program Comput, 1-32 (2010)
[43] Petch, R.; Salhi, S., A multi-phase constructive heuristic for the vehicle routing problem with multiple trips, Discrete Appl Math, 133, 69-92 (2003) · Zbl 1053.90026
[44] Prins, C.; Prodhon, C.; Calvo, R., A memetic algorithm with population management (ma-pm) for the capacitated location-routing problem, (Gottlieb, J.; Raidl, G., Evolutionary computation in combinatorial optimization, lecture notes in computer science, vol. 3906 (2006), Springer: Springer Berlin, Heidelberg), 183-194 · Zbl 06858826
[45] Salhi, S.; Petch, R. J., A ga based heuristic for the vehicle routing problem with multiple trips, J Math Model Algorithms, 6, 591-613 (2007) · Zbl 1140.90333
[46] Taillard, E.; Laporte, G.; Gendreau, M., Vehicle routeing with multiple use of vehicles, J Oper Res Soc, 47, 8, 1065-1070 (1996) · Zbl 0864.90045
[47] Tuzun, D.; Burke, L., A two-phase tabu search approach to the location routing problem, Eur J Oper Res, 116, 1, 87-99 (1999) · Zbl 1009.90056
[48] Valério de Carvalho, J., Exact solution of bin-packing problems using column generation and branch-and-bound, Ann Oper Res, 86, 629-659 (1999) · Zbl 0922.90113
[49] Valério de Carvalho, J., LP models for bin packing and cutting stock problems, Eur J Oper Res, 141, 2, 253-273 (2002) · Zbl 1059.90095
[50] Wu, T.-H.; Low, C.; Bai, J.-W., Heuristic solutions to multi-depot location-routing problems, Comput Oper Res, 29, 10, 1393-1415 (2002) · Zbl 0994.90019
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.